算法分析

Insertion sort...A[1,2,...,n]

for j <- 2 to n

i <- j - 1

key <- A[j]

while i > 0 and key > A[i]

A[i+1] <-A[i]

i <- i - 1

A[i+1] <- key

Running time:

Depends on input(e.g. already sorted)

Depends on input size

parameterize things in the input, time = f(input), so the time is a function of input

We want the time upper bonds

guarentee to the user

Kinds of analysis:

Worst-case(usually)

T(n) = max time on any input of size n

Depends on computer

relative speed(on same machine)

absolute speed(on different machine)

Average-case(sometimes)

T(n) = expected time over all inputs of size n, need assumption of standard distribution

Best-case(bogus)

BIG IDEA - asymptotic analysis

Ignore machine-dependent constants

look at the growth of T(n) as n->infinity

Asymptotic notation

theta notation, drop low order terms and ignore leading constant

E.g. 3n³ +9n² -50n+23 = θ(n³ )

Insertion sort analysis

worst-case input: reverse sorted

T(n) = sum[j from 2 to n] ( θ(j) ) = θ(n² )

Merge sort analysis

Important subroutine: merge. T(n') = θ(n')

analysis recursion as tree. recurse for lg(n) times.

so total time consuming T(n) = θ(nlgn)