算法图解笔记

2019-08-01 本文已影响0人 CherrySSS

二分查找

输入：有序列表 $n$ 个元素，最多 $log_2n$ 步找到，与简单查找相比最多需要n步
输出：找到的位置/ $null$
数据结构：使用数组，不断更新首尾index（low,high）

def binary_search(list, item):
    low = 0
    high = len(list)-1
    while low <= high:  #只要范围没有缩小到只含1个元素
        mid = (low+high)/2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
        return None
my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))    #1
print(binary_search(my_list, -1))   #None

算法运行时间用 $O()$ 表示,由快到慢的5中 $O()$ ：
- $O(log n)$ :对数时间，e.g.二分法
- $O(n)$ :线性时间，e.g.简单查找
- $O(n*log n)$ : 快速排序，合并排序
- $O(n^2)$ ：选择排序
- $O(n!)$ : e.g. 旅行商问题，一种非常慢的算法
- 算法的速度指的并非时间，而是操作数的增速
- 谈了算法速度，随着输入的增加，运行时间将以什么样的速度增加
旅行商问题：
- 问题描述：前往n个城市，同时确保旅程最短，对每种顺序都需要计算总旅程，再挑选旅程最短的路线
- 近似答案，见K近邻
数组和链表：
- 数组：元素内存中相连，同一数组中，所有元素类型必须相同，支持顺序访问+随机访问（被应用的更多）
- 链表：元素可存储在内存的任何地方，只支持顺序访问
  
  数组链表
  
  读取 $O(1)$ $O(n)$
  
  插入 $O(n)$ $O(1)$
  
  删除 $O(n)$ $O(1)$ [如何能够立即访问要删除的元素时]
选择排序：
- 双层循环，时间复杂度 $O( n^2)$
- 解释1：遍历待排序列表，找出列表中最小/最大的元素，将该元素添加到一个新的列表中，将该元素从原列表中删除。
- 解释2：首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。至于选大还是选小，这个都无所谓，你也可以每次选择最大的拎出来排，也可以每次选择最小的拎出来的排，只要你的排序的手段是这种方式，都叫选择排序
- ```
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))#.pop返回移除的元素值
    return newArr
print(selectionSort([5,3,6,2,10]))
```
队列：先进先出（First In First Out, FIFO）
- 类似于栈，不能随机地访问队列中的元素，只支持两种操作：入队和出队
调用栈（call stack）：后进先出(Last In First Out, LIFO)
- 用于存储多个函数的变量即调用栈。所有函数调用都进入调用栈
- 每当调用函数时，计算机都会将函数调用涉及的所有变量的值存储到内存中，当函数调用返回后，栈顶的内存块被弹出
- 栈包含两种操作：压入（插入）和弹出（删除并读取），栈作为一种数据结构，但不能用于查找
递归
- 调用自己的函数即递归。原理上，递归与循环作用相同，而递归只是让解决方案更清晰，并没有性能上的优势。如果使用循环，程序性能可能更高，使用递归，程序可能更容易理解，如果选择要看什么对你更重要
- 递归函数包含两个条件：边界条件（函数不再调用自身）和递归条件（函数调用自身）
- 递归函数也使用调用栈，使用上很方便，帮助跟踪当前程序执行情况，但会占用较多内存（每个函数调用都要占用一定内存），如果栈很高，将占用大量内存，替代方法：
  - 重新编写代码，使用循环
  - 使用尾递归，但并非所有语言都支持尾递归
函数式编程：
- 诸如Haskell等函数式编程语言没有循环，因此只能使用递归来编写即使可以使用循环就可以轻松实现的函数
分治法（divide and conquer, D&C）：
- D&C并非可用于解决问题的算法，而是一种解决问题的思路
- D&C算法是递归的，解决该问题的过程包含两个步骤
- 步骤1：找出边界条件，必须尽可能简单，在使用D&C处理列表时，边界条件很可能是空数组或者只包含一个元素的数组
- 步骤2：不断将问题分解/缩小规模，直到符合边界条件
- 欧几里得算法（用来求两个正整数最大公约数的算法），又称辗转相除法，例如求1997与615之间的最大公约数
  
  1997=615*3+152
  
  615=152*4+7
  
  152=7*21+5
  
  7=5*1+2
  
  5=2*2+1
  
  2=2*1+0（当被加数为0时，得出1997与615之间最大公约数为1）
- 问题变形：将一块矩形的土地（1680*640）均匀分成方块，且分出的方块要尽可能大
  - 边界条件：一条边的长度是另一条边的整数倍
  - 递归找出剩余面积可容纳的最大方块，1680*640 -> (640*2+400)*640 -> 400*640 -> (400+240)*400 -> 240*400 -> (240+160)*240 -> 160*240 -> (160+80)*160 -> 80*60(边界条件)
  1680*640 -> (640*2+400)*640
  
  400*640 -> (400+240)*400
  
  240*400 -> (240+160)*240
  
  160*240 -> (160+80)*160
  
  80*60(边界条件)，因此对于（1680*640）的土地，适用的最大方块为80*80
快速排序（最快的排序算法之一）：
- 核心思想：分治法。它的实现方式是每次从序列中选出一个基准值(pivot)，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边（数组分成两个子数组），然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动（对这两个子数组递归进行快速排序），重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列
- 边界条件：空数组/只含一个元素的数组不用排序
- 速度取决于pivot的选择，平均时间复杂度 $O( n*log n)$ ，最坏情况 $O( n^2)$ ，实现时应随机选择用作pivot的元素
- 最坏情况：假设总是将第一个元素作为pivot，且要处理的数组是有序的，数组并没有分成两半，其中一个子数组始终为空，使得调用栈很长 $O (n)$ ，而最佳情况栈长为 $O (log n)$ (最佳情况也是平均情况)，每层需要时间均为 $O (n)$ 。因为快速排序不检查输入数组是否有序，因此它依然尝试对其进行排序
- ```
def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]#所有小于等于基准值的
        greater = [i for i in array[1:] if i > pivot]#所有大于基准值的
        return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([10,5,2,3]))
```
快速排序与合并排序
- 在大O表示法 $O(n)$ 中， $n$ 实际上是指 $c*n$ ，其中 $c$ 指算法所需的固定时间量，被称为常量。
- 常量的影响一般很小，例如对于二分查找（ $c=1s$ ）和简单查找（ $c=10ms$ ）来说，在40亿个元素列表中查找所需时间，前者（ $1s*32=32s$ ）后者（ $10ms*40亿=463天$ ），二分查找还是快的多，常量没什么影响
- 常量的影响可能很大，例如对于快速查找和合并查找，快速查找的常量比合并查找小，如果二者运行时间都是 $O( n*log n)$ ，快速查找的速度将更快，实际上，快速查找的速度确实更快，对于最坏情况，遇上平均情况的可能性要大得多
散列函数
- 将输入映射到数字
- 函数满足的要求：必须是一致的，即每次输入相同时，输出也要相同|||将不同的输入映射到不同的数字（在最理想情况，散列函数将键均匀地映射到散列表的不同位置）
- 良好的散列函数：让数组中的值呈均匀分布，可以使用SHA函数
填装因子
- $填装因子=散列表包含的元素数/位置总数$
- 度量散列表中有多少位置是空的，一旦填装因子开始增大，需要调整长度（resizing）,通常将数组增长一倍，然后使用函数hash将所有元素插入到新的散列表中
- 一个不错的经验：一旦 $填装因子>0.7$ ,就调整散列表的长度
冲突(collision)
- 给两个键分配的位置相同。处理方法：若两个键映射到同一位置，就在该位置存储一个链表，单链表长度过长时，散列表的速度就会很慢（散列函数设计不好时，如果使用的散列函数很好，链表就不会很长）
- 避免冲突需要有：较低的填装因子|||良好的散列函数
散列表(hash table)
- 也被成为散列映射、映射、字典、关联数组，适合用于模拟映射关系，用于防止重复等场景
- 使用散列函数和数组创建的数据结构：散列表（一种包含额外逻辑的数据结构），因为使用数组来存储数据，因此其获取元素的速度与数组一样快
- 与数组和链表直接映射到内存不同，散列表使用散列函数来确定元素的存储位置
- 散列表由键和值组成。无需自己实现散列表，任一优秀的语言都提供了散列表实现，e.g. python提供的散列表实现为字典，可使用dict()来创建散列表，如果使用list()进行查找，只能使用简单查找，速度会很慢
- 散列表性能：平均情况 $O(1)$ ， $O(1)$ 被称为常量时间，表示不管散列表多大，所需时间都相同，兼具数组和链表的优点
  
  散列表（平均情况）散列表（最坏情况）数组链表
  
  查找 $O(1)$ $O( n)$ $O(1)$ $O(n)$
  
  插入 $O(1)$ $O(n)$ $O( n)$ $O( 1)$
  
  删除 $O(1)$ $O( n)$ $O( n)$ $O( 1)$
- 应用1：用于查找：基于姓名查找号码的电话簿、DNS解析
- 应用2：用于缓存：一种常用的加速方式，提高网站的访问速度，用户能够更快看到网页，且服务器需要做的工作更少，缓存的数据存储在散列表中，键和值分别为url和页面数据
图：
- 由节点和边组成，直接相连的节点成为邻居，分为有向图、无向图
- 实现：散列表，键：节点，值：节点的邻居构成的列表
广度优先搜索（breadth-first search, BFS）
- BFS是一种用于图的查找算法
- 解决A,B两点之间是否有路/A,B两点之间最短路径问题的算法：首先使用图建立问题模型，其次使用BFS解决问题
- 应用：编写国际跳棋AI，计算最少走多少步就可以获胜|||编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改为正确的单词|||根据人际关系网络找到关系最近的医生
- 实现：队列，在python中可使用函数deque创建一个双端队列，需要维护数组保存已检查过的人（searched），防止程序形成无限循环（e.g. 图中只包含两个节点，双向边）。算法将不断执行直到满足以下条件之一：
  - 找到一位芒果经销商
  - 队列变空，即你的人际关系网中没有芒果经销商
- 运行时间： $O(V+E)$ ,其中 $V$ 为顶点（使用队列）， $E$ 为边数（在整个关系网中搜索）。
- ```
from collection import deque
def search(name):
    search_queue = deque()#创建一个队列
    search_queue += graph[name]#将邻居（数组）都加入到这个搜索队列中
    searched = []#这个数组用于记录检查过的人
    while sear_queue:#只要队列不为空
        person = search_queue.popleft()#就取出其中的第一个人
        if person_is_seller(person):#检查这个人是否为芒果经销商
            print(person+' is a mango seller!')
            return True
        else:
            search_queue += graph[person]#不是，将这个人的朋友都加入到队列中
            searched.append(person)#将这个人标记为检查过
    return False

def person_is_seller(name):
    return name[-1] == 'm'
```

	数组	链表
读取	$O(1)$	$O(n)$
插入	$O(n)$	$O(1)$
删除	$O(n)$	$O(1)$ [如何能够立即访问要删除的元素时]

1997=615*3+152
615=152*4+7
152=7*21+5
7=5*1+2
5=2*2+1
2=2*1+0（当被加数为0时，得出1997与615之间最大公约数为1）

1680640 -> (6402+400)*640
400640 -> (400+240)400
240400 -> (240+160)240
160240 -> (160+80)160
8060(边界条件)，因此对于（1680640）的土地，适用的最大方块为80*80

	散列表（平均情况）	散列表（最坏情况）	数组	链表
查找	$O(1)$	$O( n)$	$O(1)$	$O(n)$
插入	$O(1)$	$O(n)$	$O( n)$	$O( 1)$
删除	$O(1)$	$O( n)$	$O( n)$	$O( 1)$

Dijkstra算法

广度优先搜索的应用场景针对图中边权重相同的情况【非加权图】，找到的“最短路径”是指段数最少。当图中边的权重不同时【加权图】，需要使用Dijkstra算法，只适用于权重为正的有向无环图（DAG）【使用散列表graph维护节点和有向边的权重】,即应用在有向图的场景下【无向图中每条边都是一个环，绕环的路径不可能是最短路径】，找出的是总权重最小的路径。
算法步骤：
- 找出可在最短时间内到达的节点
- 如果找到前往该节点的邻居的更短路径，更新该节点的邻居开销【维护costs散列表，维护节点和其开销】
- 重复这个过程，直到对图中的每个节点都这样做了
- 计算最终路径【维护parent散列表存储节点和其父节点，用于最终回溯】
算法假设：对处理过的节点，没有前往该节点的更短路径
负权边
- 负权边无法使用该算法
- 不满足算法假设（可能先增后减能够获取更短路径）
- 使用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
node = find_lowest_cost_node(costs)#在未处理的节点中找出开销最小的节点
while node is not None:#这个while循环在所有节点都被处理过后结束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():#遍历当前节点的所有邻居
        new_cost = cost + neighbors[n]#开销指从起点前往该节点需要多长时间
        if costs[n] > new_cost:#如果经当前节点前往该邻居更近
            costs[n] = new_cost#就更新该邻居的开销
            parents[n] = node#同时将该邻居的父节点设置为当前节点
    processed.append(node)#将当前节点标记为处理过
    node = find_lowest_cost_node(costs)#找出接下来要处理的界定啊，并循环

贪婪算法
- 寻找局部最优解，企图以这种方式获得全局最优解，易于实现，运行速度快，是不错的近似算法
- 调度问题：根据课表，将尽可能多的课安排在某间教室上
  - 每次都选择结束最早的课，后选的开始时间要晚于之前的结束时间（贪婪思想）
- 集合覆盖问题：你办了个广播节目，要让全美50个州的听众都听到，需要决定节目在哪些广播台播出，每个广播台播出需要支付费用，力图在尽可能少的广播台播出，每个广播台都覆盖特定的区域，不同广播台覆盖区域可能重叠
  - 列出每种可能广播台集合（精确解），可能子集有 $2^n$ ,因此运行时间 $O(2^n)$
  - 贪婪算法（近似解）：选出这样一个广播台，即它覆盖了最多的未覆盖州，即便这个广播台覆盖了一些已覆盖的州也没关系。重复第一步，直到覆盖了所有的州。运行时间 $O(n^2)$

while states_needed:
    best_station = None#覆盖了最多的未覆盖州的广播台
    states_covered = set()#包含该广播台覆盖的所有未覆盖的州
    for station, states in stations.items():
        covered = states_needed & states#集合交集
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered 
  states_needed -= states_covered
    final_stations.add(best_station)#存储最终选择的广播台

近似算法优劣标准：
- 速度有多快
- 近似解与最优解的接近程度
NP完全问题
- 集合覆盖问题：为橄榄球队挑选队员，清单上列出对球队的所有要求，球队名额有限，每个候选球员都满足某些需求。
  - 近似求解：找出符合最多要求的球员，不断重复这个过程直到球队满足要求（或名额已满）
- 旅行商问题：近似算法（找到较短路径即可），具体的，随便选择出发城市，每次选择要去的下一个城市时，都选择还没去的最近的城市
  - 找出经由指定几个点的最短路径即旅行商问题——NP完全问题
  - 不指定途径点，单纯求解两点之间的最短路径即Dijkstra算法
- 两问题共同点：需计算所有解，并从中选出最小/最短的那个
- NP完全问题：没有找到快速求解精确解的方法，最佳的做法即使用近似算法。但判断问题是否为NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。以下是一些tips：
  - 元素较少时算法运行速度非常快，随着元素数量增加，速度会变得非常慢
  - 涉及“所有组合”的问题通常是NP完全问题
  - 不能将问题分成小问题，需考虑各种可能情况，可能是NP完全问题
  - 如果问题涉及序列（e.g.旅行商问题中的城市序列）且难以解决，可能是NP完全问题
  - 如果问题涉及集合（e.g.广播台集合）且难以解决，可能是NP完全问题
  - 如果问题可转换为集合覆盖问题或旅行商问题，肯定是NP完全问题
动态规划：
- 每个DP算法都从一个网格开始，单元格中的值通常就是你要优化的值，e.g.背包问题中，单元格值为物品价值。每个单元格都是一个子问题，应考虑如何将问题分解成子问题，这有助于你找出网格的坐标轴。
- 动态规划可帮助你在给定约束条件下找到最优解。e.g.背包问题中，必须在背包容量给定的情况下，使得包含的物价总价值最高。
- 背包问题：
  - 问题描述：一个人有一个可装N磅的背包，可放的物品(共M件)对应不同的磅数和价值，为了让总价值最高应该选择那些物品？
  - 背包问题的网格：维护一个二维表格（ $M*N$ 维），表格行为物品（M行），列为1~N不同容量的背包，不断填充表格填满后就找到问题的答案。
  - 最优子结构： $CELL[i][j] = max(上一个单元格的值CELL[i-1][j], 当前商品价值+CELL[i-1][j-当前商品的重量])$ 前者即不放当前商品的价值
  - 明确最优子结构后，当增加物品种类时，无需重新执行之前所做的计算（DP逐步计算最大价值），只需添加新行填充即可
  - 沿网格的一列往下走，最大价值可能降低吗？不可能，每次迭代都存储当前的最大价值，不可能比以前低
  - 行的排列顺序发生变化时结果将如何？不会，各行的排列顺序无关紧要
  - 可以逐列而非逐行填充网格吗？就这个问题而言不会，但对于其他问题可能有影响
  - 添加一件更小的商品会怎样？最小单位从1磅变为0.5磅，需要重写调整网格，考虑的粒度更细
  - 可以放商品的一部分吗？动态规划（要么放，要么不放）无法处理这样的问题，可使用贪婪算法处理这种情况（尽可能多放价值最高的物品，如果放完了，再尽可能放价值次高的物品...）
- 旅游行程最优化
  - 问题描述：你有一个列举很多名胜所需的时间以及评分的清单，假期两天的话，能确定该去游览哪些名胜吗？
  - 分析：也是一个背包问题，约束条件不是背包的容量，而是有限的时间，不是决定该装入哪些物品而是决定该去游览哪些名胜。
  - DP能够解决子问题并使用这些答案解决大问题，仅当每个子问题都是离散的，即不依赖其他子问题时。当子问题见互相依赖时，无法使用DP求解。
  - 计算最终的解时会涉及两个以上的子背包吗？根据DP的设计最多只需合并两个子背包，因此不会，但这些子背包可能有包含子背包
  - 最优解可能导致背包没装满吗？可能
- 最长公共子串
  - DP中要将某个指标最大化，给定两个字符串，判断二者间的最长公共子串。网格中的值通常为要优化的值，这里为两个字符串都包含的最长子串的长度，坐标轴为两个单词。如何将问题划分为子问题呢，即网格如何填充？
  - 没有找出计算公式的简单办法，必须通过尝试才能找到管用的公式。
```
if word_a[i] == word_b[j]:#两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1
else:#两个字母不同
    cell[i][j] = 0
```
    V I S T A
    
    H 0 0 0 0 0
    
    I 0 1 0 0 0
    
    S 0 0 2（最终答案） 0 0
    
    H 0 0 0 0 0
  - 对于该问题最终答案不一定位于最后的单元格中（与上一个背包问题最终答案总在最后的单元格中不同）
- 最长公共子序列
  - 两个单词中都有的序列包含的字母数，e.g.单词fish和fosh
```
if word_a[i] == word_b[j]:#两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1
else:#两个字母不同
    cell[i][j] = max(cell[i-1][j],cell[i][j-1])
```
    F O S H
    
    F 1 1 1 1
    
    I 1 1 1 1
    
    S 1 1 2 2
    
    H 1 1 2 3
- 实际应用
  - 生物学家根据最长公共序列确定DNA链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案
  - 命令git diff用于指出两个文件的差异，是使用DP实现的
  - 编辑距离指出了两个字符串的相似程度，也是使用DP计算得到的，编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
  - Microsoft Word等具有断字功能的应用程序，使用DP确定了在什么地方断字以确保行长一致。
K最近邻算法
- 一种机器学习分类算法（编组），可用来构建推荐系统，e.g.Netflix为用户创建一个电影推荐系统，向Priyanka推荐电影，利用喜好相似（相似程度如何确定？）的用户距离较近（Priyanka与最近的K个人，e.g. Justin, JC, Joey, Lance, Chris），因此他们喜欢的电影可能Priyanka也喜欢。
- 相似程度如何确定？首先需要进行特征选取（即将样本转换为一系列可比较的数字），e.g.如何判断一个水果是橙子还是柚子？可以根据颜色和个头判断，一般而言，柚子更大更红。对这个问题，个头、红的程度即问题的特征，每种水果用2个数字表示，根据特征将不同样本放到图表中，转化为一组坐标，用于求解距离远近。使用KNN时，挑选合适的特征很重要（与问题紧密相关的特征，且是不偏不倚的特征，e.g.只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）
- 对电影推荐系统问题，将用户放入图表中，即可计算他们之间的距离了。方法：用户注册是，要求他们指出对各种电影的喜欢程度。这样，对每位用户，都将获得一组数字（构建图表）,如下表：
  
  Priyanka Justin Morpheus
  
  喜剧片 3 4 2
  
  动作片 4 3 5
  
  生活片 4 5 1
  
  恐怖片 1 1 3
  
  爱情片 4 5 1
  
  每位用户都用5个数字表示。
- 回归：用于预测结果，e.g. 进一步预测Priyanka将给这部电影打多少分，假设k=5，利用与其最近的5个人对该电影的评分预测Priyanka的打分，e.g. Justin:5, JC:4, Joey:4, Lance:5, Chris:3，预测结果为打分的平均值4.2。
- 余弦相似度：可用于计算两位用户的距离，不计算两个矢量的距离，而比较它们的角度。
- OCR，光学字符识别，google用来实现图书数字化，使用KNN实现，通过浏览大量的图像，将字的特征提取出来（训练 training），遇到新图像时，提取该图像的特征找出它最近的邻居即可。一般而言，OCR算法提取线段、点和曲线等特征。
- 创建垃圾邮件过滤器：使用朴素贝叶斯分类器，首先需使用一些数据对分类器进行训练。可研究句子中的每个单词，看它在垃圾邮件中出现的概率是多少。
二叉查找树（binary search tree）
- 对其中的每个节点，左子节点的值都比它小，右子节点的值都比它大
  
  数组二叉查找树
  
  查找 $O(log n)$ $O(log n)$
  
  插入 $O(n)$ $O(log n)$
  
  删除 $O(n)$ $O(log n)$
- 缺点：不能随机访问，处在不平衡状态时，性能不佳
高级数据结构
- 红黑树：处于平衡状态的特殊二叉查找树
- B树：一种特殊的二叉树，数据库常用它来存储数据
- 堆
- 伸展树
反向索引
- inverted index，一种数据结构，通过构建散列表，键为单词，值为包含指定单词的页面，将单词映射到包含它的搜索页面，常用于创建搜索引擎
傅里叶变换
- 给定数字信号，傅里叶变换能够将其中的各种频率分离出来。因此，可用于数字信号的压缩、地震预测和DNA分析、音乐识别软件
并行算法
- 对数组进行排序是，快速排序的并行版本所需时间为 $O(n)$
- 可改善性能和可扩展性，但速度的提升是非线性的，即pc装备了两个而非一个内核，算法的速度也不可能提高一倍，原因：
  - 并行性管理开销，e.g.对一个含1000个元素的数组排序，让两个内核每个内核对其中500个元素排序，再合并成一个有序数组，合并也是需要时间的
  - 负载均衡：10个任务，给每个内核都分配5个，但给内核A的任务很容易，10秒就完成了，而给内核B的任务很难，需要50秒完成，如何均匀分配工作让两个内核都一样忙？
MapReduce
- 在并行算法只需2-4个内核时，完全可在笔记本上运行，但如果数百个内核，可让算法在多台计算机上运行
- 是一种分布式算法（一种特殊的并行算法），可通过Apache Hadoop来使用它
- Map映射函数：接受一个数组，对其中的每个元素执行同样的处理。e.g. 你有一个URL清单，需要下载每个URL指向的页面并将内容存储在数组arr2中，当包含大量URL时，执行耗时很长。如果有100台计算机，map能够自动将工作分配给这些计算机去完成。
```
>>> arr1 = # A list of URLs
>>> arr2 = map(download_page, arr1)
```
- reduce归并函数：将很多项归并为一项
```
>>> arr1 = [1,2,3,4,5]
>>> reduce(lambda x,y: x+y, arr1)
15
```
- MapReduce使用这两个简单概念在多台计算机上执行数据查询，数据集很大（数十亿行）使用MapReduce只需几分钟就可获得查询结果，传统数据库可能要耗费数小时
布隆过滤器和HyperLogLog
- 给定一个元素，判断它是否包含的这个集合中，为快速判断可使用散列表，但元素数量庞大（数万亿）时，散列表非常大，占用大量存储空间。
- 布隆过滤器：一种概率性的算法/数据结构，它提供的答案有可能不对，但很可能是正确的。优点：占用存储空间少，非常适合用于不要求答案绝对准确的情况。e.g.判断网页以前是否已搜集，可不使用散列表（答案绝对可靠）而使用布隆过滤器。
  - 可能出现错报的情况，即Google可能指出这个网站已搜集，但实际上并没有搜集
  - 不可能出现漏报的情况，如果布隆过滤器说这个网站为搜集，就肯定未搜集
- HyperLogLog：一种概率性的算法/数据结构，Google要计算用户执行不同搜索的数量，需要一个日志包含用户执行的不同搜索，有用户执行搜索时，Google必须判断该搜索是否包含在日志中，如果不在必须将其加入到日志中。这样会导致日志很大，而HyperLogLog近似计算集合中不同的元素数，它也不能给出准确答案，但很可能是正确的，而占用的内存空间却少很多。
- 面临海量数据且要求答案八九不离十时，可考虑使用概率性算法
SHA算法
- 之前介绍的散列函数，用于确定将键关联的值放到数组中，这里希望散列函数的结果是均匀分布的，用于创建散列表的散列函数接受一个字符串，返回一个索引号
- SHA：另一种散列函数，安全散列算法（secure hash algorithm）,给定一个字符串，SHA返回其散列值（一个很长的字符串）。SHA根据字符串生成另一个字符串，对于每个不同的字符串，SHA生成的散列值都不相同。
- 可使用SHA判断两个文件是否相同，在比较超大型文件时很有用，可计算它们的SHA散列值，再对结果进行比较
- 还能在不知道原始字符串的情况下对其进行比较，e.g. Gmail攻击者窃取了所有的密码，但你的密码并未暴露，因为Google存储的并非密码，而是密码的SHA散列值。输入密码时，Google计算其散列值并将结果同其数据库中的散列值进行比较。这种散列算法是单向的，可根据字符串计算出散列值，但无法根据散列值推断出原始字符串。
- SHA是一个系列算法：SHA-0、SHA-1、SHA-2、SHA-3 ，前两者已被证明存在一些缺陷，当前最安全的密码散列函数是bcrypt
- 是一个局部不敏感算法，对字符串做微小修改得到的散列值将截然不同，令攻击者无法通过比较散列值是否类似来破解密码
局部敏感的散列算法
- Simhash算法，对字符串做细微修改，生成的散列值也只存在细微的差别，能够通过比较散列值来判断两个字符串的相似程度。用于判断网页是否已搜集，用于判断学生论文是否是从网上抄的、检查上传内容是否与某些有版权的内容类似（自动拒绝）
Diffie-Hellman密钥交换
- 加密算法，一种双方无需知道的加密算法，不必会面协商要使用的加密算法，且破解加密的消息几乎不可能。使用两个密钥：公钥（公开的可发布，有人要向你发送消息时，使用公钥对其进行加密）和私钥（加密后的消息只有使用私钥才能解密，只有知道私钥才能解密消息）。
- 替代算法RSA
线性规划
- 在给定约束条件下，最大限度的改善指定的指标。所有的图算法都可使用线性规划实现。
- 使用Simplex算法

算法图解笔记

猜你喜欢

热点阅读

	Priyanka	Justin	Morpheus
喜剧片	3	4	2
动作片	4	3	5
生活片	4	5	1
恐怖片	1	1	3
爱情片	4	5	1

	数组	二叉查找树
查找	$O(log n)$	$O(log n)$
插入	$O(n)$	$O(log n)$
删除	$O(n)$	$O(log n)$

	I	S
H	0	0
I	1	0
S	0	2（最终答案）
H	0	0