算法（Algorithm）是指用来解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

去衡量不同算法之间的优劣主要通过算法所占用的「时间」和「空间」两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间。我们通常用「时间复杂度」来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间。我们通常用「空间复杂度」来描述。

把这个算法程序运行一遍，那么它所消耗的时间就可以作为时间复杂度了吗？

可以，但不完全可以。 (逃

因为这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。

而且对测试时使用的数据规模也有很大关系。

故，「 大 O 符号表示法 」，即 T(n) = O(f(n)) 闪亮登场✨ （T 是 Time 的头字母，描述空间复杂度时则为 Space 的头字母 S）

对于时间复杂度而言，大 O 符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

其中 f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

假设每行代码的执行时间都是一样的，可以用 1 颗粒时间来表示。举个例子：

for(let i = 1; i <= n; ++i) // 耗时 1 颗粒时间
{
   j = i; // 耗时 n 个颗粒时间
   j++; // 耗时 n 个颗粒时间
}

以上代码的时间复杂度就是: T(n) = O(1 + 2n);

由于大 O 表示法表示的是代码执行时间的增长趋势，如果若 n 是无限大的，那 1 + 2n 中的 1 和系数 2 就没有意义了，可以简化为 T(n) = O(n);

反之，如果 n 是我们已知的、有限的数字，则可以简化为 O(1);

可以练习一下：

let i = 1; // 耗时 1 个颗粒时间
let j = 2; // 耗时 1 个颗粒时间
++i; // 耗时 1 个颗粒时间
j++; // 耗时 1 个颗粒时间
let m = i + j; // 耗时 1 个颗粒时间

T(n) = O(5) 简化为 O(1)。

上述代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度。

for(let i = 1; i <= n; ++i) // 耗时 1 颗粒时间
{
   j = i; // 耗时 n 个颗粒时间
   j++; // 耗时 n 个颗粒时间
}

T(n) = O(1 + 2n) 简化为 O(n)。

for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O(n) 来表示它的时间复杂度。

let i = 1; // 耗时 1 颗粒时间

while(i < n) // 耗时 1 颗粒时间
{
    i = i * 2; // 耗时 log2^n 颗粒时间
}

上述例子中，什么情况走出 while 循环？ i >= n 的时候。

i 的变化公式是什么？ 每轮循环中 i = i * 2，展平就是 i = i * 2 * 2 * 2 ... 换算数学公式 => i * 2^循环次数

取 i === n 为出界条件，数学公式可为 i * 2^循环次数 = n ;

数学意义上求解循环次数则： 循环次数 = log2^(n / i)

若 n 是无限大的，n / i 本身也是无限大的，可以由 n 表示，则循环次数简化为 log2^n。

循环次数本身就是指 i = i * 2 这行代码执行了多少次才走出循环，又因为我们定义一行代码执行一次用 1 个颗粒时间表示，所以 i = i * 2 这行代码耗时 log2^n 个颗粒时间。

所以上面例子的时间复杂度为 T(n) = O(1 + 1 + log2^n)，抹去无意义的常数就是 T(n) = O(log2^n)。

那为什么标题是 O(logN) 呢？如果把 i = i * 2 中的 2 换成 3 时间复杂度又要怎么表示呢？

其实对数阶在大 O 的表示规则中，是可以省去底数的，你想要精确点就带上底数 2 或 3 等，直接省去底数用 O(logN) 表示也没半点毛病。

for(let m = 1; m < n; m++) // 耗时 1 个颗粒时间
{
    let i = 1; // 耗时 n 个颗粒时间
    while(i < n) // 耗时 n 个颗粒时间
    {
        i = i * 2; // 耗时 n * log2^n 个颗粒时间
    }
}

T(n) = O(1 + n + n + n * log2^n)

简化一下其实就是 T(n) = O(nlogN) 了。

其实不用这样一步步算也好理解，因为循环是 O(n)，循环内要执行 n 次 O(logN)的代码不就是 n * O(logN) 也就是 O(nlogN)。

for (let x = 1; i <= n1; x++) // 耗时 1 个颗粒时间
{
   for (let i = 1; i <= n2; i++) // 耗时 n1 个颗粒时间
    {
       j = i; // 耗时 n1 * n2 个颗粒时间
       j++; // 耗时 n1 * n2 个颗粒时间
    }
}

T(n) = O(1 + n1 + n1 * n2 + n1 * n2)

由于 n1 和 n2 都可以是无限大的，所以可以都用 n 表示，再保留 f(n) 表达式中趋势变化最明显的变量操作（去掉低阶、常量、系数），则可简化为： T(n) = O(n²)。

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

额外还有 最好、最坏、平均、均摊时间复杂度，在有限的场景下才需要这些更精确的描述，就不在这里解释了，基本上我们用以上讲述的大 O 表示就够了。

空间复杂度要简单得多，同理于时间复杂度的描述，空间复杂度也并不是表示程序实际占用的空间。

它也可以用大 O 来表示，描述的是一个算法在运行过程中临时占用存储空间大小的量度的趋势。

同样看两个例子感受下

let i = 1;
let j = 2;
++i;
j++;
let m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量（改变分配空间内的数据）变化，因此它的空间复杂度 S(n) = O(1)。

const m = new arr[n];
for(let i = 1; i <= n; ++i)
{
   j = i;
   j++;
}

其实循环对第一行代码的空间的分配造不成影响，循环内都是常数阶的空间分配，所以这段代码中高阶分配只在第一行，所以 S(n) = O(n)。

注：就算在循环内再 new arr2[n]， 用大 O 表示也是 S(n) = O(n)。因为这段代码的最高阶就是线性。

const m = new arr[n][n];
for(let i = 1; i <= n; ++i)
{
   j = i;
   j++;
}

同上一个例子的分析一致，最高阶是二维数组的内存分配，所以表示为 S(n) = O(n²)

对于空间复杂度而言最常用的就是常数阶、线性阶了，通常几维数组就是几阶，其余具体情况具体分析。