“和同学菜鸡互啄了一番之后成功验证了大学的知识早已还给老师”

算法

算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数

说个粗浅的观点：在 JS 中定义的函数都是算法

算法复杂度

针对你的程序中算法的优劣、性能好坏有个评判的标准就是算法的复杂度，主要分为时间复杂度和空间复杂度两种，使用大写字母 O 表示

• 时间复杂度(Time complexity)：是一个函数，它定性描述该算法的运行时间。通常使用算法的最坏情况复杂度，记为 T(n)
• 空间复杂度(Space Complexity)：是对一个算法在运行过程中临时占用存储空间大小的量度

算法的运行时间其实就是计算你的算法在指定条件下执行的次数就是时间复杂度，而算法执行过程中所需要开辟辅助内存的次数则是空间复杂度

所以说算法运行的次数和深度分别代表时间复杂度和空间复杂度

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n)，进而分析 f(n)随 n 的变化情况并确定 T(n)的数量级。这里用”O”来表示数量级，给出算法的时间复杂度

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

它表示随着问题规模的 n 的增大，算法的执行时间的增长率和 f(n)的增长率相同，这称作算法的渐进时间复杂度，简称时间复杂度。而我们一般讨论的是最坏时间复杂度，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，分析最坏的情况以估算算法指向时间的一个上界

• 时间复杂度就是函数中基本操作所执行的次数
• 一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数
• 忽略掉常数项
• 关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数
• 计算时间复杂度是估算随着 n 的增长函数执行次数的增长趋势
• 递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数

空间复杂度

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度 S(n)定义为该算法所耗费空间的数量级

S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量 n 而言是一个常数，则称这个算法的辅助空间为 O(1)

递归算法的空间复杂度：递归深度 N * 每次递归所要的辅助空间， 如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N)

基础算法

基础算法有很多，排序、递归、二分法、贪婪算法、回溯等，以下简要列举简单为主

冒泡排序

核心代码：

// arr
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    if (arr[j] > arr[j + 1]) {
      let temp = arr[j + 1];
      arr[j + 1] = arr[j];
      arr[j] = temp;
    }
  }
}

此处只表述最基本的情况，不优化任何代码

该冒泡算法的时间复杂度： 从运行次数的角度来分析，设数组长度为 n，两层 forloop 正好组成一个 n * n 的矩阵，所以总次数为 n^2 所以该冒泡排序的时间复杂度为 O(n^2)

该冒泡算法的空间复杂度： 从每次开辟的内存来看该算法每次只是使用之前系统的分配的内存（存储 arr），所以冒泡排序的空间复杂度为 O(1)

递归

递归是很常见的算法，使用得当不仅可以使代码更为简洁也可带来显著性能提升（像之前博客中提过的尾递归），那么递归算法的复杂度是如何计算呢

只考虑有终止条件的递归，死循环的递归的复杂度当然是无穷大了

递归 demo：

let n = 10;

function recursion() {
  if (n > 1) n-- && recursion();
  else return "end of the recursive";
}

上述是一个会循环执行 10 次就终止的简单递归 该递归的时间复杂度： 设递归的执行次数为 n，也就是上述例子的终止条件，该递归的时间复杂度即为 O(n) 该递归的空间复杂度： 设递归的执行次数为 n，每次递归都要开辟新的栈帧（常数级别作 1）保留在调用栈中以用来存储返回信息，所以该递归的空间复杂度 n * 1 即为 O(n)

二分法

二分法本质依然是使用递归不断等分，代码如下：

/**
 * @description: dichotomy
 * @param {Array} arr 入参数组
 * @param {any} val match
 * @param {Number} l 索引开始
 * @param {Number} r 索引结束
 */
function dichotomy(arr, val, l, r) {
  let mid = Math.floor((l + r) / 2);
  let midval = arr[mid];

  if (l > r) return console.log("no match");

  if (midval === val) return console.log("has match, index is ", mid);

  midval > val
    ? dichotomy(arr, val, l, mid - 1)
    : dichotomy(arr, val, mid + 1, r);
}

// 测试
const arr = [1, 2, 3, 4, 5];
dichotomy(arr, 3, 0, arr.length - 1);

// optput:
// has match, index is  2

算法的执行是不断等分数组，直到无法匹配要查找的数据 设数组初始长度为 n，第一次递归后长度为 n/2，第二次等分后长度为 n/4…

.

.

.

第 x 等分后长度为 n/2^x 而算法执行的最差的情况就是每个等分的长度为 1，1 就是临界值 所以另 n/2^x = 1 时可得到等分的次数为 x = log 以 2 为底 n 的对数

所以二分法的时间复杂度为 log 以 2 为底 n 的对数（打不出上标下标 🤕） 每次需要的辅助空间依然是常数级别作为 1，所以空间复杂度也是 log 以 2 为底 n 的对数