外行人也能看懂的时间复杂度计算

什么叫时间复杂度

维基百科给出的解释：

算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。

简单一句话，时间复杂度是一个以输入值长度为参数的函数。

为什么不直接使用运行时间呢？

程序的运行时间依赖硬件，操作系统，编程语言，软件环境等各种因素。

同样的一个算法的运行时间，在不同电脑，甚至同一台电脑都会不同。

下面是我在Leetcode运行同一个算法的运行时间，可以看到有9ms的差。所以运行时间是不可靠的而且无法作为衡量算法效率的标准。

所以我们假设所有基本操作的运行时间都是常数。

基本操作就是那些在同一电脑环境，用同一语言实现的命令，他们的运行时间是不变或变化很小。所以依赖用户输入以及网络等的命令不属于基本操作。

这样我们只属于找出算法中基本操作的数量就可以得到时间复杂度。

还有一个问题是在同样输入值长度的算法，可能基本操作数不同，那么我们通常返回最坏情况即最大的数量。

以这个算法为例，假设所有基本操作的运行时间都为常数C，如果x的第一个元素为1，那么基本操作数为:

行2+行3+行4+行8=4C

如果x的第一个元素不为1，那么基本操作数为:

行2+行3+行5+（行6循环次数*（行7+行6））+行8=2nC+4C, 假设n为x的长度。

这时候我们会发现一个问题，这样子计算需要找到所有的基本操作，特别对于else，和for他们是否应该算入基本操作呢。整个计算过程有点复杂。

维基百科给出的解释：

大O符号（英语：Big O notation），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；

简单说就是，当输入值的长度趋近于无穷大时，取时间复杂度函数的最大项。并且删除最大项前的常数。

比如 $2n^2+5n+4$ ，当n无穷大时， $2n^2 >5n>4$ ,所以最大项为 $2n^2$ . 除去前面的常数2，大O表示法为 $O(n^2)$ 。

同样的算法，我们只需要找到其中的循环次数最多的那条基本操作, 也就是位于最内层循环的一条语句就可，在cal中就是行7。计算它循环的次数。所以cal的时间复杂度大O表示法为O(n)。