알고리즘의 복잡도

Binary Search

θ(logn)

Factorial

O(n)

X^n

O(n)

피보나치

T(n) < C*2^n

MergeSort

T(n)=2T(n/2)+n

θ(nlogn)

하노이 타워

T(n)=T(n-1)+1+T(n-1)

T(n)=2^n-1

SelectionSort

T(n)=O(n^2)

BubbleSort

O(n^2)

InsertionSort

O(n^2)

QuickSort

O(n^2)

HeapSort

O(nlogn)

Build-Max-Tree

O(nlogn), 운 좋으면 O(n)

Hybrid Approach (Quicksort와 Insertion Sort의 결합)

O(n log n)

 

 

• 평균 시간 복잡도: O(n log n)
• 최악의 경우 시간 복잡도: O(n log n) (피벗 선택을 무작위화하거나 중앙값을 선택하는 방법 등으로 최악의 경우 발생 확률을 낮출 수 있음)
• 작은 배열에 대한 Insertion Sort 부분: 이 부분은 O(k²)로 매우 작은 상수 크기(k)에 대해 처리되기 때문에 전체 성능에 큰 영향을 미치지 않음.

 

배열이 이미 정렬되어 있는 상태일 때!

선택정렬

O(n^2)

버블정렬

O(n^2)

삽입정렬

O(n)

병합정렬

O(nlogn)

퀵정렬

O(n^2)

힙정렬

O(nlogn)

안정성을 유지하지 않는 정렬

선택 정렬 : 최댓값 중 가장 뒤에 있는 것을 최댓값으로 삼으면 안정성을 유지할 수 있다.
퀵 정렬(피봇 활용)
힙 정렬