Asymptotic notation (updated on 5/10/2023)

Data Structure? 컴퓨터속에서 데이터를 구성하는 방법

Algorithm? 단계적으로 문제를 풀 수 있는 명령어의 집합

 

ADP (Abstract Data Type)? Data (set of value) + Behavior (set of operations)

Advantages: Encapsulation / Localization of change / Flexibility

 

좋은 알고리즘 이란? Correctness 그리고 Efficiency (time, pre-processing, space, battery, heating 등 기준이 다양)

여기서 Time complexity를 기준으로 삼으면, Best / Average / Worst 인 경우로 또 나뉘고 주로 Worst를 기준으로 성능 평가를 한다. 완벽한 시간계산을 하는 게 아니라 입력갑셍 따른 알고리즘의 실행 시간의 추이만을 살핀다.

 

Asymptotic notation?

 - 입력이 작을 때 수행시간은 의미가 없다.

 - 알고리즘의 수행시간은 항상 입력의 크기가 충분히 크다고 생각했을 때, 즉 무한으로 향한다고 점근적으로 접근하여 어떤 함수 형태에 근접해지는 지 분석한다.

 - 수행시간이 커질 수록 최고 차항만 의미가 있고, 계수 또한 의미가 없다.

     → 최고차항만 표기하고 계수는 무시한다.

 

Big O, Big Omega, Big Theta

: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 크게 세 가지 표기법을 사용한다.

 - Big O

f(x) = O(g(x)), |f(x)| =< M |g(x)| for all x >= x0 (양수인 실수 M, 실수 x0)

"x가 x0보다 커지는 시점부터는 f가 항상 g보다 빠르다." Worst case에 대해 이야기 할 수 있다. f=O(n)은 함수 f가 최악의 경우에도 함수 n보다는 작다는 뜻이며, 함수가 작으면 속도가 빠르고 속도가 빠르니 Scalability가 크다.

 

 - Big Omega

f(x) = Ω(g(x)), f(n) >= k ⋅ g(n)

Best case에 대해 이야기 할 수 있으며, Big O랑 반대개념으로 f가 아무리 빨라도 g보다는 느리다.

 

 - Big Theta

f(x) = θ(g(x)), k1⋅ g(n) =< f(n) =< k2 ⋅ g(n), Ω =< f(n) =< O

f(n)은 Ω(n) 혹은 θ(n) 둘다 될 수 있다. 양쪽 다 바운딩한다.