시간복잡도

43, 12, 43, 22, 11

위의 다섯개의 숫자가 있다. 이 숫자를 오름차순으로 정열하는 코딩을 할거다. 작성한 코딩을 실행하면 결과가 나올때까지

걸리는 시간이 runnint time이다. 

 

cpu는 코딩을 한줄한줄 처리해 나가는데 각 소스마다 걸리는 시간이 있다. 예를들어 반복문이 한번 실행하는데 1n 걸린다고 하면 반복문을 열번 돌리면 10n이 걸린다. 이 반복분을 이중 반복문으로 10번하면 100n^2이 걸린다. 이중 반복문 말고 다른 소스의 걸리는 시간이 3n + 4  걸린다고 하면 전체 걸리는 시간은 100n^2 + 3n + 4가 된다. 시간복잡도는 빅오로 나타내는데 최고차수만 나타낸다. 빅오로 나타내면 O(n^2)가 된다.

3                            >>>   O(1)

3n^2 + 2n + 4        >>>   O(n^2)

2n^4 + 3n^3 + n     >>>  O(n^4)

 

차수가 높은 순서는 다음과 같다

O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)

 

시간복잡도는 각 데이터의 상태나 값에 따라서 다른데 시간복잡도가 가장 높은 상황을

worst case

가장 낮은 상황을

best case

그리고 평균을 

average case라고 한다.