早就想把这部视频的笔记总结出来了... 麻省理工的数据结构课

Prablem:sorting

Sorting contains many algorithmic techniques

We have a sequence a1 a2 up to an of number as input

Output is a pernutation, A permutation is a rearrangement of numbers

Such that a1 < a2 … < an

Insertion sort:

Pseudo code:

A[1…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]

J++

A[i] = key

Issue of running time:

Depends on input

Depends on input size

Kind of analysis

Worst case analysis

T(n) = maximum time on any input size n

Average case analysis

T(n) = expected time on any input size

Best case analysis(bogus! No good)

Asymptotic notation

Theta notation θ : drop low order terms and ignore leading constants

EX: 3n3+2n2+55 =θ(n3)

Insertion sort analysis

Worst analysis: T(n) = ∑j to nθ(j) =θ(n2)

Margin sort

Pseudo code:

A[1 … n]

1. if n=1 done (θ(1))

2. recursive sort A[1…(n/2)] and A[(n/2)+1 … n] (2T(n/2))

3.margin two sorted array (θ(n))

Margin sort analysis

Average case:T(n) =θ(n) (linear time)

上一篇:增删索引 下一篇:快递查询API