算法时间复杂度和空间复杂度计算

87 阅读 0 评论 58 点赞

我是靠谱客的博主奋斗往事，最近开发中收集的这篇文章主要介绍算法时间复杂度和空间复杂度计算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是算法

算法的定义是这样的：解题方案的准确而完善的描述，是一系列解决问题的清晰指令。巴拉巴拉的，虽然是一小句但还是不想看（题外话：有时候吧专业名词记下来面试的时候还是挺有用的），其实就是解决一个问题的完整性描述。只不过这个描述就可能是用不同的方式或者说是“语言”了。

算法的效率

既然算法是解决问题的描述，那么就像一千个人眼中有一千个阿姆雷特他大姨夫一样，解决同一个问题的办法也是多种多样的，只是在这过程中我们所使用/消耗的时间或者时间以外的代价（计算机消耗的则为内存了）不一样。为了更快、更好、更强的发扬奥利奥..哦不，提高算法的效率。所以很多时候一个优秀的算法就在于它与其他实现同一个问题的算法相比，在时间或空间（内存）或者时间和空间（内存）上都得到明显的降低。

所以呢，算法的效率主要由以下两个复杂度来评估：

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时，时间复杂度要比空间复杂度更容易出问题，所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话，复杂度就是指时间复杂度。

1.0 空间复杂度
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。

2.0 - 时间复杂度

接下来我们还需要知道另一个概念：时间频度。这个时候你可能会说：“不是说好一起学算法吗，这些东东是什么？赠品吗？”。非也非也，这是非卖品。

因为一个算法执行所消耗的时间理论上是不能算出来的，没错正是理论上，so我们任然可以在程序中测试获得。但是我们不可能又没必要对每个算法进行测试，只需要知道大概的哪个算法执行所花费的时间多，哪个花费的时间少就行了。如果一个算法所花费的时间与算法中代码语句执行次数成正比，那么那个算法执行语句越多，它的花费时间也就越多。我们把一个算法中的语句执行次数称为时间频度。通常（ps:很想知道通常是谁）用T(n)表示。

在时间频度T(n)中，n又代表着问题的规模，当n不断变化时，T(n)也会不断地随之变化。为了了解这个变化的规律，时间复杂度这一概念就被引入了。一般情况下算法基础本操作的重复执行次数为问题规模n的某个函数，用也就是时间频度T(n)。如果有某个辅助函数f(n)，当趋于无穷大的时候，T(n)/f(n)的极限值是不为零的某个常数，那么f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，被称为算法的渐进时间复杂度，又简称为时间复杂度。

2.1 - 大O表示法

用O(n)来体现算法时间复杂度的记法被称作大O表示法

一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n^2 等，所以我们将O(1)、O(n)、O(logn)、O( n^2 )分别称为常数阶、线性阶、对数阶和平方阶。下面我们来看看推导大O阶的方法：

推导大O阶

推导大O阶有一下三种规则：

用常数1取代运行时间中的所有加法常数
只保留最高阶项
去除最高阶的常数

举好多栗子

常数阶
```
let sum = 0, n = 10; // 语句执行一次
let sum = (1+n)*n/2; // 语句执行一次
console.log(`The sum is : ${sum}`) //语句执行一次 
```
这样的一段代码它的执行次数为 3 ，然后我们套用规则1，则这个算法的时间复杂度为O(1)，也就是常数阶。

再例如：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
x=91; y=100;
while(y>0) if(x>100) {x=x-10;y–;} else x++;
解答： T(n)=O(1)，
这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有?这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数
线性阶

let i =0; // 语句执行一次
while (i < n) { // 语句执行n次
console.log(`Current i is ${i}`); //语句执行n次
i++; // 语句执行n次
}

这个算法中代码总共执行了 3n + 1次，根据规则 2->3，因此该算法的时间复杂度是O(n)。

对数阶
```
let i =0; // 语句执行一次
while (i < n) { // 语句执行n次
console.log(`Current i is ${i}`); //语句执行n次
i++; // 语句执行n次
}
```
上面的算法中，number每次都放大两倍，我们假设这个循环体执行了m次，那么2^m = n即m = logn，所以整段代码执行次数为1 + 2*logn，则f(n) = logn，时间复杂度为O(logn)。
平方阶
```
for (let i = 0; i < n; i++) { // 语句执行n次
for (let j = 0; j < n; j++) { // 语句执行n^2次
console.log('I am here!'); // 语句执行n^2
}
}
```
上面的嵌套循环中，代码共执行 2*n^2 + n，则f(n) = n^2。所以该算法的时间复杂度为O(n^2 )

例如：当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++; 　　
该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)

常见时间复杂度的比较

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)