[알고리즘] 시간 복잡도

복잡도

복작도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 크게 두가지로 나뉜다.

시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
공간 복잡도: 알고리즘을 위해 필요한 메모리 양

주로 코딩 테스트에서는 시간 복잡도를 다룬다.

연산 성능 비교

$\ O(1)$ < $\ O(log N)$ < $\ O(N)$ < $\ O(Nlog N)$ < $\ O(N^2)$ < $\ O(2^n)$

연산횟수 비교

시간 복잡도에서 "연산"은 사칙 연산, 비교 연산등을 말한다.

알고리즘 문제에서 시간 제한에 따라 시간복잡도를 따져가면서 코드 작성을 해야한다. 아래는 시간 제한이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우: 시간 복잡도가 $\ O(N^3)$인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000 경우: 시간 복잡도가 $\ O(N^2)$인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000 경우: 시간 복잡도가 $\ O(Nlog N)$인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000 경우: 시간 복잡도가 $\ O(N)$인 알고리즘을 설계하면 문제를 풀 수 있다.