[CS50] 알고리즘 - 알고리즘 표기법(Big-O, Big-Ω, Big-θ)

알고리즘이 얼마나 잘 설계되어 있는지, 코드가 얼마나 잘 구현되었는지
컴퓨터 과학자들은 알고리즘을 설명하기위해 특정 용어를 사용한다. 
가장 일반적으로 Big-O 표기법을 사용한다. 

 

Big-O 표기법

• 빅오란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다. 
• O는 "on the order of"의 약자로, "~만큼의 정도로 커지는" 것이라고 볼 수 있다. 
• 알고리즘의 효율성을 표기해주는 표기법이다.
• 보통 알고르즘의 시간 복잡도(시간 효율성)와 공간 복잡도(메모리 효율성)를 나타내는데 사용된다. 
• 빅오로 시간 복잡도를 표현할 때는 최고차항만 표기한다.

 

컴퓨터 과학자는 알고리즘의 효율성을 설명할 때 정확히는 O(n/2)일지라도 그냥 O(n)이라고 말한다.
로그의 경우도 그냥 O(log n)이라고 말한다. 

그림1	그림2	그림3

 

=> [그림1]의 빨간 선은 노란 선은 매우 비슷하게 생겼기 때문에 나누기 2를 없애도 된다. 

=> log의 밑인 2 또한 큰 의미가 없으므로 없애도 된다. 로그끼리는 대부분 비슷한 모양이다. 

=> [그림2] 처럼 볼 수 있다.

=> 해당 문제의 크기가 커져서 [그림1]과 [그림2]의 사이즈로 담기위해 축소해서 보기위해 x축과 y축을 늘리면 노란 선과 빨간 석이 아주 가까워진다.

=> [그림3] 처럼 보인다.

=> 더 큰 문제를 본다면 나중에 빨간 선과 노란 선은 거의 같아 보일 것이다.

 

 

점근적 실행 시간 (시간 복잡도)

• 실행 시간이란 프로그램이나 알고리즘이 동작하는데 걸리는 시간을 말한다.
• 몇 초가 걸리는지, 몇 번의 계산 과정이 필요한지를 말한다. 
• Big-O는 알고리즘 실행 시간의 상한을 나타낸 것이다.
• Big-Ω는 알고리즘 실행 시간의 하한을 나타낸 것이다.
• Big-θ는 어떤 알고리즘의 상한선과 하한선이 같을 때 사용한다.
• ex) 선형검색
  n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 된다.
  하지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다.

 

[Big-O 표기법]

시간 복잡도	예시
O(n²)	버블 정렬, 선택 정렬
O(n log n)	합병 정렬
O(n)	선형 검색
O(log n)	이진 검색
O(1)

 

[Big-Ω 표기법]

시간 복잡도	예시
Ω(n²)	선택 정렬
Ω(n log n)	합병 정렬
Ω(n)	버블 정렬
Ω(log n)
Ω(1)	선형 검색, 이진 검색

 

[Big-θ 표기법]

시간 복잡도	예시
θ(n²)	선택 정렬
θ(n log n)	합병 정렬
θ(n)
θ(log n)
θ(1)

 

Big-Ω 값과 Big-O 값 중 어느 것이 좋아야 좋은 알고리즘 일까? 후자인 Big-O 값이 좋아야 한다.
컴퓨터 과학자는 최악의 경우에 프로그램이 어떻게 동작할지 또는 평균적으로 어떻게 동작하는지를 가장 걱정한다.

 

think about

1) 실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?

상한이 낮은 알고리즘이 좋다.

상한은 최대의 경우를 생각하고 하한은 최소 아주 운이 좋은 경우를 생각한다.

항상 최선의 상황이 주어지는 것은 아니기 때문에 최악의 경우에 프로그램이 어떻게 동작할지 아는 것이 더 중요하다고 생각한다.

 

David J. Malan의 강의

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