[알고리듬] 2주차: 시간복잡도

Time Complexity

알고리듬의 수행시간을 '이론적으로' 분석

-> 실제로 수행해보고 시간을 측정하는 게 아니다

 

실제 수행시간은 환경에 따라 달라진다.

- 무슨 코드로 작성했는가?

- 컴파일러 버전은 무엇인가?

- 알고리즘을 수행하는 기계의 스펙은 어떻게 되는가?

- 입력으로 주어지는 데이터의 크기

- 다른 프로세스가 점유한 자원은 얼마나 되는가?

- etc.

 

-> 이런 모든 환경적 요인들은 고정되었다고(모두 같다고) 가정한다.

 

추상화

환경적 요인의 조합은 거의 무한

-> 매번 모든 알고리즘을 구현할 수는 없다.

 

통상적인 어떤 환경에서 알고리즘 A가 알고리즘 B보다 빨랐다면 다른 환경에서도 그렇지 않을까?

-> 환경적 요인을 고려할 필요가 없다: 추상화

Ex) C로 짰든 Java로 짰든 Python으로 짰든 Bubble sort는 다 같은 Bubble sort

 

알고리즘은 추상적 개념이고 어떻게 기술하냐에 따라 C 함수일 수도 있고 Java method일 수도 있는 것

 

 

$n$에 대한 함수

시간복잡도는 $n$에 대한 함수, 수행되는 기본 연산의 개수

알고리즘의 수행시간은 수행되는 기본 연산의 개수에 비례할 것

-> $n$에 대한 증가함수

 

 

시간 복잡도 분석

$n$에 대한 함수 $f(n)$

분기문(Ex: $if$)이 많아지면 정확한 $f(n)$을 알기가 어렵다

-> 근사화/단순화된 case에 대해 분석

 

ⓐ Best-case Analysis

ⓑ Worst-case Analysis

ⓒ Average-case Analysis

 

Best-case Analysis: 별 의미 없어서 잘 안 함

최선의 경우에 1초 걸린다 -> ?

 

Worst-case Analysis: 최악의 경우에 1분이 걸린다

= 어떤 입력이 주어지든 간에 1분 안에는 끝난다

-> 상한

 

 

Ex) Selection sort

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indexMin = i;
 
        for (int j = i + 1; i < n; j++) {
            if (A[j] < A[indexMin])
                indexMin = j;
        }
        int temp = A[indexMin];
        A[indexMin] = A[i];
        A[i] = temp;
    }
}

* 초기화 연산은 기본 연산 개수에서 제외

 

2행: 3개

$\lt$ $-$ $++$

 

5행: 2개 (초기화 부분의 $+$ 연산은 좀 애매함)

$\lt$ $++$

 

6행: 3개

$[]$(Indexing operation) $\lt$

 

7행: 1개 (6행 조건이 참일 때만)

$=$

=> 6~7행: 3~4개

 

9행 ~ 11행: 6

$[]$

$[]$ $=$ $[]$

$[]$ $=$

 

수행되는 연산의 개수는 6

반복문에서 연산의 개수를 셀 때는 안쪽 반복문부터

 

안쪽 for문(5~8행)

반복 할 때마다 5~6회 -> 최악의 경우는 "6회"

$i + 1\; ~\; n$ -> 반복 횟수는 $(n - i)$번. $i$는 바깥쪽 for문에서 정해짐

 

바깥쪽 for 문

2행: $3$회

안쪽 for문: $6$회

9~11행: $6$회

-> $\displaystyle{\sum_{i=0}^{n-2} {\{6(n-i) + 10\}}\; =\; 3n^2 + 13n - 16}$

가 시간복잡도 ($n$에 대한 함수)

여기에 환경적인 요인에 따른 비례상수가 붙음

 

 

Big-O Notation

그냥 시간복잡도를 나타내기에 적절하니까 쓰는 것일 뿐 시간복잡도와 별개임

(둘은 아예 다른 개념으로 시간복잡도가 없어도 빅오표기법은 있음)

 

원래는 그냥 두 함수의 관계를 나타내기 위한 표기법

여기서는 함수의 증가속도를 비교하기 위한 표기법

 

$f(n) = O(g(n))$ ($f(n) \leq O(g(n))$와 일맥상통)

함수 $f$의 증가속도가 $g$보다 빠르지 않다(= 비슷하거나 느리다)

Ex)$3n^2 + 13n - 16 = O(n^2)$

 

$f(n) = \Omega(g(n))$ ($f(n) \geq \Omega(g(n))$와 일맥상통)

함수 $f$의 증가속도가 $g$보다 느리지 않다(= 비슷하거나 빠르다)

Ex)$3n^2 + 13n - 16 = O(n^2)$

 

$f(n) = \Theta(g(n))$

함수 $f$의 증가속도가 $g$와 비슷하다

 

 

 

증가속도

$n \rightarrow \infty$일 때 어느 함수가 더 빨리 증가하는가?

= $n$이 작을 때는 무시

 

사진에서 표시된 부분은 저렇게 나타낼 수 있다.

 

 

 

극한에 의한 정의

$f(n) = O(g(n)) ($f(n) \leq O(g(n)$)

$\lim_{n \rightarrow \infty}\frac{g(n)}{f(n)} \gt 0$일 때

무한대로 발산: g(n)의 증가속도가 훨씬 빠름을 의미

양수로 수렴:

 

$f(n) = \Omega(g(n))$ ($f(n) \geq \Omega(g(n)$)

$\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} \gt 0$일 때

무한대로 발산: g(n)의 증가속도가 훨씬 빠름을 의미

양수로 수렴:

 

$f(n) = \Theta(g(n))$

$f(n) = O(g(n))$ 이고 $f(n) = \Omega(g(n))$ 일 때

$\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)}$이 0이 아닌 양수로 수렴할 때

 

Ex) $f(n) = 3n^2 + 3n -16$

$f(n) = O(n)$: 틀림

$f(n) = O(n^2)$, $f(n) = O(n^3)$, $f(n) = O(n^{100})$: 맞음

$\because \; f(n) \leq O(g(n)$

$f(n) = O(n^3)$같은 건 별 의미는 없지만 '틀린' 표현은 아님

 

$f(n) = \Omega(n)$, $f(n) = \Omega(n^2)$: 맞음

$f(n) = \Omega(n^3)$, $f(n) = \Omega(n^{100})$: 틀림

$\because \; f(n) \geq O(g(n)$

 

 

$f(n) = \Theta(n^2)$: 맞음

$f(n) = \Theta(n)$, $f(n) = \Theta(n^3)$, $f(n) = \Theta(n^{100})$: 틀림

 

$f(n) = O(12n^2+3n)$: 맞음

$f(n) = \Omega(972n - 10)$: 맞음

$f(n) = \Theta(0.2n^2)$

헷갈릴 때는 극한으로 계산해보면 됨

 

 

증가속도에 따른 함수의 서열

 

① $1 \lt \lt \log n$

② $\lt \lt \lt n \lt n\log n \lt n^2 \lt n^3$

③ $\lt \lt \lt 2^n$

④ $\lt \lt n! \lt n^n$

 

① $Poly-logarithm$

물론 $1$과 $\log{n}$ 사이에도 무수히 많은 함수가 있다.

근데 $\log({\log{n}}), \log{(\log({\log{n}}))},\;\cdots$ 같은 식이라 딱히 의미가..?

이런 걸 $Poly-logarithm$($\log$ 함수의 다항식)이라 함

 

② $Polynomial$

①과 ② 사이에는 $n^{0.5} = \sqrt{n}$이나 $n^{0.1}$같은 게 있음

의외로 $n^{0.0001}$이 $(\log{n})^{1000000}$보다 빠르게 증가함

 

③ $Exponential$

의외로 $2^n$보다 $1.1^n$이 빨리 증가함

교수님피셜) 이래서 복리를 해야 된다

 

④ 얘네보다 더 빠른 것도 많지만(Ex: $2^{2^{2^{2^n}}}$) 제일 빠른 걸 구하는 건 별 의미가 없다

 

 

 

왜 Big-O notation인가?

ⓐ 일단 최악의 경우 = 수행 연산 수의 상한

ⓑ 연산의 갯수를 정확히 세는 건 어려움

ⓒ 추상적인 대상으로써 알고리즘에서는 상수는 덜 중요하다.

기술 언어에 따라 세부 연산이 다르긴 하지만 결국 비슷함

- 세부 연산의 수행속도 차이가 있긴 하지만 환경 요인에 대한 상수로 이해한다.

 

대부분은 연산의 정확한 개수로 세는 것보다는 '$n$이 클 때 증가하는 경향이 어떤가?'가 더 중요하다.

-> Big-O notation이 적절한 표기법

 

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indexMin = i;
 
        for (int j = i + 1; i < n; j++) {
            if (A[j] < A[indexMin])
                indexMin = j;
        }
        int temp = A[indexMin];
        A[indexMin] = A[i];
        A[i] = temp;
    }
}

6~8행의 연산 횟수는 고정임 -> $c_1$회라고 치자

-> 바로 바깥쪽 for 문이 $(n-i)$번이니까 $c_1(n-i)$번

 

9~11행의 연산 횟수도 고정 -> 바깥쪽 for문 한 번 당 $c-2$회라고 치자

 

=> 총 연산 횟수 = $\sum^{n-2}_{i=0} c_1(n-i) + c_2 \; = \; O(n^2)$

 

Big-O notation에서는 이런식으로 대략적으로 세면 됨

더 loose하게 하면 안쪽 for문은 최대 n번이고 바깥쪽 for 문이 n번이니까

대충 $n \times n$ 해서 $n^2번$ -> $O(n^2)$