【进阶之路】算法的时间复杂度与空间复杂度

.markdown-body{word-break:break-word;line-height:1.75;font-weight:400;font-size:15px;overflow-x:hidden;color:#333}.markdown-body h1,.markdown-body h2,.markdown-body h3,.markdown-body h4,.markdown-body h5,.markdown-body h6{line-height:1.5;margin-top:35px;margin-bottom:10px;padding-bottom:5px}.markdown-body h1{font-size:30px;margin-bottom:5px}.markdown-body h2{padding-bottom:12px;font-size:24px;border-bottom:1px solid #ececec}.markdown-body h3{font-size:18px;padding-bottom:0}.markdown-body h4{font-size:16px}.markdown-body h5{font-size:15px}.markdown-body h6{margin-top:5px}.markdown-body p{line-height:inherit;margin-top:22px;margin-bottom:22px}.markdown-body img{max-width:100%}.markdown-body hr{border:none;border-top:1px solid #ddd;margin-top:32px;margin-bottom:32px}.markdown-body code{word-break:break-word;border-radius:2px;overflow-x:auto;background-color:#fff5f5;color:#ff502c;font-size:.87em;padding:.065em .4em}.markdown-body code,.markdown-body pre{font-family:Menlo,Monaco,Consolas,Courier New,monospace}.markdown-body pre{overflow:auto;position:relative;line-height:1.75}.markdown-body pre>code{font-size:12px;padding:15px 12px;margin:0;word-break:normal;display:block;overflow-x:auto;color:#333;background:#f8f8f8}.markdown-body a{text-decoration:none;color:#0269c8;border-bottom:1px solid #d1e9ff}.markdown-body a:active,.markdown-body a:hover{color:#275b8c}.markdown-body table{display:inline-block!important;font-size:12px;width:auto;max-width:100%;overflow:auto;border:1px solid #f6f6f6}.markdown-body thead{background:#f6f6f6;color:#000;text-align:left}.markdown-body tr:nth-child(2n){background-color:#fcfcfc}.markdown-body td,.markdown-body th{padding:12px 7px;line-height:24px}.markdown-body td{min-width:120px}.markdown-body blockquote{color:#666;padding:1px 23px;margin:22px 0;border-left:4px solid #cbcbcb;background-color:#f8f8f8}.markdown-body blockquote:after{display:block;content:""}.markdown-body blockquote>p{margin:10px 0}.markdown-body ol,.markdown-body ul{padding-left:28px}.markdown-body ol li,.markdown-body ul li{margin-bottom:0;list-style:inherit}.markdown-body ol li .task-list-item,.markdown-body ul li .task-list-item{list-style:none}.markdown-body ol li .task-list-item ol,.markdown-body ol li .task-list-item ul,.markdown-body ul li .task-list-item ol,.markdown-body ul li .task-list-item ul{margin-top:0}.markdown-body ol ol,.markdown-body ol ul,.markdown-body ul ol,.markdown-body ul ul{margin-top:3px}.markdown-body ol li{padding-left:6px}.markdown-body .contains-task-list{padding-left:0}.markdown-body .task-list-item{list-style:none}@media (max-width:720px){.markdown-body h1{font-size:24px}.markdown-body h2{font-size:20px}.markdown-body h3{font-size:18px}}

因为最近在学习软件设计师、正巧遇上了概念性的算法题。因为之前学习并不系统的原因，虽然能做题，但是却不是非常了解算法中时间复杂度。本着研究学习的心理，这几天就开始研究算法中的时间复杂度，还真学到了一些东西。

一、时间复杂度

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个与代码语句的执行次数而成正相关的函数，它定性描述该算法的运行时间。假设每条语句执行消耗的时间一致，那么执行次数越多，消耗的时间自然就多，而时间复杂度自然就高。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的(可以理解为在问题规模n趋于无穷大时算法时间复杂度T(n)的渐进上界，即得出函数T(n)的数量级(后面的例子就是它的数量级))，亦即考察输入值大小趋近无穷时的情况。

• 1、时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但是我们没有要对每个算法都上机测试。有经验的程序员只需看一看就能知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
• 2、时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

Landau符号(大O符号)其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。

所以，在其他条件不变的情况下，选择时间复杂度低的算法更有利于提高程序的效率。大家不要觉得算法这东西没有用，觉得是顶尖的程序员才用得到。其实我们在工作中，要经常根据情况新增许多工具类，这些解决具体问题的工具类往往又要涉及到递归、循环、排序、动态规划等问题。对于我们来说，能够实现功能就够了，但是如果能进一步地降低这些工具类的时间复杂度，或许能让我们感觉到自己的价值吧。

二、时间复杂度

常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n²), k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

从大佬那边拿到图片

1、常数阶O(1)

int a = 1;
int b = 2;
int c = 3;

我们假定每执行一行代码所需要消耗的时间为1个时间单位，那么以上3行代码就消耗了3个时间单位。O(1)的1代表的是常数，常数阶的算法的复杂度是不会随着问题规模的增大而增大，这样的代码不管有多少行，都可以用O(1)来表示它的时间复杂度。

2、对数阶O(logN)

int i = 1;
while(i < n) {
    i = i * 2;
}

从数学上我们可以很简单的看出它的函数：

2^f(n)<=n,所以f(n)<=log2n

每次循环的时候 i都会乘2，那么总共循环的次数就是log2n，因此这个代码的时间复杂度为O(log2n)。但是，底数如何对于程序运行的效率来说并不重要，就和之前的常数阶一样，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。

如果这样不好理解，我们可以用二叉树来表示。如果二叉树的是以红黑树等平衡二叉树实现的，则n个节点的二叉排序树的高度为 log2n+1 ，其查找效率为O(Log2n)，近似于折半查找。

3、线性阶O(n)

for(i = 0; i 复制代码

这段代码会执行多少次呢？如果从代码上来看，每一行都会执行n次（或者n-1次），所以最后会执行 T(n)=n+3(n-1)=4n-3次。 我们知道：大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。所以线性阶O(n)的时间复杂度其实是O(n);

4、线性对数阶O(nlogN)

for(m = 1; m < n; m++) {
    i = 1;
    while(i < n) {
        i = i * 2;
    }
}

线性对数阶O(nlogN) 就非常非常容易理解了，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n*O(logN)。

5、平方阶O(n²)

for(i = 1; i <= n; i++){
   for(j = 1; j <= n; j++) {
       j = i;
       j++;
    }
}

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

6、立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，O(n^k)就是k层循环。

三、空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。与时间复杂度相类似的，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。 

-1 、固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。 

-2 、可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

1、空间复杂度 O(1)

int i = 1;
int j = 1;
int k = i + j;

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。 i、j、k所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

2、空间复杂度 O(n)

int[] m = new int[n]
for(i = 0; i 复制代码

这段代码的第一行new了一个数组出来，这个数据占用的大小为n，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)，同时时间复杂度也是O(n)。

间复杂度取决于额外创建的数组m，如果使用二维数组 new int[n][m] ，则空间复杂度是 O(n*m)

四、复杂度的选择

对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为3种情况。

• 1、最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。如已经证明基于比较的排序算法的时间复杂度下限为O(nlog2n)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度的算法。
• 2、最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它给我们提供一个保障，实际情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且对于许多算法来说，平均情况通常与最坏情况下的时间复杂度一样。
• 3、平均情况。算法的平均运行时间，一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行：
  • 1 将所有的输入按其执行时间分类。
  • 2 确定每类输入发生的概率。
  • 3 确定每类输入发生的概率。

算法很重要的一点就是时间换空间或者空间换时间。

当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间。

反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。