[CS50] 알고리즘 - 알고리즘 표기법

실행 시간

프로그램을 실행하면 작업이 완료될 때까지 시간이 소요된다.

간단한 프로그램은 실행 시간을 걱정할 필요가 없지만, 데이터가 많고 작업이 복잡해질수록 실행 시간은 매우 중요해진다.

알고리즘의 실행 시간을 표기하는 방법을 알아보자.

이 그래프는 알고리즘 실행 시간을 표현한 것이다. 문제 크기가 커질수록 각 알고리즘의 실행 시간이 어떻게 증가하는지 보여준다.

 

Big O 표기법

이런 그래프를 공식으로 표기한 것이 Big O 표기법이다.

O는 "on the order of"의 약자로, "~만큼 커지는" 정도를 나타낸다.

O(n):

• n만큼 커지는 것
• n이 늘어날수록 선형적으로 증가

O(n/2):

• n이 매우 커지면 1/2은 의미가 없어짐
• 결국 O(n)과 같음

 

Big O는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다.

주요 Big O 표기

• O(n²): 이중 루프
• O(n log n): 효율적인 정렬
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1): 상수 시간

 

Big Ω 표기법

Big Ω는 알고리즘 실행 시간의 하한(최선의 경우)을 나타낸다.
예시: 선형 검색

• 상한: O(n) - 최악의 경우 n번 검색
• 하한: Ω(1) - 운이 좋으면 1번만에 찾음

 

주요 Big Ω 표기

• Ω(n²)
• Ω(n log n)
• Ω(n): 배열 값 세기
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

 

연습 문제

Q. 실행 시간의 상한이 낮은 알고리즘이 더 좋을까, 하한이 낮은 알고리즘이 더 좋을까?
일반적으로 상한이 낮은 알고리즘이 더 좋다.

• 안정성: 상한은 최악의 경우를 보장하므로 예측 가능
• 신뢰성: 어떤 입력에도 일정 시간 내에 완료 보장
• 실용성: 실제 환경에서는 평균/최악의 경우가 중요

하한(최선의 경우)은 운이 좋을 때의 성능이므로 신뢰하기 어렵다.
예외적으로 특정 상황에서 최선의 경우가 자주 발생한다면 하한도 고려할 수 있다.

• 예를 들어 거의 정렬된 데이터에 삽입 정렬을 사용하는 경우.

 

요약
대부분의 경우: 상한(Big O)이 낮은 알고리즘 선택
특수한 경우: 하한과 평균 케이스도 함께 고려