算法分析与计算复杂性.pptx

7.6算法分析与计算复杂性算法是正确的吗？算法的模拟与分析1.算法正确吗？ ①问题求解过程、方法正确吗？输出的是不是问题的解？ ②20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中。算法获得的解是最优的吗？算法的效果评价 ①算法输出的是最优解还是可行解？如果是可行解，与最优解的偏差多大？ ②证明：（1）利用数学方法 （2）仿真模拟分析算法的复杂性评价方面：时间，空间 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。时间复杂性 时间复杂度的定义 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。通常只考虑三种情况下的时间复杂度，即最坏情况、最好情况和平均情况下的时间复杂度，分别记为T max (N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是最坏情况下的时间复杂度。算法的复杂性分析示例 在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。分析：1.语句int num1, num2;的频度为1；语句i=0;的频度为1；语句in; i++; num1+=1; j=1; 的频度为n；语句j=n; j*=2; num2+=num1;的频度为n*log2n；T(n) = 2 + 4n + 3n*log2n2.忽略掉T(n)中的常量、低次幂和最高次幂的系数f(n) = n*log2n3.lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3当n趋向于无穷大，1/n趋向于0，1/log2n趋向于0所以极限等于3。T(n) = O(n*log2n)1) 加法规则 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )2) 乘法规则 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))3) 一个特例（问题规模为常量的时间复杂度） 在大O表示法里面有一个特例，如果T1(n) ＝ O(c)， c是一个与n无关的任意常数，T2(n) = O ( f(n) ) 则有T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )也就是说，在大O表示法中，任何非0正常数都属于同一数量级，记为O(1)。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。Thank you~