점근적 분석이란
알고리즘에 입력 되는 데이터의 크기에 따라 수행 시간과 차지하는 공간이 측정된다. 그리고 수행 시간과 차지하는 공간을 통해서 효율적인 알고리즘인지를 판단한다. 여기서 점근적 분석이란, 정확한 것이 아니고 대략 이 정도의 수행시간이 나온다라는 것을 측정하는 용도로 사용한다.
점근적 표기법,시간 복잡도(Time Complexity), Big-O
🎇 점화식의 점근적 분석 방법
Asymptotic Analysis Method
- 반복 대치
- 추정 후 증명
- 마스터 정리
(여기서 마스터 정리는 다루지 않는다. 왜냐면 아직 삐약삐약 대학생인 내가 다루기에는 너무 하드하기 때문이다.)
점화식
Recurrence
어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계를 표현한 식
ex)
f(n) = f(n-1) + f(n-2)
f(n) = nf(n-1)
An = An-1 + 2🔗 반복 대치
점화식을 반복하여 대치해가면서, 점화식을 전체적으로 나열시킨 후에 점근적 시간복잡도 (Time complexity)를 구하는 방법
(더 작은 문제에 대한 함수로 반복해서 대치해나가는 방법)
T(n) = T(n-1) + 1, T(1) = 1
T(n) = T(n-1) + 1
T(n-2) + 1 + 1
T(n-3) + 1 + 1 + 1
...
T(1) + (n-1)
n
T(n) = n
n > (1/2) * n -> Ω(n)
n < 2 * n -> O(n)
--> Θ(n)🔗 추정 후 증명
점화식의 모양을 보고 점근적 복잡도를 추정한 후, 귀납적으로 증명하여 점근적 시간복잡도
Time Complexity를 구하는 방법
- 추정
- 증명
2-1. 귀납법 상 경계조건
(경계조건을 만족시키는 경계치는 항상 잡을 수 있으므로,
경계조건을 확인하는 과정은 생략해도 무관하다.)
2.2. 귀납법 가정 및 전개
수학적 귀납법의 전개 방법
방법 1 : n = k 일 때 성립하면 n = k + 1도 성립한다.
방법 2 : n1 <= k < n 인 모든 k에 대해 성립하면 n일 때도 성립한다.
방법 3 : n = k 일 때 성립하면 n = 2k일 때도 성립한다.
추정 후 증명법
T(n) = T(n-1) + 1, T(1) = 1 -> T(n) --> Θ(n)인 것을 증명
[경계 조건]
n = 2 일 때,
T(2) = T(1) + 1 = 2 , 3*2 보다 작거나 같고, (1/3)*2 보다 크거나 같을 것
n = 3 일 때,
T(3) = T(2) + 1 = 3, 2*3 보다 작거나 같고, (1/2)*3 보다 크거나 같을 것
즉, T(n)은 Θ(n)을 만족한다.
[가정]
n-1일 때, T(n-1)이 c * T(n-1)보다 작거나 같거나 또는
c * T(n-1)보다 크거나 같을 c가 존재한다고 가정
[전개 1] : n일 때, O(n) 증명
T(n) = T(n-1) + 1
<= c * (n-1) + 1
<= c * n (만약에 c>1이라면) --> O(n) 성립
[전개 2] : n일 때, Ω(n) 증명
T(n) = T(n-1) + 1
>= c * (n-1) + 1
>= c * n (만약에 c>1이라면) --> Ω(n) 성립
결론으로, Θ(n)이 성립한다. 자... 이해가 안된다. 이해가 안될 때에는 수많은 예제와 함께 싸워보자...
🚦 The Tower Of Hanoi
하노이의 탑은 세 개의 기둥과 이 기둥에 꽂을 수 있는 서로 다른 크기의 원판들로 구성된다. 원판들은 하나의 기둥에 정렬되어 있는데, 아래에서 위로 갈수록 원판의 크기가 작아진다. 이 퍼즐의 목표는 전체 원판들을 다른 하나의 기둥으로 옮기는 것인데, 이 때 아래와 같은 규칙이 주어진다.
🔗 규칙
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안된다. 🔗 접근
기둥A,B,C가 존재하고,
기둥 A에 있는 원판을 기둥 C로 옮기는 것을 목표로 한다.
원판이 한 개인 경우, A에서 C로 바로 옮기면 된다.
원판이 n개인 경우, 맨 밑에 있는 원판을 제외한 모든 n-1개의 원판을 B로 옮긴다.
그 후 맨 밑 원판을 C로 옮기고, B에 있는 원판을 C로 옮긴다.
이 때 B에 남아 있는 원판들을 C로 옮기는 것은, 처음과 똑같은 과정이다.
즉 같은 로직에서 데이터의 개수가 감소한 것이며 재귀를 사용하면 된다!
🔗 코드
public class Hanoi {
public void move(int n, int from, int to) {
if (n == 1) {
System.out.println("Disk " + n + " : " + from + "번 ==> " + to + "번");
return;
} else {
int k = 3 - from - to; // 기둥이 0, 1, 2일 때, 원판을 옮길 기둥
move(n - 1, from, k);
System.out.println("Disk " + n + " : " + from + "번 ==> " + to + "번");
move(n - 1, k, to);
}
}
public static void main(String[] args) {
Hanoi myTower = new Hanoi();
myTower.move(5, 0, 1); // Disk 5개를 타워 중 0번에서 1번으로 옮겨라
}
}다음으로 반복 대치를 하며 시간복잡도를 구하기 위해
하노이의 탑에서 n개의 원판을 옮기는데 필요한 연산의 수를 구해보자.
위의 알고리즘에서 한 번의 순환을 보면,
n개의 원판을 옮길 때 n-1개의 원판을 먼저 옮기고 그 후 가장 아래의 1개의 원판을 옮긴 다음, 다시 n-1개의 원판을 옮겼다.
🔗 반복 대치
T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1
T(n) = 2T(n-1) + 1
= 2*2T(n-1) + 1 + 1
= 2*2*2T(n-1) + 1 + 1 + 1
...
= 2^n-1 * T(1) + ... + 2^2 + 2^1 + 2^0
T(1) = 1이고 n개의 항을 가지는 초항이 1, 공비가 2인 등차수열의 합이다.
따라서 총 연산의 개수는 `T(n) = 1*(2^n-1)/2-1 = 2^n -1
T(n) = 2^n - 1
< 2 * 2^n -> O(2^n)
> (1/2) * 2^n -> Ω(2^n) 이 성립하므로,
--> Θ(2^n)이 성립한다.🔗 추정 후 증명
추정 후 증명법
T(n) = 2T(n-1) + 1, T(1) = 1, T(n) = Θ(2^n)임을 증명
[경계 조건]
T(1) = 2T(0) + 1 = 1
<= 2 * 1
>= (1/2) * 1
[가정]
n-1일 때, T(n-1) <= c * 2^n-1 또는
>= c * 2^n-1인 c가 존재한다고 가정
[전개 1] : n일 때, O(2^n) 증명
T(n) = 2T(n-1) + 1
<= 2 * c * 2^n-1 + 1 = c * 2^n + 1
<= k * 2^n, (if c<k)
-> O(2^) 성립
[전개 2] : n일 때, Ω(2^n) 증명
T(n) = 2T(n-1) + 1
>= 2 * c * 2^n-1 + 1 = c * 2^n + 1
>= k * 2^n, (if c>k)
-> Ω(2^n) 성립
결론으로, Θ(2^n)이 성립한다. 