시간 복잡도 계산(이해하기 쉬운)

O(N) --> 직선적 시간

n번 동안 돌아다님

ex) for i in range(n)

 

O(N**2) --> 두번 훑어봄

for i in range(n):

    for j in range(k)

 

O(logn) --> 1/2씩 훑어보는 경우

예시) 이진탐색

f4함수(

재귀적으로 --> f4(n/2)

)

 

o(nlogn) --> 둘씩 나뉘어서 훑어보는 경우

둘로 나눈다 logn && 그 둘로 나뉜것을 훑어본다 n

So nlogn

예시 병합정렬

 

O(N!) --> 1씩 줄어들면서 훑어보는 경우

 함수 factorial(n) {

    factorial(n-1) --> 재귀적으로..

}

 

O(2^n) --> 둘씩 나눠지면서 계속 뻗어나감

ex) 

함수 fibo() {

    return    fibo(n-1) + fibo(n-2)

}

계속 둘씩 뻗어나감 근데 이 둘씩 뻗어나가는 것이 반으로 줄면서 훑어보는 것(logn)이 아니라

새로운 값들이 두개씩 뻗어나간다