算法图解笔记

第一章 算法简介

二分查找

• 必须是有序的数组
• 对于n个元素的列表，使用二分查找最多需要 log2 n步，用普通的查找最多需要n步

  def binary_search(l, item):
      low = 0
      high = len(l) - 1
      while low <= high:
          mid = int((low + high) / 2)  # 这里需要转成int，不然没办法做index
          if l[mid] == item:
              return mid
          elif l[mid] < item:
              low = mid + 1
          else:
              high = mid - 1
      return None

运行时间

• 大O表示法表示了操作数，表示的是这个算法的增量
• 大O表示了在最糟情况下的运行时间 -> 但是也是需要讨论平均时间的
• 常见的大O时间
  • logN 对数时间 Logarithmic
  • N 线性时间 Linear
  • N * logN 包括快速排序等，速度较快
  • N ^ 2 选择排序等，速度较慢
  • N！ Factorial time 非常慢

旅行商问题 travelling salesman problem, TSP

• 一个搞不好可以用n！来解决的问题
• 你要去五个不同的地方，需要规划怎么样路线最短，最开始的思路就是把每种可能性都列出来，然后对每种路线进行计算。这样的话五个地方就是120种，地方越多越呈阶乘增长

第二章 选择排序

数组和链表

• 数组需要的空间是固定的（也就是说必须连在一起），所以如果后面加进去了其他东西的话就不行了，需要转移位置，或者预留空间
• 链表的每一个位置都会有到下一个位置的指针，所以不需要移动元素。
  • 但是链表的问题在于，如果想直接找后面的东西的时候需要一个接着一个读取
• 需要读取整个数据的时候链表效率很高，需要跳跃的时候链表效率很低。而数组在读取随机元素的时候效率很高
  • 数组插入 / 删除线性，读取常数。
  • 链表读取线性，插入 / 删除常数。
• 在实际中，因为数组支持随机访问（但是链表只支持顺序访问），所以数组的适用范围大一些

选择排序

• 实现方法：每次都从所有的里面选出最大 / 最小，然后放在最开头
• 时间复杂度 n ^ 2

  def select_sort(l):
      newArr = []
      for j in range(len(l)):
          smallest = float('inf')
          index = None
          for i, item in enumerate(l):
              if item < smallest:
                  smallest = item
                  index = i
          newArr.append(l.pop(index))  # 注意这里需要把l的大小改变了
          # 但是是在带l的loop外面变得所以没有关系
      return newArr

第三章 递归 recursion

何为递归

• 函数自己调用自己
• 递归和循环的作用效果是相同的，没有性能上的优势，但是可以让方案更加清晰
  • base case：告诉函数什么时候不再调用自己，停止循环
  • recursive case：函数调用自己

栈 stack

• 先进后出的数据结构，push（压入）和pop（读取和删除）
• 在调用另一个函数的时候，当前函数暂停并且处于未完成状态，函数的所有变量都储存在内存里
• 使用递归的一个问题：如果调用栈的时候很长，会占据大量内存
  • 这种时候需要重新编写代码使用循环
  • 或者使用尾递归（并不是所有语言都支持）

第四章 快速排序（分而治之 divide and conquer）

分治

• 核心：把一个问题分成子问题，再把子问题分成更小的子问题，最后的子问题可以直接求解，这样的话原问题的解就是子问题的解的合并
  • 比如把n规模的问题分成k份，然后在k个问题里面分别再分开
• 特征
  • 问题缩小规模可以轻松解决
  • 可以分解成若干个小问题
  • 分解出的子问题可以再合并（如果不满足这条，应该考虑贪心或者DP）
  • 分解出的各个子问题是独立的（不满足应该考虑DP）
• 不用循环而用递归：函数式编程里面没有循环（Haskell）

def RecursiveSum(l):
    if l == []:
        return 0
    else:
        return l[0] + RecursiveSum(l[1:])  # 这里不能改变l本身的大小


def MaxNum(l):
    if len(l) == 2:
        return l[0] if l[0] > l[1] else l[1]
    submax = MaxNum(l[1:])
    return l[0] if l[0] > submax else submax

• 注意：
  • 需要找好基本条件，如果找最大值的base就是还剩下两个值
  • 注意return的内容

快速排序

• 比选择排序速度快很多
• base条件，一个元素或者空的数组就不需要排序了
• 需要设定一个基本值（比如取第一个值，根据这个值把原数组分成两部分），这样这三个大块就分类完成了。然后对于每个小块，再继续分组
  • 比基准小的子数组
  • 基准
  • 比基准大的子数组

    def QuickSort(l):
        if len(l) < 2:
            return l
        else:
            piv = l[0]
            # 这里是快读得到比他大和比他小的写法，主要从l[1:]开始
            less_part = [i for i in l[1:] if i < piv]
            more_part = [i for i in l[1:] if i > piv]
            return QuickSort(less_part) + [piv] + QuickSort(more_part)
    
    
            # 注意这里piv是个int，所以连接的时候需要改成list

时间复杂度

• 快速排序的速度取决于选择的piv的值的大小，也就是说如果完全排好的情况下，复杂度是n2
• 合并排序的速度是 nlogn，快速排序的平均速度是 nlogn，最佳情况是 logn
  • 快速排序需要logn层，每层需要把n个元素全都遍历一次，所以最终的结果是nlogn
• 在计算复杂度的时候，复杂度是操作的次数，而这个次数需要乘一个每次操作的常量，在快速排序的时候常量更小，而且快速排序没那么容易遇到最糟情况

第五章 散列表（hash表）

hash函数

• 最终的目的是查找的时候时间复杂度是 1
• 函数构造：把输入映射到一个数字
  • 无论你什么时候输入，输出的数字是一致的
  • 将不同的输入映射到不同的数字
  • 知道整个存储的范围有多大，不会返回超过这个大小的数字

应用：缓存

• 网站的缓存数据就存在hash表里面，这样访问速度更快，网站本身需要做的工作更少
• 访问一个网页 -> 是否在缓存里 -> 有的话调用缓存 -> 没有的话存进缓存

冲突

• 虽然假设的时候认为每个东西都被映射到不同地方，其实会产生冲突
• 这种情况下要在hash后面加上list
  • hash函数需要把内容比较平均分分配
  • 如果储存的链表很长，那么性能就会急剧下降

性能

• 最佳性能，1
• 最糟性能，插入，删除，查询全都是n
• 装填因子： 装填的元素数 / 元素总数
  • 一旦超过0.7就需要调整hash的长度了

第六章 BFS：最短路径问题

BFS

• 用于图的查找算法，可以解决两种问题
  • 从A出发有前往B的路径吗
  • 从A出发到B的路径最短是什么
• 实现图 -> hash表，需要将node映射到所有的邻居
• 在python里面使用deque创建双端队列
• 算法实现（广度搜索）：
  • 创建一个队列，储存用于查找的人
  • 首先把初始化的人载入队列
  • 从队列里弹出一个人，查找他是不是（查过之后标记成已检查，列表记录），不是的话把这个人的相邻加入队列（一直重复）
    • 标记成已检查非常重要，因为不标记的话可能会陷入无限循环
  • 如果最后队列空了还没找到，那就是没有

def BFS(name, graph):
    search_queue = deque()
    search_queue += graph[name]
    searched = [name]  # 用来储存已经探索过的人数
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person[-1] == "m":  # 只是一个判断是不是这个人的办法
                return person
            else:
                search_queue += graph[person]
                searched.append(person)
    return None

更新版本，不但可以搜索还可以计算长度

def BFS(name, graph):
    search_queue = deque()
    search_queue.append(name)
    searched = [name]  # 用来储存已经探索过的人数
    distance = {name: 0}
    while search_queue:
        current = search_queue.popleft()
        for person in graph[current]:
            if person not in searched:
                searched.append(person)
                distance[person] = distance[current] + 1
                if person[-1] == "m":
                    return person, distance[person]
                else:
                    search_queue.append(person)
    return None, None

• 注意点：
  • 增加了distance这个dict来储存开始点到这个点的距离
  • 在初始化的时候只在已搜索队列里添加了第一个点的信息，在后面的循环里才添加后面的点
  • 对于每个从queue里面拿出来的点，如果不在已经查找的点里就一定需要加进去，并且计算距离，距离即是和上一点的距离+1
  • 计算过距离之后再判断是不是要找的点

• 运行时间

  • 需要沿着每条边前进，所以在边上的运行时间是 O(E)
  • 把每个人加到queue里面也需要时间，每个人的时间是常数，所以人数的时间是 O(V)
  • 总的运行时间 E + V

• 拓扑排序

  • 如果任务A依赖于任务B，那么任务A就必须排在B的后面，这种就是拓扑排序

第七章 狄克斯特拉算法

• 之前的图找的是最短路径，现在需要给图加权，找加权之后的最短路径
• 加权之后的最短不一定是边数最短
• 负的权重不顶用，因为负权重不能确定没有比目前消耗更小的
• 书里写的错的地方：可以有环，没环都是树了！有向无环图可以直接拓扑排序
• 核心思想：找到到这个点消耗最少的路径，并且确保没有路径比这个小了

算法流程

• 找出消耗最低的点
• 更新这个点相邻点的开销
• 重复这个过程，直到对所有点都做了（即A点最小之后更新B点，然后更新C点，以此类推）
• 计算最终流程

具体实现

• 创建一个表格
  • 包含了每一项和每一项的具体开销，目前不知道的开销标记成inf
  • 需要包含每个点的父节点，才能保证最后可以计算流程
• 不停的更新这个表，从开销最低的一直更新到开销最高的，如果更新了开销的话同样需要更新父节点
• 在确定路径的时候，从结尾的地方开始找，然后一路找到开头

一个问题：关于图在python里面的表示

• 实际就是一个dict叠dict，如果直接访问G[a][b]就可以直接得到这两个点的距离

• 如果没有加权的话，可以直接dict叠list，因为不需要记录距离了

• 注意点

  • 最好是最开始指定了第一个消耗最低点，然后再循环里面最后找消耗最低点
  • 初始化的时候注意：cost里面初始为0，father里面去掉这个点，Node（cost最低点）初始化成这个点，循环的条件是Node不是空

    def dijkstra(graph, src, target):
        # 需要创建一个cost表和一个父节点表
        cost = {}
        father = {}
        visited = []
        for i in graph.keys():  # 访问这个图里面所有的key，就是所有的店
            cost[i] = float('inf')
            father[i] = None
        cost[src] = 0  # 起始点的cost是0
        father.pop(src)  # 起始点不需要父节点
    
        Node = src
        # 最小开销点还存在的时候更新所有的点
        while Node is not None:
            for near in graph[Node]:
                new_distance = cost[Node] + graph[Node][near]
                if new_distance < cost[near]:
                    cost[near] = new_distance
                    father[near] = Node
            visited.append(Node)
    
            # 找到最小开销的点(放在循环里面好一点)
            Node = None
            smallest = float('inf')
            for i in cost:
                if i not in visited:
                    if cost[i] < smallest:
                        smallest = cost[i]
                        Node = i
    
        # 跳出循环，得到结果
        
    
    
    N = {
        "start": {"a": 2, "b": 6},
        "a": {"fin": 1},
        "b": {"a": 3, "fin": 5},
        "fin": {}
    }
    # print(N["start"]["a"])
    dijkstra(N, "start", "fin")

第八章 贪心算法

• 处理npc问题，即没有快速算法的解法的问题
• 对NPC问题找到近似解

例子问题

• 课表问题：
  • 希望尽可能多的课在这个屋子里面上，但是上课时间冲突，如何排课
  • 先找到这个教室里最早开始的课，然后找到这节课结束之后最早开始的课
• 装东西
  • 背着包去装东西，容量有限，如何装到最大价值的
  • 从最大的开始装，但是得到的不是最优解，最优解应该动态规划
• 核心思想：每一步都用局部最优解，得到的结果就是全局最优解。即使得不到最优解，也可以得到近似最优解

只能用贪心的问题

• 集合覆盖问题，比如想在全部区域广播，但是每家电台只覆盖特定区域，如果才能花费最小的计划
• 列出所有的可能性的话，复杂度是 2^n
• 近似算法：从覆盖最多地方的电台开始找，一直到覆盖所有地方
• 贪心算法的复杂度是 n^2，n是广播台的数量
  • 因为每次都需要遍历一次找出最需要的那个（n)，这样的操作需要进行最多n次（万一每次都覆盖不上）

NPC问题：从旅行商问题详解

• 旅行商问题和求路径问题的区别在于，旅行商问题需要访问一遍所有的地方，找到最短路线
• 旅行商问题需要查看所有的可能的路线
• 从简单问题出发
  • 两个地方的时候，可能的路线有两条（一来一回）
  • 三个地方的时候 6条
• 需要计算出所有的解才有可能从中选出最短的路线 -> NPC问题
• 近似方法：每次都去离得最近的地方

识别问题

• 元素较少的时候速度快，随着元素增加非常慢
• 涉及所有组合
• 不能分成小问题，必须考虑所有情况
• 涉及序列（比如旅行商中的城市序列），集合（集合覆盖问题）且难以解决。或者可以转换成这种问题的

第九章 动态规划

核心思想

• 把一个大的问题拆分成很多小问题的解的合并
• 最终的结果其实类似一个表，每次再得到新的结果的时候，其实是在比较
  • 同等大小下上一个的值（即上一行的值，这个值已经是之前储存下来的最大的值了）
  • 当前放新的东西的价值+放完这个东西之后剩下空间可以放的东西的最大价值（这个最大价值同样也被记录了）
• DP处理问题的时候只能整件的处理，也就是说分布应该是离散的而不是连续的
• 而且DP处理问题的时候各个子问题之间不能互相依赖，如果互相依赖了就很复杂了

最长公共子串

• 比如搜索引擎误输入，怎么判断相近词
• 每种动态规划都涉及网络，每个网格里面的值就是我需要优化的值
  • 每个单元格里是什么
    • 每个单元格是这个格子之前相同的字母数量
  • 如何把这个问题分成子问题
    • 如果相同，就是前一个的字母数+1，如果不同就是0
  • 网络的坐标轴是什么
    • 在这个问题中，是两个单词的各个字母
• 注意在这个问题里面，最终答案不是在最后出现的
• 最长公共字序列！！和子串不一样，对比的是序列而不是字母的个数
  • 当字母不同的时候，选择上边或者左边最大的那个

应用

• levenshtein distance（字符串的相似程度，也就是上面的公共子序列）
• 指出文件的差异，DNA的相似性，确定什么地方断字
• 核心思想：需要把两个str里面所有的substr的combination都计算一下
• 实现
  • 初始化条件：插入
  • 实际上来说一个格子有三种操作，删除，插入和置换，这个格子需要改变的操作是这三个操作的最小值
  • 删除 = d[i - 1][j] + 1
  • 插入 = d[i][j - 1] + 1 （相当于这个单词的前一个字母，加上一个插入，这两个没有本质区别）
  • 替换 = d[i - 1][j - 1] + cost，其中这个cost，如果两个相同就是0，两个不同就是1
• 具体说明见levenshtein distance说明

第十章 K最近邻

创建推荐系统

• 向这个人推荐电影，找到离这个人最近的五个用户
• 如何判断最近：特征抽取

第十一章 接下来如何

树（数据库 + 高级数据结构）

• 二叉查找树：对于每一个节点，左节点都比他小，右节点都比他大
  • 时间复杂度 logn
  • 平衡问题
• 延伸： B树，红黑树，堆，延展树

反向索引

• 搜索引擎的工作原理
• 把网页创建hash表，key是单词，value是包含单词的页面

傅里叶变换

• 信号处理

并行算法（提高速度）

• 对速度的提升是非线性的
  • 并行管理开销
  • 负载均匀

MapReduce

• 分布式算法
  • 把一台电脑上面处理的工作分布到多台电脑，处理大量数据
• 分布+归并

布隆过滤器

• 概率型数据结构：可能出现错报，但是不可能出现漏报
  • 储存空间很少

HyperLogLog

• 类似于布隆过滤器的算法，不能给出准确的答案但是占据的空间很小

SHA

• 另一种hash，安全散列算法，给定一个字符串返回hash
• 比较大型文件
• 检查密码
• 局部不敏感，修改其中一个字符，会改变很多

Diffie-Hellman 密钥交换

• 如何对消息加密，让只有收件人看得懂

线性规划

• 在给定的约束条件下最大限度的改善指定的指标