알고리즘(Algorithm) - Algorithm Analysis

알고리즘(Algorithm) - Algorithm Analysis

1. Brute force

모든 경우의 수를 다 따져보며 최적의 솔루션을 찾는 방법으로, 일반적으로 실행하기는 불가능하다.

대게, input size가 n일 때 2^n 또는 그 이상의 러닝타임을 갖는다.

ex) stable matching problem에서 n명의 남자와 n명의 여자가 있을 때 Brute force search
      알고리즘을 사용한 러닝타임은 n!이다.

- Polynomial Time algorithm

러닝타임이 다항식(polynomial)의 형태인 알고리즘 (<->Exponential Time algorithm)

다항식의 constant는 러닝타임에 영향을 미치지 못한다고 가정한다.
(실제로 constant가 전체 알고리즘에 영향을 미치는 경우는 매우 드물기 때문)

def) An algorithm is efficient if its running time is polynomial.

 

2. Worst-Case Analysis

알고리즘의 좋고 나쁨을 평가하는데에는 러닝타임을 이용하는데, Worst-Case일때의 러닝타임을
기준으로 비교한다. 알고리즘의 최대 한계치를 보장해준다.

 

3. Asymtotic Order of Growth

- Upper bounds

Worst case일 때 러닝타임은 알고리즘의 최대 한계를  나타내주며, O(f(n))으로 표기한다.

- Lower bounds

Best case일 때 러닝타임은 알고리즘의 최소 한계를 나타내주며, Ω(f(n))으로 표기한다.

- Tight bounds

Upper bound와 Lower bound가 같은 경우이며, θ(f(n))으로 표기한다.

ex) T(n) = 32n^2 + 17n +32 일 때 T(n)은 O(n^2), O(n^3), Ω(n^2), θ(n^2)이며
      O(n), Ω(n^3), θ(n), θ(n^3)은 아니다.

ex) if f = O(g) and g = O(h) then f = O(h)
      if f = Ω(g) and g = Ω(h) then f = Ω(h)
      if f = θ(g) and g = θ(h) then f = θ(h)

ex) if f = O(h) and g = O(h) then f + g = O(h)
      if f = Ω(h) and g = Ω(h) then f + g = Ω(h)
      if f = θ(h) and g = θ(h) then f + g = θ(h)

ex) c*O(n^2) = O(n^2)
      logn*O(n^2) = O(n^2logn)
      n*O(n^3) = O(n^3)

ex) if x > 0, logn = O(n^x) log스케일은 모든 polynomial스케일보다 퍼포먼스다 좋다.
      if r > 1 and d > 0, n^d = O(r^n) polynomial스케일은 모든 exponential스케일보다
                                                   퍼포먼스가 좋다.

 

4. O(n) Time

- 최댓값 찾는 알고리즘

max <- a1 for i = 2 to n { if (ai > max) max <- ai }

- Merge

i = 1, j = 1 while (both lists are nonempty) { if (ai ≤ bj) append ai to output list and increment i else append bj to output list and increment j } append remainder of nonempty list to output list

 

5. O(nlogn) Time

- Merge sort / Heap sort

위의 Merge과정을 logn번만큼 시행하므로 O(nlogn)이다.

 

6. O(n^2) Time

- n개의 점이 주어졌을 때, 거리가 가장 가까운 순서쌍을 찾는 문제

min <- (x1 - x2)^2 + (y1 - y2)^2 for i = 1 to n { for j = i+1 to n { d <- (xi - xj)^2 + (yi - yj)^2 if (d < min) min <- d } }

 

7. O(n^3) Time

- n개의 집합과 1~n의 숫자가 주어졌을 때, 1~n의 숫자를 n개의 집합에 중복을 허락하여
   집어넣는다. 이때, 겹치는 숫자를 가진 집합이 있는지 없는지 검사하는 문제

foreach set Si { foreach other set Sj { foreach element p of Si { determine wherher P also belongs to Sj } if (no element of Si belongs to Sj) report that Si and Sj are disjoint } }

모든 쌍 : nC2 = n(n-1)/2 = O(n^2)
한번 비교 : Worst case -> 하나의 집합에 1~n-1이 있고, 다른 집합에 n이 있을 때 O(n)
∴ O(n^3)

 

8. O(n^k) Time

- graph에서 size가 k인 노드들의 집합중에 서로 인접한 노드가 하나도 없는 집합
   (Independent set)이 있는지 없는지 검사하는 문제 (k는 constant)

foreach subset S of k nodes { check whether S in an independent set if (S is an independent set) { report S is an independent set } }

size가 k인 노드들의 집합 갯수 : nCk = [n(n-1)…(n-k+1)]/[k(k-1)…2*1] <= (n^k)/k!
independent set인지 검사 : O(k^2)
∴O( (k^2)(n^k)/k! ) = O(n^k)

 

9. Exponential Time

- graph가 주어졌을 때 independent set의 maximum size를 구하는 문제

S* <- ￠ foreach subset S of nodes { check whether S in an independent set if (S is largest independent set seen so far) { update S* <- S } }

모든 subset의 갯수 : 2^n
인접한 노드가 있는지 없는지 검사하는 횟수 : O(n^2)
∴ O( (n^2)*(2^n) )