图解算法学习笔记

Contents

• 1 第一章，算法简介
  • 1.1 1.2，二分法查找元素
• 2 第二章，选择排序
  • 2.1 2.1，内存工作原理
    • 2.1.1 2.2.1，链表
    • 2.1.2 2.2.2，数组
    • 2.1.3 2.2.3，术语
  • 2.2 2.3，选择排序
  • 2.3 2.4，小结
• 3 第三章，递归
  • 3.1 3.2，基线条件和递归条件
  • 3.2 3.3，栈
    • 3.2.1 3.3.1，调用栈
    • 3.2.2 3.3.2，递归调用栈
  • 3.3 3.4，小结
• 4 第四章，快速排序
  • 4.1 4.1，分而治之
  • 4.2 4.2 快速排序
  • 4.3 4.3 再谈大Ｏ表示法
  • 4.4 4.4，小结
• 5 第五章，散列表
  • 5.1 5.3，冲突
  • 5.2 5.4，性能
  • 5.3 5.5，小结
• 6 第六章，广度优先搜索
  • 6.1 6.1，图是什么
  • 6.2 6.2，广度优先搜索
  • 6.3 6.3，队列
  • 6.4 6.4，代码实现图结构
  • 6.5 6.4.1 运行时间
• 7 参考资料

第一章，算法简介

1.2，二分法查找元素

一般而言，对于包含n个元素的列表查找某个元素，使用二分法最多需要log_{2}n步(时间复杂度为log_{2}n)，简单查找最多需要n步。大O表示法指出了算法最糟糕情况下的运行时间

第二章，选择排序

2.1，内存工作原理

在计算机中，存储多项数据时，有两种基本方式－数组和链表。但它们并非适用于所有情形。

2.2.1，链表

链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。链表结构直观显示如下图所示：

链表的优势在插入元素方面，那数组的优势又是什么呢？

2.2.2，数组

需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。

2.2.3，术语

数组的元素带编号，编号从0而不是１开始，几乎所有的编程语言都从０开始对数组元素进行编号，比如C/C++的数组结构和Python的列表结构。元素的位置称为索引。下面是常见数组和链表操作的运行时间。

2.3，选择排序

选择排序时间复杂度O(n^{2})

def findSmallest(arr):
    smallest = arr[0] # 存储最小的值
    smallest_index = 0 # 存储最小元素的索引
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest_index = i
            smallest = arr[i]
    return smallest
# 选择排序法对数组进行排序
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        arr.remove(smallest)
        newArr.append(smallest)
    return newArr
# 实例应用
print(selectionSort([5, 3, 6, 100])) # [3, 5, 6, 100]

2.4，小结

• 计算机内存犹如一大堆抽屉。
• 需要存储多个元素时，可使用数组或链表。
• 数组的元素都在一起。
• 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
• 数组的读取速度很快。
• 链表的插入和删除速度很快。
• 在同一个数组中，所有元素的类型都必须相同（都为int、 double等）。

第三章，递归

学习如何将问题分成基线条件和递归条件，学习如何使用递归算法，递归算法直观上更好理解，步骤简单。

3.2，基线条件和递归条件

编写递归函数时，必须告诉它何时停止，因此，每个递归函数有两个部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。

3.3，栈

栈的定义：栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。 调用栈(call stack)

3.3.1，调用栈

计算机在内部使用被称为调用栈的栈。调用另一个函数时，当前函数暂停 并处于未完成状态。该函数的所有变量的值都还在内存中。栈顶的方框指出了当前执行 到了什么地方。

3.3.2，递归调用栈

栈在递归中扮演着重要角色。使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。 + 重新编写代码 + 使用尾递归

3.4，小结

• 递归值的是调用自己的函数
• 每个递归函数都有两个条件：基线条件和递归条件
• 栈有两种操作：压如和弹出
• 所有函数调用都进入调用栈
• 调用栈可能很长，这将占用大量内存

第四章，快速排序

快速排序使用分而治之的策略，分而治之是我们学习的第一种通用的问题解决办法。 分而治之(divide and conquer，D&C)-一种著名的递归式问题解决办法。

4.1，分而治之

D&C 算法 是递归的。使用D&C解决问题的过程包括两个步骤： + 找出基线条件，这种条件必须尽可能简单。 + 不断将问题分解（或者说缩小规模），直到符合基线条件。 D&C 并非可直接用于解决问题的算法，而是一种解决问题的思路。

4.2 快速排序

C语言标准库中的函数qsort实现的就是快速排序。快速排序也是用了D&C思想。 对数组进行快速排序，步骤如下： 1. 随机选择一个基准值； 2. 将数组分成两个子数组：小于基准值的元素和大于基准值额元素； 3. 对这两个子数组进行排序。

在平均情况下，快速排序时间复杂度O(nlogn) 快速排序代码如下：

def quicksort(array):
    if len(array) < 2: 
        # 基线条件：为空或只包含一个元素的数组是“有序”的
        return array
    else:
        # 递归条件
        pivot = array[0] 
        less = [x for x in array[1:] if x <= pivot]
        greater = [x for x in array[1:] if x > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([4, 90, 0, 2, 17, 79, 12])) # [0, 2, 4, 12, 17, 79, 90]

4.3 再谈大Ｏ表示法

快速排序的独特之处在于，其速度取决于选择的基准值。在讨论快速排序的运行时间前，我 们再来看看最常见的大O运行时间。常用排序算法运行时间，如下图所示：

选择排序，其运行时间为O(n2)，速度非常慢。 还有一种名为合并排序（ merge sort） 的排序算法，其运行时间为O(n log n)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。 由对数的换底公式，loga n和 logb n只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作O(log n)，而不论对数的底是多少，是对数时间算法的标准记法。

4.4，小结

• D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元 素的数组。
• 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时， O(log n)的速度比O(n) 快得多。

第五章，散列表

数组和链表结构可以用以查找，栈不行。散列表也叫哈希表(Hash table)，散列表有些类似Python中的字典dict结构。散列表可用以： + 模拟映射关系； + 防止重复； + 缓冲/记住数据，以免服务器再通过处理来生成它们。

5.3，冲突

给两个键分配的位置相同，这被称为冲突（collision）。处理冲突最简单的办法就是：如果两个键映射到了同一个位置，就在这个位置存储一个链表。

5.4，性能

散列表，数组，链表的查找、插入、删除元素的时间复杂度，如下表所示：

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速 度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。 因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有： + 较低的填装因子； + 良好的散列函数。

5.5，小结

散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。 你可能很快会发现自己经常在使用它。 + 你可以结合散列函数和数组来创建散列表。 + 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。 + 散列表的查找、插入和删除速度都非常快。 + 散列表适合用于模拟映射关系。 + 一旦填装因子超过0.7，就该调整散列表的长度。 + 散列表可用于缓存数据（例如，在Web服务器上）。 + 散列表非常适合用于防止重复。

第六章，广度优先搜索

图算法：广度优先搜索（breadth-first search, BFS）算法 广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广 度优先搜索可以： + 编写国际跳棋AI，计算最少走多少步就可获胜； + 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将 READED改为READER需要编辑一个地方； + 根据你的人际关系网络找到关系最近的医生。

解决最短路径问题的算法被称为广度有限算法，一般步骤为： 1. 使用图来建立问题模型。 2. 使用广度优先搜索解决问题。

6.1，图是什么

图由节点（node）和边（edge）组成。

6.2，广度优先搜索

在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。

6.3，队列

栈：后进先出（Last In First Out，LIFO）的数据结构 队列：先进先出（First In First Out，FIFO）的数据结构，支持入队和出对操作。

6.4，代码实现图结构

图中每个节点都与相邻节点相连，散列表结构可以表示这种关系。 图分为有向图（directed graph）和无向图（undirected graph），有向图关系是单向的，无向图没有箭头，直接相连的节点互为邻居。对从自己出发有指向他人的箭头，则有邻居。

代码实例如下：

# 使用了队列的先进先出结构
from collections import deque

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

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    # This array is how you keep track of which people you've searched before.
    searched = []
    while search_queue:
        person = search_queue.popleft()
        # Only search this person if you haven't already searched them.
        if person not in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                # Marks this person as searched
                searched.append(person)
    return False

search("you") # thom is a mango seller! True

6.4.1 运行时间

如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为 O(边数)。你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为 O(1)，因此对每个人都这样做需要的总时间为 O(人数)。所以，广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作 O(V + E)，其中V为顶点（ vertice）数， E为边数。

参考资料

《图解算法》