算法設计与分析开卷.docVIP

算法(Algorithm)有限性：每条指令的执行次数、时间有限；确定性：每条指令有确定的含义、无歧义；输入：0个或多个输入；输出：1个或多个输出；有效性 分治算法的特征：将较大规模的问题分解为若干个较小规模的子问题，每个子问题的求解过程与原问题一样，并利用自底向上的求解策略得到最终的解。 直接或间接地调用自身的算法称为递归算法。在定义函数时调用到函数自身称为递归函数。 边界条件与递归方程是递归函数的二要素。递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 贪心算法设计思路：总是做出在当前看来最好的选择，即贪心算法并不是从整体最优考虑，它所做的选择只是在某种意义上的局部最优选择。前提：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 贪心算法与动态规划算法的差异：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。背包、活动安排、最优装载、单源最短路径问题。 一、算法时间复杂性问题 1. 试证明下面的定理： (1)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n));(2)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n)) 根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n= N1，f（n）=C1s(n)；对所有的n= N2,g(n) =C2r(n) 所以 f（n）+ g(n) = C1s(n)+ C2r(n)，f（n）*g(n)= C1C2s(n)r(n)； 令 C3=max（C1,C2），C4=C1*C2； 则：f（n）+ g(n) = C3[s(n)+ r(n)]=O(s(n)+ r(n)) f（n）*g(n) = C4*s(n)*r(n)=O(s(n)* r(n)) 2. 假设某算法在输入规模为n时的计算时间为：T（n）=3*2n ，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A型计算机的64倍。试求出若在先进的B型机上运行同一算法在则T秒内能求解输入规模为多大的问题？某台t秒内完成的基本运算的次数=3*2^n新机器t秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6) 设N为B型机上钟能的问题的规模N)=3*2^N=3*2^(n+6) 则：N=n+6 3. 试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。 一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为 指数时间算法一般有Ο(2n)、Ο(n!)和Ο(nn)等。其关系为： 其中，最常见的是时间为Ο(2n)的算法。当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因为根本就找不到一个这样的m，使得2n囿界于n^m。换言之，对于任意的m≥0，总可以找到n0，当n≥n0时，有2n＞nm。因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。Ο(log2n)、Ο(n)和Ο(nlog2n)比另外三种时间函数的增长率慢得多。～ 由这些结果可看出，当数据集的规模(即n的取值)很大时，要在现代计算机上运行具有比Ο(nlog2n)复杂度还高的算法往往是很困难的。尤其是指数时间算法，它只有在n值取得非常小时才实用。尽管通过提高计算机的速度之前快，甚至，但指数规模的n足够大，n增加的瞬间化为乌有，所以 简答 对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何