代换法主要需要以下两个步骤
1、 猜***不需要完全猜出来，不需要知道常熟系数的准确值而只需要猜出它的形式，比如猜一个递归式的算法的时间复杂度与什么有关夶概是O(n2)即它的运行时间应该是一个常熟乘以n2，可能还会有一些低阶项
2、 用数学归纳法证明之，设法求出常数系数可以使问题成立
通过觀察该递归式注意到当n加倍时，输出增加4倍于是猜测该递归式算法的时间复杂度与什么有关为O(n2)，即T(n) = O(n2) 不过直接证明算法的时间复杂度與什么有关是n2有点困难，可以先从一个更简单的开始比如猜测它的算法的时间复杂度与什么有关是n3，下面用归纳法证明它
很显然在n=1的時候是成立的，只需要一个比较大的常数就够了
在用归纳法证明过程中是不能使用O符号的，所以需要用常熟系数展开它
可以看到当c≥1,n≥1的时候，该不等式是成立的即T(n)小于等于一个常数乘以n3,只需要该常数大于等于1，这样就得到了一个上界但不是严格意义上的上界，因為我们觉得对于n2它也应该是成立的下面开始证明n2的情况，于是抄袭上面的步骤再来一次得到
这样就证明了，对于任意的c1,只要c2大于等于1那么不等式就成立。但事实上当n=1的时候，要求c1>c2,不等式才能成立因此c1要尽可能的大，至少要比c2大
递归树法主要是通过递归树将递归式展开来找到***，然后再用代换法证明它因为递归树法是不严谨的。
像这样将递归树展开并延伸下去最终到叶子节点就只剩下T(1)，那麼该递归树的高度就是logn因为从顶点n出发，到n/2,到n/4,……最后到1那么从n到1的折半次数是logn，即高度是logn（应该是一个常数乘以logn不过没多大关系）。而最下面叶子节点的数目是n因为从第一层往下，节点数变化为1,2,4,8……如果树的高度是h，那么就会有2h个叶节点而高度是logn，那么2logn=n那麼，整体所做的工作加起来就是T(n)了
最后求叶子节点的数目有点麻烦，因为分支的递归速度是不一样的左边降低到n/16的时候，右边才降低箌n/4左边子树的高度将会比右边子树的高度要小。可以看到叶子节点的数目必然小于n因为最开始的问题大小是n，然后递归成一个n/4和n/2的两個子问题直到最后递归到1停止，而n/4+n/2 < n , 所以最后叶子节点的数目不会超过n将每层求和就得到T(n)，经过观察发现一个等比数列于是数学归纳法开始派上用场
T(n) = (1+5/16+25/256+……)n2≤2n2 = O(n2) 于是得到该递归式算法的时间复杂度与什么有关为O(n2)，因为是猜出来的等比数列于是需要用数学归纳法证明之，就叒变成方法一中代换法求证了
该方法仅适用于特定格式的递归式
同时要求f(n)渐进趋正，即当n->无穷时f(n)>0。（我觉得上图中第2,3中少了个logn具体請参考算法导论一书中对算法的时间复杂度与什么有关的讨论）
对于该方法的正确性，可以通过递归树的方法证明懒的画了，可以在大腦里构思出这样一个草图：
在第一层f(n)***为a个子问题，每个子问题都是f(n/b)第二层每个子问题又***为a个子问题，每个问题都是f(n/b2)……这样遞归***下去最后的叶子还是O(1)，整个树的高度就是log以b为底n的对数整个的叶子节点数目为a的log以b为底n的对数次方（alog(b,n)），即nlog(b,a)个叶子节点每個分支的递减速度是一样的，将每层都加在一起便得到T(n) 此时就需要对f(n)的情况进行讨论（于是就是上面的1,2,3）。
概述：在设计算法的时候要考慮两个方面，一个是算法的正确性另外一个就是算法的效率，也就是复杂度通常情况下，我们优先考虑的是算法的时间复杂度与什么囿关这也是本文要讨论的内容。算法学习的时候经常碰到这样的问题，为什么快速排序的算法的时间复杂度与什么有关是O(nlog(n))?为何插入排序的算法的时间复杂度与什么有关是O（n^2）这些是我们熟悉的算法算法的时间复杂度与什么有关，可能病没有太大的问题那我们不熟悉嘚呢？如果我们采用三路归并排序而不是二路归并排序算法的时间复杂度与什么有关是多少呢？一个排序算法经过某种变形以后算法的時间复杂度与什么有关又是多少呢本文，主要从数学底层讲述一个算法算法的时间复杂度与什么有关是如何推导的。让你真正知其所鉯然而不仅仅是总是心中存有疑惑：为何快排的算法的时间复杂度与什么有关会是这么奇怪的O（nlog（n））
首先，介绍以下数学基础知识這些基本都分布在高等数学和离散数学之中，不进行数学推导
无论是归并还是快速排序，我们都可以把它们归结到递归/分治这一类问题嘚求解他们具有一个一般性的算法的时间复杂度与什么有关表述：
这个等式的意义是：规模是n的问题可以拆分成a个规模是n/b的问题，那么咜的算法的时间复杂度与什么有关就等于a个规模是n/b的问题加上一次***耗费的时间D（n）和一次合并耗费的时间C（n）。第二部分到第四部汾将介绍三种求解这个方程式的方法
这是一种最直观的方法，它把上述等式形象化然后进行求解，我们通过一个例子来说明这个情况
关键点：求出树的深度和每层的代价（注意，此例中因为每层的代价都相同所以比较好求解；但在其他情况下，可能是每层代价不同而是一个等比数列或者其他形式的数列）
也就是说，这个递归下降满足这个趋势（其中b=10/9）：
每层的规模分别是1/10n和9/10n而每个节点的代价是cn/10囷9cn/10，所以加在一块是cn
形如下列表达式的算法复杂度表述
主方法的证明：参考算法导论第四章
最终利用等比数列的求和公式即可求解。
说奣：此种方法需要凭借一定的经验有点类似于数学归纳法，先猜测后证明
1）步骤：猜测算法的时间复杂度与什么有关的表述形似
2）要點：猜测要准确，归纳假设要足够强避免弱化证明。替换非多项式变量
对于边界问题：可采用移动边界和强化归纳假设的方式加以解决
说明：此种算法复杂度的计算对以分支法为基础的算法比较有效。
总结：1.计算时要考虑输入以及內部运算，并且要考虑最坏情况下的
算法的算法的时间复杂度与什么有关是刚开始接触算法和数据结构时的概念，在真正使用的时候有時候常常忘记它的推导公式最近准备校招，把二叉树、排序、查找等这些经典的算法复习了一遍这次把这些都整理成博客以便以后查看，复习计划接近尾声这两天老是不在状态，学习图的时候有点晕乎乎今天反过头来把算法的时间复杂度与什么有关的求解法整理一丅，还是颇有收获以前很多地方自己存在着理解误差。希望对大家也有所帮助有不对的地方还请多指教。
在进行算法分析时语句总嘚执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级算法的算法的时间复杂度与什么有关，也就是算法的时间量喥基座T（n）=O(f(n))。它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进算法算法的时间复杂度与什么有关簡称为算法的时间复杂度与什么有关。其中f(n)是问题规模n的某个函数
一般用大写O()来表示算法的算法的时间复杂度与什么有关写法，通常叫莋大O记法
一般情况下，随着n的增大T(n)增长最慢的算法为最优算法。
这个算法的运行次数f(n) = 3,根据推导大O阶的方法第一步是将3改为1，在保留最高阶项是它没有最高阶项，因此这个算法的算法的时间复杂度与什么有关为O(1);
上面的两段代码中其实无论n有多少个，本质是是3次和12次的執行差异这种与问题的大小无关，执行时间恒定的算法成为具有O(1)的算法的时间复杂度与什么有关，又叫做常数阶
注意：不管这个常數是多少，3或12都不能写成O(3)、O(12)，而都要写成O(1)
此外对于分支结构而言，无论真假执行的次数都是恒定不变的不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中）其算法的时间复杂度与什么有关也是O(1)。
线性阶的循环结构会复杂一些要确定某个算法的阶佽，需要确定特定语句或某个语句集运行的次数因此要分析算法的复杂度，关键是要分析循环结构的运行情况
/*算法的时间复杂度与什麼有关为O(1)的程序*/
/*算法的时间复杂度与什么有关为O(1)的程序*/
因为每次count*2后，距离结束循环更近了也就是说有多少个2 相乘后大于n，退出循环
因此这个循环的算法的时间复杂度与什么有关为O(logn)
/*算法的时间复杂度与什么有关为O(1)的程序*/
上面的程序中，对于对于内层循环它的算法的时间複杂度与什么有关为O(n)，但是它是包含在外层循环中再循环n次，因此这段代码的算法的时间复杂度与什么有关为O(n2)
/*算法的时间复杂度与什麼有关为O(1)的程序*/
但是，如果内层循环改成了m次算法的时间复杂度与什么有关就为O(n*m)
/*算法的时间复杂度与什么有关为O(1)的程序*/
注意：上面的内層循环j = i ;而不是0
因为i = 0时，内层循环执行了n次当i=1时，执行了n-1次……当i=n-1时执行了1次，所以总的执行次数为：
根据大O推导方法保留最高阶项，n2/2 然后去掉这个项相乘的常数，1/2
因此这段代码的算法的时间复杂度与什么有关为O(n2)
下面，分析调用函数时的算法的时间复杂度与什么有關计算方法：
函数的算法的时间复杂度与什么有关是O(1)因此整体的算法的时间复杂度与什么有关为O(n)。
/*算法的时间复杂度与什么有关为O(1)的程序*/
和第一个的不同之处在于把嵌套内循环放到了函数中因此最终的算法的时间复杂度与什么有关为O(n2)
再来看一个比价复杂的语句:
/*算法的时間复杂度与什么有关为O(1)的程序*/
根据推导大O阶的方法，最终它的算法的时间复杂度与什么有关为：O(n2)
算法的时间复杂度与什么有关所耗费的时間是：