算法图解笔记

2019-02-12  本文已影响0人  此间流逝

书名: 算法图解
出版社: 图灵出版社
网址: http://www.ituring.com.cn/book/1864

在学习C语言的时候，理解到了程序由算法+数据结构组成。算法的理解和学习是程序员必不可少的内容。这周看了《图解算法》这本书，书本采用Python语言，通俗易懂，虽然书本上有些算法没有讲解，但通过大量的例子加深对算法的理解，是不错的入门书籍。

下面是我看了书籍后做的读书笔记，便于日后复习加强学习。

图解算法

基础

表达的方式为: O(n) 其中n表示的是操作数，操作数前的O，所以称为大O表示法。

常见的大O运行时间

常见的运行时间

O(logn)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。

算法运行时间并不以秒为单位，而以操作数为单位，且从算法增速角度度量。

常量对大O表示法影响:
大O表示法的常量有时候事关重大，如快速排序比合并排序快，因为其大O表示运行时间都为O(nlogn)。有时常量无关紧要，如简单查找O(n)和二分查找O(nlogn)。

最糟情况:调用算法运行，经过最多次操作才得出结果。
最佳情况:调用算法运行时，经过最少次操作就得出结果。
平均情况:结果等同于最佳情况，如快速排序平均运行时间为O(nlogn)

例如:

def sum(list):
    if list == []: #基线条件
        return 0
    return list[0] + sum(list[1:]) #递归条件
    
#循环写法
def sumCircle(list):
    allSum = 0
    for i in list:
        allSum = allSum + i
    return allSum

特征:

元素较少运行速度非常快，随元素增加，速度变得非常慢

涉及“所有组合”问题通常是NP完全问题

不能将问题分成小问题，必须考虑各种可能情况，可能是NP完全问题

如果问题涉及序列且难以解决，则可能是NP完全问题

如果问题涉及集合且难以解决，则可能是NP完全问题

如果问题涉及旅行商和集合覆盖问题，则肯定是NP完全问题

数据结构

例如途中待办事项就是数组


数组

数组链表比较


比较
  1. 返回必须是一致的，即输入的返回值不发生变化
  2. 将不同的输入映射到不同数字。

散列函数和数组构成散列表。散列表也被称为散列映射、映射、字典和关联数组。Python提供的散列实现为字典，使用函数dict创建散列表。

散列表应用:

  1. 通过创建映射，用于查找
  2. 防止重复
  3. 将散列表用于缓存

使用散列表，可能会遇到冲突问题，即存储时分配的位置已经被使用。这时，要保证:散列函数很重要，理想情况是散列函数均衡地映射到散列表的不同位置，呈均衡分布；散列表存储的链表不要太长，不然影响效率。

性能:一般情况下，散列表兼具数组和链表的优点，在最糟糕的情况下，各种操作速度都很慢，这时要避免冲突，做到:较低的填装因子和良好的散列函数

散列表性能

填装因子:用于反映数组中被占用的位置数，计算公式为：

\frac {\text{散列表包含的元素数}}{\text{位置总数}}
填装因子越低，发生冲突的可能性越小，散列表性能越高。经验规则:一旦填装因子大于0.7，就调整散列表长度

队列

队列是一种先进先出(First In First Out, FIFO)的数据结构，而栈是一种后进先出(Last In First Out, LIFO)的数据结构。

图

图包括有向图和无向图。

有向图:边为箭头，箭头的方向指定了关系的方向，例如 dog \to animal表示狗属于动物

无向图:边不带箭头，其中的关系是双向的，例如 上海——广州表示上海可以到广州，广州也可以到上海

加权图:每条边都有关联的数字的图，这些数字称为权重(weight)。带权重的图称为加权图(weighted graph)，不带权重的图为非加权图(unweighted graph)，使用狄克斯特拉算法。

加权图

使用代码实现图:


实现图 
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'] = []

键值对交换顺序不会有影响，因为散列表是无序的。

拓扑排序:某种程度上说，有向图构成的列表是有序的，如果任务A依赖于任务B，则在列表中任务A必须在任务B后面，这就是拓扑排序，使用它可以根据图创建一个有序列表。

集合操作:

1)并集意味着集合合并 setA | setB

2)交集意味着找出两个集合中都有的元素 setA & setB

3)差集意味着将从一个集合中剔除出现在另一个集合中的元素 SetA - setB

对于其中的每个节点，每个节点最多只能有两个节点(对应二叉树的二),左子节点的值都比它小 ，而右子节点的值都比它大 。

在二叉查找树中查找节点时，平均运行时间为O(log n )，但在最糟的情况下所需时间为O (n)；而在有序数组中查找时，即便是在最糟情况下所需的时间也只有O(logn )，因此你可能认为有序数组比二叉查找树更佳。然而，二叉查找树的插入和删除操作的速度要快得多。

二叉树数组比较

二叉树缺点:不能随机访问。此外，分布不平衡的树会造成性能不佳。也有一些处于平衡状态的
特殊二叉查找树，如红黑树。

策略

使用D&C可以推导出递归函数。D&C理念的方法是快速排序。

使用例子:
输入错别字时，原本输入的判断：如果错输入hish，判断原输入是fish，还vista

最长公共子串

最长公共子串

伪代码

if word_a[i] == word_b[i]:
    cell[i][j] = cell[i-1][j-1]+1
else:
    cell[i][j] = 0

hish和fish的最长公共子串包含三个字母，而hish和vista的最长公共子串包含两个字母。因此很可能原本要输入的是fish。

最长公共子序列

最长公共子序列

结果:


结果

伪代码

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])

没有放之四海皆准的计算动态规划解决方案公式。

算法

例如在100个数字中查找1,最多需要log100 \approx 7步:

二分查找

代码:

def binary_search(list, item):
    low = 0 #low和high用于跟踪要在其中查找的列表部分
    high = len(list) - 1
    while low <= high: #只要范围没缩小到只剩一个元素
        mid = (low + high)/2 #检测中间元素
        guess = list[mid] 
        if guess == item: #找到元素
            return mid
        if guess > item: #猜测的数字大了
            high = mid - 1
        else:  #猜测的数字小了
            low = mid + 1 
    return None #没有指定元素

代码:

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)) #把找到的最小值加入到新数组中
    retrun newArr

代码:

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)

搜索的顺序是先找一度关系，再到二度关系中查找，知道找到目标，该路径是最短路径。运行时间为
O(V+E)，其中V为顶点(vertie)数，E为边数。

代码:

from collections import deque
search_queue = deque() #创建队列
search_queue += graph["you"] #将邻居加入到搜素队列中
def object_is_target(input): #检查这个是否是查找的目标
    return input[-1] == 'm' #假设查找目标以字母m结尾
while search_queue: #只要队列不为空
    input = search_queue.popleft() #就取出其中第一对象
    if object_is_target(input):
        print ('找到目标')
        return True
    else:
        search_queue += graph[input] #如果不是目标，则将该输入的邻居加入到队列
return False #如果到达这里，说明没有找到目标

该代码的缺点是如果图中节点的邻居有重复的现象，可能把重复的对象重复加入到队列中，造成查找恶性循环，进入死循环。
优化代码：

def search(object):
    search_queue = deque() #创建队列
    search_queue += graph[object] #将邻居加入到搜素队列中
    search = [] #记录查找过的对象
    while search_queue: #只要队列不为空
        input = search_queue.popleft() #就取出其中第一对象
        if not input in searched: #仅当这个对象没有被检查过
            if object_is_target(input):
                print ('找到目标')
                return True
            else:
                search_queue += graph[input] #如果不是目标，则将该输入的邻居加入到队列
                searched.append(input) #标记该对象检查过
return False #如果到达这里，说明没有找到目标

步骤:

  1. 找出“最便宜”的节点，即可在最短时间内(最低代价)到达的节点。
  2. 对于该节点的邻居，检测是否有前往他们的更短路径，如果有，更新该节点的开销。
  3. 重复这个过程，直到对图中所有节点都这样做了
  4. 计算最终路径

代码:

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 cost[n] > new_cost: #如果经当前节点前往该邻居更近
            cost[n] = new_cost #更新该邻居开销
            parents[n] = node #同时将该邻居的父节点设置为当前节点
    processed.append(node) #标记节点为已经处理过
    node = find_lowest_cost_node(costs) #找出接下处理节点，并循环

代码:

object_need = set(["a","b",...])#创建一个集合，包含所有目标
objects = {} #散列表创建
objects['sone'] = set(['a','c','e'])
objects['stwo'] = set(['b','c','d'])
...#根据图，创建所有集合，保存到objects中
final_objects = set() #创建集合来存储最终选择。
while object_need: #循环需要的目标
    best_object = None
    object_covered = set()
    for s, object in objects.items():
        covered = object_need & object #计算交集
        if len(covered) > len(object_covered):
            best_object = s
            object_covered = covered
    object_need -= object_covered #去除掉已经覆盖的
    final_objects.add(best_object)
贪婪算法
上一篇 下一篇

猜你喜欢

热点阅读