时间复杂度

请原谅我也是一个标题党！

关于时间复杂度和空间复杂度分析的文章其实不少，但大多数都充斥着复杂的数学计算，让很多读者感到困惑，我就不跟大家扯皮了，关于什么是渐近分析、最坏时间复杂度、平均时间复杂度和最好的时间复杂度，以及大  记法等等，大家好好花点儿时间看看严老师的书就会了。

我们从代码和实现的层面讲讲，如何计算你写的代码的时间复杂度？

任何一门语言的逻辑结构无非三种：顺序结构、循环结构和分支结构，但是真正影响到时间复杂度只有循环结构，如果分支结构影响复杂度，也是因为分支内部包含了循环。

循环的实现有 for 和 while 两种形式，但是本质都是一样的，我们接下来均以for 循环进行说明。

如果一个函数（语句）不包含循环、迭代或非常数时间的函数，则可以认为函数为 的时间。

比如交换两个数的 swap() 函数的时间复杂度就是O(1)  : 

一个循环如果仅仅运行常数次，那么时间复杂度也可以当作 O(1) 来处理：

如果循环控制变量 i 递增/递减的步长为一个常数c  ，则认为循环的时间复杂度为 O(n) 。例如，以下函数的时间复杂度为 O(n) ：

，嵌套循环的时间复杂度等于最内层语句的执行次数。例如，下面示例循环的时间复杂度为  ： 

如果循环控制变量 i 乘以或除以一个常数  ，则循环的时间复杂度为  量级： 

简单地分析一下，循环控制变量到达 n 的顺序为  ，如果我们令  ，那么   ，也就是循环到达 n 仅仅会执行 次，复杂度自然为 量级。

比如二分查找（binary search）的迭代实现的时间复杂度就是  ：

如果循环控制变量 i 以指数级别增加或者减少，则时间复杂度为 量级。

情况一：

这种情况下，i 的取值为  ，而最后一项一定小于等于 n，即   ，也就是说循环执行了  次，每一次迭代的时间为常数时间，则上面的迭代总的时间复杂度为 量级。

情况二：

i 的取值为，  ，所以迭代总共执行 次，时间复杂度为  量级。

如果程序中包含多个循环，又该如何时间复杂性？

如果程序中存在多个连续循环时，时间复杂度为多个单循环的时间复杂度之和。

上面程序的时间复杂度为  ，当  时，则  ，依旧是O(n)  量级。

如果循环内部包含大量的 if...else... 语句时，又该如何计算时间复杂度？

在最好、平均和最差时间复杂度中，我们一般只关注最坏时间复杂度。考虑最坏的情况，当if...else... 条件中的语句导致执行时间复杂度的增加，就需要将其计算到最坏时间复杂度中。

例如，考虑上面的线性搜索函数，其中我们考虑元素出现在数组 arr[] 的末尾或根本不存在的情况，分别对应  和  的时间复杂度，但是我们仅关注最坏的时间复杂度  。

当代码太复杂而无法考虑所有 if...else 情况时，我们可以忽略 if...else 和其他复杂的控制语句来计算最坏情况下的时间复杂度。

递归算法的时间复杂度又该如何计算？

很多算法都是基于递归思想的，我们分析这些递归算法，可以得到关于时间复杂度的递归关系式。比如 「归并排序」 的时间复杂度一般表示为  ，还有二分查找，汉诺塔问题等等，但是关于递归的时间复杂度并不简单。

对于递归的时间复杂度的计算主要有三种方式：