[알고리듬] 시간복잡도 분석(피보나치, Peasant, Hanoi, Quick sort, Merge sort)

지난주는 시간복잡도, 알고리즘을 수행하는데 걸리는 시간(running time)
어떻게 측정하는가?
알고리즘 자체가 추상적인 상태이므로, 시간 복잡도를 이용하자.

시간 복잡도 분석 = 연산의 개수 세기  >> (시간복잡도 = n에 대한 함수)
n에 대한 개수를 정확하게 세는 것은 어렵다. 따라서 최악의 경우를 따짐 -> 최대 개수에 대한 상한을 분석

◇예제. 피보나치 수열◇
 : O(mn)만큼의 한 자릿수 곱셈

피보나치 수열

(안쪽 for문)
 >> ppt 내용 인덱스 범위 지정이 잘못됐음. if문을 써서 i <n, k-i<m이 가정되어야 한다.
 >> 안쪽 for 문 : 상수 개+1번의 상한을 갖게 됨.                                                    // O(k+1)를 넘지 않는 빅오를 갖게 된다.
 >> 안쪽 for문에서 hold += hold*X[i][j]의 값이 O(mn)의 값을 가진다.
 그 이유는 i와 j의 쌍의 개수는 k와 같다. 항상 k개는 아니지만 최대한 i가 가능한 k의 개수는 n개고, j가 가능한 k의 개수는 m개이기 때문에 O(mn)의 이 알고리즘에서 가정하고 있는 기본 연산 횟수이기  때문인데 덧셈과 한 자릿수의 곱셈을 가정하고 있기에 교재에서는 O(mn)의 시간복잡도를 가진다.
(바깥 for문)
 >> n+m-1만큼의 반복문을 돌린다. n+m까지의 합 ΣO(k+1)
 >> O((n+m)²) 

※기본 연산에 따라서 시간 복잡도가 달라지는 경우가 생긴다.※


◇예제. PeasantMultiply◇

피보나치 곱

(( while x>0 인 반복문 ))
x <- [x/2] 로 인해 x값이 작아지는 점 >> 따라서 반복 횟수가 log x
y <- y+y  >> n+n만큼의 덧셈을 할 때 걸리는 시간은 n의 자릿수만큼 걸린다. 따라서 log y번의 연산.

>> 빅오에서는 log2x * logy 가 있다면 2와 같은 로그 밑 값이 필요가 없어진다.  
>> 반복 * 연산 횟수 = (log x) * (log y)

┌ ┐실링 : 안에 있는 값을 올림 // └ ┘플로어: 안에 있는 값을 버림
------------------------------------------------------------------------------------------

// Recursion을 이해하려면 Reduction에 대해서도 이해해야 한다. 동전의 양면과 같음.

"재귀"
: 무한을 유한한 텍스트로 표현하는 방법 중 하나
재귀 호출을 하는 함수 >> 재귀 함수

Recursion의 예들
예시 1)     1.  n! = {n=0,    1  }
                             {n>0,   n*(n-1)}
               2. 자연수의 정의 { 1은 자연수이다.    }
                                         { n이 자연수이면, n보다 1 큰 수도 자연수이다.  }
예시 2)    1. (Linked) List 
                     - NULL은 list이다.
                     - A가 list이면, A 앞에 노드를 연결한 전체도 list이다. 
              2. Binary Tree
                     - 공집합은 binary tree이다. (공 트리)
                     - T1과 T2가 binary tree라면... 재귀적 구조
예시 3) int factorial(int n) {if (n==1) return 0; else return n*fact(n-1);}

Reduction
- 가장 많이 사용하는 technique
- x 문제를 풀기 위해 x에 대한 알고리즘을 짜고 싶었는데, 그것을 풀기 위해 y 알고리즘을 사용하게 된다.
- y를 풀기 위한 알고리즘을 호출하는 것이지, 그것을 들여다볼 필요가 없으므로 마치 black box 같다.
- "문제 간의 관계" 개념

예시)
최솟값 찾기
1. A를 정렬한다. // 최솟값 찾기 problem에 정렬 알고리즘이 사용됨. 
2. return A[0];

Selection(A[0 ... n-1, k] // 배열 A에서 k번째로 작은 값찾기
1. A를 정렬한다.
2. return A[k-1]

Selection is reduced to Sorting >> selection문제를 풀기 위해 sorting 알고리즘을 subroutine으로 활용함
                                                   >> 우리가 푼 알고리즘이 더 큰 알고리즘을 풀기 위한 building blocks으로 사용되기도 한다.


■Recursion■
: Recursion은 reduction의 한 종류
: instance(입력) 개수가 하나 이상이라면, 사이즈를 줄기 위해 같은 문제로 reduction 하거라.
: "문제의 사이즈를 줄여라"

int factorial(int n)
{
   if(n==0) return 0;
   else return n*factorial(n-1); // 이게 함수 본인이라는 것을 잊어라.
} // 그저 나는 fact함수가 (n-1)!이라는 것만 생각하라.  


■Peasant Multiplication■
//곱셈 문제
x*y :  if x=0  return 0
       else if  x=even  return  (플로어 x/2) * (y+y)
       else  x=odd   return  ((플로어 x/2) * (y+y)) +y

// 알고리즘  PeasantMultiply(x,y) :  if { x=0 return 0 }  else {     x' <- 플로어x/2     y' <- 플로어y/y     prod <- PeasantMultiply(x', y')     if x==odd         prod <- prod+y     return prod  }

■Hanoi Tower■
 - n개의 disc와 3개의 Peg(막대기)
 - 하노이 규칙 : 큰 disc가 작은 disc 위에 올라가서는 안된다.
1. n-1개의 disc를 peg1에서 peg2로 옮긴다.(by recursion)
2. disc n을 peg1에서 peg3로 옮긴다.
3. n-1개의 disc를 peg2에서 peg3로 옮긴다.(by recursion)

n-1개를 옮기는 것은 원래 instacne보다 작은 하노이 탑 문제의 instance
즉, 같은 문제로의 reduction -> recursion

Hanoi(n, src, dis, tmp)
if n>0 //base case
  Hanoi(n-1, src, tmp, dst) 
  move disk n from src to dst  
  Hanoi(n-1, tmp, dst, src)

재귀 함수가 동작 하는 알고리즘을 짜려면 어떻게 하는가? 작은 수부터 해봐라
base case : instance
recursion step : reduce/simpler instances

Simplify & Delegate
- Simplify : 더 작은 instance를 만들고
- Delegate : 던져버리고 잊어버리자 -> 내가 하는 일이 아님. recursion으로 만들어라

왜 동작하는가? 이건 수학적 귀납법에 의해서 설명 가능함.

----------------------------------------
Hanoi Tower : 시간 복잡도 분석
move 연산을 몇 번 수행하게 될까?
n=1일 때 1번/ n=2일 때 2번/ n=3일 때 7번/...

if n>0 //base case
Hanoi(n-1, src, tmp, dst) // T(n-1)
move disk n from src to dst // 1
Hanoi(n-1, tmp, dst, src) // T(n-1)
----------------------------------------
점화식 >> T(n)을 Hanoi(n, src, dst, tmp) 함수를 실행했을 때의 move  연산의 횟수라고 하자.
     if n=0, return 0 
     else n>0, return 2*T(n-1)+1
이제 우리가 알고 있는 T(n)=2*T(n-1)+1의 점화식을 풀면 T(n) = 2ⁿ-1이고, 여기서 무한대의 값만 취급해주면 빅오 표기법으로, O(2ⁿ)이라는 시간 복잡도를 가진다. // 굉장히 큰 사이즈를 가짐.

■Mergesort■
: Recursion을 이용하는 정렬 알고리즘
: EDVAC에 구현된 최초의 컴퓨터 프로그램 중 하나

1. 주어진 배열을 절반으로 나눈다.
2. 두 subarray를 각각 정렬한다. >> by recursion
3. 정렬된 두 subarray를 합쳐서 하나의 정렬된 배열로 만든다.

MergeSort  :                               //basecase는 n=1이거나 공집합일 경우.  if n>1     m <- n/2  MergeSort(A[1 ... m])  MergeSort(A[m+1 .. n])  Merge(A[1 ... n], m)               //따로 함수를 만들어서 구현함.  Merge :  i <- 1;  j <- m+1                       // i와 j는 인덱스 취급  for  k <- 1  to  n                          화살표가 가리키는 위치의 값들을 비교하여 작은 것을 앞으로.       if j>n            B[k] <- A[i];  i <- i+1;       else if i>m            B[k] <- A[i];  i <- j+1;       else if A[i] <A[i];              B[k] <- A[i];  i <- i+1;       else            B[k] <- A[j];  j <- j+1;

(정확성에 대한 증명) >> 수학적 귀납법
proof by induction
- (base case) n=1일 때,
- (induction step) n>1일 때, 
     // (★induction High processes★라고 부름.)
    <Assume> MergeSort가 n-1개 이하의 원소를 가진 배열은 정확하게 정렬한다고 가정하자.
     n>1이므로 m<n이고 n-m<n이므로 ... 
두 번의 recursive call은 올바르게 동작하여 두 개의 정렬된 배열을 만든다.
이걸 가지고 Merge 하니까 전체가 정렬될 것이다.

두 조건(n=1일 때, n>1일 때)이 만족하므로 수학적 귀납법에 의해 어떤 자연수 n에 대해 정렬할 수 있다.
recursion : button up
 
시간 복잡도
T(n)을 MergeSort(A[1 ... n])의 시간복잡도 함수라고 정의하자
Merge sort
if n>1
m <- n/2
MergeSort(A[1 ... m])     // T(n)
MergeSort(A[m+1 .. n]) // T(n-m-1)
Merge(A[1 ... n], m)       // O(n)

T(n) = T(실링(n/2)) + T(플로어(n/2))+O  //플로어랑 실링은 무시할 수 있음
T(n) = 2*T(n/2) + O(n) >> 여기서 빅오는 c(상수)xn
      ≤ 2*T(n/2) + c(상수)xn = T(n)O(n log n) //이걸 어떻게 풀까?

----------------------------------------

Quick Sort
: Mergesort와 다르게 recursion 하기 전에 분류 작업이다.

알고리즘
1. 주어진 배열의 원소 중에 pivot을 고른다.
2. Partition : Pivot을 기준으로 작은 것과 큰 것을 분류
   pivot보다 작은 건 앞으로, 큰 건 뒤로 분류
3. 이 두 subarray를 각각 정렬한다.

/*정렬*/  QuickSort(A[1 ... n]):  if (n>1)     Choose a pivot element A[p]  r <- Parttition(A,p)  QuickSort(A[1 ... r-1])  QuickSort(A[r ... n])  /*분할*/  Partition(A[1 ... n], p):   swap A[p] <-> A[n]   l <- 0   for i<-1 to n-1      if A[i] < A[n]         l <- l+1         swap A[l] <-> A[i]   swap A[n] <-> A[l+1]   return l+1

명확성
Mergesort와 같은 방식으로 증명 가능
By iduction

시간 복잡도
T(n) = T(r-1) + T(n-r) + O(n)
최악의 경우 r=1이거나 r=n //pivot이 맨 끝으로 지정됐을 경우.
T(n) = T(n-1) + O(n) = O(n²)
 >> 평균적인 분석을 하면 QuickSort는 대개 O(n log n) 시간이 걸린다.


-----------------------------------------------------------
/*정리*/

- 팩토리얼 함수  >>  T(n) = T(n-1)+c
- 하노이 타워 >>  T(n) = 2*T(n=1)+1
- Merge sort >>  T(n) = 2*T(n/2) + O(n)
- Peasant Multi >>  T(n) = T(n/2) + O(log y)

Peasant Multiplication에서.. 최초에 나온 알고리즘은 반복문으로 되어 있었습니다.
그 반복 횟수가 log x 번이고 그때마다 O(log y) 번의 연산을 하니까 곱하면 됩니다.