前言

开篇，先来看看我的技术学习良性循环图，将对技术的热情提起来。

前面一篇对算法有了初步的了解和认知。

算法最吸引我的有三个点：

• 在算法中，存在秩序和规则，工作中我喜欢有条不紊；
• 算法可以帮助我解决一些问题；
• 探索解题过程很有趣，虽然过程会有点曲折。

前一篇提到了，「好」算法，高效性和低存储性是两个标准，这两个标准应对的是算法的运行时间和存储空间。

算法的运行时间一般称之为时间复杂度。

算法的存储空间的大小一般称之为空间复杂度。

本篇从这两点出发，深入了解一下算法的复杂性。

算法复杂性

时间复杂度

渐近界

以函数f(n)为例，O(f(n))表示时间复杂度渐进上界，Ω(f(n))时间复杂度渐进下界。

渐进上界代表算法完成工作所需的最长的时间。

渐进下界代表算法完成工作所需的最佳的时间（最短时间）。

这两个值可以用来衡量算法的时间复杂度。通常用O(f(n))表示时间复杂度。

来看一个计算的例子

function funC(n) {
  let i = 1; // 运行1次
  while (i < n) {
    // 可假设运行x次
    i = i * 2; // 可假设运行x次
  }
}

假设可运行x次，当i=n时结束,由此可以得到公式：

则可以求得x的值为：

时间复杂度渐近上界为:

渐近准确界

θ(f(n))表示渐近准确界，θ会更加精确。当即接近渐近上界又接近渐近下界时就是渐近准确界。

三个边界的图形实例

空间复杂度

算法储存空间分类

算法占用的储存空间包括：

• 算法本身：可以忽略不计（应该吧，我看大部分文章中，列等式的时候没有它）
• 输入空间：输入数据所占的空间
• 输出空间：算法运行之后，存储输出数据所需的空间大小
• 辅助空间：算法执行中使用的额外空间或临时空间

当输入数据大小为N时，空间复杂度 = 辅助空间+输出空间。其中辅助空间是衡量算法空间复杂度的关键因素。

常数O(1)

算法执行中的辅助空间大小固定，不随输入数据N的大小而变化，此时算法的空间复杂度为常量，空间复杂度用O(1)表示。

let a = 1;
let b = a;
a+=1;

线性O(N)

当算法分配的空间是与N 呈线性关系的任意类型的集合（如数组等）时，空间复杂度用 O(n)表示。

let arr = new Array(n); // 数组占用的大小为n

未完待续

以前对算法的时间复杂度和空间复杂度，只是知道皮毛。认真学习之后，有了更深入的了解。

上篇文章中有五个问题，只回答了前两个，后面三个还在思考中，对于「如何实现从掌握到精通？」这个问题，已经有点眉目了，我整理整理，下篇详细聊聊。

扪心自问的问题们：