Algorithm 2 - Asymptotic notation & recurrence

 앞서 살펴본 것 처럼, Asymptotically tight bound는 가장 높은 차수의 변수만 남기고 모두 제거하여 big theta 표현으로 나타낼 수 있다. (계수와 낮은 차수)

Properties of asymptotic notation
1. Transitivity : A=B, B=C일 때 A=C와 동일한 의미. 모든 5개의 notation이 모두 만족함. 이를 사용하여 결과를 확장할 수 있음

2. Reflexivity : 자기 자신을 반영하는 경우. 즉, equal이 포함된 3 개의 notation만 만족함. (f(n)은 자기 자신의 O(f(n))을 만족함)

3. Symmetry : Theta만 만족하는 것으로 필요 충분 조건을 나타냄

4. Transpose Symmetry : Theta를 제외한 나머지 4개가 만족함. 대소 비교를 하는 경우 서로의  f(n), g(n)을 교환할 때 부등호의 방향을 바꾸면 성립한다는 것을 의미함.

* f(n), g(n)은 모두 running time, time complexity이므로 항상 0보다 크다.
임의의 두 함수는 asymptotically comparable 하지 않다. 왜냐하면 주기 함수의 경우, 대소 비교가 가능한 n0를 찾을 수 없기 때문이다.
Sorting Algorithm & Divide and Conquer

- Insertion sort : 이름 처럼, sorted 된 파트에 unsorted 파트의 key element를 올바른 위치에 하나씩 삽입하는 과정을 반복하는 것이다.

selection은 가장 작은 것을 하나 골라 sorted portion에 비교하지 않고 삽입하는 반면, insertion은 순서대로 원소를 선택하고, sorted portion에서 크기를 비교하여 삽입하는 것이다.
즉, selection은 선택 과정에서 대소를 비교하고, insertion은 삽입 과정에서 대소를 비교한다.

for문 안에 while문이 nested 되어 있으므로 이 경우도 O(n2)의 time complexity를 가진다. 그러나 sorted part가 많을 경우 상대적으로 빠르다는 장점이 있다.


Best Case scenario : 모두 sorted된 array에 알고리즘을 적용할 경우

- insertion sort : 만약 sorted 부분을 옮기지 않고 맨 끝에 추가하면 된다면 (거의 sorted 되어 있을 경우) 내부 while 문은 반복이 필요하지 않으므로 (바로 제자리를 찾을 수 있음) O(n)의 time complexity를 가진다. 따라서 큰 부분은 다른 알고리즘으로 제자리를 찾은 다음, insertion을 사용하여 부분적으로 분류된 array를 다시 sorting하는 것이 더 효율적일 수 있다.

- bubble sort : 모두 sorted되어 있다면 첫 iteration에 교환이 하나도 이루어지지 않으므로 반복 한 번에 n-1 번의 비교만 이루어진다. 따라서 이 경우에도 O(n)의 time complexity를 가진다.

- selection sort : 그러나 selection sort는 항상 하나를 고르고, 나머지와 비교하여야 하므로 반복이 n번, 비교가 n-1번 발생하므로 best case 일 때도 O(n2)의 time complexity를 가진다.

일반적으로 best case를 비교하는 것은 의미가 없지만, 특정 경우에는 유의미한 결과를 가져올 수 있다. Average case는 all input에 대해 비교하는 것인데 측정하기가 매우 어렵다.
Worst case는 input이 reverse order일 때의 time complexity가 된다.

지금껏 배운 것들은 모두 in-place sorting algorithm으로 추가적인 공간이 필요 없다. 따라서 space complexity는 모두 O(1)이 된다.


Divide & Conquer
1. break down a large problem into multiple sub problems. (dividing)
2. Solve each sub problems individually (conquering)
3. Combine the solutions of sub problems for original one

한 번의 분해로 문제가 충분히 단순화 되지 않을 경우, 여러번의 반복을 통해 분해를 해도 된다. 이 경우, 합치는 과정도 동일하게 반복하게 된다.

- Merge sort : Divide & Conquer를 사용한 sorting 방법.
주어진 array를 더 이상 나눌 수 없을 때까지 분리한 후, 합쳐가며 sort 하는 방법.

Time complexity T = 2*T(n/2) + O(n)
divide는 그냥 중간 element를 선택하면 되므로 O(1), conquer는 반복적으로 수행되므로 자기 자신의 반복(recursion)이 되고, combine의 경우 O(n)이 된다.

반복 과정은 절반으로 나누어 가는 과정이므로 한 단계를 실행할 때마다 절반이 된다. 따라서 n 번의 분해가 이루어지면 (level n) , 2^n개의 element가 발생한다. 따라서 거꾸로 생각하면, 2^n개의 element를 분해하려면 n 번의 과정이 필요하다. 즉, log2(n)+1 번의 과정이 필요하다.

그래서 이를 combine과 합치면 T(n) = cn(log2(n)+1) 이 되므로 time complexity는 O(nlogn)이라는 것을 알 수 있다.

그러나 merge sort는 분해해 나가는 과정이 필요하므로 sorting 과정에 자기 자신 array의 크기만큼 공간이 더 필요하다. 따라서 space complexity는 O(n)이 된다.

이러한 divide & conquer algorithm은 효율적이고 간단하며 병렬화가 가능하고, 캐시 사용이 용이하다는 장점이 있다. (각 small fraction에 접근하므로 캐시 사용 가능)
그러나 recursive 작업이 필요하므로 메모리 사용량이 크며 사용 가능한 문제의 타입이 정해져있다. (반복적으로 분해 가능해야만 사용가능) 그리고 complexity를 측정하기 어렵다는 단점이 있다.

- Recurrence (점화식) : 더 작은 input으로 나누어 함수/부등식을 표현하는 방법
T(n) = 2 * T(n/2) + O(n) 와 같은 점화식의 asymptotic bound(omega, O)를 얻기 위해서는 Substitution method를 사용해야 한다.

Substitution method : Guess the solution -> Use mathematical induction to prove the guess.
그러나 추측만으로 충분히 tight 한 것을 찾을 수 없다.

Recursion-Tree Method
Recursion tree를 그려서 각 level의 cost를 계산하고, 모든 level의 cost를 합하여 total cost를 계산할 수 있다. 위에서 merge sort가 O(nlogn)이라는 것을 증명한 것 방법이 바로 이 방법이다.
여기서 구한 nlogn을 위의 T(n) 식에 집어넣으면 tight bound라는 것을 보일 수 있다.