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

알고리즘의 시간 복잡도와 Big O 표기법

1주차에 알고리즘의 실행 시간을 시각적으로 표현한 예제를 보았다.

 

시각적 표현을 공식으로 나타낸 것이 Big O 표기법이다.

 

 

Big O 표기법

Big O 표기법에서 O는 "on the order of"의 약자로 쉽게 말해 "시간이 ~만큼의 정도로 커지는" 것을 의미한다.

 

예를 들어 O(n)은 입력 크기 n만큼 커지는 것으로 n이 증가할수록 선형적으로 실행 시간이 증가함을 나타낸다.

 

비슷하게 O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)과 동일하게 취급된다.

 

주로 사용되는 Big O 표기법이다.

• $O(1)$: 상수 시간 복잡도
• $O(log \space n)$: 로그 시간 복잡도 (예: 이진 검색)
• $O(n)$: 선형 시간 복잡도 (예: 선형 검색)
• $O(n \space log \space n)$: 로그 선형 시간 복잡도
• $O(n^2)$: 이차 시간 복잡도

 

 

Big O 속도 비교

$O(1) \space < \space O(log⁡ \space n) \space < \space O(n) \space < \space O(n \space log \space ⁡n) \space < O(n^2) \space < \space O(2^n)$

 

 

Big Ω 표기법

Big O 표기법이 알고리즘 실행 시간의 상한을 나타낸다면, Big Ω 표기법은 하한을 나타낸다.

 

선형 검색에서는 최악의 경우 n번의 검색이 필요하므로 상한이 O(n)이지만, 최선의 경우 한 번만에 검색이 끝날 수 있으므로 하한은 Ω(1)이 된다.

 

주로 사용되는 Big Ω 표기법이다.

• $Ω(1)$: 상수 시간 하한 (ex, 선형 검색, 이진 검색)
• $Ω(log \space n)$: 로그 시간 하한
• $Ω(n)$: 선형 시간 하한 (ex, 배열 내 특정 값의 개수 세기)
• $Ω(n \space log \space n)$: 로그 선형 시간 하한
• $Ω(n^2)$: 이차 시간 하한

 

 

시간 복잡도의 중요성

알고리즘의 시간 복잡도를 분석하는 것은 매우 중요하다. 알고리즘이 커지는 입력 크기에서 어떻게 동작할지를 예측할 수 있게 해주기 때문이다.

 

Big O와 Big Ω 표기법을 통해 알고리즘의 최악과 최선의 성능을 이해하고 시간 복잡도를 평가해 알고리즘의 효율성을 비교할 수 있다.

 

다양한 알고리즘의 시간 복잡도를 이해하고 적절한 알고리즘을 선택하는 것은 앞으로 알고리즘을 정할 때 중요한 척도가 될 것이다.

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)