本文由mysky_2012贡献
南开大学信息技术科学学院
杨巨峰
Webster词典
? 算法即在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复。更广义地说，一个算法就是为解一个问题或实现某一目标的逐步过程
D.E.Knuth
? 算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。此外，他还应具有如下五个重要特性
有穷性确定性输入输出能行性《计算机程序设计艺术》
2
1. 2. 3. 4.
算法评估与分析 MAXMIN问题排序问题字符串匹配
3
4
正确性
? 原则上应该证明算法对于任意合理的输入都正确 ? 实际中常用推理法证明
时间代价
? 必须抛弃的评价指标
算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数
空间代价最优性
5
是指算法运行中起主要作用且花费最多时间的操作
? 两个实数矩阵的乘法问题中，矩阵的实数元素之间的数乘 ? 对N个整数进行排序的算法中，整数间的比较和交换
引入基本操作的概念，用其执行次数来度量算法的时间代价，是算法分析的基础
6
算法的运行时间代价除了与算法本身的基本操作数有关外，还与问题实例的长度有关，即受输入规模影响
? ? ? ? 排序问题：待排序元素序列的长度n 矩阵乘积：n阶方阵的阶数n 图问题：图的顶点数n和边数m 字符串匹配问题：文本T的长度n
T(n)
? 算法的时间复杂度，用问题实例长度的函数表示 ? 也就是用该算法用于问题长度为n的实例所需要的基本操作次数来刻画
7
如果解决问题P的算法A和算法B，其时间复杂度分别是TA(n)和TB(n)，则判断A、B性能优劣的标准是查看在n足够大时TA(n)和TB(n)的大小关系
8
对于同一算法，如果有相同的问题长度，但采用不同的输入，其时间代价一般也不同。因此在实际的算法分析中，复杂度函数值T(n)不是唯一的设Dn为问题P的所有长度为n的实例集合，输入实例I∈Dn，t(I)是用来解决问题P的算法A在以I为输入时的执行代价（基本操作数），则算法A的最坏情形时间复杂度和最好情形时间复杂度定义如下
W (n) = MAX {t ( I )}
I ∈D n
B(n) = MIN{t ( I )}
I ∈D n
一般地，T (n) = W (n)
9
InsertSort
void InsertSort(int A[], int n) { for(int i=2;i<=n;i++) { int V = A[i]; int j=i-1; while((A[j]>V)&;&;(j>0)) { A[j+1]=A[j]; j=j-1; 1 2 3 4 5 6 7 8 9 10 } 10 9 8 7 6 5 4 3 2 1 A[j+1]=V; 3 7 4 5 10 2 9 6 1 8 return; } }
9次比较 45次比较？次比较
10
许多实际问题的可能实例集是一个极大的集合，即使把问题长度限定为n，实例集Dn依然很大。其中使算法A耗费最大代价W(n)的实例往往只占很小的一部分，而大多数实例耗费的代价常常远小于W(n),因此转而使用期望复杂度或称平均情形复杂度评价算法性能
A(n) =
I ∈D n
∑ P( I )t ( I )
11
解析表达式阶表达式
? O ? ? ? θ
多项式函数和指数函数
12
形式化定义
? 称复杂度函数T(n)是O(f(n))，即T(n)=O(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)<=cf(n),例如：
T1(n)=(n+1)/2=O(n) c=1,n0=1 T2(n)=3n2+4n+5=O(n2) c=10,n0=2
? T1(n)=O(n2)和T2(n)=O(n3) 也是对的
13
形式化定义
? 称复杂度函数T(n)是?(f(n))的，即T(n)=?(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)>=cf(n)，例如：
T1(n)=(n+1)/2=?(n) c=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c=3,n0=1
? T1(n)=O(1)和T2(n)=O(n) 也是对的
14
形式化定义
? 称复杂度函数T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常数c1>0,c2>0与n0，当n>n0时有 c1f(n)>=T(n)>=c2f(n)，例如：
T1(n)=(n+1)/2=?(n) c1=1,c2=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c1=10,c2=3,n0=2
? 显然如果T(n)=O(f(n))而且T(n)=?(f(n))，则容易得到 T(n)=θ(f(n))
15
类型 1 logn n nlogn n2 n3 2n n!
名称常量对数线性 n-log-n 平方立方指数阶乘
说明效率最高，但是很少有算法达到算法的每一次循环都会消除问题规模的一个常数因子。一个对数算法不可能关注输入的每一个部分扫描规模为n的列表分治算法两重嵌套循环三重嵌套循环
16
下列等式哪些是正确的？哪些是错误的？
A. B. C. D. n(n+1)/2=O(n3) n(n+1)/2=O(n2) n(n+1)/2=θ(n3) n(n+1)/2=?(n)
17
18
题目
? 求n元中的最大元MAX(n)和最小元MIN(n)
学习目的
? 理解算法的评价方法 ? 体会算法设计及算法改进
19
void MAXMIN1(int L[], int n){ int MAX = L[1], j; for(int i=2;i<=n;i++){ if(MAX
算法讨论：算法讨论： 1.算法是正确的； 2.以元素之间的比较为基本操作，则求 MAX的代价是n-1，求MIN的代价是n-2 ，故总时间是2n-3 3.算法的代价只与L的长度n有关，而与L 的具体元素没有关系，故 T(n)=W(n)=A(n)=2n-3，亦可记为 T(n)=O(n)或T(n)=θ(n) 4.空间消耗除了L之外只需几个单元 S(n)=O(1) 算法思考：算法思考：从n元中求最大元用n-1次比较是最优的，从剩下的n-1元中求最小元用n-2次比较也是最优的，但是把二
者结合起来用 2n-3次比较求最大元和最小元是否是最优的呢？
20
void MAXMIN2(int L[], int n){ int MAX=L[1], MIN=L[1]; for(int i=2;i<=n;i++){ if(MAX
算法讨论：算法讨论： 1.把MAX和MIN放在一起处理； 2.算法总时间是2n-2，所以从效率上来说没有任何改进算法思考：算法思考：从算法结构可以很容易的看到其不合理的地方：如果MAX
21
void MAXMIN(int L[], int n){ int MAX=L[1], MIN=L[1]; for(int i=2;i<=n;i++){ if(MAX
算法讨论：算法讨论： 1.算法的时间代价与L[1…n]的内容有关： L[1…n] 为递增序列，需要n-1次比较， L[1…n] 为递减序列，需要2n-2次比较； 2.显然最好情形B(n)=n-1，最坏情形 W(n)=2n-2，平均情形时间复杂度A(n)难以计算，但估计应该介于二者之间，且有 A(n)<2n-3
22
void MAXMIN(int L[], int n, int M1, int M2){ if(n==2){ if(L[1]>L[2]){ 算法讨论：算法讨论： M1=L[1];M2=L[2]; 1.算法是针对n=2k设计的，同时可以 } 扩展到n为一般正整数的情况；else{ 2.算法的时间代价与L[1…n]的内容无M1=L[2];M2=L[1]; 关，T(n)=1.5n-2比较原来有较大改进 } 3.基本思想是每一次比较都有助于求 } 最大元和最小元 else{ T (n) = T (n / 2) + T (n / 2) + 2 Divide L into L1 and L2; = 2(2T (n / 4) + 2) + 2 MAXMIN(L1,n/2,M11,M21); k ?1 k ?1 MAXMIN(L2,n/2,M12,M22); = 2 T ( 2) + 2 i M1=MAX(M11,M12); i =1 M2=MIN(M21,M22); = 2 k ?1 + 2 k ? 2 } 3n } = ?2
∑
2
23
24
排序
? ? ? ? ? 是人们对数据集合最常用的基本操作之一通讯录或电话本中记录一般按照人名的字典顺序排列打牌时按牌色和点数排列体育比赛的获奖情况按实际成绩排序所有计算机工作中，排序占25%以上
25
全序集
? 两个元素一定存在大小关系并且具有传递性
排序问题
? n项纪录的集合R，其中一个域是关键字Key属于全序集，利用Key的顺序对R重新排列稳定排序算法
? 相同大小的元素不被交换的算法
内部排序算法外部排序算法原址排序算法
? 占用有限额外空间或者说额外空间与n无关
26
思想
? 开始的时候，扫描整个列表，找到它的最小元素然后和第一个元素交换，将最小元素放到它在有序表中的最终位置上 ? 然后从第二个元素开始扫描列表，找到最后n-1个元素中的最小元素，再和第二个元素交换位置，把第二小的元素放在它的最终位置上 ? 一般来说，在对列表做第i遍扫描的时候，该算法在最后 n-i个元素中寻找最小元素，然后拿它和Ai 交换 ? 在n-1遍以后，列表排好
A0 ≤ A1 ≤ ? Ai ?1 | Ai ,? Amin ,? , An ?1
27
for i 0 to n-2 do min i for j i+1 to n-1 do if A[j] 45 45 29 | 29 29 29 29 68 68 68 34 | 34 34 34 90 90 90 90 45 | 45 45 29 29 45 45 90 68 | 68 34 34 34 68 68 90 89 | 17 89 89 89 89 89 90 令比较操作为关键操作，则选择排序算法的时间消耗是： T ( n) = ∑ n ? 2 n ?1 i = 0 j =i +1 ∑1 = ∑ [(n ? 1) ? (i + 1) + 1] = ∑ (n ? 1 ? i) = i =0 i =0 n?2 n?2 n(n ? 1) = O(n 2 ) 2 28 利用选择排序算法对序列{2,8,5,1,6,4,3,9,7,0}进行排序，写出执行的过程 29 思想 ? 比较表中的相邻元素，如果它们是逆序的话就交换它们的位置 ? 重复多次以后，最小的元素就像气泡一样升到了列表的第一个位置 ? 第二遍操作将第二小的元素升起来 ? 这样一直做，直到n-1遍以后，该列表就排好序了 A0 ≤ A1 ≤ ? Ai ?1 | Ai ,? A j ?1 ? A j ?, An ?1 30 ? for(i=0;i List[j-1] = List[j]; List[j] = temp; 89 89 89 89 89 89 17 | 17 | 17 | 17 | 17 | 17 45 45 45 45 45 17 89 89 89 89 89 29 | 68 90 29 68 90 29 68 90 17 68 17 90 17 68 90 45 68 90 45 68 90 45 45 45 29 89 68 68 29 45 45 90 29 68 68 68 34 17 17 34 29 34 29 34 29 34 29 34 29 34 29 90 90 90 90 34 34 34 34 34 T ( n) = O ( n 2 ) …… 31 int p=1; for(i=0;i 2 3 1 | 2 4 3 5 4 6 5 7 6 8 7 9 8 1 9 32 思想 ? 与选择排序不同，插入排序是从列表的无序部分不经选择任取一元，然后插入到有序部分的正确位置上。类似于玩家整理手中的扑克牌 ? i=1 ? 把L[i+1]插入到L[1…i]中的正确位置，i++ L[i+1] L[1…i] i++ ? if(i A0 ≤ ? A j < A j +1 ≤ ? Ai ?1 | Ai ? An ?1 33 for i 1 to n-1 do v A[i] j i-1 while j>=0 and A[j]>v do A[j+1] A[j] j j-1 A[j+1] v 89 | 45 68 90 29 34 17 45 89 | 68 90 29 34 17 45 68 89 | 90 29 34 17 45 68 89 90 | 29 34 17 45 68 89 90 90 34 17 45 68 89 89 90 34 17 45 68 68 89 90 34 17 45 45 68 89 90 34 17 29 45 68 89 90 | 34 17 29 34 45 68 89 90 | 17 17 29 34 45 68 89 90 因为内层循环的次数不定，所以： n2 T ( n) ≈ = O(n 2 ) 4 34 思想 ? 按照元素的值进行划分 ? 对给定数组中的元素进行重新排列，以得到一个快速排序的分区 ? 在一个分区中，所有在s下标之前的元素都小于等于A[s]， s A[s] 所有在s下标之后的元素都大于等于A[s] s A[s] ? 建立了一个分区以后，A[s]已经位于它在有序数组中的最终位置。接下来使用同样的方法继续对A[s]前和A[s]后的子数组分别进行排序 A[0]? A[ s ? 1] A[ s] A[ s + 1]? A[n ? 1] 都小于等于A[ s ] 都大于等于A[ s ] 35 //Quicksort[A[l…r]] //input:数组A[0…n-1]中的子数组A[l…r] //output:排序后的数组 if l 算法的前提是选择一个元素，根据该元素的值来划分子数组，这个元素就是中轴，我们暂时选择数组的第一个元素作为中轴，即p=A[l] T (n) = O(n log 2 n) 36 思想 ? 为了建立一个分区，有许多不同的方法对元素重新排列，其中一种是基于两次扫描子数组的高效算法 ? 一次是从左到右，另一次是从右到左，每次都把子数组的元素和中轴进行比较 ? 从左到右的扫描（i）从第二个元素开始，因为我们希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止 ? 从右到左的扫描（j）从最后一个元素开始，扫描忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止 ? 两次扫描停止后，取决于扫描的指针是否相交，会发生3种不同的情况 37 描述 ? 如果扫描指针i和j不相交，也就是说i 示意 38 描述 ? 如果扫描指针相交，也就是说i>j，把中轴和A[j]交换 示意 39 描述 ? 如果指针停下来时指向的是同一个元素，也就是说i=j，被指向元素的值一定等于p，此时建立的分区中分裂点的位置S=i=j 示意 40 p A[l] i l,j r+1 repeat repeat i i+1 until A[i]>=p repeat j j-1 until A[j]<=p swap(A[i],A[j]) until i>=j swap(A[i],A[j]) swap(A[l],A[j]) return j 算法合并了情况二和情况三，即当i=j 时也做了一次无谓的交换 i可能越界而j不可能越界，因此实现时需要对i进行特殊处理 41 南开大学信息技术科学学院 第 42 页 发明 ? ? ? ? 英国计算机科学家Hoare 图灵奖得主爵士爵位“我是非常幸运的，以发明一种新的排序方法开始一个人的计算机职业生涯实在是太美妙了” 改进 ? 随机数、两平均、三平均中轴选择算法 ? 当子数组足够小时改用最简单的排序算法 ? 综合运用这些措施，可缩减20%时间 43 思想 ? 对于一个需要排序的数组A[0…n-1]，把它一分为二： A[0…n/2-1]和A[n/2…n-1]，并对每个子数组递归排序 ? 然后把这两个排好序的子数组合并为一个有序数组 44 //Mergesort if n>1 copy A[0…n/2-1] to B[0…n/2-1] copy A[n/2…n-1] to C[0…n/2-1] Mergesort(B[0…n/2-1]) Mergesort(C[0…n/2-1]) Merge(B,C,A) 时间代价较小，空间消耗较多 T (n) = O(n log 2 n) 45 思想 ? 对两个有序数组的合并 ? 初始状态下，关注两个待合并数组的第一个元素 ? 然后比较这两个元素的大小，将较小的元素添加到一个新创建的数组中 ? 接着被复制数组中的下标后移，指向该较小元素的后继元素 ? 上述操作一直持续到两个数组中的一个被处理完为止 ? 然后在未处理完的数组中，剩下的元素被复制到新数组的尾部 46 //Merge(B[0…p-1],C[0…q-1],A[0…p+q-1]) i 0,j 0,k 0 while i 47 48 49 描述 ? 在文本处理系统、操作系统、编译系统、数据库系统和 Internet信息检索系统中，字符串匹配是使用最频繁的操作 ? 算法复杂度一般不高，但是： ? 问题长度n很大，常常需要在大量信息中进行搜索，因此 n 算法的一次执行时间不容忽视 ? 搜索操作经常被调用，执行频率很高，因此算法的累积消耗和算法改进的累积效果同样不容忽视 50 字符串（String） ? 由字符集∑中的字符组成的序列 ? ∑={0,1}，01100011是一个二进制字符串 ? ∑={a,b,c,…,z}，bryant是一个英语字符串 文本（Text） ? 一个n长字符串 样本（Pattern） ? 一个m长字符串，一般m 匹配（Match） ? 两个字符串的字符对应相同 51 定义 ? 如果0<=s<=n-m，并且T[s+1…s+m]=P[1…m]（即对1<=j<=m，有T[s+j]=P[j]），则说模式P在文本T中出现且位移为s。或者等价的说，模式P在文本T中从位置 s+1开始出现 ? 如果P在T中出现且位移为s，称s是一个有效位移 ? 否则s是无效位移 s ? 字符串匹配问题实际上是在一段指定的文本中，找出某指定模式P出现的所有有效位移的问题 52 ∑* ? 用字母表∑中的字符形成的所有有限长度字符串的集合 ε ? 长度为0的空字符串，显然ε∈∑* |x| ? 字符串x的长度 xy ? 两个字符串x和y的连接 53 w［x ? 如果x=wy，就说字符串w是字符串x的前缀 ? |w|<=|x| w］x ? 如果x=yw，就说字符串w是字符串x的后缀 ? |w|<=|x| 显然 ? 空串是每个字符串的前缀，也是每个字符串的后缀 ? 对于任意字符串x和y以及任意字符a，x ］y当且仅当xa ］ ya 54 假设x，y和z是满足x ］z和y ］z的三个字符串 ? ? ? ? 如果|x|<=|y|，则x ］y 如果|x|>=|y|，则y ］x 如果|x|=|y|，则x=y 可用图形 法证明 55 Pk ? 模式P[1…m]的由k个字符组成的前缀P[1…k] Tk ? 文本T的由k个字符组成的前缀 字符串匹配问题 ? 找出范围为0<=s<=n-m并满足P ］Ts+m的所有位移 约定 ? 把比较两个等长的字符串是否相等的操作当作原语操作 56 思想 ? 用一个循环来找出所有有效位移，该循环对n-m+1个可能的每一个s值检查条件P[1…m]=T[s+1…s+m] 描述 NA?VE-STRING-MATCHER（T，P） n length[T] m length[P] for s 0 to n-m do if P[1…m]=T[s+1…s+m] then print ”Pattern occurs with shift” s 示例 ? T=acaabc，P=aab 57 思想 ? 由于串匹配问题的特征，样本P[1…m]在文本T[1…n]上进行两次相邻匹配操作时，进行比较的对象T[i-1…i+m-2] 和T[i…i+m-1]有m-1个字符相同，因此从T[i-1]开始的匹配比较结果可能决定了P[1…m]从T[i]开始的匹配操作是否必要 示例 ? T[1…9]=ABABABCAC，P[1…5]=ABABC。从T[1]=A开始的匹配操作结果是P[1…4]=T[1…4]，但P[5]!=T[5]，因此P应该右移 ? 由于P[1…3]=ABA和P[2…4]=T[2…4]=BAB是不相等的，因此从T[2]开始的匹配肯定失败，所以样本P不必右移一位，至少可以右移两位 58 原则 ? 一般情况下，P在文本T的某一位置匹配失败后，它可以向右移动的位数只与样本P本身以及匹配失败的字符位置j有关 ? 样本P能向右直接移动的距离，可以根据样本P的字符组成计算出来 59 思想 ? P[1…m]移动到文本T的某一位置进行匹配时，假设前j-1 个字符相等，第j个字符不等，因而匹配失败 ? 计算Next(j)等于字符串P[1…j-1]从两端计算的最大可匹配的长度再加上1 ? 令样本P[1…m]右移△=j-Next(j)位，匹配比较从 P[1…m] =j-Next(j) P[Next(j)]开始 ? 绘制图形说明上述思想 60 j P[j] Next(j) 1 a 0 2 b 1 3 a 1 4 b 2 5 a ? 6 b ? 7 a ? 8 b ? 9 c ? 10 a ? Next(j) 1 1 2 3 4 5 6 7 1 61 void Next(char P[], int m, int&; Next[]){ int i,j; Next[1]=0; for(j=2;j<=m;j++){ i=Next[j-1]; while(i>0&;&;P[i]!=P[j-1]) i=Next[i]; Next[j]=i+1; } return; } 62 void KMP int i=1,j=1; while(i<=n-m+1){ while(j>0&;&;P[j]!=T[i]) j=Next[j]; if(j==m){ cout< 63 在算法的若干评价指标中，时间代价是最被关注的一种排序和字符串匹配是两种应用范围特别广泛的问题，相应的研究也特别多，产生了许多经典算法 64 练习所学的五种排序算法 ? 对下述序列{52,41,30,35,18,27,9,20,10,16,8,12}进行排序 ? 绘制其简要的中间数据 流图并比较其繁简程度 计算下面每个样本P的next和delta函数值 ? ? ? ? aaaaa aaaab ABABCBABA AABAACAABABA 65 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1 Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1 Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1 Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i] Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1 Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v) 多线程算法（完整版） ——算法导论 第3版新增第27章 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Ste in 邓辉译 原文：https://www.doczj.com/doc/d87765765.html,/sites/products/documentation/cilk/boo k_chapter.pdf 本书中的主要算法都是顺序算法，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。 并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些 PC 级的电脑）组成的集群，通过专用的网络连 接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。 多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。 对于片上多处理器和其他共享内存并行计算机来说，使用静态线程是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。 遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。 Partial Solutions for Introduction to algorithms second edition Professor: Song You TA: Shao Wen ACKNOWLEDGEMENT CLASS ONE: JINZI CLASS TWO: LIUHAO, SONGDINMIN, SUNBOSHAN, SUNYANG CLASS FOUR:DONGYANHAO, FANSHENGBO, LULU, XIAODONG, CLASS FIVE:GAOCHEN, WANGXIAOCHUAN, LIUZHENHUA, WANGJIAN, YINGYING CLASS SIX: ZHANGZHAOYU, XUXIAOPENG, PENGYUN, HOULAN CLASS: LIKANG,JIANGZHOU, ANONYMITY The collator of this Answer Set, SHAOWen, takes absolutely no responsibility for the contents. This is merely a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the solutions are wrong. If you have found an error, have a better solution or wish to contribute in some constructive way please send an Email to shao_wen_buaa@https://www.doczj.com/doc/d87765765.html, It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Have fun with your algorithms and get a satisfactory result in this course. Best regards, SHAOWen Chapter19 Michelle Bodnar,Andrew Lohr April12,2016 Exercise19.2-1 First,we take the subtrees rooted at24,17,and23and add them to the root list.Then,we set H.min to18.Then,we run consolidate.First this has its degree2set to the subtree rooted at18.Then the degree1is the subtree rooted at38.Then,we get a repeated subtree of degree2when we consider the one rooted at24.So,we make it a subheap by placing the24node under18. Then,we consider the heap rooted at17.This is a repeat for heaps of degree1, so we place the heap rooted https://www.doczj.com/doc/d87765765.html,stly we consider the heap rooted at23,and then we have that all the di?erent heaps have distinct degrees and are done,setting H.min to the smallest,that is,the one rooted at17. The three heaps that we end up with in our root list are: 23 17 38 30 41 and 1 Chapter10 Michelle Bodnar,Andrew Lohr April12,2016 Exercise10.1-1 4 41 413 41 418 41 Exercise10.1-2 We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R. Algorithm1PUSH(S,x) 1:if S==T then 2:if T.top+1==R.top then 3:error“over?ow” 4:else 5:T.top=T.top+1 6:T[T.top]=x 7:end if 8:end if 9:if S==R then 10:if R.top?1==T.top then 11:error“over?ow” 12:else 13:R.top=R.top?1 14:T[T.top]=x 15:end if 16:end if 1 Algorithm2POP(S) if S==T then if T.top==0then error“under?ow” else T.top=T.top?1. return T[T.top+1] end if end if if S==R then if R.top==n+1then error“under?ow” else R.top=R.top+1. return R[R.top?1] end if end if Exercise10.1-3 4 41 413 13 138 38 Exercise10.1-4 Algorithm3ENQUEUE if Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow” end if Q[Q.tail]=x if Q.tail==Q.length then Q.tail=1 else Q.tail=Q.head+1 end if Exercise10.1-5 As in the example code given in the section,we will neglect to check for over?ow and under?ow errors. 2 实验一常见排序算法的实现与性能比较 一、实验环境 操作系统：Windows XP操作系统 编程语言：C语言 开发工具：Microsoft Visual C++ 6.0 二、问题描述 实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 三、实验要求 A．在随机产生的空间大小分别为 N = 10， 1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。 B．结果输出: 1） N=10时，排序结果。 2） N=1000，10000，100000时，对同一个样本实例，不同排序完 成所需的时间。 3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。 四、各种排序算法的原理及算法语言描述 （1）合并排序算法 1）合并排序的原理： 采用分治法。分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。 2）合并排序算法语言描述： void Merge(float A[],int p,int q,int r){ int n1,n2,i,j,k; float L[10],R[10]; n1=q-p+1; n2=r-q; for(i=1;i<=n1;i++){ L[i]=A[p+i-1]; } for(j=1;j<=n2;j++){ R[j]=A[q+j]; } L[n1+1]=MAX; R[n2+1]=MAX; i=1; j=1; 1 算法导论第三次习题课 2008.12.17 2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略 3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点] 4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j; 5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i 6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ Chapter17 Michelle Bodnar,Andrew Lohr April12,2016 Exercise17.1-1 It woudn’t because we could make an arbitrary sequence of MULT IP USH(k),MULT IP OP(k). The cost of each will beΘ(k),so the average runtime of each will beΘ(k)not O(1). Exercise17.1-2 Suppose the input is a1followed by k?1zeros.If we call DECREMENT we must change k entries.If we then call INCREMENT on this it reverses these k changes.Thus,by calling them alternately n times,the total time isΘ(nk). Exercise17.1-3 Note that this setup is similar to the dynamic tables discussed in section 17.4.Let n be arbitrary,and have the cost of operation i be c(i).Then, n i=1c(i)= lg(n) i=1 2i+ i≤n not a power of2 1≤ lg(n) i=1 2i+n=21+ lg(n) ?1+n≤4n?1+n≤5n∈O(n) So,since to?nd the average,we divide by n,the average runtime of each com-mand is O(1). Exercise17.2-1 To every stack operation,we charge twice.First we charge the actual cost of the stack operation.Second we charge the cost of copying an element later on.Since we have the size of the stack never exceed k,and there are always k operations between backups,we always overpay by at least enough.So,the ammortized cost of the operation is constant.So,the cost of the n operation is O(n). Exercise17.2-2 1 Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1 Chapter1 Michelle Bodnar,Andrew Lohr April12,2016 Exercise1.1-1 An example of a real world situation that would require sorting would be if you wanted to keep track of a bunch of people’s?le folders and be able to look up a given name quickly.A convex hull might be needed if you needed to secure a wildlife sanctuary with fencing and had to contain a bunch of speci?c nesting locations. Exercise1.1-2 One might measure memory usage of an algorithm,or number of people required to carry out a single task. Exercise1.1-3 An array.It has the limitation of requiring a lot of copying when re-sizing, inserting,and removing elements. Exercise1.1-4 They are similar since both problems can be modeled by a graph with weighted edges and involve minimizing distance,or weight,of a walk on the graph.They are di?erent because the shortest path problem considers only two vertices,whereas the traveling salesman problem considers minimizing the weight of a path that must include many vertices and end where it began. Exercise1.1-5 If you were for example keeping track of terror watch suspects,it would be unacceptable to have it occasionally bringing up a wrong decision as to whether a person is on the list or not.It would be?ne to only have an approximate solution to the shortest route on which to drive,an extra little bit of driving is not that bad. 1算法导论第二章答案
算法导论 第三版 第21章 答案 英
算法导论 第三版 第六章 答案 英
算法导论 第三版 第七章 答案 英
算法导论 第三版 第二章 答案 英
算法导论 第三版 第24章 答案 英
算法导论第三版新增27章中文版
算法导论 课后题答案
算法导论 第三版 第十九章 答案 英
Ch10算法导论 第三版 第十章 答案 英
中科大算法导论实验报告
《算法导论2版》课后答案_加强版2
算法导论 第三版 第十七章 答案 英
算法导论 第三版 第35章 答案 英
算法导论 第三版 第一章 答案 英
相关主题
文本预览