BIg-O 표기법의 O(log n)복잡도

Big-O 표기법

n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략 후 가장 빨리 증가하는 항에 곱해진 상수 또한 생략. 그 후 남은 항을 O()안에 넣어 표기하는 방법.

 

 

O(log n)의 시간 복잡도

• log₂N 으로 데이터에 원소가 N개 있을 때 알고리즘이 log₂N 시간이 걸림
• 예를 들어 이진 탐색 트리에서 원하는 항목을 찾는 알고리즘

 

 

Quicksort 의 시간복잡도 구해보기

 

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

n개의 수를 정렬할 때

1. 평균적인 경우

pivot을 기준으로 리스트가 두 개의 거의 같은 부분집합으로 나눠진다고 가정시

log n 번 나눠지게 되고 각 단계에서 n번의 탐색을 하게 된다.

이 경우 시간복잡도는 O(nlog n)

 

    2. 최악의 경우

pivot이 항상 최소값이나 최대값만을 지정하는 경우 리스트는 n번 나눠지게 된다.

탐색은 동일하게 n번 수행하므로 시간복잡도는 O(n*2)