[알고리즘] 시간복잡도

시간복잡도 (time complexity)

입력에 대해 알고리즘이 얼마만큼의 시간을 사용하는지 근사적으로 나타내는 것

 

표기법

Big-O(빅 오) - 상한, Big-Ω(빅 오메가) - 하한, Big-θ(빅 세타) - 정확한 시간복잡도 (이때는 빅오와 빅오메가도 빅 세타와 동일)

 

자주 사용하는 시간복잡도 (빠른순)

• O(1) : 상수 시간 알고리즘 | 입력 크기에 영향을 받지 않음. 예) 공식을 사용하여 바로 답을 계산하는 경우
• O(logN) : 로그 시간 알고리즘 | 단계마다 (입력값 N만큼 단계를 수행한다면) 입력의 크기를 절반씩 줄여가는 계산을 하는 경우. 예) N을 2로 나눠가면서 1이 되는 과정, 이분탐색 (탐색구간을 절반씩 줄여가는 탐색 알고리즘)
• O(√N) : 제곱근 시간 알고리즘 | 예) ..?
• O(N) : 선형 시간 알고리즘 | 입력을 처음부터 끝까지 한번 보는 것. 대부분의 알고리즘 문제에서 O(N)이 가장 효율적인 시간복잡도임 답을 구하려면 원소를 적어도 한번씩은 훑어야 하는 경우가 많기 때문에. | 예) DP 알고리즘이 대부분 O(N)이었던 것 같다. 선형 탐색도 O(N)
• O(NlogN) : 정렬 알고리즘 중 가장 효율적인 알고리즘의 시간 복잡도이기 때문에(퀵정렬), 정렬 알고리즘의 시간복잡도로 많이 사용 예) 입력 개수 마다 O(logN)의 연산을 수행하는 경우, 퀵정렬
• O(N^2) : 제곱 시간 알고리즘 | 보통 2중 중첩 반복문을 사용시 해당. 예) 입력 원소 중 2개로 만들 수 있는 조합 구하기 (n=3 (1~3), 3*3) 
• O(N^3) : 세제곱 시간 알고리즘 | 3중 중첩 반복문 사용시 해당. 예) 입력 원소 중 3개로 만들 수 있는 조합 구하기

여기까지가 다항 시간 알고리즘 (Polynomial Algorithm). 다항 시간 알고리즘은 O(N^k) 이내에 풀리는 알고리즘을 말한다. 흔히 효율적인 알고리즘의 상한선이라고 생각하면 될 것 같다. 아직 다항 시간 내에 풀 수 있는 알고리즘이 발견되지 않은 문제를 NP-hard 문제라고 한다.

• O(2^N) : 효율적이진 않지만 N이 작으면 가능한 문제. 예) 입력원소로 만들 수 있는 부분집합 구하기 (각 수마다 포함/불포함 경우를 나눠서 곱한다고 생각하면)
• O(N!) : 예) 입력원소로 만들 수 있는 순열을 구하는 문제

효율성 추정하기

대부분 현대 컴퓨터가 1초에 처리할 수 있는 간단한 연산이 수억개(10^8 정도)라고 한다.

그럼 문제의 입력 범위와 시간제한을 통해 O(10^8)*a 이내가 되도록 알고리즘을 짜야 하는걸 미리 알 수 있다.

아래 표를 통해서 문제마다 내가 어느정도의 효율성을 만족하는 알고리즘을 짜야하는지 파악할 수 있다. 유용할 것 같다!

입력의 크기	1초에 처리 가능한 알고리즘의 시간 복잡도
N <= 10	O(N!)
N <= 20	O(2^N)
N <= 500	O(N^3)
N <= 10^6	O(NlogN) or O(N)
N이 충분히 클 때	O(1) or O(logN)

 

 

참고한 책 

https://product.kyobobook.co.kr/detail/S000001033132

알고리즘 트레이닝 | 안티 라크소넨 - 교보문고