• 慢的开始，
– 形成交叉的框架
• 熟悉的快一些，
– 节约出时间提高熟练度 – 反复是克服难点的必要手段
• 学习应该涵盖两个方面：
– 内容，方法
• 目录是帮助回忆的
– 素描，轮廓
算法例子，算法类型，对应资源
• 看着目录 • 填表检查 • 回忆算法 • 回忆资源消耗
理解文明？
• 文明是和狭隘，妒忌，仇恨，虚假背离的
• 如果你的同学没成为人才，你如何感想？
– 应感：平等 & －尊重
方法
• 以点带面 • 重点突破 • 张弛有度 • 综合提高 • 循环反复（最多的反复有５次）
• 主动学习，培养主动学习
自我测试
一.填空(１０分）
１、F(n)=n5+n5logn, g(n)=en + nn
5
F(n)= O(n5logn ),
• ３、Ｆ。算法的确定性指给出一个确定的 输入，多次执行结果相同。确定性算法对 问题会产生的结果也可以无解，不一定只 是正确解。
三、应用合适算法
(10’)一个矩阵链乘，M1,M2,M3,M4,M5;顺序 的阶的排列为３，５，７，６，１０，４； 用一个２维表，把最佳的结合方案求出来。
(10’)广东某物流公司，负责粤Ｄ，粤Ｃ，粤 Ｅ，粤Ａ，粤Ｂ间的某种材料配送，市际 配送费用如下表，请选择一个算法，求出 最好的一次配送完Ａ～Ｅ城市的方案。
28
(A,C)
-5
B 0 0 C 0 18
A 1 5 1 B 0 0 0
E
27
0
ABD
C E
9 27
0 0
10
18
ABC D
调配方案：(A,C),(B,A),(E,B),(C,D),(D,E)， ｂｏｕｎｄ=129
四、综合（各１５分）
１、用分治法搜索数组Ａ，规模为ｎ，查找 对象为ｘ是否出现在Ａ中，对Ａ有何要求， 给出算法思想，计算时间费用。
ＡB C D E A 25 24 37 46 B 30 20 28 30 C 28 9 35 19 D 65 15 40 20 E 57 20 30 56
• １、
C[1,1]=0 M1
C[1,2]=105 (M1×M2)
三
C[1,3]=231 C[1,4]=411 M1(M2×M3) (M1(M2×M3))M4
• 文明，我理解，不一定准确，是用科学知 识，科学方法，做有益于大家未来，大家 生活的事，文明需要一种博爱的态度（随 和，理性），和一种严谨的行为方式。
青出于蓝
• 态度
– 欣赏的 – 乐观其成的 – 例如：羽毛球，带过的学生，
• 鼓励，引导主动学习 • 如果你的同学成为人才，你如何感想？
– 应感：荣耀， & －欣赏
g(n)= (nn )
2
２、基于比较的排序算法，最好的算法费时下界为：___(nlogn)_
3、数组Ａ＝{1,2,…,9,10}, 给出二分查找１的搜索树图示_____
1
４、随机算法分为两种，但有共同目的，即_使输入处于随机态，使最坏情形几乎
不出现_____
５、k=logn
nlogn/2 6、
nlogn-n+1
引导回顾
主题列表
总结 复杂度具体计算 贪婪法中最短路，最小生成树 归纳法中例子 动态规划的例子
感谢同学们遵守纪律，参与学习
• 同学们的配合,
– 到课,作业,问答,
• 同学们的实验,
– ３个教学班统一的题目,
• 被鼓励和表扬的同学,
– 榜样
• 没被我表扬的同学,
– 一样优秀, – 低调
提纲帮助有效学习
２、贪婪法能否求出最优解？求解下图的最 小生成树，用Ｐｒｉｍ，Ｋｒｕｓｋａｌ 两种方法，并比较这两个方法的思想。
四、１ 解
１）分治搜索ｘ在ｎ元组Ａ中，要求Ａ有序 ２）取A[Floor(n/2)]比较ｘ，
若A[Floor(n/2)]<ｘ, 取A[Floor(n/2)+1,…,n]做递归输入； 若A[Floor(n/2)]>ｘ, 取A[0,…,Floor(n/2)-1]递归输入; ３）由２）得，T(n)=T(n/2)+1, 若ｎ＝２ｋ，
二、判断下列说法，简述理由或改正
１、由于３ｎ和３n-1的比值极限为非０常数， 且３ｎ－１和３n－２也是如此， … … 所以３ｎ＝（３n-1）
说法错误。 ３ｎ和３n-1的比值恒为３，它们 之间是精确关系，不适用近似表示，而且 表示要求的阶应是n的最简形式，即３ｎ才 可以表示阶的形式。
解二
１、Ｆ。题设有陷阱，3ｎ/3n-1 3, 3ｎ-1/3n 1/3, 根本无需讨论极限， 3ｎ× 1/3 () 3ｎ -1 () 1/3 × 3n, 3ｎ-1 =(3ｎ).
C[1,5]=531 ((M1(M2M3))M4)M5
C[2,2]=0 M2
C[2,3]=210 (M2×M3)
C[2,4]=510 (M2×M3)M4
C[2,5]=548 M2(M3(M4M5))
C[3,3]=0 M3
C[3,4]=420 (M3×M4)
C[3,5]=408 M3(M4M5)
C[4,4]=0 M4
C[4,5]=240 (M4×M5)
C[5,5]=0 M5
三
2.写出矩阵
分ห้องสมุดไป่ตู้界限法
25 24 37 46 24
30 20 28 30 20
28
9
35
19
9
65 15 40 20 15
57
20
30
56
20
-10
-8 -5
1 0 5 17 Bound=111
0 0 0 5
9
0
18
5
40 0 25 0
27
0
10
28
选择与否二叉
(D,E)
(D,E) Bound=116
选择删去其行列
1 0 5 B ound=111 1 0 5 17
不选阻塞其行列
0 0 0
9
0 18
0 0 0 5
9
0
18
5
27
0
10
-5
40 0 25
27
0
10
７、８皇后问题的解空间大小为： __n!____ ８、能够得到最优解的算法方法有： __动态规划，贪心法，分支界限，穷举____
９、２－ｎ， , nn, logn2 ， log2n, n, 2n , n!,按增长速 度非减排序为____ ２－ｎ< logn2 < log2n < n < 2n <n!<nn __
２、
２、快速排序的随机算法虽然最坏时为O(ｎ２) 但是由于有了随机化，使得最坏情形永远 不出现，所以，随机快速排序为最优的。
2、Ｆ。随机算法不能让算法的时间复杂度发 生改变，最坏情形的时间消耗不变，只是 通过随机扰动，让最坏不太可能出现。使 得期望时间消耗比较理想。
３、
• ３、算法如果不能输出正确的解，那一定 是非确定算法。