《算法图解》笔记

阅读《算法图解》一书的一些笔记记录。

选择排序:

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))
    return newArr

递归
1.调用自己的函数
2.条件: 基线(退出)条件+递归条件

栈:
1.两种操作: 压入和弹出
2.所有函数调用都是调用栈 3.后进先出LIFO。

快排
1.使用分而治之策略

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)

二分查找:

def binary_search(list, item):
    low = 0
    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

各算法大O运行时间对比如图:

1

分而治之(D&C)问题解决问题的两个步骤:
1.找出基线条件,此条件尽可能简单
2.不断分解问题,知道满足基线条件 备注:
1.D&C不是解决问题的办法,而是解决问题的思路。
2.D&C处理列表时,基线条件很可能是空列表或者只包含一个元素。

散列表:
1.处理冲突的方式的简单办法,如果两个键映射到同一个位置,可在该位置存储一个链表。
2.目的是要将键均匀的映射到散列表的不同位置处。
3.避免冲突:
3.1.较低的填装因子
填装因子=散列表保护元素数/位置总数,度量散列表中多少位置是空的。填装因子月底,冲突可能性越小,散列表性能越高。经验:一旦填装因子大于0.7,就调整散列表长度。
3.2.良好的散列函数
4.可用来表示图关系。

广度优先搜索BFS:
1.找到两件东西的最短距离
2.解决最短路径的算法被称为广度优先搜索
3.运行时间:O(人数+边数),通常为O(V+E),V为顶点数,E为边数。
4.广度优先搜索指出是否有A到B的最短路径。
5.你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径。因此搜索列表必须是队列。
6.对于检查过的人,不需要再检查,否则会造成无限循环。

def search(name):
    search_queue = deque() 
    search_queue += graph[name]
    searched = [] //标记检查过的人
    while search_queue:
        person = search_queue.popleft() 
        if person not in searched://仅当这个人没检查过才检查
            if person_is_seller(person):
                print person + " is a mango seller!" 
                return True
            else:
                search_queue += graph[person] 
                searched.append(person)//将这个人标记检查过
    return False

队列
1.先进先出,FIFO,按添加顺序进行检查
2.

图:
1.有向图:关系是单向的
2.无向图,直接相连的节点,无箭头。

拓扑排序:
1.列表中任务A必须在任务B后面,这成为拓扑排序。
2.使用它可根据图创建一个有序列表。
3.比如起床-》刷牙-》吃早饭-》上班

迪杰斯塔拉算法
1.起点到终点的耗时最短路径
2.加权图:带权重的图
3.计算非加权图的最短路径是广度优先搜索,计算加权图的最短路径是迪杰特斯拉算法
4:只适合有向无环图(DAG)
5.不适用于负权边的图。 6.负权边的图,找出最短路径使用:贝尔曼-福德算法。
7.四步骤:
7.1.找到最便宜的节点
7.2.对于该节点的邻居,检查是否有通往他们的更短路径,如果有,更新其开销
7.3.重复这个过程,直到所有节点都这样做了
7.4.计算最终路径

node = find_lowest_cost_node(costs) //找到开销最小的节点
while node is not None:
    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) //循环

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

贪婪算法
1.每步都采取最优的做法,即每步都选择局部最优解,最终得到全局最优解。
2.旅行商和集合覆盖问题共同点:都需要计算所有解,并从中选出最小/最短的那个,这两个问题都属于NP完全问题
3.如何判断是不是NP完全问题:

1.设计所有组合问题都是NP完全问题。
2.不能将问题分成小问题,需要考虑各种可能情况,这可能是NP完全问题。
3.问题涉及序列,(旅行商问题中城市序列)且难以解决,可能是NP完全问题。
4.问题涉及集合(广播台集合),且难以解决,可能是NP完全问题。
5.问题可转为旅行商问题或者集覆盖问题,肯定是NP完全问题。

4.面临NP完全问题,最佳做法是使用近似算法。
5.贪婪算法易于实现,速度快,是不错的近似算法。

动态规划:
1.每个单元格都包含当前可装入背包的所有商品。
2.最长公共字串:

if word_a[i] == word_b[j]://两个字母相同
    cell[i][j] = cell[i-1][j-1] +1
else: //两个字母不同 
    cell[i][j] = 0

3.最长公共子序列:

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

4.动态规划应用: 最长公共子序列确认DNA链的相似性,从而判断疾病相似性;git diff命令,指出两个文件差异,使用动态规划来实现的。编辑距离指出两个字符串的相似程度。
5.使用场景: 5.1给定约束条件下优化某种指标:动态规划很有用。
5.2问题可分解为离散子问题,可使用动态规划来解决。

二叉查找树:
1.查找,插入,删除时间O(logn)

傅立叶变换:
1.给定歌曲,将其中各种频率分离出来。

布隆过滤器:
1.一种概率型数据结构,提供的答案可能不对,可能正确
2.判断网页是否收集,可不使用散列表,使用布隆过滤器。
3.两个特点: 可能出现错报情况,说收集了,可能没收集;不可能出现漏报情况,说没收集,肯定没收集。
4.优点:占用存储空间少,
5.使用散列表需要存储所有搜集的url。使用布隆过滤器不需要都存储。
6.适合于不要求答案绝对正确的情况。
7.比如,对于某个网站,这样说完全可行:我们认为这个网站可能是恶意的,请小心。 8.面临海量数据,且要求答案八九不离十使用,可使用概率性算法。

SHA散列函数:
1.安全散列算法函数。给定一个字符串,返回一个字符串。
2.在比较超大型文件时候,可用来比较两个文件是否相同。
3.重要特性: 局部不敏感。即你修改其中一个字符,散列值截然不同。攻击者无法比较散列值来破解密码。
4.希望散列函数是局部敏感的,可是有simhash函数。对字符串的细微更改,simhash的散列值也会有细微的差别。可通过此比较散列值来比较两个字符串的相似程度。
5.google提供simhash判断网页是否已搜集
6.老师根据simhash来判断学生作业是否从网上抄袭的。
7.需要检查两项内容相似程度,simhash很有用。



版权申明

知识共享许可协议
本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 转载文章请注明原文出处。

天道酬勤
评分4.8/5 based on 20