转载：https://baijiahao.baidu.com/s?id=1634508207797410717&wfr=spider&for=pc
作者：松宝写代码
一、前言
时间复杂度和空间复杂度，我们在大学里的算法与数据结构课程中已经学习过，这回根据项目工作中整理一下，这个估计只是一个粗略的估计分析，并不是一个准确的估计分析。
1、学习时间复杂度和空间复杂度是很有必要的，这个属于算法与数据结构的范畴，学这个是为了解决代码中的“快”和“省”的问题。这样才能使你的代码运行效率更高，占用空间更小。代码执行效率需要通过复杂度分析。
2、数据规模的大小会影响到复杂度分析。比如排序，如果是一个有序的数组，执行效率会更高；如果数据量很少的时候，这个算法看不出性能上差别。
3、比如说不同物理机环境不一样，比如i3，i5，i7的cpu等等，运行内存1G，2G，4G，8G等等；时间上肯定有差别。
二、大O的复杂度
我们来看个简单的例子，一个循环累加器。
function total(n) {
var sum = 0; //t
for (var i = 0; i < n; i++) { // nt
sum += i; //nt}return sum; // t
}
分析：假设每一行代码执行耗时都一样，为t，这样整个代码总执行时间为（t+nt+nt+t）=(2n+2)t。
我们再来看一个栗子：
function total(n) {
var sum = 0; // t
for (var i = 0; i < n; i++) { //nt
for (var j = 0; j < n; j++) { //n*n*t
sum = sum + i + j; //n*n*t
}} return sum; //t
}
分析：假设每一行代码执行耗时都一样，为t，这样整个代码总执行时间为（t+nt+nnt2+t）=(2nn+n+2)t。
从数学角度来看，我们可以得出个规律：代码的总执行时间 T(n) 与每行代码的执行次数成正比.
所以上边两个函数的执行时间可以标记为 T(n) = O(2n+2) 和 T(n) = O(2n*n+n+2)。这就是大 O 时间复杂度表示法，它不代表代码真正的执行时间，而是表示代码随数据规模增长的变化趋势，简称时间复杂度。
而且当 n 很大时，我们可以忽略常数项，只保留一个最大量级即可。所以上边的代码执行时间可以简单标记为 T(n) = O(n) 和 T(n) = O(n2)。
三、时间复杂度分析
1、循环次数最多的代码块
在分析的时候，只需要关心哪个代码块循环次数最多的那段代码，比如说刚才的第一个例子，循环最多的代码块是这两行，循环都是n次。
for (var i = 0; i < n; i++){
sum += i;
}
执行了n次，所以事件复杂度就是O(n)。
2、最大值原则：总复杂度等于最大的代码块的复杂度
function total(n) {// 第一个 for 循环var sum1 = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
sum1 = sum1 + i + j;
}}
// 第二个 for 循环var sum2 = 0;
for(var i=0;i<1000;i++) {
sum2 = sum2 + i;
}
// 第三个 for 循环var sum3 = 0;
for (var i = 0; i < n; i++) {
sum3 = sum3 + i;
}
return {sum1:sum1, sum2: sum2, sum3:sum3}
}
分别分析每一段循环时间复杂度，取他们最大的量级决定整段代码复杂度。
第一段，时间复杂度 O(n2)。
第二段，时间复杂度可以忽略，循环执行了 1000 次，是个常数量级，尽管对代码的执行时间会有影响，但是当 n 无限大的时候，就可以忽略。
第三段，时间复杂度O(n)。
综上所述，所以上述代码的时间复杂度为 O(n2)。
3、乘法原则：嵌套代码复杂度等于嵌套内外代码复杂度乘积
举个例子：
function f(i) {
var sum = 0;
for (var j = 0; j < i; j++) {
sum += i;
}
return sum;
}
function total(n) {
var res = 0;
for (var i = 0; i < n; i++) {
res = res + f(i); // 调用 f 函数
}
}
分析一下：total方法时间复杂度O(n)，f方法的时间复杂度O(n)。
所以整段代码的时间复杂度O(n2)。
四、常见的时间复杂度分析
最高量级的复杂度，效率是递减的
最高量级的复杂度，效率是递减的
最高量级的复杂度，效率是递减的
如上图可以粗略的分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!) 对应的增长率如下图所示
O(2n) 和 O(n!) 对应的增长率
O(2n) 和 O(n!) 对应的增长率
当数据规模 n 增长时，非多项式量级的执行时间就会急剧增加，所以，非多项式量级的代码算法是非常低效的算法。
1、常数阶复杂度O(1)
O(1) 只是常量级时间复杂度表示法，并不是代码只有一行，举个例子：
function total() {
var sum = 0;
for(var i=0;i<100;i++) {
sum += i;
}
return sum;
}
虽然有这么多行，即使 for 循环执行了 100 次，但是代码的执行时间不随 n 的增大而增长，所以这样的代码复杂度就为 O(1)。
2、对数阶O(logn)和O(nlogn)
（1）对数阶时间复杂度的常见代码如下:
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i; i = i * 2;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 2) {
sum += i;
}
}
上面函数total1和total2有一个相同点：变量 i 从 1 开始取值，每循环一次乘以 2，当大于 n 时，循环结束。
所以真正循环了x次。2x =n;，所以 x = log2n。
所以上面两个函数时间复杂度都是 O(log2n)。
（2）我们在举个例子：
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i; i = i * 3;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 3) {
sum += i;
}
}
同理可知：这两个函数的时间复杂度为 O(log3n) 。
由于我们可以忽略常数，也可以忽略对数中的底数，所以在对数阶复杂度中，统一表示为 O(logn)；那 O(nlogn) 的含义就很明确了，时间复杂度 为O(logn) 的代码执行了 n 次。
3、其他复杂度O(m+n)和O(m*n)
举个例子：
function total(m,n) {
var sum1 = 0;
for (var i = 0; i < n; i++) {
sum1 += i;
}
var sum2 = 0;
for (var i = 0; i < m; i++) {
sum2 += i;
}
return sum1 + sum2;
}
因为我们无法评估 m 和 n 谁的量级比较大，所以就不能忽略掉其中一个，这个函数的复杂度是有两个数据的量级来决定的，所以此函数的时间复杂度为 O(m+n)；那么 O(m*n) 的时间复杂度类似。
五、空间复杂度分析
空间复杂度的话和时间复杂度类似推算。 所谓空间复杂度就是表示算法的存储空间和数据规模之间的关系。
举个例子：
function initArr(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr[i] = i;
}
}
时间复杂度的推算，忽略掉常数量级，每次数组赋值都会申请一个空间存储变量，所以此函数的空间复杂度为 O(n)。
常见的空间复杂度只有 O(1)、O(n)、O(n2)。其他的话很少会用到。
六、复杂度优化
function total(n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
这段代码我们很容易知道时间复杂度 O(n)。
但是我想把复杂度降一降，降低到常数阶O(1)。
其实求和怎么求呢？等比数列，直接用公式，这就说明了数学好的人，算法应该高level点。
function total(n) {
var sum = n*(n+1)/2
return sum;
}
上面函数的时间复杂度仅仅为 O(1)，在数据规模比较庞大的时候，下面的函数是不是明显比上面的函数运算效率更高呢。
七、总结
分析算法执行效率与数据规模之间的增长关系，可以粗略的表示，越高阶复杂度的算法，执行效率越低。
复杂度学习之后，有时候可以避免写出效率低的代码。
网友评论