4: 알고리즘-2(알고리즘 표기법)

알고리즘을 설명하기 위해 특정 표기법을 사용하는 이유(Big-O와 Ω:오메가)

- 알고리즘이 얼마나 잘 설계되어 있는지 확인하기 위해

- 코드가 얼마나 잘 구현되었는지 확인하기 위해

- 일반적으로는 Big-O 표기법 사용

 

알고리즘을 실행하는 데 걸리는 시간

n은 일일이 하나씩 다 찾아보는 경우 

n/2는 두 칸씩 찾아보는 경우(2,4,6,8...)

logn는 이진 탐색처럼 반으로 쪼갠 다음에 거기서부터 비교하는 경우

---

Big-O 표기법

알고리즘을 수행하는 데 필요한 시간의 상한선을 의미

여기서 대문자 O는 “on the order of”의 약자로, 쉽게 보면 “~만큼의 정도로 커지는”것이라고 볼 수 있음

O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됨. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지기 때문에 O(n)이라고 볼 수 있음(O(n) == O(n/2))

---

실행시간을 나타내기 위해 사용되는 Big-O 표기

 

O(n^2)

O(n log n)

O(n): 선형검색

O(log n): 이진검색

O(1)

Big Ω 표기법

Big-O가 알고리즘 실행 시간의 상한을 나타낸 것이면, 반대로 Big Ω(Omega)는 알고리즘 실행 시간의 하한을 나타내는 것

ex) 예를 들어 선형 검색에서는 n개의 항목이 있을 때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번 만에 검색을 끝낼 수도 있기 때문에 하한은 Ω(1)이 됨

---

실행시간을 나타내기 위해 사용되는 Big-Ω 표기

 

Ω(n^2)

Ω(n log n)

Ω(n):배열안에 존재하는 값의 개수 세기

Ω(log n)

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

 

https://www.boostcourse.org/cs112/joinLectures/41307

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