计算机算法基础..ppt

* * * * 在分析算法之前，需要对算法运行的计算机类型作出假定。 * 在讨论怎样分析算法之前，需要对算法运行的计算机类型作出假定。这对解出问题的速度影响甚大。 * 确定使用什么样的运算及其执行时间。 * 如何分析非时间囿界于常数的运算？分解成若干时间囿界于常数的运算。 * 对算法进行全面分析，可分两个阶段进行：事前分析、事后测试 * 在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。 * 根据符号O的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界，这个上界的阶越低则评估就越精确，结果就越有价值。所以试图求出最小的g(n)，使得f(n) = Ο(g(n))。 * 指数时间算法只有在n取值非常小时才实用。 当数据集的规模（即n的取值）很大时，在现代计算机上运行具有比O（nlogn）复杂度还高的算法往往是很困难的。尤其是指数时间算法。 * 【例1.9】循环次数间接依赖规模n-变量计数之二。 (1) x=1； (2) for(i=1；i=n；i++) (3) for(j=1；j=i；j++) (4) for(k=1；k=j；k++) (5) x++； 该算法段中频度最大的语句是(5)，从内层循环向外层分析语句(5)的执行次数： 则该算法段的时间复杂度为：T(n)=O(n3/6+低次项)=O(n )。 3 * b.算法的时间复杂度与输入实例的初始状态有关。 这类算法的时间复杂度的分析比较复杂，一般分最好情况（处理最少的情况),最坏情况(处理最多的情况)和平均情况分别进行讨论。 【例1.10】在数值A[0..n-1]中查找给定值K： (1) i=n-1； (2) while( i=0 and A[i]k ) (3) i=i-1； (4) return i； 此算法的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及k的取值有关： 1. 若A中没有与k相等的元素，则(2)频度f(n)=n(最坏情况)； 2. 若A最后一个元素等于k ，则(2)频度f(n)是常数1(最好情况); * 在求平均情况时，一般地假设查找不同元素的概率P是相同的,则算法的平均复杂度为： 若对于查找不同元素的概率P不相同时，其算法复杂度就只能做近似分析，或在构造更好的算法或存储结构后，做较准确的分析。 * 【例1.11】求N！ 构造算法中的两个步骤： 1）N!=N*(N-1)！(n1) 2）0!=1， 1!=1(n=0,1)。 递归算法如下： 以n=3为例，调用过程如下： fact(3)-fact(2)-fact(1)-fact(2)-fact(3) 递 归 回 溯 递归算法分析 * 【例1.11】求N！ 递归方程为： T(n)=T(n-1)+O(1) 其中O(1)为一次乘法操作。 迭代求解过程如下： T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) …… =O(1)+……+O(1)+O(1)+O(1) =n*O(1) =O(n) * 【例1.12】抽象地考虑以下递归方程，且假设n=2k，则迭代求解过程如下： ∴ T(n) =O(n) * 【例1.13】一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时一次跨两个台阶，编写一个算法，计算此人有几种不同的上楼方法，并分析算法的时间复杂度。 解：设计一个递归算法。 H(int n) {