算法导论复习资料

算法导论复习资料一、选择题：第一章的概念、术语。

二、考点分析：1、复杂度的渐进表示，复杂度分析。

2、正确性证明。

考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，©，替换法证明，先猜想，然后给出递归方程）。

循环不变性的三个性质：1）初始化：它在循环的第一轮迭代开始之前，应该是正确的；2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。

插入排序算法：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 - 15 while i > 0 and A[i] > key6 do A[i + 1] ←A[i]7 i ←i - 18 A[i + 1] ←key插入排序的正确性证明：课本11页。

归并排序算法：课本17页及19页。

归并排序的正确性分析：课本20页。

3、分治法（基本步骤，复杂度分析）。

——许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。

（解：共有24种状态，至少称重3次可以找出不同的球）不是考点：线性时间选择，最接近点对，斯特拉算法求解。

解：基本步骤：一、分解：将原问题分解成一系列的子问题；二、解决：递归地解各子问题。

若子问题足够小，则直接求解；三、合并：将子问题的结果合并成原问题的解。

复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式T(n)=Q(1) n<=cT(n)=aT(n/b)+D(n)+C(n) n>c附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

算法导论-9.红⿊树习题这⼀篇解决《算法导论》中红⿊树章节的部分习题，在上⼀篇⾃⼰亲⾃实现红⿊树后，解决这些题⽬就轻松多了。

练习13.1-6 在⼀棵⿊⾼度为 $k$ 的红⿊树中，内节点最多有多少个？最少有多少个？⿊⾼度为 $k$ 的⼆叉树，全⾼度最⼩为 $k+1$，最⼤为 $2k+2$ 。

内节点最多有 $2^{k+1}-1$ 个，这种情况下红⿊树中没有红节点，⿊节点全满（满⾜所有叶⼦节点⿊⾼度⼀致的条件）；内节点最多有 $2^{2k+2}-1=4^{k+1}-1$ 个。

这种情况下红⿊树全满。

练习13.1-7 在 $n$ 个关键字上构造出来的⼆叉树，红节点与⿊节点个数的⽐值最⼤为多少？最⼩是多少？红节点最多时，⽐值为：$$\frac{n-2^{h-1}-2^{h-3}-...-(2)-1}{2^{h-1}+2^{h-3}+...+(2)+1},h=\lfloor\lg n\rfloor$$红节点最少时，⽐值时为：$$\frac{n-2^{\lfloor\lg n\rfloor}}{2^{\lfloor\lg n\rfloor}}$$练习13.2-2 证明，在⼀棵 $n$ 个节点的⼆叉查找树中，刚好有 $n-1$ 种可能的旋转。

思路：每⼀个可能的旋转对应于⼀条边，每⼀个条边也只能对应⼀个可能的旋转，因此可能的旋转数就是边的数⽬。

每⼀条边都对应⼀个⼉⼦节点，每⼀个节点（除了根节点）都对应⼀个边，所以边的数⽬为 $n-1$ ，也就是可能的旋转的数⽬。

练习13.2-4 证明任意⼀颗含有 $n$ 个节点的⼆叉查找树都能通过 $O(n)$ 次旋转，转变为另⼀颗含有同样节点（节点位置可以任意不⼀样，但仍然保持⼆叉查找树性质）的⼆叉查找树。

思路：考虑⼀颗⼆叉查找树的“右链”，即从根节点向具有最⼤节点值的节点的路径。

不断地右旋右链上具有左⼦树的节点，每⼀次旋转可以使右链上多⼀个节点，（⼜，右链上⾄少有⼀个节点，根节点），所以⾄多 $n-1$ 次右旋后，⼆叉树的右链上连接了所有的节点，这时⼆叉树实际上称了⼀个已排序（旋转保持⼆叉查找树的性质）的单链表。

计算机科学与技术专业编程考试复习资料推荐计算机科学与技术专业的编程考试对学生来说是一项重要的挑战。

为了帮助同学们更好地备考，本文将推荐一些优质的复习资料，希望能够为大家提供一些参考和指导。

一、教材推荐1.《C++ Primer》《C++ Primer》是一本经典的C++教材，适合初学者和有一定基础的同学。

该书全面介绍了C++的语法和常用编程技巧，并通过大量的实例帮助读者理解和掌握知识点。

同时，书中还包含了一些编程练习题，有助于巩固所学知识。

2.《算法导论》《算法导论》是一本经典的算法教材，对计算机科学与技术专业的学生来说是必备的参考书之一。

该书详细介绍了各种常用算法和数据结构，并提供了相应的伪代码和实现方法。

通过学习和理解这本书，同学们可以提高编程能力和解决实际问题的能力。

二、在线资源推荐1.leetcodeleetcode是一个在线的编程练习平台，提供了大量的编程题目和解答。

同学们可以通过在leetcode上刷题，提高自己的编程能力和解题思维。

该平台还提供了讨论区，可以与其他同学交流和分享解题思路，对于理解和掌握算法和数据结构非常有帮助。

2.GitHubGitHub是一个全球最大的代码托管平台，上面有大量的开源项目和代码资源。

同学们可以通过搜索相关的项目，找到一些优秀的编程示例和实践经验。

此外，GitHub还提供了版本控制和协作开发的功能，可以帮助同学们更好地组织和管理自己的代码。

三、学习方法推荐1.理论与实践相结合编程考试不仅要求掌握理论知识，还需要具备实际操作的能力。

因此，同学们在复习过程中应该注重理论与实践相结合。

可以通过编写小项目或者参与开源项目的方式，将所学知识应用到实际中，提高自己的编程能力。

2.刷题与总结编程考试中经常会涉及到一些经典的算法和数据结构。

同学们可以通过刷题的方式来加深对这些知识点的理解和掌握。

在刷题的过程中，可以总结一些常用的解题思路和技巧，形成自己的思维导图或者笔记，方便复习和回顾。

算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。

链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。

矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。

汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。

习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。

习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。

但若有边连接相同类的结点，则⽆法划分。

wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。

重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。

问题变成要遍历所有边⼀次。

访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。

u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。

全部结点出列后达到遍历所有边⼀次。

Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort 重写为按非递减顺序排序2.1.3 计算两个n 位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数32/10001001003n n n --+用符号Θ表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n 个元素已经是最大的元素了.最好时间和最坏时间均为2()n Θ2.3 Designing algorithms2.3.3 计算递归方程的解22()2(/2)2,1k if n T n T n n if n for k =⎧=⎨+ = >⎩ （1） 当1k =时，2n =，显然有()lg T n n n =（2） 假设当k i =时公式成立，即()lg 2lg22i i i T n n n i ===⋅，则当1k i =+，即12i n +=时，111111()(2)2(2)222(1)22lg(2)lg i i i i i i i i T n T T i i n n ++++++==+=⋅+=+== ()lg T n n n ∴ =2.3.4 给出insertion sort 的递归版本的递归式(1)1()(1)()1if n T n T n n if n Θ =⎧=⎨-+Θ >⎩2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x)QuickSort(A,n);i←1; j←n;while A[i]+A[j]≠x and i<jif A[i]+A[j]<xi←i+1elsej←j -1if A[i]+A[j]=xreturn trueelsereturn false时间复杂度为)(n Θ。

算法导论第四版引言算法是计算机科学中的重要概念，它是解决问题的步骤和方法的描述。

《算法导论第四版》是一本经典的算法教材，深入浅出地介绍了各种常见的算法和数据结构。

本文将对这本书进行全面、详细和深入地探讨，帮助读者更好地理解和应用算法导论。

为什么学习算法导论1.提升编程技能：算法是编程的基础，学习算法可以提升编程的技能和水平。

2.解决实际问题：算法解决了许多实际问题，学习算法可以帮助我们更好地解决实际问题。

3.备战面试：许多技术面试都会考察算法和数据结构的知识，学习算法导论可以更好地应对面试。

基础知识算法分析1.时间复杂度：衡量算法的执行时间随输入规模增长的速度。

2.空间复杂度：衡量算法执行过程中所需的额外空间随输入规模增长的速度。

排序算法1.冒泡排序：反复交换相邻的元素，将最大的元素逐渐“冒泡”到最后。

2.插入排序：通过构建有序序列，依次将未排序的元素插入到已排序的序列中。

3.快速排序：选择一个基准元素，按照它的值将数组分成两部分，递归地对两部分进行排序。

4.归并排序：将数组分成两部分，分别对两部分进行排序，然后将两个有序的子数组合并成一个有序的数组。

数据结构数组和链表1.数组：连续的内存空间，支持随机访问，但插入和删除的时间复杂度较高。

2.链表：不连续的内存空间，只支持顺序访问，但插入和删除的时间复杂度较低。

栈和队列1.栈：后进先出的数据结构，主要有进栈和出栈两个操作。

2.队列：先进先出的数据结构，主要有入队和出队两个操作。

哈希表1.哈希函数：将关键字映射到哈希表中的位置。

2.哈希冲突：不同的关键字映射到了同一个位置，解决冲突的方法有开放寻址法和链地址法。

3.哈希表的应用：常用于高效地插入、删除和查找操作。

树和二叉树1.树：由节点和边组成的一种数据结构，常见的树包括二叉树、平衡二叉树和B树等。

2.二叉树：每个节点最多有两个孩子节点的树。

堆和优先队列1.堆：完全二叉树，堆可以分为最大堆和最小堆。

精心整理填空题动态规划算法的基本要素为：最优子结构性质与重叠子问题性质1)算法分析中，记号O表示渐进上界，记号Ω表示渐进下界，记号Θ表示紧渐进界。

2)回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

3)分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。

）4)5)6)7)8)9)算法中通常以自底向下的方式求解最优解的是动态规划法10)背包问题的贪心算法所需的计算时间为O（nlogn）11)0-1背包问题的回溯算法所需的计算时间为O（n2n）12)用动态规划算法解决最大字段和问题，其时间复杂性为n13)一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性，确定性，可行性，输入，输出。

1.算法的复杂性有时间复杂性和空间复杂性之分。

2、程序是算法?????用某种程序设计语言的具体实现。

3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。

4.矩阵连乘问题的算法可由动态规划设计实现。

6、算法是指解决问题的一种方法或一个过程。

7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。

891015题。

161719.21.后从这些子问题的解得到原问题的解。

23、大整数乘积算法是用分治法来设计的。

26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

27.快速排序算法是基于分治策略的一种排序算法。

30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。

33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。

34.任何可用计算机求解的问题所需的时间都与其规模有关。

35.快速排序算法的性能取决于划分的对称性。

37.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是m n，解空间树中每个内结点的孩子数是m。

1.用计算机求解问题的步骤：1、问题分析2、数学模型建立37、程序调试8、结果整理文档编制2.最优二叉搜索树问题的动态规划算法{inti,j,k,t,l;for(i=1;i<=n+1;i++){}{{t=m[i][k-1]+m[k+1][j]+w[i][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。

算法导论第九章习题答案（第三版）IntroductiontoAlgorithm Exercise
9.1-1
对所有的元素，两个⼀组进⾏⽐较，共需n-1次⽐较，可以构成⼀棵⼆叉树，最⼩的元素在树的根结点上，接下来，画出⼆叉树，可以很容易的看出共需lgn-1次⽐较，所以共需n+lgn-2次⽐较才可以找出第⼆⼩的元素。

9.1-2
略。

9.2-1
在randomized-select中，对于长度为0的数组，此时p=r，直接返回A[p],所以不会进⾏递归调⽤。

9.2-2
略。

9.2-3
RANDOMIZED-SELECT(A,p,r,i){
while(true){
if(p==r)
return A[p];
q=RANDOMIZED-PARTITION(A,p,r);
k=q-p+1;
if(i==k)
return A[q];
else if(i<k)
q--;
else{
q++;
i-=k;
}
}
}
9.2-4
每次都以最⼤的元素进⾏划分即可。

9.3-1
数学计算，根据书中例题仿照分析即可。

9.3-3
随机化
9.3-5
类似主元划分，只要把⿊箱⼦输出的值作为主元划分去选择即可。

9.3-6
多重⼆分即可。

9.3-7
算出中位数，之后算出每⼀个数与中位数的差即可。

9.3-8
分别取两个数组的中位数进⾏⽐较，如果两个中位数相等，那么即为所求，否则，取中位数较⼩的⼀个的右边，取较⼤的⼀个的右边，直到就剩4个元素为⽌，这时候只要求这4个元素的中位数即可。

算法导论答案第一章：算法概述啊算法的定义算法是一系列解决问题的明确指令。

它是一个有穷步骤集，其中每个步骤或操作由确定性和可行性特征。

算法是通过将预期的输入转换为输出来解决问题的工具。

第二章：插入排序插入排序的思想插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，并将其插入到已排序部分的正确位置，直到所有元素都被排序。

插入排序的算法实现以下是插入排序的伪代码：INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]// Insert A[j] into the sorted sequence A[1.. j-1].i = j - 1while i > 0 and A[i] > keyA[i + 1] = A[i]i = i - 1A[i + 1] = key插入排序的时间复杂度插入排序的时间复杂度为O(n^2)，其中n是排序的元素个数。

虽然插入排序的最坏情况下的复杂度很高，但是对于小规模的数据集，插入排序是一种较快的排序算法。

第三章：分治策略分治策略的基本思想分治策略是一种解决问题的思想，它将问题的规模不断缩小，直到问题足够小而可以直接解决。

然后将子问题的解合并起来，得到原问题的解。

分治策略的应用实例一种经典的应用分治策略的算法是归并排序。

归并排序将待排序的序列划分为两个子序列，分别排序后再将两个有序子序列合并为一个有序序列。

以下是归并排序的伪代码：MERGE-SORT(A, p, r)if p < rq = floor((p + r) / 2)MERGE-SORT(A, p, q)MERGE-SORT(A, q + 1, r)MERGE(A, p, q, r)MERGE(A, p, q, r)n1 = q - p + 1n2 = r - qlet L[1..n1+1] and R[1..n2+1] be new arraysfor i = 1 to n1L[i] = A[p + i - 1]for j = 1 to n2R[j] = A[q + j]L[n1 + 1] = infinityR[n2 + 1] = infinityi = 1j = 1for k = p to rif L[i] <= R[j]A[k] = L[i]i = i + 1elseA[k] = R[j]j = j + 1分治策略的时间复杂度归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。

一、算法设计实例1、快速排序（分治法）int partition(float a[],int p,int r) {int i=p,j=r+1;float x=a[p];while(1){while(a[++i]<x);while(a[--j]<x);if(i>=j)break;swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}void Quicksort(float a[],int p,int r){//快速排序if(p<r){int q=partition(a,p,r);Quicksort(a,p,q-1);Quicksort(a,p+1,r);}}2、归并排序（分治法）void mergesort(Type a[],int left,int right) {if(left<rigth){int mid=(left+right)/2;//取中点mergesort(a,left,mid);mergesort(a,mid+1,right);mergesort(a,b,left,right);//合并到数组bmergesort(a,b,left,right);//复制到数组a}}3、背包问题（贪心算法）void knapsack(int n,float m,float v[],float w[],float x[]) {sort(n,v,w)//非递增排序int i;for(i=1;i<=n;i++)x[i]=0;float c=m;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}4、活动安排问题（贪心算法）void Greadyselector(int n,Type s[],Type f[],bool A[]) {//s[i]为活动结束时间，f[j]为j活动开始时间A[i]=true;int j=1;for(i=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}5、喷水装置问题（贪心算法）void knansack(int w,int d,float r[],int n){//w为草坪长度d为草坪宽度r[]为喷水装置的喷水半径，//n为n种喷水装置，喷水装置的喷水半径>=d/2sort(r[],n);//降序排序count=0;//记录装置数for(i=1;i<=n;i++)x[i]=0;//初始时，所有喷水装置没有安装x[i]=0for(i=1;w>=0;i++){x[i]=1;count++;w=w-2*sqart(r[i]*r[i]-1);}count<<装置数:<<count<<end1;for(i=1;i<=n;i++)count<<喷水装置半径：<<r[i]<<end1;}6、最优服务问题（贪心算法）double greedy(rector<int>x,int s){rector<int>st(s+1,0);rector<int>su(s+1,0);int n=x.size();//st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间//su[]是求和数组，su[j]为第j个队列上所有顾客的等待时间sort(x.begin(),x.end());//每个顾客所需要的服务时间升序排列int i=0,j=0;while(i<n){st[j]+=x[i];//x[i]=x.begin-x.endsu[j]+=st[j];i++;j++;if(j==s)j=0;}double t=0;for(i=0;i<s;i++)t+=su[i];t/=n;return t;}7、石子合并问题（贪心算法）float bebig(int A[],int n) {m=n;sort(A,m);//升序while(m>1){for(i=3;i<=m;i++)if(p<A[i])break;elseA[i-2]=A[i];for(A[i-2]=p;i<=m;i++){A[i-1]=A[i];m--;}}count<<A[1]<<end1}8、石子合并问题（动态规划算法）best[i][j]表示i-j合并化最优值sum[i][j]表示第i个石子到第j个石子的总数量|0f(i,j)=||min{f(i,k)+f(k+1,j)}+sum(i,j)int sum[maxm]int best[maxm][maxn];int n,stme[maxn];int getbest();{//初始化，没有合并for(int i=0;i<n;i++)best[i][j]=0;//还需要进行合并for(int r=1;r<n;r++){for(i=0;i<n-r;i++){int j=i+v;best[i][j]=INT-MAX;int add=sum[j]-(i>0!sum[i-1]:0);//中间断开位置，取最优值for(int k=i;k<j;++k){best[i][j]=min(best[i][j],best[i][k]+best[k+1][j])+add;}}}return best[0][n-1];}9、最小重量机器设计问题（回溯法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void backstack(Qnode*p){if(p->ceng==n+1){if(bestw>p->wei){testw=p->wei;best=p;}}else{for(i=1;i<=m;i++)k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->val=vt;s->wei=wt;s->ceng=k+1;s->no=1;s->parent=p;backstrack(S);}}}10、最小重量机器设计问题（分支限界法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void minloading(){float wt=0;float vt=0;float bestw=Max;//最小重量Qnode*best;s=new Qnode;s->wei=0;s->val=0;s->ceng=1;s->no=0;s->parent=null;Iinit_Queue(Q); EnQueue(Q,S);do{p=OutQueue(Q);//出队if(p->ceng==n+1){if(bestw>p->wei){bestw=p->wei;best=p;}}else{for(i=1;i<=m;i++){k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->ceng=k+1;s->wt=wt;s->val=val;s->no=i;s->parent=p;EnQueue(Q,S);}}}}while(!empty(Q));p=best;while(p->parent){count<<部件：<<p->ceng-1<<end1;count<<供应商：<<p->no<<end1;p=p->parent;}}11、快速排序（随机化算法—舍伍德算法）int partion(int a[],int l,int r){key=a[l];int i=l,j=r;while(1){while(a[++i]<key&&i<=r);while(a[--j]>key&&j>=l);if(i>=j)break;if(a[i]!=a[j])swap(a[i],a[j]);}if((j!=l)&&a[l]!=a[j])swap(a[l],a[j]);return j;}int Ranpartion(int a[],int l,int r) {k=rand()%(r-1+l)+1;swap(a[k],a[l]);int ans=partion(a,l,r);return ans;}int Quick_sort(int a[],int l,int r,int k){int p=Randpartion(a,l,r);if(p==k)return a[k];else if(k<p)return Quick_sort(a,l,p-1,k);else{int j=0;for(int i=p+1;i<=r;i++)b[j++]=a[i]return Quick_sort(b,1,j,k-p);}}12、线性选择（随机化算法—舍伍德算法）二、简答题1．分治法的基本思想分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

算法复习资料第一章1.可计算性理论描述那些在算法上可解的问题的特征。

定义：一个问题是算法上可解的，如果能够设计出一个计算机程序，对于该问题的任何一个输入都可以给出正确的答案。

假设所需要的计算资源（时间和存储空间）是充分大的。

2.著名的不可解例子Does the following program stop for any n? While (n > 1)If (odd(n))N = 3*n + 1 ;ElseN = n / 2;End (while)3.丘奇图灵论点：凡是可计算的函数都是一般递归函数（或都是图灵机可计算的，或都是λ演算可计算的，或都是波斯特系统可计算的）。

4.算法（非正式定义）是以一步接一步的方式来详细地描述计算机如何将输入转化为所要求的输出的过程，算法是在计算机上执行的计算过程的具体描述。

算法性质：正确性。

对于任意的一组输入，包括合理的输入与不合理的输入，总能得到预期的输出具体性。

由一系列的具体步骤所组成，每一步都能够被计算机所理解和执行，而不是抽象和模糊的概念。

确定性。

每个步骤都有确定的执行顺序，即上一步在哪里、下一步是什么，都必须明确，无二义性。

有限性。

在任何情况下，算法都不能陷入无限循环中。

5.问题定义：可计算问题（或算法可解问题）是一个需要计算执行或实现的任务。

问题的三种类型：判定性问题：这类问题的输出是给出一个是与否的判断。

例如连通性问题、回路问题、查找与排序问题以及字符串匹配等。

最优值或最优化问题：这类问题是在所有可能的解中求出最优解。

例如求函数的最大值、最短路径问题以及最小生成树问题等。

数值计算问题：这类问题是在一定的约束条件（如精度范围）下求近似解。

例如解方程组和矩阵运算等。

6.算法设计方法：分治法（Divide and Conquer）贪心法（Greedy Method）回溯法（Back Tracking）分支限界法（Branch Band）动态规划（Dynamic Programming）7.算法设计的任务有两个：第一是设计容易理解、容易编程实现且容易调试的算法；第二是使算法能够有效地使用计算机资源，减少计算机的工作量，即节省时间、空间和计算机硬件资源。

第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。

另，思考题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-15 while i > 0 and A[i] > key6 do A[i+1]←A[i]7 i ←i − 18 A[i+1]←keyC#对揑入排序算法的实现:public static void InsertionSort<T>(T[] Input) where T:IComparable<T>{T key;int i;for (int j = 1; j < Input.Length; j++){key = Input[j];i = j - 1;for (; i >= 0 && Input[i].CompareTo(key)>0;i-- )Input[i + 1] = Input[i];Input[i+1]=key;}}揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j]这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1 for j ← 1 to length[A]2 do key ←A[j]3 i ←j-14 while i ≥ 0 and A[i] > key5 do A[i+1]←A[i]6 i ← i − 17 A[i+1]←key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。

算法导论5.3-3转⾃风清云淡的博客，他给出的解法⾮常的妙。

问题：描述RANDOM(a,b)的过程的⼀种实现，它只调⽤RANDOM(0,1)。

作为a和b的函数，你的程序的期望运⾏时间是多少？注：RANDOM(0,1)以等概率输出0或者1，要求RANDOM(a,b)以等概率输出[a,b]之间的数(整数)解决⽅案：1，取 n=b-a+1，取最⼩的正整数m，使得 2^m >= n2，调⽤RANDOM(0,1)，输出m-bit位整数N ( N >= 0 and N <= 2^m-1)3， if N >=0 and N <= b-athen return a+Nelse 重新执⾏步骤 2[a,b]之间每个数都是以 1/2^m 的概率输出的渐进运⾏时间分析：我觉得渐进时间分析应该⽤概率分析的⽅法，我觉得是服从⼏何分布：假设进⾏⼀系列伯努利试验，每次成功的概率是p，失败的概率是q=1-p，在取得⼀次成功前⼀共要进⾏多少次试验？令随机变量X为取得⼀次成功所要进⾏的试验次数，则X的取值范围{1,2,......}。

对k>=1，因为在⼀次成功前有k-1次失败，从⽽有Pr[X=k]= q^(k-1)p满⾜上式的分布称为⼏何分布 [见算法导论 P686]在算法中 p=(b-a+1)/2^m期望运⾏次数(算法中⽣成m位序列的调⽤次数)为： E[X]=sum(k*q^(k-1)p) [k=1......+⽆穷]=1/p=2^m/(b-a+1)⽤T表⽰调⽤⼀次RANDOM(0,1)所需要的时间，每次运⾏时间为输出m位bit的时间：O(log(b-a) × T)期望运⾏时间：O（T × log(b-a) × 2^m/(b-a+1) ）=(约等于)O(T × log(b-a)) (因为m=(约等于)log(b-a+1))。

《算法导论（原书第3版）》第24章部分题⽬解答第24章单源最短路径24.1 Bellman-Ford算法24.1-4思路：先做|V|-1遍松弛操作，然后再做⼀遍松弛操作，对于这次松弛操作中dist值被更新的点，必然包含了每个负环中的⾄少⼀个点。

对于这些点做dfs查找它们能够在图中到达哪些点，所有被搜索到的点即为题⽬要求找的点部分c++代码：#include <bits/stdc++.h>using namespace std;const int maxn = ...;const int inf = 0x3f3f3f3f;//正⽆穷struct E{int x,y,z;//三元组（x,y,z)表⽰⼀条有向边。

从x出发到y，权值为z。

}vector<E> es;//存边vector<int> e[maxn];//模拟邻接链表vector<int> vec;//存起始点void bellman(int s){for(int i = 1; i<=n; i++)d[i]=inf;d[s] = 0;for(int t = 1; t<n; t++){for(auto e:es){if(d[e.x]!=inf && d[e.x]+e.z<d[e.y])d[e.y] = d[e.x] + w;}}for(auto e:es){if(d[e.x]!=inf && d[e.x]+e.z<d[e.y]){vec.push_back(y);}}}int v[maxn];void dfs(int x){v[x] = 1;for(auto y: e){if(!v[y]) dfs(y);}}void solve(int s){bellman(s);for(auto x:vec){if(!v[x]) dfs(x);}for(int i = 1; i<=n; i++){if(v[i]) cout<<"负⽆穷"<<endl;else if(d[i]==inf) cout<<"不可达"<<endl;else cout<<d[i]<<endl;}}24.1-5思路：跑⼀遍Bellman-Ford算法，具体做法如下：1、初始化∀v∈V,d[v]=0。