初识数据结构之算法的时间复杂度和空间复杂度

空间复杂度：

根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

我们要处理一个变量N，如下面程序，要输出0-N之间的所有整数。

由于这是一个递归程序，加入N=100000，那么在程序结束之前要在存储空间中存下所有1-100000的所有数据。如图：

就是说内存需要的空间随着N做线性增长。所以空间复杂度可以用一个常数*N来表示。即：

时间复杂度：

根据算法写成的程序在执行时耗费时间的长度。这个长度往往与输入数据的规模有关。时间复杂度过高的算法可能导致我们在有生之年都等不到运行的结果。

数据运算主要是做加减乘除四则运算，而计算机做加减法的速率比乘除法要快的多，加减法可以忽略不计，所以时间复杂度主要是看程序做了多少次乘除法运算。

比如上面是一个多项式的运算的程序，主要的运算都是在for循环里面做的，pow(x,i)求的是x的i次方，所以做了i-1次乘法，再加上最前面乘以a[i]的一次，每一个for循环里面做了i次乘法，一共n次循环，所以一共做了次乘法。用时间复杂度表示为：

第二个程序是求同一个多项式运算的程序，这个程序里面每次for循环只做了一次乘法，所以一共做了n次乘法。用时间复杂度表示为

比较上面两个程序，虽然不知道C1,C2和C分别为多少，但是当n足够大时，n²远远大于n，所以这个时候第一个程序的时间复杂度要大于第二个程序的时间复杂度！

复杂度的渐进表示法：

        当我们在分析算法复杂度的时候，其实是没有必要分析这个算法把什么操作做了多少次的，我们只需要知道随着处理数据规模的增大，这个复杂度增长的性质会怎么样就足够了。比如说比较前面两个算法的时候，我们只要知道当n足够大的时候，T1是n²在起主要作用，T2是n在起主要作用，所以在n足够大的时候T1肯定比T2大就可以了。

        所以就有了复杂度的渐进表示法：

        我们如果把一个时间复杂度T(n)写成是一个O(f(n))的形式，即表示存在常数C>0，>0使得当的时候，f(n)大概表现的是T(n)的一个上界，即。简单表示来说对于充分大的n而言，O(f(n))表示f(n)是T(n)的某种上界。

        类似的，如果是一个的形式，表示存在常数C>0，>0使得当的时候，g(n)就是T(n)的某种下界，即。

        如果是的形式，那就表示对于这个里面的函数来说，O和Ω是同时成立的，它既是上界也是下界。即同时有和。

上面关于时间复杂度的渐进表示法同样适用于空间复杂度。但是我们要注意到一个函数的上界和下界并不是唯一的，比如一个算法的复杂度是n的常数倍，那么我们既可以把它写成O(n)，也可以写成O(n²)，还可以写成O(n³)...下界也是一样。但是太大的上界和太小的下界对于分析算法的效率而言是没有什么帮助的。我们在分析算法效率的时候希望它的上界和下界和真实情况越贴近越好，所以我们一般在写的时候通常写的是我们能力范围内找到的最小的上界和最大的下界。

下面三张图分别为不同函数的增长速度数值表、不同函数增长速度线形图和每秒10亿指令计算机的运行时间表可供参考。

不同函数随着n的增长的增长速度 不同函数的增长速率 每秒10亿指令计算机的运行时间表