1. 빅오 표기법의 개념
𝑓(𝑥) = 𝑂(𝑔(𝑥))
x가 무한히 증가할 때 𝑓(𝑥)의 시간 복잡도는 Worst Case에서도 𝑔(𝑥)의 시간 복잡도보다 작거나 같다는 의미를 지닙니다.
2. 빅오 표기법의 계산
def InsertionSort(A): //ascending sort version
if len(A) > 1:
for i in range(1, len(A)):
key = A[i] //save element at index i as a key
j = i - 1 //set j as 1 less than i
while j >= 0 and A[j] > key: //element at index j > key
A[j + 1] = A[j] //move the element to the right by 1
j -= 1 //decrease j index value
A[j + 1] = key //place key at correct location
예를 들어 삽입 정렬은 위와 같이 구현할 수 있으며, 배열의 요소가 역순인 최악의 경우 for loop에서 각 반복마다 i번의 비교를 수행하게 됩니다. 따라서 1 + 2 + 3 + ... + (𝑛 - 2) + (𝑛 - 1) = 𝑛(𝑛−1) / 2임을 알 수 있으며, 이는 아래가 성립함에 따라 삽입 정렬의 시간복잡도는 O(𝑛^2)가 됩니다.
3. 빅오 표기법의 특징
빅오 표기법에서는 상수항과 계수를 무시하고 최고차항만을 남기어 표시하도록 합니다.
실행 속도의 측면에서 비교하면, O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) 순이 됩니다.