Java | 알고리즘 분석, 점화식의 점근적 분석, Hanoi Tower 분석

BOZZANG·2022년 4월 20일
0

점근적 분석이란

알고리즘에 입력 되는 데이터의 크기에 따라 수행 시간과 차지하는 공간이 측정된다. 그리고 수행 시간과 차지하는 공간을 통해서 효율적인 알고리즘인지를 판단한다. 여기서 점근적 분석이란, 정확한 것이 아니고 대략 이 정도의 수행시간이 나온다라는 것을 측정하는 용도로 사용한다.

점근적 표기법,시간 복잡도(Time Complexity), Big-O

🎇 점화식의 점근적 분석 방법

Asymptotic Analysis Method

  1. 반복 대치
  2. 추정 후 증명
  3. 마스터 정리
    (여기서 마스터 정리는 다루지 않는다. 왜냐면 아직 삐약삐약 대학생인 내가 다루기에는 너무 하드하기 때문이다.)

점화식

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를 구하는 방법

  1. 추정
  2. 증명
    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)이 성립한다. 

0개의 댓글