[Algorithm] 기초 지식 - big O notation

Complexity

컴퓨터가 주어진 문제를 효율적으로 해결할 수 있을까? (알고리즘은 존재)

- 효율의 기준 : polynomial의 존재 여부

Computability

컴퓨터가 이 세상의 모든 문제를 해결할 수 있는가? (알고리즘이 존재하는가)

 

Algorithm이란

a finite set of instructions

- algorithm의 5가지 요건

① input : (input 개수) ≥ 0

② output : (output 개수) ≥ 1

③ definiteness : 명확해야함.

④ finiteness : 모든 경우에서 유한한 시간 안에 종료되어야 함.

⑤ effectiveness : 간단하고 실행 가능해야함. (구현 가능성 측면)

 

 

Big O notation

두 함수 f(n), g(n)이 주어졌을 때, 모든 n ≥ k 에 대하여 f(n) ≥ c*g(n)을 만족하는 상수 k, c가 존재하면,
f(n)의 big O는 O(g(n))이다. ( Big O of f(n)은 g(n)이다. )

- 데이터의 수(n)의 증가에 따른 연산횟수의 증가를 상한선으로 표현함. (upper bound)

- 일반적으로 tight upper bound로 표현함.

- g(n) ∈ O(f(n))일 때, g(n)을 f(n)의 big O라 한다.

ex) f(n) = 7n^2 + 6n + 10 의 big O는 O(n^2), O(n^3), O(2^n) 등이 가능하다.

이때 tight upper bound는 O(n^2)이 된다.

 

Big Omega notation (Ω)

- 점근적 하한.(asymptotic lower bound)

ex) f(n) = 7n^2 + 6n + 10 의 big Ω는 Ω(n^2), Ω(n), Ω(logn) 등이 가능하다.

이때 tight lower bound는 Ω(n^2)이 된다.

 

Big Theta notation (Θ), order

- g(n) = O(f(n)) = Ω(f(n))일 때, g(n)을 f(n)의 order라 한다.

- 상한과 하한이 같은지 아닌지를 결정한다.

ex) f(n) = 7n^2 + 6n + 10 의 order는 Θ(n^2)이다.