시간 복잡도 개념 (점화식)

시간 복잡도란

시간 복잡도란 알고리즘을 수행하는데 걸리는 시간을 말하며
보통 다룰 변수의 크기 혹은 개수 를 n으로 두고 계산한다.

 

시간 복잡도를 분석 종류로는 3가지이며
최악인 경우 에서의 시간, 평균적인 경우 에서의 시간, 최적의 경우 에서의 시간으로 나뉜다.
여기서는 보통 최악의 경우에서의 시간을 다루며 평균적인 경우에서의 시간은 가끔 쓰인다고 한다.

 

시간 복잡도를 식으로 표현하는 예로는 아래처럼 하면 된다.

int factorial(int n) { return n == 1 ? n : n * factorial(n - 1); }

위 코드는 factorial을 재귀 함수로 구현한 코드이며 해당 함수의 시간 복잡도는 아래의 식처럼 나온다.

 

$T(n) = T(n - 1) + c$ ($c$ 는 상수, $T(1) = c$)

$T(n)$ : 해당 factorial 함수의 시간복잡도를 의미하며 n은 입력될 변수의 크기이다.
$T(n - 1)$ : factorial 함수의 반환 값에서 factorial(n - 1)의 시간 복잡도를 표시한 것이다.
$c$ : return, 삼항 연산자, 연산 등 계산할 때 수행되는 일정한 횟수이다. (적분 상수와 비슷하다.)

위에서의 *, /, %, +, - 연산은 시간복잡도에서 1로 취급한다.

따라서 위 점화식을 풀어쓰면
$T(n) = T(n - 1) + c = T(n - 2) + 2c = ... $

$= T(2) + c(n - 2) = T(1) + c(n - 1) = c(n - 1) + c$
$T(n) = cn$ 해당 식이 된다.

시간 복잡도 표기법

시간 복잡도에는 3가지 표기법이 있으며
각각 O(빅오) 표기법, Θ(빅세타) 표기법, Ω(빅오메가) 표기법이 있다.

• O 표기법은 시간 복잡도에서 나오는 값의 상한 을 표기하는 방식을 말한다.
  만약 $T(n) = 2n^2$ 이면 $T(n) = O(n^2)$ 혹은 $T(n) = O(n^3)$ 등으로 표기할 수 있다.
• Ω 표기법은 시간 복잡도 값의 하한 을 표기하는 방식을 말한다.
  만약 $T(n) = 2n^2$ 이면 $T(n) = Ω(n)$ 혹은 $T(n) = Ω(\log{n})$ 등으로 표기할 수 있다.
• Θ 표기법은 시간 복잡도 값의 상한과 하한의 교집합을 표기하는 방식을 말한다.
  만약 $T(n) = 2n^2$ 이면 $T(n) = Θ(n^2)$ 으로만 표기할 수 있다.

자세한 정의에 대해서는 아래 사이트에서 참고해 주세요. programiz.

시간 복잡도 계산

시간 복잡도는 factorial 함수에서 나온 식처럼 다양한 식을 계산할 수 있으며
그 방법으로는 반복 대치, 추정 후 증명, 재귀 트리, 마스터 정리 4가지가 있다.

반복 대치

첫 번째는 반복 대치이며 점화식을 더 작은 식으로 계속 풀어나가는 방법을 말한다.
예로는 위 factorial 함수의 시간 복잡도를 푼 것으로 볼 수 있다.
$T(n) = T(n - 1) + c $ ($c$는 상수, $T(1) = c$)

$T(n) = T(n - 1) + c = T(n - 2) + 2c = ... $

$= T(2) + c(n - 2) = T(1) + c(n - 1) = c(n - 1) + c$
$T(n) = cn$

추정 후 증명

두 번째는 추정 후 증명이며 구하려 하는 시간 복잡도를 임의의 값으로 추정을 한 후 증명을 하는 방법이다.
예로는 아래의 과정으로 볼 수 있다.
$T(n) = 2T(n/2) + 2n$

• 추정 : if $T(n) = O(n)$ then $T(n) \leq cn$
  $T(n) = 2T(n/2) + 2n \leq 2c(n/2) + 2n = cn + 2n$
  $T(n) \nleq cn$ 따라서 $T(n) \neq O(n)$
• 추정 : if $T(n) = O(n\log{n})$ then $T(n) \leq cn\log{n}$
  $T(n) = 2T(n/2) + 2n \leq 2c((\log{n}-\log{2})n/2) + 2n = cn\log{n}-cn\log{2} + 2n$
  $T(n) = cn\log{n} - (c\log{2} - 2)n \leq cn\log{n}$
  따라서 $T(n) = O(n\log{n})$

$T(n) = 2T(n/2) + 3$

• 추정 : if $T(n) = O(n)$ then $T(n) \leq cn$
  $T(n) = 2T(n/2) + 3 \leq 2c(n/2) + 3 = cn + 3$
  $T(n) \nleq cn$ 따라서 $T(n) \neq O(n)$
• 추정 : if $T(n) = O(n)$ then $T(n) \leq c_1n - c_2$
  $T(n) = 2T(n/2) + 3 \leq 2(c_1(n/2) - c_2) + 3 = c_1n + 3 - c_2$
  $T(n) \leq cn$ 따라서 $T(n) = O(n)$

 

재귀 트리

재귀 트리는 시간 복잡도의 진행을 트리 형태로 그려 시간 복잡도 값을 구하는 방식이다.
예로는 아래의 과정으로 볼 수 있다.

$T(n) = 2T(n/2) + 2n$

 

 

위 그림에 나온 트리에서 모든 값을 더하면 총합 시간 복잡도이다.
따라서 $T(n) = 2cn(1 + 2(1/2) + 4(1/4) + ... + 2^i(1/2^i) + ... + n(1/n))$
$T(n) = 2cn(1\times\log_{2}{n}) = 2cn\log_{2}{n}$
$T(n) = O(n\log{n})$

 

재귀 트리는 불균형 트리에서도 구할 수 있지만
개인적으로 조금 널널하게 계산을 하거나 추정 후 증명으로 풀이하는 것을 추천한다.

여기서 널널하게 계산한다는 것은 트리에서 제일 긴 부분(높이가 제일 큰 경로)을 모든 트리에 리프 노드에 동일한 과정으로 도달한다고 가정하여 푸는걸 의미한다.

예로는 아래의 과정을 통해 볼 수 있다.

$T(n) = T(n/4) + T(n/2) + 2n$

• 널널하게 계산하는 방식 (개인적인 방법)
  $T(n) = T(n/4) + T(n/2) + 2n$
  $T(n) \leq T(n/2) + T(n/2) + 2n = 2T(n/2) + 2n$
  따라서 위에서 계산한 과정의 결과로 $T(n) = O(n\log{n})$
• 추정 후 증명
  추정 : if $T(n) = O(n)$ then $T(n) \leq cn$
  $T(n) = T(n/4) + T(n/2) + 2n \leq c(n/4) + c(n/2) + 2n = (3/4)cn + 2n$
  $T(n) = cn + 2n - (1/4)cn$
  $T(n) \leq cn$ 따라서 $T(n) = O(n)$

마스터 정리

마스터 정리는 아래와 같은 식에서 시간 복잡도를 간단히 구할 수 있는 정리이다.

$T(n) = aT(n/b) + f(n)$ 이때 $(a \geq 1, b > 1)$

여기서 $n^{\log_{b}{a}}$를 기준으로 3가지 경우로 나누어 결과를 구할 수 있다.

• $\displaystyle\lim_{n\to\infty} n^{\log_{b}{a}} / f(n) = \infty$ 이면 $T(n) = Θ(n^{\log_{b}{a}}) $
• $\displaystyle\lim_{n\to\infty} n^{\log_{b}{a}} / f(n) = c $ ($c \neq 0 $) 이면 $T(n) = Θ(n^{\log_{b}{a}}\log{n}) $
• $\displaystyle\lim_{n\to\infty} n^{\log_{b}{a}} / f(n) = 0 $ 이면 $T(n) = Θ(f(n)) $

아래 예로 과정을 볼 수 있다.

$T(n) = 2T(n/2) + 2n$

마스터 정리로 $a = 2, b = 2$ 이므로
$\displaystyle\lim_{n\to\infty} n^{\log_{2}{2}} / 2n = \displaystyle\lim_{n\to\infty} n/2n = 1/2$

따라서 $T(n) = Θ(n\log{n})$

 

이러한 예와 달리 마스터 정리에서 사용할 수 없는 경우도 있으며 아래와 같은 예가 있다.

$T(n) = \sqrt{n}T(\sqrt{n}) + n = \sqrt{n}T(n/\sqrt{n}) + n$

마스터 정리로 $a = \sqrt{n}, b = \sqrt{n}$ 이므로
$\displaystyle\lim_{n\to\infty} n^{\log_{\sqrt{n}}{\sqrt{n}}} / n = \displaystyle\lim_{n\to\infty} n/n = 1$

따라서 $T(n) = Θ(n\log{n})$

 

하지만 위 답은 틀린 답이며 실제로 나와야 하는 답은 $T(n) = Θ(n\log{\log{n}})$ 이다.

자세한 풀이는 해당 사이트에서 참조하길 바랍니다.
stackexchange.

 

참고로 마스터 정리를 보면 추정 후 증명에서 추정을 다르게 하여 풀 수 있는 것을 볼 수 있었다.

$T(n) = 4T(n/2) + 2n$

추정 : if $T(n) = O(n^a)$ then $T(n) \leq cn^a$
$T(n) = 4T(n/2) + 2n \leq 4c(n/2)^a + 2n = 4c(n^a/2^a) + 2n$
따라서 $4/2^a \leq 1$ 이여야 성립하며 해당 식이 1 일때 a의 값이 최소이므로
$4/2^a \leq 1$ 에서 a값을 구하면 최소 시간 복잡도를 구할 수 있다.

여기서 $+ 2n$은 마지막에 추정을 다시 한번 하면 해결되므로 무시한다.

$4/2^a = 1$
$2^a = 4$
$a = \log_{2}{4} = 2$ 이므로 $T(n)$을 다시 증명해보면

$T(n) = 4T(n/2) + 2n \leq 4c(n/2)^2 + 2n = cn^2 + 2n$
따라서 $T(n) \nleq cn^2$

 

추정 : if $T(n) = O(n^2)$ then $T(n) \leq c_1n^2 - c_2n$
$T(n) = 4T(n/2) + 2n \leq 4c_1(n/2)^2 - 4c_2(n/2) + 2n = c_1n^2 - (2c_2 - 2)n$
따라서 $T(n) \leq cn^2$ 이므로 $T(n) = O(n^2)$

참고 사이트

시간 복잡도 표기법 정의 참고 : https://www.programiz.com/dsa/asymptotic-notations

시간 복잡도 계산 참고 : https://yjg-lab.tistory.com/273
https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/