[알고리즘] Prologue - Performance & Big-O

1. 성능

• 성능=효율(efficiency), 어떤 성과를 얻기 위해 얼마나 많은 자원을 투입하였는지 측정하여 도출, 효율적≠효과적

• Efficiency = Solution ÷ Resource

• 자원 중요도 : 시간(cpu) >>> 공간(memory) 

• 성능의 세 가지 경우

   1) 최선의 경우 (Best case)

   2) 평균의 경우 (Average case)

   3) 최악의 경우 (Worst case) ★

• 입력의 크기에 따라 성능 결정

   - n = 입력의 크기

   - f(n) = 시간복잡도의 그래프 표현

   - 성능 그래프 = (n, f(n))

      → (3)은 존재하지 않으며 (1)은 일반적인 경우, (2)는 최고의 성능

 

2. 점근적 분석법

• 시간 복잡도는 매우 큰 입력에 대해서 측정함

   - n이 매우 큰 경우에 대해서만 의미있는 성능을 측정할 수 있음

 

• g(n)을 이용한 f(n)의 성능 표현

   - g(n) : f(n)의 최악의 경우를 표현함

   - 같은 입력을 받아 처리할 때 g(n)은 f(n)보다 더 많은 시간을 요구함

      ⇒ g(n)은 항상 f(n)보다 커야함

   - 표현

      "g(n)은 f(n)보다 성능이 나쁘다"

      "g(n)은 f(n)의 worst case"

      "f(n)의 상한은 g(n)"

 

3. Big-O 표기법

• g(n)이 f(n)의 최악의 경우일 때

   (1) f(n) ≤ g(n)

   (2) f(n) ≤ g(n) for n0 < n

   (3) f(n) ≤ Mg(n) for n0 < n (동일한 비율로 증가하는 함수를 허용하기 위해 상수 M을 인정함)

f(n) is O(g(n)) as n →∞, if and only if ∃ n0, ∃ M>0 such that f(n) ≤ Mg(n) for n0 < n

• Big-O 성질

   - 성질1

   : 어떤 n>n0에 대해서 g1(n)<g2(n)이면 f(n)=O(g1(n))은 f(n)=O(g2(n)) 이다.

    Ex) f(n)=O(n) 이라면 f(n)=O(n^2)

    - 성질2 

   : 어떤 상수 k에 대해 f(n)=O(kg(n)) 이라면 f(n)=O(g(n))이다.

   Ex) f(n)=O(5n^2) 이라면 f(n)=O(n^2)

    - 성질3

   : f(n)=O(g1(n)+g2(n))이고, 어떤 n>n0에 대해서 g1(n)<g2(n)이라면 f(n)=O(n^2)이다.

   Ex) f(n)=O(n^2+n)이라면, f(n)=O(n^2)

 

* Big-Omega 표기법 : 최선의 경우 표현

f(n)=O(g(n)) ⇒ g(n)=Ω(f(n))

 

* Big-theta 표기법

f(n)=O(g(n)) & f(n)=Ω(g(n)) ⇒ f(n)=Θ(g(n))

   즉, f(n)과 g(n)은 동일한 비율로 증가함 

 

4. Big-O 표기법 예시

• g(n)=1

   - 상수 시간 복잡도 (Constant time complex)

   - f(n)=O(1)

   - 입력에 상관 없이 항상 일정한 시간이 소요됨 (가장 이상적)

• g(n)=n

   - 선형 시간 복잡도 (Linear time complex)

   - f(n)=O(n)

   - 시간은 입력의 크기에 비례해서 증가

• g(n)=n^k (k≥2인 상수)

   - 다항 시간 복잡도 (Polynominal time complex)

   - f(n)=O(n^k)

   - 시간은 입력 크기의 k제곱에 비례하여 증가

• g(n)=k^n

   - 지수 시간 복잡도 (Exponential time complex)

   - f(n)=O(k^2)

 

• g(n)=logkn

   - 로그 시간 복잡도 (Log time complex)

   - 시간은 n의 log에 비례해서 증가

   - 밑(k)는 중요하지 않다

• g(n)=nlogn

   - f(n)=O(nlogn)

 

※ 요약 - 시간복잡도 비교

n(=입력)	1	log(10)n	n	nlogn	n^2	2^n
1	1	0	1	0	1	2
10	1	1	10	10	100	2^10
100	1	2	100	200	10,000	2^100
1,000	1	3	1,000	3,000	1,000,000	2^1,000
10,000	1	4	10,000	40,000	100,000,000	2^10,000

(*왼쪽일수록 성능 좋음)