用渐进符号大O表示算法的时间和空间复杂度

工作之余，花点时间总结以前自学过的知识，也有利于新的知识的研究和学习，趁着周末总结了下自己学完后对于时间复杂度等的理解。

一、什么是“大O”

什么是“大O”符号呢？在计算机科学中，采取这样的渐进符号分析算法的复杂性又有哪些用处？

首先，我们先来看下关于“大O”符号的一个定义。

“大O符号（Big O notation）是用来描述函数渐进行为的数学符号”，假设原有的函数程序执行步为T(n)，那么当T(n)=O(f(n))时，当且仅当存在正常数C和n0，使得T(n)≦C*f(n)对于所有n，n≧n0都成立。其中的f(n)这个函数用来描述原来的函数的数量级的渐进上界。使用大O符号时，用的O代表无穷大的渐进，它表示n趋近于无穷大时的一种情况。此时我们把O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。时间复杂度的渐进上界表示如下图所示：

渐近上界

二、举几个例子

（1）sum函数，通过计算可得到程序执行步数为T(n)=2n+3。

Sum函数

这里我们设f(n)=n，那么可以得到

因为对于所有的n≧2（n0=2）时，有2n+3<3n，此时C=3。对于所有的n≧1，都有2n+3≦5n，此时C=5。也就是说C取大于2的任何一个整数时，都可以找到满足条件的n0，使得T(n)≦C*f(n)。这个时候我们就可以把代表程序总执行步数的T(n)用渐进符号描述为O(f(n))，在这里把时间复杂度记为O(n)。

那T(n)的时间复杂度可表示为O(1)吗？显然不行，因为无法找到一个正整数C和n0，使得2n+3<C。其实在该例子中，我们也可以讲T(n)=O(n^2)，因为当n>=3时，有2n+3≦n^2，此时C=1。但为了让该大O更有意义，我们一般选的时f(n)中较小的那一个。我们一般认为，O(f(n))表示算法执行的最低上界。因此对于程序执行步数来说，若得到的n的幂为1次的话，一般时间复杂度都记为大O(n)。

（2）若一个算法计算出来的程序总执行步数为T(n)=4n^2-2n+2，我们来用O来表示它的时间复杂度。

这里我们设f(n)=n^2，可以得到

因此对于所有的n>1，都有4n^2-2n+2<5n^2、6n^2等等，也就是说C取大于1的任何一个整数时，都可以找到满足条件的n0，使得T(n)≦C*f(n)。而且在该函数T(n)中，当n越来越大时，n^2将开始占据主导地位，其它项目也可以忽略包括系数C，因此我们就可以把代表程序总执行步数的T(n)用渐进符号描述为O(f(n))，在这里记为O(n^2)。

（3）来分析一个while循环算法的时间复杂度

while循环

观察算法，无法立即确定while及 i=i*2 运行了多少次。这时可假设运行了 x 次，每次运算后 i 值为 2，2 ^2，2^3，…，2 ^x，当i=n时结束，即 2 ^x＝n时结束，则 x= $log _2n$ ，那么算法的运算次数为 $1+2log_ 2n$ .。同上可得，当n大于某个值时且C取大于2的任何一个整数时，

存在

因此算法的时间复杂度渐近上界为О(f (n))＝О(log n)。

那为什么算法复杂度为О(log n)，而不是写成 $О(log_2 n)$ ，我们不关注log的底是多少呢？其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。

对数图

假设有底数为2和3的两个对数函数，如上图。当x取N（数据规模）时，记

运用换底公式可得： $y=log_2 N/ log_3 N=(lnN/ln2) / (lnN/ln3) = ln3 / ln2$ 。可以发现y的值是一个常数，与变量N无关。也就是说不同的对数底数对应的时间复杂度之比为一个常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。

三、常用函数值

分析算法的时间复杂度时，我们常用的是以下几个常用的函数，注意都是处于数据规模n趋近于无穷大的情况，我们重点关注的就是数据规模。

函数表

其时间复杂度排序为 $O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)$

四、空间复杂度

每个算法的输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。我们通过例子简单介绍下。

swap函数

上图是一个两个数大小的交换算法，从程序中可以发现只使用了一个辅助变量temp，故空间复杂度为O(1)。也就是说如果算法用了多个类似temp这样的辅助变量，那它的辅助空间是常数级的，空间复杂度记为O(1)。

依次类推可以得到若是算法采取了一个数组作为辅助空间，那么空间复杂度是线性阶的，也就是O(n)。如果使用了一个二维数组作为辅助空间，那么空间复杂度是平方阶的，也就是O(n^2)。

在算法空间复杂度分析这一块，最有代表性的就是递归调用算法，这是有空间代价的。来看下列一个最简单的例子：

sum2函数

递归调用该算法时，递归栈空间包括参数，局部变量以及返回地址。假设返回地址只需要一个字节，那么每次递归时至少需要的栈空间为3个字节【该部分涉及堆栈的操作，了解函数运行时堆栈变化便可知道，这里小编不解释】。递归深度为n+1，因此需要的栈空间大于等于3(n+1)，为线性阶，故空间复杂度为O(n)。因此递归的深度为多少，空间复杂度就是多少。

这是小编的一点学习总结，欢迎批评指正。关于递归算法的时间复杂度分析，对二分搜索，树的递归调用等算法会有更好的理解，小编下次也做个总结。