[WIL] Day 10 (기말준비 Day 1)

<알고개>
Sorting 문제
삽입 정렬: 인덱스 0부터 n까지 점차 인덱스를 1씩 키워가면서 이미 정렬된 배열에 해당 인덱스의 숫자를 맞는 위치에 삽입을 해준다. 
수도 코드: 
A는 input 배열, n은 배열 크기, key는 배열될 값
i값은 j-1, 즉 이미 정렬된 값중 가장 오른쪽값. 
마지막 반복문은 i가 0보다 크고 A[i]가 key보다 클때까지 반복. key가 A[i]보다 크거나 같으면 반복문 탈출.
INSERTION-SORT(A, n)
  For j<- 2 to n
    Do key <- A[j]
    I <- j - 1
    While I > 0 and A[I] > key
       Do A[I+1] <- A[I]
          I <- I - 1
    A[I+1] = key

해당 코드에서 A[n-1]이 해당 배열의 가장 작은 값이면 worst case이다.

알고리즘 퍼포먼스-running time
Upper bound == worst case. 
Insertion sort의 worst case는? 
Asymptotic Analysis사용, asymptotic analysis란 T(n)이 주어졌을 때 n->Inf으로 간주하는 상황.
세타 notation으로 machine independent 알고리즘을 표현 가능. 
예) 3n^3 + 90n^2-5n+6046=Θ(n^3)

다시 insertion sort의 퍼포먼스를 보면
Worst case는 모든 input이 거꾸로 정렬되어있을때, 시그마j=2~n일때Θ(j) = Θ(n^2). 왜? 시그마 n에 대한 값이 n(n+1)/2인걸 알고 n^2가 가장 큰 지수값인걸 알기 때문이다. 
Average case는 Θ(j) 대신에 Θ(j/2)로 바꿔서 계산. 그 이유는 최악의 경우에는 모든 값에 대해서 교환을 해주어야 하는데 평균이니까 그 절반의 범위의 값에 대해서만 정렬을 한다고 간주하기 때문이다. 

Merge Sort nlogn 의 정렬방법
A[1..n]이 주어졌을 때 만약 n=1일때는 정렬 끝. 반복적으로 A[1..n/2]와 A[n/2+1…n]두 배열을 정렬. 그리고 2 정렬이 완성된 배열을 merge. 
두 배열을 정렬하는 방법은 먼저 두개의 변수로 각 배열의 가장 작은 값으로 지정. 그리고 그 두 값을 비교해서 더 작은 값을 다른 배열에 추가하고 추가된 값의 변수는 해당 배열의 그 다음으로 작은 값을 할당. 그리고 두 변수를 계속해서 이전과 같은 방식으로 비교 추가 비교 추가…
이 두 배열을 합치는 작업은 Θ(n)이 걸림. 

Merge sort analysis
Merge sort한번 하는 것 자체를 T(n)이라고 할때. 그래서 만약에 1~n/2까지 정렬을 하면 T(n/2)이고, 2 정렬된 배열을 정렬한다고 했으니까 2T(n/2)가 된다. 그리고 앞서 두 정렬을 합치는 과정을 Θ(n)이라는 것을 확인했음. 
그래서 n이 1보다 클때 T(n) = 2T(n/2) + cn인데 이걸 recursion tree로 solve. 
우리는 n이 1이 될때까지 배열을 나눌 수가 있으니까 계속 n을 2로 나누어서 트리를 만들면 결국 마지막에는 배열에 원소가 한개밖에 남지 않음. 그러면 중요한 점은 트리의 높이이다. 높이는 logn이된다. 
그리고 Merge하는 과정은 Θ(n)이였기 때문에 Merge sort의 복잡도는 Θ(nlogn)이다. 

알고리즘위한 기초 수학
N: 자연수 집합
R: 실수 집합
R >= 0 음수가 아닌 실수 집합
만약 X가 finite set이면 |X|는 X의 원소 갯수.
Polynomials: degree n의 polynomial이라고 하면 p(x) = Cnx^n + Cn-1x^n-1 + … + C1x + C0
예를 들면 polynomial of degree 5, p(x) = 3x^5 -12x^3 + 9x^2 - 200x + 4 
Upper bound, lower bound, 정의만 간단히 설명했는데 뭔 소리야…

Mathematical Induction(증명법)
S(1), S(2), S(3)…가 있을 때, 
Basic step: S(1)이 true임을 증명.
Inductive step: S(n)이 사실이라고 가정을 하고(이 과정을 inductive hypothesis라고 한다), S(n+1)이 사실임을 증명하는 과정.  이것이 가능한 이유는 S(1)이 사실이란것을 이미 증명했기 때문에.
이전 statement를 이용해서 다음 statement를 증명하면 weak mathematical induction이고 이전것 이외의 다른걸 사용해서 증명하면 strong임. 

예) sigma I=1~n, I = n(n+1)/2임을 증명해라. 
일단 n=1를 적용. 1~1까지의 합은 1, 1(1+1)/1=1 그럼으로 S(1)은 true.
그 다음에 inductive hypothesis으로 시그마가 n(n+1)/2가 true로 가정. 그래서 (n+1)(n+2)/2가 true임을 증명. 해당식은 시그마 식이니까 S(n+1) = S(n) + (n+1) = n(n+1)/2 + n+1 = n(n+1)/2 + 2(n+1)/2 = n(n+1)+2(n+1)/2 = (n+2)(n+1)/2 임을 증명. 끝

예2) 2n+1 <= 2^n for all n>=3임을 증명하라. 
Basic n이 최소 3이니까, n=3을 넣어서 2*3+1 <= 2^3, 9 <= 9, true.
이후에 S(n) = 2n+1 <= 2^n이 true라고 가정. 그래서 S(n+1) = 2(n+1) +1<= 2^(n+1)를 증명.
2(n+1)+1 = (2n+1) + 2 <= 2^n + 2 = 2^n+1, since 2<=2^n for all n>=1

Analysis of 알고리즘
Input 사이즈 n이 주어졌을 때 maximum time과 평균 시간을 물어볼 수가 있다. (Worst/average time)

F,g가 양수에 대해서 nonnegative function일때 f(n) = O(g(n))
여기서 f(n)이 복잡한 식 예를 들어 60n^2+2n+1이고 g(n)이 n^2일때 , f(n)은 of order at most g(n). At most 라는 건 upper bound라는의미. 빅오는 upper bound에 사용된다. f(n) <= C1g(n) for all n>=N1, N1은 n의 최소값. 이러면 f(n)=O(g(n)). 
반대로 오메가는 lower bound를 의미. 그리고 빅오와 오메가 둘다 맞으면 세타도 맞다. 

예) 60n^2+5n+1이 있을 때 해당 식이 60n^2+5n^2+n^2=66n^2보다 작거나 같고, C1=66 and N1=1 이여서 O(n^2)이다. (응?) 그니까 어차피 O(n^2)가 되어야 하니까 해당 식의 n^2를 제외한 나머지 떨궈지들한테도 n^2가 붙어야하고 대충 더해버려서 C1값과 N1값을 지정해주면 되나봄. 
오메가인 경우에는 60n^2만 남기고 다 없앰. C2=60, N2=1. 그래서 세타(n^2)이다….ㅅㅂ

Substitution method
3가지 스텝, guess, verify, solve.
step2에서 증명 필요, 이전에 했던 mathematical induction. 
그래서 T(n)=4T(n/2)+n을 증명하는데 T(1) = theta(1)이라고 가정하고.
빅오와 오메가를 증명. 여기서 O(n^3)으로 guess. 이걸 증명하려면 T(n)<=cn^3이어야함(빅오의 정의로 인해서). 그래서 이걸 증명하기 위해서 inductive hypothesis가 필요. 그게 T(k) <= ck^3 for k<n.
그리고 inductive hypothesis를 적용을 해서 … 하…

Recursion-tree method.
T(n) = T(n/4)+T(n/2)+n^2
guess를 트리로 나온 값으로 추측할 수가 있음. 이 문제는 theta(n^2)로 추측할 수가 있음. 

Substitution method가 이해하기 난해했음, 앞에서 빅오랑 오메가 관한 정의 다시보고 복습해야함.


[과제]
저번에 이진탐색에 대해서 잠시 복습.
이미 정렬되어 있는 배열에서 찾고자하는 숫자를 탐색하는 알고리즘.
배열의 중간기준으로 해당 중간값과 찾고자하는 값과 비교하여
절반의 배열을 제외하여 점차 탐색하는 기법이였음.
다만 배열을 사용하기 때문에 중간에 새로운 값을 넣거나 하는 것이 
어렵기 때문에 이진 탐색 트리를 빌드할 니드가 생김.

이진 탐색 트리 또한 한쪽으로 트리가 계속 커져서 균형을 잃어버리는 것 때문에(이는 worst case O(n)이 되기 때문이다)
레드블랙트리가 탄생하게 된다. 어떻게든 균형을 맞추게 된다.
레드블랙트리의 5가지 특징:
1.노드는 레드 혹은 블랙 중의 하나이다.
2.루트 노드는 블랙이다.
3.모든 리프 노드들(NIL)은 블랙이다.
4.레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5.어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.