# 算法图解

## 第一章 算法简介

### 二分法

```python
def binary_search(array, target):
    low = 0
    high = len(array)-1
    while low < high:
        mid = (low+high) >> 1
        if target > array[mid]:
            low = mid+1
        else:
            high = mid
    return high
```

## 第二章 选择排序

每次把最小的push进数组里面，O(n^2)

```python
def findSmallestIndex(array):
    smallest = array[0]
    smallestIndex = 0
    for i in range(1, len(array)):
        if array[i] < smallest:
            smallest = array[i]
            smallestIndex = i
    return smallestIndex


def selectionSort(arr):
    newArr = []
    for _ in arr:
        smallest = findSmallestIndex(arr)
        newArr.append(arr.pop(smallest))
    return newArr
```

## 第三章 递归

循环性能更高，递归更容易理解

## 第四章 快速排序

分治策略(D\&C)：

1. 选择一个**基准条件**，也就是递归的退出条件

   要尽可能简单。比如空数组，或者数组只有一个元素
2. 不断将问题分解、缩小规模，变得更加简单，直到符合基准条件

   每次递归调用，都要缩小问题的规模

### 快排

选一个基准值，左边都比他小，右边都比他大，然后递归排序

退出条件就是，数组是空的或者元素只有一个。

```python
def quicksort(arr):
    if len(arr) < 2:
        return arr
    pivot = arr[0]
    less = [i for i in arr[1:] if i <= pivot]
    greater = [i for i in arr[1:] if i > pivot]
    return quicksort(less)+[pivot]+quicksort(greater)
```

![image-20191112170324843](https://tva1.sinaimg.cn/large/006y8mN6gy1g8vd631ywej30nw0dmgoc.jpg)

选择基准值很重要，决定了性能的上限

## 第五章 散列表/哈希表

### 散列函数

能把输入翻译成一个数字。

翻译是一一对应，而且尽可能均匀

得到数字就是存放数组的索引，可以O(1)直接拿

存的表叫**散列表**

### 冲突

两个值分配了同一个位置。

最简单解决方法是，那个位置放一个链表

所以散列函数很重要

### 填装因子

还有多少位置是空的，返回一个比例。

一般大于0.7，即70%满了，就要换一个更大的数组放，一般是扩展一倍。

所有元素都插进这个新的数组当中。

## 第六章 广度优先搜索

用一个数组记录已经遍历过的人。

一个个入栈遍历，出栈检查。

```python
def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
```

## 第七章 狄克斯特拉算法

求图上最短路径，带权重的那种

1. 找最短成本的节点，确保没有更短路径
2. 更新该节点所有邻居的成本
3. 重复过程，找下一个最小成本的节点，得到所有路径的开销
4. 计算最终路径

* 不适合带环的节点，只适合 有向无环图

![image-20191112193326572](https://tva1.sinaimg.cn/large/006y8mN6gy1g8vhi6y0nbj30dg09k758.jpg)

* 不适合有 负权重 的图

因为节点一旦处理，默认就是最优的了。但在有 负权重 的图中就不成立。

可以用bellman-ford算法

```python
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node
```

## 第八章 贪婪算法

每步都走局部最优解。

最大优点就是简单易行。

如果想找到一个能大致解决问题的算法，可以用贪婪算法。追求优秀而非完美

### 近似算法

![image-20191112200159547](https://tva1.sinaimg.cn/large/006y8mN6gy1g8vibwdj0pj30be0esjtl.jpg)

每个广播台覆盖一部分区域，如何选尽可能少的广播台，覆盖尽可能多的区域？

每次都选择尽可能多覆盖的广播台。直到全部覆盖完。

### np完全问题

简言之就是非常复杂的问题，不可能有最优解，只能找近似解

#### 旅行商问题

要前往几个不同城市，找最短路径。

#### 集合覆盖问题

如，橄榄球队挑选队员，每个候选人都满足某些需求。

#### np完全问题特点

判断是否np完全，非常困难

* n增加，速度变得非常慢，如n!
* 涉及 所有组合、 序列、集合 等，可能是
* 可转换为集合覆盖或者旅行商问题

## 第九章 动态规划

动态规划适用条件：

* 需要在给定约束条件下，优化某种指标。
* 问题可以分解为，离散的子问题（子问题不能有相互依赖）
* 需要填网格，里面是需要优化的值

### 背包问题

有多个东西价值不同，但你包有固定大小，如何装价值最多的东西

把包分解成不同大小的包，然后填表

![image-20191113204156850](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wp3tyugcj30is0a8wgn.jpg)

每一行写当前背包大小下，最大能装东西的价值。

第一行就只能有一个东西装，第二行就是，能装的拓展到了两个

![image-20191113204321708](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wp59hy7pj30l20dw0wr.jpg)

![image-20191113204336041](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wp5i8b8tj30ys080q5d.jpg)

这和行排序无关，再加几个也可以

每次迭代都存储当前最大价值，最后一个数就是答案。

* 只能考虑拿走整件商品，不能拿一部分（一定要有最小单位）

不然用贪婪算法

### 最长公共子串

![image-20191113204623099](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wp8ejqhmj30qm0h4tdl.jpg)

## 第十章 k最近算法

* 分类
* 特征提取
* 回归，求出预测结果

  可以用毕达哥拉斯公式，或者算角度的余弦相似度

挑合适的特征很重要。

## 十一章 10种算法

### 树

二叉查找树：左边都小，右边都大。插入删除操作速度比数组快。

但可能不平衡

B树、红黑树、堆、伸展树

### 反向索引

搜索引擎工作原理。

哈希表，单词映射到包含他的页面。

### 傅立叶变换

拆成不同频率，适合处理信号。

### 并行算法

多个内核并行执行算法。但速度提升非线性：

* 有并行管理开销。分配开销
* 负载均衡

### mapreduce

分布式算法，能让算法在多台机器上执行。

适合在短时间内运行海量工作。

#### map映射

把数组每个元素，执行同样的处理。

#### reduce归并

计算结果转换成一个元素。

### 概率型数据结构和算法

追求完美代价太高，概率型，答案可能不正确，但绝对不是错误的。

#### 布隆过滤器

概率型数据结构

* 可能出现错报，搜集过却记录为没搜集过
* 不可能出现漏报

#### hyperLogLog

近似计算集合中不同的元素数，如搜索数、商品数。

准确率大差不差，但占内存小很多

### SHA

安全散列算法

类似于哈希函数，输入字符串，输出字符串（散列值）

* 可以用来判断两个大文件是否相同
* 可以不知道原始密码情况下，比较密码

  服务器存的密码都是SHA，窃取了也没用
* SHA是单向的，无法反推

实际上是一系列算法

#### 局部敏感/不敏感

* 局部不敏感：修改一点点，散列值完全不同

  无法通过散列值，反推密码
* 局部敏感：Simhash

  原文差别小，散列值也差别小。可以用来判断相似程度

### 非对称加密Diffie-Hellman

公钥/私钥

### 线性规划

给定约束条件下，最大限度改善指定指标。

所有图算法都可以用线性规划来实现