[Algorithm] 시간복잡도

✔️시간 복잡도란?

시간 복잡도는 알고리즘의 수행 시간이 입력 크기에 어떻게 의존하는지를 나타내는 개념입니다. 즉, 알고리즘이 얼마나 빠르게 실행되는지를 표현하는 지표입니다. 알고리즘의 성능을 분석하고 비교하기 위해 중요한 개념 중 하나입니다.

 

💡 Big-O 표기법

알고리즘의 시간 복잡도를 나타내는 방법 중 하나로 Big-O 표기법이 있습니다. Big-O 표기법은 알고리즘의 최악의 경우 실행 시간의 상한을 표현합니다. 이는 입력 크기에 따른 알고리즘의 실행 시간의 증가 추이를 나타내는 것으로, 주로 가장 느린 실행 시간을 고려하는 것이기 때문에 실제로 알고리즘이 얼마나 빠른지를 정확하게 나타내지는 않을 수 있습니다.

 

📌상수 시간 복잡도 (O(1))

알고리즘의 실행 시간이 입력 크기에 상관없이 일정한 상수 시간이 걸리는 경우입니다. 예를 들어, 배열에서 인덱스로 직접 접근하는 경우나 상수 번만큼의 연산을 수행하는 경우가 이에 해당합니다.

 

📌선형 시간 복잡도 (O(n))

입력 크기에 선형으로 비례하여 시간이 증가하는 경우입니다. 선형 탐색이나 배열의 모든 원소를 순회하는 경우 등이 선형 시간 복잡도를 갖습니다.

 

📌로그 선형 시간 복잡도 (O(n log n))

일반적으로 정렬 알고리즘에서 나타나며, 입력 크기에 대해 선형 로그 시간으로 실행 시간이 증가합니다. 병합 정렬, 퀵 정렬 등이 이에 해당합니다.

 

📌이차 시간 복잡도 (O(n^2))

이중 반복문을 사용하여 각 요소를 다른 모든 요소와 비교하는 경우입니다. 선택 정렬이나 버블 정렬과 같은 알고리즘이 이에 속합니다.

 

📌다항 시간 복잡도 (O(n^k))

 

(이차 시간 복잡도 보다 좀 더 가파르다고 보면 됩니다)

 

 

k차 다항식 시간 복잡도로, 다중 반복문이 사용되는 경우에 해당합니다. 행렬 곱셈 알고리즘과 같은 경우가 여기에 속합니다.

 

📌지수 시간 복잡도 (O(2^n))

입력 크기에 대해 지수적으로 시간이 증가하는 경우로, 부분 집합 생성이나 완전 탐색 알고리즘이 이에 해당합니다.

 

📌팩토리얼 시간 복잡도 (O(n!))

n의 팩토리얼에 비례하여 시간이 증가하는 경우로, 순열 생성과 같이 경우의 수를 모두 고려해야 하는 알고리즘이 이에 속합니다.

 

 

💡요즘 코테를 보며 문제 풀이도 중요하지만 풀이만큼 시간복잡도 또한 중요하다고 느낀다.. 꼭 먼저 고려하여 풀이하도록 하자..!

 

💡사진 출처

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/