算法排序：input：sequence 《a1,a2,a3…..an》output: permutation 《a11,a22,a33,..ann》$ a110
?insertion sort
Insertioon-Sort(A,n) //Sorts A[1..n]? ? peusocode
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
EX:[8,2,4,9,3,6]
start j = 2;
…..
[2,3,4,6,8,9]
Running time
—depends on input (e.g. already sorted)
—depends on input size (6 elem vs 6*10^9)
—parameter in input size
—Want upper bounds
Kinds of analysis
Worst -case(usually)
T(n) = max time on any input of size n
Average-case(sometimes)
T(n)=expected time overall input of size n
(Need assumption of stat distribution——equal )
Best-case(bogus)
Worst -case
—relative speed
—absolute speed
Big Idea? Asymptotic analysis
1.Ignore machine dependent
2.Look at growth of T(n) as n->oo
Asymptotic notation
Big O (theta notation) Drop low order terms Ignore leading constants
EX:3n^3 + 90 n^2-5n + 6046=Theta(n^3)
Insertion sort analysis
Worst -case: input reverse sorted
T(n)=qiuhe (j <—2–n)O(j) = O(n^2)
Is Insertion fast?? Not for large n
Merge sort
Merge sort A[1..n]? ? T(n)
1.if n = 1 ,done? ? //Theta(1)
2.Recursive sort? //2T(n/2)
A[1..n/2] and A[n/2+1…n]
3.Merge 2 sorted list? //Theta(n)
Key subroutine? Merge
Time = Theta(n) Linear time
Recurrence
T(n) ={ theta(1) if n=1;? 2T(n/2)+O(n) if n >1}
Recursion Tree T(n) = 2T(n/2)+c*n (c>0)
T(n) = cn? =? ? ? ? ? ? ? ? ? cn =……? =? ? ? ? cn? ? cn
/? ? \? ? ? ? ? ? ? ? ? /? ? ? \? ? ? ? ? ? ? ? ? ? ? ….? ? cn
T(n/2) T(n/2)? ? cn/2? ? cn/2? ? ? ? ? ? O(1)? ? O(n)
/? ? \? ? ? ? /? ? \
T(n/4) T(n/4) T(n/4) T(n/4)
Height of the tree is lg(n)? leaves = n
Total = cn * lg(n) + O(n)= O(n*lg(n))
bounds is 30
