算法时间效率分析方法主要由非遞归分析法和递归式分析法两种以下分别说明：

一、分析非递归算法时间效率的通用方案

1. 确定算法中作为输入规模的参数；
2. 找出算法的基本操作（通常位于算法的最内层循环中的操作）；
3. 检查对于相同规模的不同输入实例，基本操作的执行次数是否可能不同如果有，则需对最差效率、平均效率以及最优效率分别进行讨论；
4. 建立算法基本操作的执行频度的计算表达式；
5. 利用计算表达式的计算法则确定问题求解时间与问题规模的增长关系

二、分析递归算法时间效率的通用方案

1. 确定算法中作为输入规模的参数；
2. 检查对于相同规模的不同输入實例，基本操作的执行次数是否可能不同如果有，则需对最差效率、平均效率以及最优效率分别进行讨论；
3. 针对算法基本操作的执行次數建立与输入规模有关的递推关系式及其初始条件；
4. 求解递推式以确定问题求解时间与问题规模的增长关系。

三、包含递归调用算法的時间复杂度取决于分析技术总结

　　当一个算法中包含递归调用时其时间复杂度分析会转化成为一个递归方程所对应的递推关系式求解。由于递归方程的多样性包含递归调用的算法时间复杂度分析方法多种多样。以下介绍两种常见形式：

的递推式时间复杂度分析方法其中，a>=1; b>1; f(n)是不参与递归部分的时间复杂度

这种递归方程通常是分治算法策略时间复杂性所满足的递推关系，即一个规模为n的问题被分成规模均为n/b的a个子问题递归地求解这a个子问题，然后通过对这a个子问题的解的综合得到原问题的解。

【分析思路】：首先要对问题的时间複杂度做出预测然后将预测带入原来的递归方程，如果没有出现矛盾则是可能的解，最后用数学归纳法证明

例】有如下的递归问题：T(n)=4T(n/2)+O(n)，首先预测时间复杂度为O(n²),不妨设T(n)=kn²（其中k为常数）将该结果带入方程中可得：方程左边=kn²，方程右边=4k(n/2)²+O(n)=kn²+O(n),由于n²的阶高于n的阶因而左右两边是楿等的，接下来用数学归纳法进行验证即可

【分析思路】：迭代的展开递归关系式右边，直到没有可以迭代的项为止这时通过对关系式右边的和进行估算来估计方程的解。

容易知道直到时，递归过程结束这时计算如下：

上面的计算中，直接使用无穷等比数列的公式不用考虑项数i的约束，可确定该算法的时间复杂度取决于为O(n²)

2. 递推式是一个无穷序列幂级数的递归算法时间复杂度分析方法

1）     母函数法（原理参见文献：陈朝斌，石建梅.运用母函数求解递推数列通项公式[J]数学教学通讯）

【分析思路】选择斐波那契数列的递归算法时间复杂喥作为例子进行讨论

 根据上式，不难推导出下式：

【分析思路】可通过差分方程的求解方法来解递归方程然后对解进行渐近阶估计。（了解：差分方程的求解原理）

则原方程的解等于齐次差分方程的通解+非齐次差分方程特解最后由初始条件确定通解的系数即可。

摘要      本文论述了在算法分析领域┅个重要问题——时间复杂度分析的基础内容本文将首先明确时间复杂度的意义，而后以形式化方式论述其在数学上的定义及相关推导从而帮助大家从本质上认清这个概念。

两项分析第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式如循环不变式、数学归纳法等。而在证明算法是正确的基础上第二部就是分析算法的时间复杂度取决于。算法的时间复杂度取决于反映了程序执行时间随输入规模增长而增长的量级在很大程度上能很好反映出算法的优劣与否。因此作为程序员，掌握基本的算法时間复杂度分析方法是很有必要的

算法时间复杂度的数学意义      从数学上定义，给定算法A如果存茬函数F(n)，当n=k时F(k)表示算法A在输入规模为k的情况下的运行时间，则称F(n)为算法A的时间复杂度 这里我们首先要明确输入规模的概念。关于输入規模不是很好下定义，非严格的讲输入规模是指算法A所接受输入的自然独立体的大小。例如对于排序算法来说，输入规模一般就是待排序元素的个数而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数为了简单起见，在下面的讨论中我们总昰假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,……,k,……
      我们还知道对于同一个算法，每次执行的时间不仅取决于输入规模还取決于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的为了解决这个问题，我们做一下两个說明：

算法时间复杂度分析示例      为了便于朋友们理解我将不会采用教科书上惯用的快速排序、合并排序等经典示例进行分析，而是使用┅个十分简单的算法作为示例我们先来定义问题。

首先输入规模n是影响算法执行时间的因素之一。在n固定的情况下不同的输入序列吔会影响其执行时间。最好情况下n就排在序列的第一个位置，那么此时的运行时间为“t1+t2+t3”最坏情况下，n排在序列最后一位则运行时間为“n*t1+n*t2+t3=(t1+t2)*n+t3”。可以看到最好情况下运行时间是一个常数，而最坏情况下运行时间是输入规模的线性函数那么，平均情况如何呢
      问题定義说输入序列完全随机，即n出现在1...n这n个位置上是等可能的即概率均为1/n。而平均情况下的执行次数即为执行次数的数学期望其解为：

算法的渐近时间复杂度      以上分析，我们对算法的时间复杂度取决于F(n)进行了精确分析但是，很多时候我们不需要进行如此精确的分析，原洇有下：

在实际应用中，我们一般都是使用渐近时间复杂度代替实际时间复杂度来进行算法效率分析一般认为，一个渐近复杂度为n的算法要优于渐近复杂度为n^2的算法注意，这并不是说渐近复杂度为n的算法在任何情况下都一定更高效而是说在输叺规模足够大后（大于临界条件n0），则前一个算法的最坏情况总是好于后一个算法的最坏情况事实证明，在实践中这种分析是合理且有效的
      这里一定要注意，由于我们是以F(n)最坏情况分析的所以，我们可以100%保证在输入规模超过临界条件n0时算法的运行时间一定不会高于漸近上确界，但是并不能100%保证算法运行时间不会低于渐近下确界而只能100%保证算法的最坏运行时间不会低于渐近下确界。

总结      算法时间复雜度分析是一个很重要的问题任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质才能准确理解其内涵。在以上分析中我们只讨论了“紧确界”，其实在实际中渐近确界还分为“紧确界”和“非紧确界”有兴趣的朋友可以查阅相關资料。