笔记

代码效率优化就是要将可行解提高到更优解，最终目标是：要采用尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。

时间昂贵、空间廉价

代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间，花钱买服务器就可以了。这是个花钱就能解决的问题。相反，如果是缺少计算时间，只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器，也是毫无用处。相比于空间复杂度，时间复杂度的降低就显得更加重要了。

结论：空间是廉价的，而时间是昂贵的。

降低空间复杂度的核心思路就是：能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

程序开发中复杂度降低的核心方法论

1. 暴力解法：在没有任何时间、空间约束下，完成代码任务的开发

   先解决问题

2. 无效操作处理：将代码中的无效计算、无效存储剔除，降低时间或空间复杂度

   学会并掌握递归、二分法、排序算法、动态规划等常用的算法思维

3. 时空转换：设计合理数据结构，完成时间复杂度向空间复杂度的转移

   对数据的操作进行细分，全面掌握常见数据结构的基础知识

示例

1. 假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性

暴力解法

代码共执行n + n² + n³次，则f(n) = n³。时间复杂度为O(n³)

function fn(n = 100) {
  let count = 0;
  for (let i = 0; i <= n / 7; i++) {
    for (let j = 0; j <= n / 3; j++) {
      for (let k = 0; k <= n / 2; k++) {
        if (i * 7 + j * 3 + k * 2 === n) {
          count += 1;
        }
      }
    }
  }
  return count;
}

代码优化

代码共执行n + n²次，则f(n) = n²。时间复杂度为O(n²)

function fn(n = 100) {
  let count = 0;
  for (let i = 0; i <= n / 7; i++) {
    for (let j = 0; j <= n / 3; j++) {
      if (n - i * 7 - j * 3 >= 0 && (n - i * 7 - j * 3) % 2 === 0) {
        count += 1;
      }
    }
  }
  return count;
}

2. 查找出一个数组中，出现次数最多的那个元素的数值

暴力解法

代码共执行n + n²次，则f(n) = n²。时间复杂度为O(n²)

function fn(arr = [1, 2, 3, 4, 5, 5, 6]) {
  let val_max = 1;
  let time_max = 0;
  for (let i = 0; i < arr.length; i++) {
    let time_tmp = 0;
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        time_tmp += 1;
      }
      if (time_tmp > time_max) {
        time_max = time_tmp;
        val_max = arr[i];
      }
    }
  }
  return val_max;
}

代码优化

通过采用更复杂、高效的数据结构，完成了时空转移，提高了空间复杂度O(n)，降低了时间复杂度O(n)

function fn(arr = [1, 2, 3, 4, 5, 5, 6]) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    // 实现数组转字典
    if (map.has(arr[i])) {
      map.set(arr[i], map.get(arr[i]) + 1);
    } else {
      map.set(arr[i], 1);
    }
  }

  let val_max = -1;
  let time_max = 0;
  for (const key of map.keys()) {
    if (map.get(key) > time_max) {
      time_max = map.get(key);
      val_max = key;
    }
  }
  return val_max;
}

练习

示例 1 中是否存在更优的解法？如果有，请写出来

答案解析

第 4 行代码，j 需要遍历到 33。但很显然，随着 i 的变大，j 并不需要遍历到 33。例如，当 i 为 9 的时候，j 最大也只能取到 12。如果 j 大于 12，则 7 * 9 + 3 * 13 > 100。虽然减少了循环次数，但是时间复杂度并没有降低，因为 j 的取值范围也是与 n 线性相关的

function fn(n = 100) {
  let count = 0;
  for (let i = 0; i <= n / 7; i++) {
    for (let j = 0; j <= (n - 7 * i) / 3; j++) {
      if (n - i * 7 - j * 3 >= 0 && (n - i * 7 - j * 3) % 2 === 0) {
        count += 1;
      }
    }
  }
  return count;
}