[CS50] 4.6 정렬 알고리즘의 실행시간

지금까지의 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은 다음과 같다.

 

 

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬

• O(n log n)

• O(n): 선형 검색

• O(log n): 이진 검색

• O(1)

 

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬

• Ω(n log n)

• Ω(n)

• Ω(log n)

• Ω(1): 선형 검색, 이진 검색

 

 

 

만약 이미 정렬이 되어 있는 배열이 주어진다면,

아래와 같이 바깥 루프를 '교환이 일어나지 않을 때'까지만 수행하도록 하여

버블 정렬을 좀 더 효율적으로 실행할 수 있을 것이다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

따라서 최종적인 버블 정렬의 하한은 Ω(n)이 된다.

 

 

 

실행시간의 하한

• Ω(n^2): 선택 정렬

• Ω(n log n)

• Ω(n): 버블 정렬

• Ω(log n)

• Ω(1): 선형 검색, 이진 검색

 

 

 

 

출처: www.boostcourse.org/cs112