算法图解-note

[ronghaoZHI]

1 简介：

一般谈到复杂度较优的查找算法 都会想到介 -- 二分查找（tips: 所有的算法都用它的适用场景，遇到问题要先分析问题具体场景，否则方法再牛只是画蛇添足！ ）。
what is ‘二分查找’？
👇👇

/* 二分查找 */
function binarySearch(arr = [], item) {
  let low = 0,
    high = arr.length - 1;
  while (low <= high) {
    const mid = parseInt((low + high) / 2);
    const guess = arr[mid];
    if (guess === item) {
      return mid;
    }
    if (guess > item) {
      high = mid - 1;
    }
    if (guess < item) {
      low = mid + 1;
    }
  }
  return null;
}

const myList = [1, 3, 5, 7, 9];
console.log(binarySearch(myList, 3));

下面介绍1下，what is ‘大O’ ？
对，大O 一般用来表示算法复杂度（时间复杂度，空间复杂度）
下面列出常见的5种大O运行时间
👇👇

O(log n):也叫对数时间，这样的算法包括二分查找；
O(n):也叫线性时间，这样的算法包括简单查找；
O(n * log n): 这种算法包括快速排序 —— 一种速度较快的排序算法；
O(n²):这样的算法包括选择排序 —— 一种速度较慢的排序算法；
O(n!): 这样的算法包括难以解决的旅行商问题 —— 一种非常慢的算法。（旅行商问题  感兴趣的可以研究一下狄克斯拉特算法 Dijstra's algorithm）

2 数组&&链表

数组-- 在内存空间中地址始终是连续的（索引值与内存地址都是连续的），并且数组长度扩大时 会开辟一块新长度的内存空间，因此访问操作时效率较高，插入删除操作时效性能较差。
链表-- 在内存空间中地址可以间断，因此插入，删除操作时效率较高，访问操作时效率较低（因为需要从头进行遍历查找）。

链表和数组各种操作的时间复杂度对比

3 递归

递归由两部分组成：

• 基线条件（base case）：函数不再调用自己的条件
• 递归条件（recursive case）: 函数调用自己的条件

举个🌰，常见的递归算法

/*斐波纳契数列*/
  function fib(n){
        if(n<1)  return
        if (n <=2) {
          return 1
        } else {
          return fib(n-1)*fib(n-2)
        }
      }

很明显此递归方法中-- 1. 结束条件 2. 调用自身

but...使用递归很方便，但是要付出代价：存储详尽的信息需要占用大量的内存。递归中函数会嵌套执行多层函数，每个函数调用都要占用一定的内存，如果栈很高，计算机就需要存储大量函数调用的信息，这就是为什么有的语言会限制递归最多的层数.

顺便开个小灶 —— 介绍下 尾调用优化

如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，
这将大大节省内存。这就是"尾调用优化"的意义。

尾调用优化

通过变量保存函数运算结果，然后通过参数传递给下层递归函数，如果可以确切的知道下层函数需要从上层函数得到什么信息，则可把所有用到的内部变量改写成函数的参数，构成尾递归

4 快速排序

• 选择基准值
• 将数组分为两个子数组，小于基准值的元素和大于基准值的元素
• 对两个子数组再次运用快速排序

function quickSort(arr){
        if(arr.length<=1) {
          return arr;
        }
        let q = arr[0];
        let left = [];
        let right = [];
        for(let i=1,len=arr.length;i<len;i++){
          if(arr[i]<q){
            left.push(arr[i]);
          }else{
            right.push(arr[i]);
          }
        }
        return [].concat(quickSort(left), [q], quickSort(right));
      }
 var result = quickSort([1,5,7,90,55,4,2]);

5 散列表 Object/dict

6 广度优先搜索 graph

7 狄克斯拉特算法

8 贪婪算法（NP完全问题）

9 动态规划 （背包问题）

10 K最近邻算法 （推荐系统）