2算法分析【荐】.pdf

本讲主要内容 • 关于算法 • 排序问题的算法分析 – 插入排序、归并排序 – 分析算法时间效率 • 最坏情形、平均情形 – 算法正确性证明 • 循环不变量 • 算法时间效率的渐进表示 – Ο （Θ 、Ω、о 、ω ） Algorithm • Problem definition 问题 • Objective 目标(very important) • Evaluation 算法评价 • Methods 方法 6 Algorithm evaluation • Quality: – how far away from the optimal solution ? • Cost: –Running time – Space needed • Our goal is to design algorithm with high quality, but in low cost 2/23/2011 7/74 Reasonable times •Poly(|I|), Time polynomial in |I|, where |I| is the size of the problem instance •Input size: size(x) of an instance x with rational data is the total number of bits needed for the binary prepresentation. 2/23/2011 8/74 Hardness of problems Easy 2 3 1000 • Polynomial (e.g. n , n log n, n , n ). 2 7 • Quasi-polynomial(e.g.:n log n, n log n, c log n). • Sub-exponential (e.g.: 2√n, 5(n0.98)). n n n • Exponential (e.g.: 2 , 8 , n!, n ). Hard 2/23/2011 9/74 Running time • Computer A is 100 times faster than computer B • Sort n numbers – Computer A requires 2n2 instructions – Computer B requires 50nlgn instructions • n = 1,000, 000 6 2 9 – Computer A: 2(10 )