introduction_to_algorithms_lecture_1

发表于

网易公开课《算法导论》的学习笔记，第一节课

先贴上一段Charles Leiserson教授的话。

why_learn_algorithm_1

why_learn_algorithm_2

why_learn_algorithm_3

why_learn_algorithm_4

why_learn_algorithm_5

进入正题，先讲了一下插入排序(Insertion Sorts)。

Problem:sorting

Input: sequence < a1, a2 ,…, an > of numbers
Output: permutation <a’1, a’2 ,…, a’n>, such that a’1 <= a’2 <= a’3 … <= a’n

Insertion Sort.

1
2
3
4
5
6
7
8
9
10
11
//Pseudocode

Insertion Sort(A, n)	//Sorts 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]
				i <- i-1
		A[i+1] <- key

算法分析，见下图。

insertion sort

数组A，1～j-1是已经排好序的，现将j插入到已经排好序的数组中。令j的值为key，分别与j-1,j-2,j-3,…比较，直到找到合适的位置，插入。
后面的Example演示了这一过程。

Running time:

1
2
3
4
5
Depends on input(eg. already sorted)
Depends on input size(6 elements vs 6*10^9)
	-parameterize in input size
want upper bound
	-guarantee to user

Kinds of analysis

1
2
3
4
5
6
7
8
9
Worst-case(usually)
T(n) = max time in any input of size n

Average-case(sometimes)
T(n) = expected time over all inputs of size n
(Need assumption of Statistics Distribution)

Best-case(bogus)
Cheat

What is insertion sort’s worst-case time?

1
2
3
4
5
6
7
Depends on computer
	-relative speed(on same machine)
	-absolute speed(on diff machine)

BIG IDEA! Asymptotic analysis
1.Ignore machine dependent constants
2.Look at growth of T(n) as n -> infinite

Asympototic notation

1
2
3
4
5
6
theta-notation: 
	Drop low-order terms
	Ignore leading constants

Ex. 3n^3+90n^2-5n+6046=theta(n^3)			
As n -> infinite, theta(n^2) alg always beats a theta(n^3) alg.even theta(n^2) runs on a slow machine.

ps:theta equals to $$\theta$$

一张图来对比。
photo_vs_theta

Insertion sort analysis

Worst-case:input reverse sorted

$$T\left( n\right) =\sum _{j=2}^{n}\Theta \left( j\right) = \Theta\left( n^{2}\right)$$

(Arithmetic series)

Is insertion sort fast?

1
2
-moderately for small n
-Not at all for large n

Merge sort

1
2
3
4
5
Merge sort A[1,...n]	--------T(n)
1.If n = 1, done			--------theta(1),abuse
2.Recursively sort		--------2*T(n),sloppy
	A[1,...ceil[n/2]] and A[ceil[n/2]+1,...n]
3.Merge 2 sorted arrays

Key subroutine: Merge
Key subroutine: Merge

两个已经排好序的数组。分别有两个指针指向首元素，比较大小，小的就提取出来，然后指针指向后一位。时间与两个数组之和成正比。

Recursive

T(n) = theta(1), if n = 1 (use omit)
2T(n/2) + theta(n), if n > 1

Recursive tree. T(n) = 2T(n/2) + cn, const c > 0

Performance

merge sort performance
树的长度lg(n)，叶子个数n。
最后得出mergesort的时间 theta(nlgn)。