시간 복잡도

 

최근 자료구조 및 CS 지식에 부족함을 느껴 이전에 학습했던 것들을 복습하며 추가적인 학습을 시작했다.

 

알고리즘에 기본이 되는 시간 복잡도(Big O)에 대해 정리해본다.

 

시간 복잡도란?

 

const arr = [1, 2, 3, 4, 5]

만약 4를 찾는다?

좌측 부터 4번째이기에 작업량은 4

컴퓨터는 첫번째부터 하나하나 확인한다.
(사람도 마찬가지)

n개의 배열에서의 작업량은 n


Big O 최선의 경우
Big θ 최선과 최악이 같을때
Big Ω 최악의 경우

O(1)
O(logn)
O(N)
O(NlogN)
O(N²)
O(N³)

등으로 나타낸다.

 

복잡도는 주로  빅오 표기법을 사용해 나타낸다. 최악의 경우 걸리는 시간을 표기하는 방법으로, 최대값을 표기한다.

 

             O(N),  O(NlogN),  O(N²),     O(2^N)
N=1            1                0               1                 2     
N=10        10              23           100          1024
N=100    100            460       10000    0이 30개

하나당 0.01초가 걸린다고 해도 100개를 정렬하는 경우,  O(NlogN)은 4.6초이지만 O(N²)은 100초가 걸리게 된다..

 

사실 100초까지는 안걸리겠지만

 

 

그래프를 보면 O(N²) 부터 성능이 말도 안되게 안좋아 진다.

 

이외에 θ(theta) 표기법도 있는데 평균의 경우를 나타낸다(O와 Ω의 중간)

최악의 경우가 잘 일어나지 않는 알고리즘의 경우는 θ표기법이 파악에 좀 더 유리하다고 하며

 

사용은 빅오 표기법과 비슷하여 O만 θ로 바꾸면 된다.

 

차이점이 있다면 어떤 알고리즘이 빅오 표기법의 경우에는 최선의 경우 O(1)도 나올수 있다면

세타 표기법은 항상 평균의 값만 나오게된다는 점정도라 생각된다.