11-05 01:52 阅读 106

算法之空间复杂度

我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法，以此来追求最低的算法复杂度，提升代码质量。复杂度分为时间复杂度和空间复杂度。在介绍时间复杂度之前，先说下大 O 复杂度表示法。

大 O 复杂度

所有代码的执行时间 T(n) 与每行代码的执行次数 n 是成正比的可以用一个公式来表示这种关系：

T(n) = O(f(n))

T(n)：表示代码的执行时间
n：表示数据规模的大小
f(n)：表示一个公式，像上面的 2n + 2 或 (2n²+2n+3)，表示所有代码执行的次数总和
O：表示代码的执行时间 T(n) 与 f(n) 表达式成正比

这就是大 O 时间复杂度表示法。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

由公式可以看出，当 n 很大时，比如达到 10000，甚至 100000，此时公式中的低阶、常量、系数三部分就可以忽略不计，那么刚刚两个示例的时间复杂度可以简化为： T(n) = O(n)； T(n) = O(n²)。

从图中可以看到时间复杂度的类型有好多种，但我们只要熟悉常用的几种即可，O(1)，O(n)、O(logN)
与 O(n²)。以及各个表达式的执行时间快慢：

1 < log2n < √n < n < nlog2n < n2 < 2n < n! 复制代码

O(1) 不是指只执行了一行代码，而是常量级时间复杂度的一种表示方法，比如如下代码的时间复杂度就是 O(1)，而不是 O(4)。

function sum() {   var i = 0;   i += 1;   var j = 1;   var sum = i + j; } 复制代码

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 Ο(1)。

循环执行了 n 次

for (let i = 0; i < n; i += 1) {     console.log(i) } 复制代码

加法法则：总复杂度等于量级最大的那段代码的复杂度

O(n) 足够大时，O(1) 忽略不计

let i = 0; i +=1 for (let i = 0; i < n; i += 1) {     console.log(i) } 复制代码

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

for (let i = 0; i < n; i += 1) {     for (let j = 0; j < n; j += 1) {         console.log(i, j)     } } 复制代码

实际上就是求2的多少次方等于 n，如下图：在这里插入图片描述

let i = 1; while (i < n) {     console.log(i)     i * 2; }

作者：webInRun
链接：https://juejin.cn/post/7026708721342349319