Algorithm - HsuJv/Note GitHub Wiki
- This is the lecture note to the SMA 5503 (Analysis and Design of Algorithms)
- Course Description
- This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.
- Textbooks: Introduction to Algorithms 3rd Edition
- THOMAS H. CORMEN
- CHARLES E. LEISERSON
- RONALD L. RICEST
- CLIFFORD STEIN
- The analysis of algorithm is the theoretical study of computer program performance and resource usage.
- What's more important than performance?
- Correctness, Security, User-friendliness, etc.
- Performance is like money which is the bedrock that to implement all other counts.
-
Problem Description
- Input: Sequence
$[a_1,\ a_2,\ \ldots,\ a_n]$ of numbers - Output: Permutation
$[a^{'}_1,\ a^{'}_2,\ \ldots,\ a^{'}_n]$ such that$a^{'}_1 \leq a^{'}_2 \leq \ldots \leq a^{'}_n$
- Input: Sequence
-
Pseudocode:
// INSERTION-SORT(A)
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- Running Time
- Depends on the input itself (e.g. already sorted, reverse sorted)
- Depends on the input size (6 elem. vs 6 * 10^9 elem.)
- Parameterize the input size
- Want the upper bounds
- guarantee for the user
- Kinds of analysis
- Worst case (usually)
- T(n) = max time on any input of size n
- Average case (sometimes)
- T(n) = expected time over all inputs of size n
- Need assumption of the statistical distribution of inputs
- Usually uniform distribution
- Best case (bogus)
- Can cheat with slow algorithm
- Worst case (usually)
- Asymptotic Analysis
- Ignore machine-dependent constants
- Look at the growth of the running time
- Notation:
- Θ-notation: drop low order terms and ignore leading constants
- As
$n \rightarrow \infty$ ,$Θ (n^2)$ algorithm always beats$Θ (n^3)$ alg.
- Insertion Sort Analysis
- Worst case: reverse sorted:
-
$T(n) = \sum^{n}_{j=2}Θ(j)=Θ(n^2)$ (Arithmetic series)
-
- For small n, it is moderately fast
- Not at all for large n
- Worst case: reverse sorted:
- Merge sort
$[a_1, \ a_2, \ \ldots, \ a_n]$ - If n = 1, done
- Θ(1)
- Recursively sort
$[a_1,\ \ldots,\ a_{[\frac{n}{2}]}]$ $[ a_{[\frac{n}{2}]+1},\ \ldots,\ a_n]$ $2 T(\frac{n}{2})$
- Merge 2 sorted lists
- Θ(n)
- If n = 1, done
- Key subroutine: Merge
- Time: Θ(n) on n total elems (linear time)
- Recurrence
- $T(n)=\begin{cases}Θ(1)&,n=1\\ 2T(\frac{n}{2})+Θ(n)&,n \geq 2\end{cases}$
- Big O notation
O: $ f(n) = O(g(n)) $- Defination: there are consts $ c > 0 $ and $ n_0 > 0 $, such then $ 0 \leq f(n) \leq c \cdot g(n) $ for all $ n \geq n_0 $
- More intuitive notion: assume that f(n) is non-negative, and is to be bounded above by g(n)
- Example: $ 2n^2 = O(n^3) $
- Note: it is asymmetric