目录

• 1.算法设计与分析概述
• 2.非递归算法分析
• 3.递归算法分析
  
  • 3.1利用数列知识
  • 3.2代入法
  • 3.3递归树
  • 3.4主方法求解递推式
• 4.参考资料

1.算法设计与分析概述

  在总结递归算法的时间复杂度分析之前，应该明确几组概念。
  算法仅仅是求解问题的解决方案，这个解决方案本身并不是问题的答案，而是能获得答案的指令序列。只有通过执行算法才可以获得求解问题的答案。
  从算法是否递归调用的角度看，算法可以分为非递归算法和递归算法。
  非递归算法时间复杂度分析较为简单，通常是计算算法中基本语句执行次数，一般都是一个关于问题规模n的表达式，然后用渐近符号$<![CDATA[Θ、Ο、o、Ω、ω]]>$表示出算法的时间复杂度。
  递归算法是采用分治的方法，把一个“大问题”分解出若干个相似的“小问题”求解。在分析算法复杂度时，关键是根据递归过程建立递推关系式，然后求解递推关系式，得到算法执行的时间表达式（一般都与问题规模n相关），最后用渐近符号$<![CDATA[Θ、Ο、o、Ω、ω]]>$表示出算法的时间复杂度。
  在《算法导论》、《算法设计与分析》这2门课中，我们已经学习一些通用的算法设计技术，如增量法、分治法、贪心法、动态规划、线性规划、回溯法、分支限界法等；在算法设计完成后，对算法的复杂度进行分析是必然的，所以本篇的中心将围绕算法时间复杂度展开。

2.非递归算法分析

例1：如果算法的执行时间不随着问题规模n的增加而增长，它的基本语句执行的次数是固定的，总的时间由一个常数来限界。此类算法的时间复杂度是O(1)。
例2：当有若干个循环语句时，时间复杂度是由嵌套层数最多的循环语句中的基本语句的执行次数决定。如下

void fun(int n){
    int x=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<=j;k++){
                x++;             //基本语句
            }
        }
    }
}

解：该算法的基本语句是x++;所以
$<![CDATA[f(n)=sumlimits_{i=1}^nsumlimits_{j=1}^{i}sumlimits_{k=1}^{j}1=sumlimits_{i=1}^nsumlimits_{j=1}^{i}j=sumlimits_{i=1}^nfrac{i(i+1)}{2}=....=O(n^3)]]>$，时间复杂度为$<![CDATA[O(n^3)]]>$。

虽然非递归算法的时间复杂度比较好分析，但往往需要用到多项式的求和技巧和放缩技巧，如：

1. 等差数列$<![CDATA[left{a_kright}]]>$求和：$<![CDATA[sumlimits_{k=1}^na_k=frac{n(a_1+a_n)}{2}]]>$
2. 等比数列$<![CDATA[left{aq^kright}]]>$求和：$<![CDATA[sumlimits_{k=0}^naq^k=frac{a(1-q^{n+1})}{1-q}]]>$
3. 调和级数$<![CDATA[left{ frac{1}{k} right}]]>$求和：$<![CDATA[sumlimits_{k=1}^nfrac{1}{k}=lnn+O(1)]]>$（需要用微积分知识证明）
4. 对数级数$<![CDATA[lg 1+lg 2+...+lg n=lg(n!)=Θ(nlg n)]]>$（利用Stirling公式证明）
5. 放缩1：用序列中的最大项代替序列中的每个项，这种方法可以表示为：$<![CDATA[sumlimits_{k=1}^na_k≤na_{max}]]>$
6. 放缩2：在等比数列中，假设存在常数$<![CDATA[r<1]]>$，使得$<![CDATA[frac{a_{k+1}}{a_k}≤r]]>$对一切$<![CDATA[k≥0]]>$成立，那么有：
   ∑k=0nak≤∑k=0∞a0r

   版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
   原文链接：https://blog.csdn.net/so_geili/article/details/53444816
   站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

   • 发表于 2020-03-01 21:44:27
   • 阅读 ( 1084 )
   • 分类：算法
   0 推荐 收藏