[알고리듬] 시간복잡도 분석(피보나치, 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) 번의 연산을 하니까 곱하면 됩니다.