iicey

博采众长 独立思考

首页 归档 标签 关于

读《算法图解》收获

2019-09-09 7 min read # 算法

二分查找

# -*- coding: utf-8 -*-

# Author: 桑葚ICE
# Email: 152516cc@gmail.com
# Blog: iicey.github.io
# JueJin: juejin.im/user/5c64dce8e51d45013c40742c

def er_fen(arr, num):
    arr.sort()
    start, end = 0, len(arr)
    while (end - start) >= 0:
        san = (end + start) // 2
        if arr[san] == num:
            return san
        if arr[san] > num:
            end = san - 1
        else:
            start = end + 1
    return -1

if __name__ == '__main__':
    print(er_fen([234, 421, 6534, 8765, 154, 1, 64231, 654, 1654], 654))

小结

  • 二分查找的速度比简单查找快得多。
  • O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
  • 算法运行时间并不以秒为单位。
  • 算法运行时间是从其增速的角度度量的。
  • 算法运行时间用大O表示法表示。

选择排序

# -*- coding: utf-8 -*-

# Author: 桑葚ICE
# Email: 152516cc@gmail.com
# Blog: iicey.github.io
# JueJin: juejin.im/user/5c64dce8e51d45013c40742c

def my_xz(arr):
    length = len(arr)
    for i in range(length):
        for j in range(i + 1, length):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    return arr

if __name__ == '__main__':
    print(my_xz([234, 421, 6534, 8765, 154, 1, 64231, 654, 1654]))

小结

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

递归

小结

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

快速排序

# -*- coding: utf-8 -*-

# Author: 桑葚ICE
# Email: 152516cc@gmail.com
# Blog: iicey.github.io
# JueJin: juejin.im/user/5c64dce8e51d45013c40742c
import sys

def my_kp(arr):
    if len(arr) < 2:
        return arr
    else:
        _ = arr[0]
        __ = [i for i in arr[1:] if i >= _]
        ___ = [i for i in arr[1:] if i < _]
        return my_kp(__) + [_] + my_kp(___)

if __name__ == '__main__':
    print(my_kp([234, 421, 6534, 8765, 154, 1, 64231, 654, 1654]))

小结

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

散列表

小结

散列表适合用于：

  • 模拟映射关系；
  • 防止重复；
  • 缓存/记住数据，以免服务器再通过处理来生成它们。

你几乎根本不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。你可使用
Python提供的散列表，并假定能够获得平均情况下的性能：常量时间。

散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。
你可能很快会发现自己经常在使用它。

  • 你可以结合散列函数和数组来创建散列表。
  • 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
  • 散列表的查找、插入和删除速度都非常快。
  • 散列表适合用于模拟映射关系。
  • 一旦填装因子超过0.7，就该调整散列表的长度。
  • 散列表可用于缓存数据（例如，在Web服务器上）。
  • 散列表非常适合用于防止重复。

广度优先搜索

小结

  • 广度优先搜索指出是否有从A到B的路径。
  • 如果有，广度优先搜索将找出最短路径。
  • 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。
  • 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。无向图中的不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约会，而rachel也与ross约会”。
  • 队列是先进先出（FIFO）的。
  • 栈是后进先出（LIFO）的。
  • 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
  • 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

狄克斯特拉算法

# -*- coding: utf-8 -*-

# Author: 桑葚ICE
# Email: 152516cc@gmail.com
# Blog: iicey.github.io
# JueJin: juejin.im/user/5c64dce8e51d45013c40742c
graph = dict()  # 整个图的散列表
graph["start"] = dict()
graph["start"]["A"] = 6
graph["start"]["B"] = 2
graph["A"] = dict()
graph["A"]["fin"] = 1
graph["B"] = dict()
graph["B"]["A"] = 3
graph["B"]["fin"] = 5
graph["fin"] = dict()

infinity = float("inf")  # 散列表是开销
costs = dict()
costs["A"] = 6
costs["B"] = 2
costs["fin"] = infinity

parents = dict()  # 散列表是父子节点
parents["A"] = "start"
parents["B"] = "start"
parents["fin"] = None

processed = []


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:  # 在所有节点都被处理后结束
    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)  # 找出接下来要处理的节点，并循环
print(processed)
print(costs)
print(parents)
# start -> B -> A -> end

小结

  • 广度优先搜索用于在非加权图中查找最短路径。
  • 狄克斯特拉算法用于在加权图中查找最短路径。
  • 仅当权重为正时狄克斯特拉算法才管用。
  • 如果图中包含负权边，请使用贝尔曼福德算法。
Powered by iicey RSS