시간 복잡도 설명

1. 시간 복잡도란

알고리즘의 동작 속도와 입력의 크기간의 함수관계를 의미한다. 당연한 소리지만 모든 프로그램은 입력이 커질 수록 동작 소요 시간도 비례해서 커질 수 밖에 없다. 더 많은 입력이 주어지는데 동작 속도가 빨라진다는 것은 어불성설이다. 실제 컴퓨터의 코드에는 수많은 단위 동작들이 포함되므로 이를 정확하게 예측하는 것은 힘들기 때문에 입력의 양과 계산의 양 간의 함수 관계로 알고리즘의 속도를 표현한다. 최선의 경우(하한), 평균의 경우, 최악의 경우(상한) 3가지가 있지만 실제로 알고리즘 성능을 표기할 때 최악의 경우를 많이 사용한다. $N$개의 수 중 100보다 작은 수를 찾는 코드를 만든다고 생각해보자. 만약 입력이 1 1 1 1 1이라면 첫번째 수를 보자마자 반환해서 시작하자마자 알고리즘이 종료된다. 이런 경우를 최선의 경우라고 한다. 복잡도는 $o(1)$이다. 만약 입력이 1000 1000 1000 1000 1000이라면 알고리즘은 $N$개의 수를 모두 순회할 수 밖에 없다. 이런 경우가 최악의 경우다. 복잡도는 $O(N$)이다.

2. Big-O 표기법

Big-Ω