[CS50 4주차] 알고리즘 표기법

Big O 표기법 (실행 시간의 상한)

O : on the order of의 약자로 ~만큼의 정도로 커지는

실행 시간을 나타내기 위해 많이 사용됨

$O(n^2)$

$O(n logn)$

$O(n)$

 Linear search (선형검색)

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

$O(log n)$

 Binary search ( 이진 검색 )

$O(1)$

Big Ω 표기법 (실행 시간의 하한)

$\Omega(n^2)$

$\Omega(nlogn)$

$\Omega(n)$

$\Omega(logn)$

$\Omega(1)$ >> linear search, binary search

선형검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 $O(n)$이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 $\Omega(1)$이 됨.

 

실행시간의 상한이 낮은 알고리즘이 더 좋은거

ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

www.boostcourse.org/cs112/lecture/119020

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