下载文档原格式
第一章：算法定义: 算法是若干指令的有穷序列, 满足性质: (1)输入: 有外部提供的量作为算法的输入。
(2)输出: 算法产生至少一个量作为输出。
1. (3)确定性：组成算法的每条指令是清晰, 无歧义的。
2. (4)有限性：算法中每条指令的执行次数是有限的, 执行每条指令的时间也是有限的。
3. 程序定义: 程序是算法用某种程序设计语言的具体实现。
可以不满足算法的性质(4)。
4. 算法复杂性分为时间复杂性和空间复杂性。
5. 可操作性最好且最有使用价值的是最坏情况下的时间复杂性。
6. O(n)定义: 存在正的常数C 和自然数N0, 当N>=N0时有f(N)<=Cg(N),则称函数f(N)当N 充分大时有上界, 记作f(N)=O(g(n)). 7. Ω(n)定义: 存在正的常数C 和自然数N0, 当N>=N0时有f(N)>=Cg(N),则称函数f(N)当N 充分大时有上界, 记作f(N)=Ω(g(n)). 8. (n)定义:当f(n)=O(g(n))且f(N)=Ω(g(n)), 记作f(N)= (g(n)), 称为同阶。
求下列函数的渐进表达式: 3n2+10n ~~~O(n2) n2/10+2n~~~O(2n) 21+1/n~~~O(1) logn 3~~~O(logn) 10log3n ~~~O(n) 从低到高渐进阶排序: 2 logn n2/3 20n 4n2 3n n!第二章：1. 分治法的设计思想: 将一个难以直接解决的问题, 分割成一些规模较小的相同问题, 以便各个击破分而治之。
2. 例1 Fibonacci 数列 代码（注意边界条件）。
int fibonacci(int n) {if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2);}3. Ackerman 函数双递归。
A(1,1)代入求值。
A(1,1)=A(A(0,1),0)=A(1,0)=24. 全排列的递归算法代码。
计算机科学算法设计与复杂性分析计算机科学算法设计与复杂性分析是计算机科学领域的重要课题。
在计算机科学领域中，算法是解决问题的步骤和方法。
它的设计涉及到问题的建模和解决方案的设计与实现。
在实际应用中，算法的性能和复杂性是评估其优劣的关键因素。
本文将介绍计算机科学中算法设计的基本原则和复杂性分析的方法。
一、算法设计的基本原则在计算机科学中，算法设计的基本原则包括以下几个方面：1. 清晰和明确的问题描述：在设计算法之前，首先需要对问题进行清晰和明确的描述。
问题描述应包括问题的输入和输出，以及问题的约束条件。
2. 模块化和分解：复杂的问题可以通过将其分解为若干个较简单的子问题来进行解决。
模块化的设计思想有助于提高算法的复用性和可维护性。
3. 合适的数据结构选择：选择合适的数据结构对于算法的性能至关重要。
不同的数据结构适用于不同类型的问题，例如数组、链表、栈、队列等。
4. 适当的算法选择：在设计算法时，需要综合考虑算法的时间复杂性和空间复杂性。
有时候，一个简单但时间复杂性较高的算法可能比一个复杂但时间复杂性较低的算法更加合适。
二、复杂性分析的方法复杂性分析是用于评估算法性能的重要方法，常用的复杂性分析方法包括时间复杂性分析和空间复杂性分析。
1. 时间复杂性分析：时间复杂性是衡量算法在执行过程中所需时间的度量。
常用的时间复杂性分析方法有最坏情况分析、平均情况分析和最好情况分析。
最坏情况分析给出了算法在最坏情况下的执行时间上界，平均情况分析则考虑了各种输入情况的概率分布，最好情况分析给出了算法在最理想情况下的执行时间下界。
2. 空间复杂性分析：空间复杂性是衡量算法在执行过程中所需空间的度量。
与时间复杂性类似，空间复杂性也可以进行最坏情况分析、平均情况分析和最好情况分析。
通常情况下，空间复杂性主要考虑算法所需的额外空间。
三、算法设计与复杂性分析的应用举例为了更好地理解算法设计与复杂性分析的具体应用，下面将介绍两个与计算机科学相关的实际问题。
算法设计与分析——算法复杂性分析这篇博客的内容摘⾃课本，针对课本中缺少的5道证明题，作为练习，给出证明。
算法运⾏时所需要的计算机时间资源的量称为时间复杂性。
这个量应该集中反应算法的效率，并从运⾏该算法的实际计算机中抽象出来。
换句话说，这个量应该是只依赖于要解的问题的规模、算法的输⼊和算法本⾝的函数。
如果分别⽤ N,I和A 表⽰算法要解的问题的规模、算法的输⼊和算法本⾝，⽽且⽤ T 表⽰时间复杂性，那么，应该有 T=T(N,I,A)。
通常 A 隐含在复杂性函数名中，因⽽将 T 简写为 T(N,I) 。
现在，时间复杂性分析的主要问题是如何将复杂性函数具体化，即对于给定的 N,I和A ，如何导出 T(N,I) 的数学表达式，来给出计算T(N,I) 的法则。
根据 T(N,I) 的概念，它应该是算法在⼀台抽象的计算机上运⾏所需要的时间。
设此抽象的计算机所提供的原运算有 k 种，它们分别记为O1,O2,...,Ok 。
⼜设每执⾏⼀次这些元运算所需要的时间分别为 t1,t2,...,tk 。
对于给定的算法 A ，设经统计，⽤到元运算 Oi 的次数为 ei,i=1,2,...,k 。
很清楚，对于每⼀个 i,1≤i≤k,ei 是 N和I 的函数，即 ei=ei(N,I)。
因此有 式中， ti（i=1,2,...,k )，是与 N和I ⽆关的常数。
显然，不可能对规模为 N 的每⼀种合法的输⼊都去统计 ei(N,I),i=1,2,...,k 。
因此 T(N,I) 的表达式还要进⼀步简化，或者说，只能在规模为 N 的某些或某类有代表性的合法输⼊中统计相应的 ei,i=1,2,...,k ，评价其时间复杂性。
通常只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为 Tmax(N)、Tmin(N)和Tavg(N) 。
在数学上有 式中， DN 是规模为 N 的合法输⼊的集合； I∗是 DN 中使 T(N,I∗) 达到 Tmax(N) 的合法输⼊；I∼是 DN 中使 T(N,I∼)达到 Tmin(N) 的合法输⼊；⽽ P(I) 是在算法的应⽤中出现输⼊ I 的概率。
第7章_随机化算法随机化算法是一类基于随机数生成的算法，它的主要思想是通过引入随机性来改善算法的效率、正确性或可伸缩性。
在计算机科学中，随机化算法被广泛应用于各个领域，如优化问题、图论、排序等。
本文将介绍随机化算法的概念、应用以及一些常见的随机化算法。
一、概念随机化算法是一种利用随机数生成器的算法，通过引入随机性来改善算法的性能表现。
随机化算法的核心思想是使用随机数来决定算法的一些操作，使算法具有更好的平均性能或概率分布。
随机化算法有两个主要的特点：1.随机性：随机化算法依赖于随机数生成器产生的随机数，使用这些随机数来决定算法的一些操作。
2.概率分布：随机化算法通常具有其中一种概率分布特性，即算法的输出结果在一定概率上是正确的。
二、应用随机化算法在实际应用中有广泛的用途，主要包括以下几个方面：1.优化问题：对于一些优化问题，随机化算法可以提供一个近似解。
常见的例子有旅行商问题、背包问题等。
2.图论：在图论中，随机化算法可以用于生成随机图、图的遍历等问题。
3.排序：随机化算法可以用于改进排序算法的时间复杂度。
例如，快速排序算法就是一种经典的随机化排序算法。
4.模拟：在模拟领域，随机化算法可以用于生成随机事件，如蒙特卡洛模拟法。
1.快速排序算法：快速排序是一种基于分治思想的排序算法，它通过随机地选择一个元素作为基准，将数组分成左右两部分，然后对左右两部分分别进行快速排序。
2.蒙特卡洛模拟法：蒙特卡洛模拟法是一种通过随机采样来估计数学问题的方法。
它通过生成大量随机数，并利用这些随机数的统计性质来得出数学问题的近似解。
3.随机化算法在图论中的应用：在图论中，随机化算法可以用于生成随机图、图的遍历等问题。
例如，随机化算法可以用于生成连通图，即图中任意两个顶点之间存在至少一条路径。
4. Metropolis-Hastings算法：Metropolis-Hastings算法是一种用于模拟复杂概率分布的随机化算法。
概率算法随机数概念伪随机数生成算法几种主要的概率算法Sherwood算法Las Vegas算法Monte Carlo算法1伪随机数随机数与伪随机数概率算法中要进行随机选择，需要大量随机数.通常根据某种规则生成随机数，这些随机数不是真正随机的，但在一定程度上可以模拟随机数，一般叫做伪随机数随机变量X的取值范围是(0,1)且对任意的0<a<1,P{0<X≤a}=a, 则称X服从(0,1)上的均匀分布23伪随机数生成算法---线性同余法生成伪随机序列为{a i }, i = 0,1,…, n ,…,0<a i <m⎩⎨⎧=+==−,...2,1mod )(10n m c ba a d a n n 模数：m , 机器最大数.乘数：b , 2≤b <m ，计算前给定常数：c , 0≤c <m ，计算前给定种子：d , 0≤d <m, 计算时随机给出伪随机数生成算法4乘同余法⎩⎨⎧===−,...2,1mod 10n m ba a d a n n 参数：c = 0，d ≠0，m =231-1, b =75实例：d =116,807, 282,475,249, 1,622,650,073, 984,943,658, 1,144,108,930, 470,211,272, 101,027,544, 1,457,850,878……确定型算法与随机算法1.特点：确定型算法: 对某个特定输入的每次运行过程是可重复的，运行结果是一样的.随机算法：对某个特定输入的每次运行过程是随机的，运行结果也可能是随机的.2. 随机算法的优势：在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进随机算法设计简单6随机算法复杂性度量随机算法A对于规模为n的某个给定的实例I 的一次执行的时间与另一次可能不一样.随机算法A对于某个规模为n的实例I 的运行时间的期望：算法A反复求解实例I 的平均时间.一般情况下，许多随机算法对于规模为n的不同的实例，运行时间的期望都一样，因此这个值代表随机算法的平均时间的期望.79确定型排序算法Quicksort 最坏情况下时间为O (n 2)平均情况下为O (n log n )确定型排序+选择算法如果选用中位数进行划分, 时间为O(n log n )随机快速排序算法期望时间O (n log n )最坏情况概率非常小，在实际应用中可以忽略算法比较13拟中位数选择算法最坏情况O (n )平均情况O (n )随机算法平均时间O (n )最坏情况O (n 2)每次恰好选到边界元素与实例无关，只与选择有关概率很小，可以忽略期望时间O (n )算法比较15算法能得到正确的解算法比确定型算法简单算法的平均性能与确定型算法一样算法改善了最坏情况的期望运行时间运行时间基本与输入实例无关确定算法最坏情况在随机选择出现的概率接近0实现途径通过改进确定型算法得到将确定型选择原则改为随机选择在确定型算法前增加随机洗牌步骤Sherwood算法总结Las Vegas 算法总结一次运行可能得不到解得到的解一定是正确的改进途径：与确定型算法相结合改进确定型算法的平均情况下复杂度修改确定性算法得到20例5串相等测试问题：A有一个长串x, B有长串y，A和B希望知道x=y?方法一：A 将x 发送给B，B 测试x = y?发送消耗：长串占用信道资源大方法二：A 用x 导出一个短串f(x) (fingerprints)A 将f(x) 发送到BB 使用同样方法导出相对于y 的短串f(y)B 比较f(x) 与f(y)如果f(x) ≠f(y)，则x ≠y;如果f(x) = f(y)，则不确定.25fingerprints的产生方法设x 和y 的二进制表示为正整数I(x), I(y)选择素数p, fingerprint函数为Ip(x) = I(x) mod pA 传送p 和Ip(x) 给B. 当p 不太大时，传送一个短串. 存在问题：x = y ⇒Ip(x) = Ip(y)Ip(x) = Ip(y) ⇏x = y出错条件：固定p | (I(x) −I(y))26算法二Knuth, Morris, Pratt利用有限状态自动机模式匹配算法Introduction to Algorithms运行时间：O(m+n)算法三随机算法设计思想：设X(j) = xjx j+1 …x j+m-1改造算法一不是比较每个X(j) (j = 1, 2, …, n-m+1) 与Y，而是将Ip (Y) 与I p(X(j)) 比较其他算法34时间复杂度W p, I p(Y), I p(X(1)) 计算O(m) 时间从Ip(X(j)) 计算I p(X(j+1)) 总共需要O(n)时间总时间为O(m+n)出错条件：∏≠−⇔=∧≠)}(|{|))(()(| |))(()( )(jXYj ppjXIYIp jXIYIjXY算法分析38例7素数测试•求x的m次幂•求a的模n的m次幂•Fermart小定理•测试算法分析40算法的问题Fermat小定理的条件是必要条件，不是充分条件，满足这个条件的也可能是合数.对上述所有与n 互素的正整数a，都满足上述条件的合数n 称为Carmichael数，如561，1105，1729，2465等。
如何进行算法分析和复杂性分析算法分析和复杂性分析是计算机科学中非常重要的一部分，它们帮助我们评估和理解算法的效率和性能。
本文将介绍算法分析和复杂性分析的概念、方法和常见的计算复杂性类别。
一、算法分析算法分析是对算法性能的评估和比较。
它提供了对算法资源使用情况的度量，例如时间复杂性和空间复杂性。
1.时间复杂性：时间复杂性是算法运行时间相对于输入规模的度量。
我们通常关注最坏情况下的运行时间，即最长时间。
常用的表示方式有大O表示法。
例如，如果一个算法的时间复杂度是O(n)，表示算法的运行时间与输入规模n成正比。
当n变大时，运行时间也会相应增长，但增长的速度是线性的。
2.空间复杂性：空间复杂性是算法运行时所需的额外内存的度量。
同样，通常关注最坏情况下的额外内存使用。
也可以使用大O表示法表示空间复杂性。
算法分析的目标是找到高效的算法来解决问题。
通过对不同算法的复杂性进行度量和比较，我们可以选择最适合特定问题的算法，或者优化现有算法以获得更好的性能。
二、复杂性分析复杂性分析是一种对问题复杂性进行分类和比较的方法。
它研究了问题的难度和所需的计算资源。
根据问题的性质和计算资源的限制，我们可以将问题分为不同的复杂性类别。
1. P类问题（多项式类问题）：这些问题可以在多项式时间内解决，即随着输入规模的增加，算法的运行时间以多项式速度增长。
最常见的例子是排序和搜索问题。
2. NP类问题（非确定性多项式类问题）：这些问题可以在多项式时间内验证解的正确性。
虽然我们目前无法在多项式时间内找到解，但一旦解被提供进来，我们可以在多项式时间内验证它们的正确性。
最著名的例子是旅行商问题和背包问题。
3. NP-完全问题（非确定性多项式完全问题）：这是一类特殊的NP问题，它被认为是NP问题中最困难的一类。
这些问题在NP类中是最难解决的，目前还没有发现多项式时间内的解决方法。
代表性的例子有布尔可满足性问题和子集和问题。
通过对问题的复杂性进行分析，我们可以确定是否存在有效的算法来解决问题，或者将问题归类为NP完全问题。
