算法复杂度分析

算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)

判断一个算法是不是属于这种时间复杂度的一个简单方法是关注循环执行次数最多的那一段代码，这段代码执行次数对应n的量级，就是整个算法的时间复杂度。如果是一层n的循环，那么时间复杂度就是O(n)；如果嵌套了两层n的循环，那么时间复杂度就是O(n2)，以此类推。

二分查找的时间复杂度通常是O(logn)，一些基于比较的排序算法的时间复杂度可以达到O(nlogn)，典型的有快速排序、归并排序

上面的代码是一个典型的二分查找，由于每次循环都可以将问题的规模缩减一半，其时间复杂度是O(logn)

指数的增长非常恐怖，一个指数阶的算法通常是不可用的，或者存在优化的空间。一个典型的例子是fibonacci数列的递归实现版本

可以看出fibonacci(n)等价于fibonacci(n-1)+fibonacci(n-2)。这一过程可以持续下去，即fibonacci(n-1)等价于fibonacci(n-2)+fibonacci(n-3 )……如果你把上述每一个计算过程看成树的一个节点，那么整个计算过程就像一棵很大的树。一个节点分裂为2个节点，2个节点分裂为4个节点。

算法的时间复杂度和图中树的节点数同阶，而树的节点数的数量级为O(2n)，因此这个算法的时间复杂度是 O(2n)。可以看出其中有许多重复的计算，可以通过存储记忆的方式进行优化

递归树分析是一种将递归过程描述成树结构的方法。初始树只有一个节点，随着每一次递归，树的深度加1。每一层的节点数取决于具体的场景。在得到递归树后，将树每层中的节点求和，然后将所有层的节点求和，就大致可以得出树的总节点数n了。而整个算法的基本操作数等于树上每一个节点的基本操作数t乘以树的总节点个数n。以归并排序为例，它是一个典型的分治算法。其基本过程分成两个阶段：分与合。其中分的过程采用自顶向下的方式，每次将问题规模缩小一半，直到问题规模缩小到寻常情况，即可以被直观解决的情况。合的过程恰好相反，采用自底向上的方式，将问题一步步解决，直到还原到原问题规模。如果你将这两个过程化成递归树的话，就会发现这两个过程递归树的深度都是logn。而每一层的节点数都是n，也就是说总节点数是nlogn，而节点的基本操作数是常数（这一点读者可以通过归并代码发现），因此总的算法时间复杂度为O(nlogn)。

这种分析方法需要一点数学知识，相对来说没有那么直观，这种方法的入手点在于递归公式。比如有如下递归公式：T(n)=T(n-1)+T(0)，如何求解其时间复杂度？T(n)=T(n-1)+T(0)指的是规模为n的问题，可以转化为规模为n-1的子问题和一个常数的操作。我们来尝试代入，就像高中数学那样。T(n)=T(n-1)+T(0)=T(n-2)+T(0)+T(0)=T(n-3)+T(0)+T(0)+T(0)=T(0)+…+T(0)+T(0)+T(0)=n×T(0)可以得出其时间复杂度为O(n)。

注以上内容来自于算法通关之路一书
算法学习推荐书籍：《算法设计与分析》《算法导论》《算法图解》《大话数据结构》《剑指offer》《编程之美》《
算法》