算法图解

第一章 算法简介

二分法

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)

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. 不断将问题分解、缩小规模，变得更加简单，直到符合基准条件

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

快排

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

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

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

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

第五章 散列表/哈希表

散列函数

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

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

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

存的表叫散列表

冲突

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

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

所以散列函数很重要

填装因子

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

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

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

第六章 广度优先搜索

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

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

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

• 不适合有 负权重 的图

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

可以用bellman-ford算法

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

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

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

np完全问题

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

旅行商问题

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

集合覆盖问题

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

np完全问题特点

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

• n增加，速度变得非常慢，如n!

• 涉及 所有组合、 序列、集合 等，可能是

• 可转换为集合覆盖或者旅行商问题

第九章 动态规划

动态规划适用条件：

• 需要在给定约束条件下，优化某种指标。

• 问题可以分解为，离散的子问题（子问题不能有相互依赖）

• 需要填网格，里面是需要优化的值

背包问题

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

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

image-20191113204156850

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

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

image-20191113204321708

image-20191113204336041

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

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

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

不然用贪婪算法

最长公共子串

image-20191113204623099

第十章 k最近算法

• 分类

• 特征提取

• 回归，求出预测结果

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

挑合适的特征很重要。

十一章 10种算法

树

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

但可能不平衡

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

反向索引

搜索引擎工作原理。

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

傅立叶变换

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

并行算法

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

• 有并行管理开销。分配开销

• 负载均衡

mapreduce

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

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

map映射

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

reduce归并

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

概率型数据结构和算法

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

布隆过滤器

概率型数据结构

• 可能出现错报，搜集过却记录为没搜集过

• 不可能出现漏报

hyperLogLog

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

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

SHA

安全散列算法

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

• 可以用来判断两个大文件是否相同

• 可以不知道原始密码情况下，比较密码

  服务器存的密码都是SHA，窃取了也没用

• SHA是单向的，无法反推

实际上是一系列算法

局部敏感/不敏感

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

  无法通过散列值，反推密码

• 局部敏感：Simhash

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

非对称加密Diffie-Hellman

公钥/私钥

线性规划

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

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