시간복잡도의 점근 표기법 (Big-O, Big-Ω)

점근 표기법의 종류에는 빅오(Big-O) 표기법과, 빅 오메가(Big-Ω) 표기법이 있다.

 

빅오 표기법 - 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) O(N)

빅오메가 표기법 - 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) Ω(1)

 

for element in array:     # array 의 길이만큼 아래 연산이 실행
    if number == element: # 비교 연산 1번 실행 
        return True
return False

다음과 같은 함수가 있을 때 이 함수의 시간복잡도는 N * 1 인 것을 알 수 있다.

만약 array = [3, 5, 6, 1, 2, 4]에 대해 3을 찾는다면 1번의 연산만에 답을 찾을 수 있을 것이다.

하지만 array = [5, 6, 1, 2, 4, 3]에 대해 3을 찾는다면 array의 길이(N)만큼 연산을 해야 답을 찾을 수 있다.

 

이처럼, 알고리즘의 성능은 항상 동일한 게 아니라 입력값에 따라 달라질 수 있다. 

어떤 값을 가지고 있는지, 어떤 패턴을 이루는 데이터인지에 따라 뭐가 좋은 알고리즘인지 달라질 수 있다는 의미.

 

이를 표로 표기하면 다음과 같다.

입력값이	소요되는 연산량
좋을 때	1
안 좋을 때	N

즉, 위의 경우에는

빅오 표기법으로 표시하면 O(N), 

빅 오메가 표기법으로 표시하면 Ω(1)

의 시간복잡도를 가진 알고리즘이다! 라고 말할 수 있다.

 

하지만 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다. 

대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐 더러, 우리는 최악의 경우를 대비해야 하기 때문이다.