算法小节--algorithm analysis

algorithm efficiency due to input size

Asymptotic Analysis: for real time programming, to conclude the worst cost.(grow array is O(n), need shift whole array)
Amortized Analysis: measure average performance and consider time to grow for longer time
(scripting to grow array will be O(1) bc do it rarely)


worst case: most time, index get to upper bound

average case: sometimes,  uniformly distributed, sum cases/size (n*n-1....)/(n+1)

best case: bogus

Θ(g(n)), it means that the running time of the algorithm as n (input size) gets larger is proportional to g(n).(tight bound) - best case & worst case is same
O(g(n)), it means that the running time of the algorithm as n gets larger is at most proportional to g(n).(upper bound)
 Ω(1)- best case

→ Rank:
log(n) <sqrt(n)< n <n^2 < n^log(n)<2^n
Master Theorem (recursion analysis)


→ Quick sort:
good for large size of number, no need extra space
Time: Average O(nlgn) Worstcase O(n^2)
Space: O(lgn) - stack
http://rainykat.blogspot.com/2017/01/quicksort.html
General:
Time: T(n) = T(k) + T(n-k-1) + Θ(n)
Best:middle element as pivot
 T(n) = 2T(n/2) + \theta(n)
Worst: smallest or largest pivot,O(n^2), array already sorted
T(n) = T(0) + T(n-1) + Θ(n)
which is equivalent to 
 T(n) = T(n-1) +Θ(n)
Average
T(n) = T(n/9) + T(9n/10) +Θ(n)

→ Merge Sort: T(n) = 2T(n/2) + Θ(n),
Time: Θ(NlogN) Space: O(n) - merge array

→ Heap Sort: Time O(NlogN) Space O(1)

→ Bubble sort-

worst case: O(n^2)//pass through 2(at most n-1) times for n[3,2,1]
- each time 1 element is sorted at left


→ Selection sort-Split into 2 part
Time O(n^2) -- n + (n-1) + ..+2+1, Ω(n^2)

Sorted | Unsorted
-  find min in unsorted
- swap with the 1st of unsorted part
- increase the sorted part


→ Insertion sort-Split into 2 part
-Time Complexity: 1+2+...(comparison for nth element)
  n(n-1)/2 = O(n^2)
 OMEGA(n) - Sorted list best case

Sorted | Unsorted
- Maintain sorted list, so move left
- grab unsorted element and put into sorted portion
- double ptr: i, j(end of sorted list)
- array是由尾向头（左）， list则是从dummy head开始比较再插入
相关题：
http://rainykat.blogspot.com/2017/03/leetcode-147-insertion-sort-list.html

➤ Recursion
- 讲解： https://www.youtube.com/watch?v=t4MSwiqfLaY
- ex: factorial
base: just return 1
each step: return n*(n-1)!
     which is return n*factorial(n-1)
                                  - pretend it works, treat like variable

if ( base case 1 )
   // return some simple expression
else if ( base case 2 )
   // return some simple expression
else if ( base case 3 )
   // return some simple expression
else if ( recursive case 1 )
  {
     // some work before 
     // recursive call 
     // some work after 
  }
else if ( recursive case 2 )
  {
     // some work before 
     // recursive call 
     // some work after 
  }
else // recursive case 3
  {
     // some work before 
     // recursive call 
     // some work after 
  }

➤ Backtracking
Hamiltonian cycle -  time O(N!) space O(N) recursion stack
round trip visited every nodes (n edges used to cover n nodes) from a node in graph
X1, X2,X3, ... ,Xn, X1
    [2 -     N]
    (N - 1)! order permutation, dfs try all these possibilities