北京工业大学算法分析与设计一纸开卷资料

如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))如果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))试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。当数据集的规模（即n的取值）很大时，要在现代计算机上运行具有比O（nlog2n）复杂度还高的算法是很困难的，尤其是指数时间算法，它只有在在n值取得非常小的时候才实用。例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n^2和nlogn.则N=1024，分别需要1048576和10240次运算。N=2048：分别需要4194304和22528次运算。由此，在n加倍的情况下，一个O（n^2)的算法计算时间增长4倍，而一个O（nlogn）算法则只用两倍多一点的时间。所以数量级的大小对算法的有效性有决定性的影响。尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000倍的提速即可瞬间化为乌有。1、什么是计算机科学中所说的“算法（algorithm）”？算法是一种描述程序行为的语言，是满足下述性质的指令序列。有限性：每条指令的执行次数、时间有限确定性：每条指令有确定的含义、无歧义输入：0个或多个输入输出：1个或多个输出2、满足何种性质的问题被称为称为NP完全问题？请简述研究NP完全问题的意义；（1）NP即是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题。如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内解决。（2）它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.知道一个问题是NP完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。简言之，NP完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向3、“当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。1、棋盘覆盖问题2、使用一个快速排序的迭代模型可以使原递归算法所需的栈空间总量减至O（logn）。试设计这一迭代模型（算法）。（18分）3、社会名流问题给定一个n×n邻接矩阵，确定是否存在一个i，其满足在第i列所有项（除了第ii项）都为1，并且第i行所有项（除了第ii项）都为0。大致的算法思路：随便取一个非对角线元素比如Array[i][j]，如果Array[i][j]=0成立，则j不是社会名流，于是删去第j行和第j列。同样，如果Array[i][j]=1成立，则删去第i行和第i列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。重复此操作直至剩下最后一个元素。最后，检验该元素是否为社会名流即可。如果该元素不是，则该群人中不存在社会名流。补充：1假设某算法在输入规模为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型机上t秒钟能求解的问题的规模所以T=T(N)=3*2^N=3*2^(n+6)则：N=n+64.试说明如何修改快速排序算法，使它在最坏情况下的计算时间为O(nlgn)。可以通过减少递归栈的使用进行优化，快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。对系统栈的频繁存取会影响到排序的效率。在数据量较大时，快速排序的复杂度为O(nlgn)。当数据集较小时，快排的复杂度有向O(n^2)发展的趋势，此时不必继续递归调用快速排序算法，使用插入排序代替快速排序。STL中sort就是用的快排+插入排序的，使得最坏情况下的时间复杂度也是O(nlgn)．这一改进被证明比持续使用快速排序算法要有效的多。5.试设计一个构造连通图G生成树的算法，使得构造出的生成树的边的最大权值达到最小。解答：可以证明，图G的最小生成树即为满足题意的生成树。假设T，T’分别为图G的最小生成树及边的最大权值达到最小值的生成树。v，v’分别为它们的最大权边。假如w(v)w(v’),则将v从T删除之后，T变为两个连同的分支，此时，一定有T’的边v1连同这两个分支，否则T’将是不连通的。从而将v1加入到T中构成一新的生成树T’’=T-v+v1。且有w(v1)w(v’)w(v),从而w(T”)=w(T-v+v1)w(T)。这与T为最小生成树矛盾。证毕。据此利用prim算法或者Kruskal算法算得G的最小生成树即可1证明0-1背包问题满足最优子结构性质假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。2对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。1.最大值和最小值问题的最优算法：给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A中的最大值和最小值6.试设计在O(n)时间内求得数组A[1..n]的中位数的算法。将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整)个。找出这n/5(上取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。第1行测试：如果i=n，表示已经搜索到了叶节点。如果从x[n-1]到x[n]以及从x[n]到起点x[1]有一条边，则找到了一条回路。此时，第3行需要判断该回路是否是目前发现的最优回路。如果是，第4行-6行则更新回路的权和bestw以及最优回路。第7-13行继续回溯，在第8行，如果从x[i-1]到x[j]有一条边，且B(i)小于当前最优解的值bestw，则表示可以继续往下搜索，同时更新目前所构造路径的权值cw。证明一个问题具有贪心选择性质的一般方法令子问题Sij≠Ø且a1为子问题Sij中的最优解，则a1一定包含在子问题Sij中某个任务相互兼容的最大子集中。TSP问题此问题相当于在一个有向赋权图中寻找一个最短的哈密顿回路。--：第i个顶点，假设推销员从第0号点出发，调用s时就要传入V：从出发，要到达的顶点的集合：从出发，经过V中各点，并仅经过一次后，回到所需的最短路径长度（若与目标点不直接连通，则记其路程为无穷大）：点i到j的距离广义背包问题（从最大递归，决定每个放不放，价值增不增加）i：（第）i种物品；j：背包中剩余载重量；m（i,j）：当背包内剩余载重量为j，考虑对于前i种物品的装入方案时，得到的最大物品价值：第i种物品的重量：第i种物品的价值证明f(n)–g(n)!=O(s(n)–r(n))设f(n)=n^2+ng(n)=n^2有f(n)–g(n)=n;O(s(n)–r(n))=0不相等