시간복잡도 Big O

O(1): 상수 시간

  -> N의 값에 관계없이 동일한 숫자의 스텝이 필요한 시간복잡도

print(2)

O(logN): 로그 시간

  -> 각 단계에서 입력 데이터의 크기를 (반으로) 줄일 때

  -> 예) 퀵 정렬

arr = [3, 6, 7, 2, 5, 8, 1, 4, 9, 0]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
        
    pivot = arr[0]
    tail = arr[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(arr))

O(N): 선형 시간

  -> 실행 시간이 입력 데이터와 정비례하고 선형적으로 증가할 때

  -> 예) 일반적인 for문 1회

for i in range(30):
    print(i)

O(nlogN): 선형 로그 시간

  -> 예) 합병 정렬

O(N^2): 2차 시간

  -> 선형 시간 안의 선형 시간

  -> 예) 2중 for문

for i in range(30):
    for j in range(40):
        print(i, j)

 

O(2)나 O(2N+1)과 같은 표현은 없다.

Big O는 함수의 디테일까지 파고들지 않기 때문에 위의 식과 같이 정형화해 표현한다.