真锋
永远保持一颗学习和专注的心
嵌入式视觉笔记

图解算法学习笔记

第一章,算法简介

1.2,二分法查找元素

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

第二章,选择排序

2.1,内存工作原理

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

2.2.1,链表

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

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

2.2.2,数组

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

2.2.3,术语

数组的元素带编号,编号从0而不是1开始,几乎所有的编程语言都从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运行时间。常用排序算法运行时间,如下图所示:

选择排序,其运行时间为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为边数。

参考资料

《图解算法》

赞赏

发表评论

textsms
account_circle
email

嵌入式视觉笔记

图解算法学习笔记
第一章,算法简介 1.2,二分法查找元素 一般而言,对于包含n个元素的列表查找某个元素,使用二分法最多需要$log_{2}n$步(时间复杂度为$log_{2}n$),简单查找最多需要n步。大O表示法指出了…
扫描二维码继续阅读
2019-05-01