算法可以总结为针对指定问题的方法论，而问题按照类型又有递归、排序、分治、动态规划等分类。

什么是递归？

递归的特点：

  • 可以归纳会若干个规模较小的，与原问题形式相同的子问题。
  • 临界条件。

汉诺塔问题。

分治法

分治法：将大的问题分割成可以一些可以解决的小问题，如果依然无法解决则继续分割。

可以使用分治法的问题提特征：

  1. 使用分治法后，难度在降低。
  2. 问题可分。
  3. 解可合并。
  4. 互相独立。

典型即二分法。

  • 二分法查找的时间复杂度是 O(logn)，这也是分治法的普遍特性。
  • 二分法查找的循环次数不确定。
  • 二分法处理的原问题必须是有序的。

典型题：

  • 找数组 arr = [-1,2,3,4,5,6,6,8,9,10,12,15] 中第一个大于 9 的数：二分法，取中middle + （middle - 1/middle + 1） 对比。

排序

比较排序算法优劣的分析角度：

  • 时间复杂度：具体包括最好时间复杂度、最坏时间复杂度以及平均时间复杂度。
  • 空间复杂度：如果空间复杂度为1 ，也叫做原地排序。
  • 稳定性：稳定性是指相等的数据对象，在排序之后，顺序是否保持不变。

常见的排序算法及思想：

以已下数据为例：

  1. let a = [1, 3, 4, 2, 7, 6, 9, 8];
  2. let b = [9, 8, 7, 6, 5, 4, 3, 2, 1];
  3. let c = [1, 2, 3, 4, 5, 6, 7, 8, 9];

冒泡排序

算法 - 图1

  1. function maopao(arr) {
  2.     let flag = false;
  3.     for (let i = 1; i < arr.length; i++) {
  4.         for (let j = 0; j < arr.length - i; j++) {
  5.             count++;
  6.             if (arr[j] > arr[j + 1]) {
  7.                 flag = true;
  8.                 let temp = arr[j];
  9.                 arr[j] = arr[j + 1];
  10.                 arr[j + 1] = temp;
  11.             }
  12.         }
  13.         if (flag === false) { //如果一次遍历后没有任何相邻的两个值是逆序的，则说明整个数组就是顺序的。无需再次执行
  14.             break;
  15.         }
  16.     }
  17.     return arr;
  18. }

冒泡排序的复杂度：

  • 对于完全顺序的数据，当添加 flag 标志后最好时间复杂度是 O(n),即只需对比一次。
  • 对于完全逆序的数据，时间复杂度为O(n+(n-1)+…+1) 即 O(n*n)。
  • 平均复杂度也是 O(n*n)。
  • 因为不需要额外的空间，所以空间复杂度度为 O(1)。

插入排序

算法 - 图2

  1. function charu(arr) {
  2.     for (let i = 1; i < arr.length; i++) {
  3.         let temp = arr[i]
  4.         let j = i - 1;
  5.         for (; j >= 0; j--) {
  6.             if (arr[j] > temp) {
  7.                 arr[j + 1] = arr[j];
  8.             } else {
  9.                 break;
  10.             }
  11.         }
  12.         arr[j+1] = temp;
  13.     }
  14.     return arr;
  15. }

插入排序算法复杂度：

  • 对于完全顺序的数据，最好时间复杂度是 O(n),即只需对比一次。
  • 对于完全逆序的数据，时间复杂度为O(n+(n-1)+…+1) 即 O(n*n)。
  • 平均复杂度也是 O(n*n)。
  • 因为不需要额外的空间，所以空间复杂度度为 O(1)。

归并排序

算法 - 图3

  2. function guibing(arr) {
  3.     let temp = new Array(arr.length);
  4.     console.log(`原始数据：${arr.length}`);
  5.     customMergeSort(arr, temp, 0, arr.length - 1);
  6.     console.log(`归并排序数据：${arr}`);
  7. }
  9. function customMergeSort(arr, temp, start, end) {
  10.     if (start < end) {
  11.         let mid = Math.floor((start + end) / 2);
  12.         //对左侧子序列进行递归排序
  13.         customMergeSort(arr, temp, start, mid);
  14.         //对右侧子序列进行递归排序
  15.         customMergeSort(arr, temp, mid + 1, end);
  16.         //合并
  17.         customDoubleMerge(arr, temp, start, mid, end);
  18.     }
  19. }
  21. function customDoubleMerge(arr, temp, left, mid, right) {
  22.     let p1 = left;
  23.     let p2 = mid + 1;
  24.     let k = left;
  25.     while (p1 <= mid && p2 <= right) {
  26.         count++
  27.         if (arr[p1] <= arr[p2]) {
  28.             temp[k++] = arr[p1++];
  29.         } else {
  30.             temp[k++] = arr[p2++];
  31.         }
  32.     }
  33.     while (p1 <= mid) {
  34.         count++
  35.         temp[k++] + arr[p1++];
  36.     }
  37.     while (p2 <= right) {
  38.         count++
  39.         temp[k++] = arr[p2++];
  40.     }
  41.     //复制回原数组
  42.     for (let i = left; i <= right; i++) {
  43.         arr[i] = temp[i];
  44.     }
  45. }

归并排序算法复杂度：

  • 因为采用了二分法，所以，最好、最坏、平均时间复杂度都是 O(nlogn)
  • 空间复杂度上面，因为每次合并操作都要开辟基于数组的临时内存空间，所以空间复杂度为 O(n)。
  • 因为归并排序设计交换操作，所以归并排序是不稳定的排序算法。

快速排序

算法 - 图4

  1. function kuaisu(arr, start, end) {
  2.     if (start > end) {
  3.         return;
  4.     }
  5.     let i = start;
  6.     let j = end;
  7.     let temp = arr[start];
  8.     let t;
  9.     while (i < j) {
  10.         //先从右侧开始，将小于 temp 的值都放到左侧
  11.         while (temp <= arr[j] && i < j) {
  12.             j--;
  13.         }
  14.         //从左侧开始将大于 temp 的值都放到右侧。
  15.         while (temp >= arr[i] && i < j) {
  16.             i++
  17.         }
  18.         t = arr[j];
  19.         arr[j] = arr[i];
  20.         arr[i] = t;
  21.     }
  22.     arr[start] = arr[i];
  23.     arr[i] = temp;
  24.     kuaisu(arr, start, j - 1);
  25.     kuaisu(arr, j + 1, end);
  26. }

快速排序复杂度：

  • 最好的情况下都是：O(n*logn)
  • 最坏的情况下则是O(n*n)。
  • 平均则是 O(n*logn)。
  • 空间复杂度为 O(1)。
  • 因为涉及交换操作，所以快排是不稳定的排序算法。

排序算法总结

最简答的暴力排解时间复杂度是 O(n*n), 例如冒泡和插入排序。

如果利用算法思维去解决问题，使用分治法是，最好则能降低到 O(n*logn)。同时不同的算法又对空间复杂度有不同的消耗。

动态规划

  • 最短路径问题。
  • 最大子串问题。