阅读《算法图解》的随手记，一些概念性的东西和一些简单的代码逻辑
# -*- coding: utf-8 -*-
"""
一些常见的大 O 运行时间，从快到慢：
O(1): 常量时间
O(log n): 对数时间，如二分查找
O(n): 线性时间，如简单查找
O(n * log n): 如快速排序
O(n^2): 如选择排序
O(n!): 如旅行商问题
尾递归
递归语句出现在函数末尾，且不存在于表达式中。
这样可以复用栈（当前栈不有继续存在的意义），而不创建新的栈。
即不是等待满足基线条件的值，往前回溯计算，而是依次计算当前值传向基线条件
例如：求 6 的阶乘
一般递归：1 * 2 * 3 * 4 * 5 * 6
尾递归：6 * 5 * 4 * 3 * 2 * 1
欧几里得算法
即辗转相除法求最大公约数
gcd(a, b)=gcd(b, a mod b)
散列表
良好性能的两大要素：
- 较低的填装因子，一旦填装因子超过 0.7 就应该调整散列表的长度
- 良好的散列函数，尽可能均匀分布
广度优先搜索 -- 非加权图
解决两类问题：
- 从节点 A 是否有前往节点 B 的路径
- 从节点 A 前往节点 B 的最短路径是什么
运行时间：O(V + E)，V 为顶点（vertice）数，E 为边数
对于搜索过的节点，不能重复搜索，否则可能无限循环
广度优先搜索不会主动收敛，直到待搜索队列为空
有向图与无向图
有向即单向，无向即双向（环）
狄克斯特拉算法 -- 加权图，有向无环图 DAG（directed acyclic graph）
贝尔曼-富德算法 -- 包含负权边
狄克斯特拉算法不能计算负权边在于，优先计算开销小的节点 且 不重复计算节点开销
即从 A-C 所需开销小于 A-B，则狄克斯特拉算法认为 A-B-C 一定大于 A-B 大于 A-C
近似算法
贪婪算法
每步都是局部最优解，企图最终得到的就是全局最优解 -- 并非任何情况下有行之有效，但易于实现
广度优先搜索、狄克斯特拉算法都属于贪婪算法
NP 完全问题 -- 通常需要寻求近似算法解决
动态规划
在给定约束条件下找到最优解
仅当每个子问题都是独立且离散的，即不依赖其他子问题时，动态规划才管用
字符串相似度比较 -- 动态规划
最长公共子串：两个单词中都有的子串，每个子串的字母数
最长公共子序列：两个单词中都有的序列包含的总的字母数
K 最近邻算法
余弦相似度 -- 距离公式
K 值选取，经验规则：有 N 个用户就选取 sqrt(N) 个邻居
PS:
二叉查找树（binary search tree） -- 对于其中每个节点，左子节点的值都比它小，而右子节点的值都比它大
反向索引 -- 搜索引擎
傅里叶变换
并行算法
MapReduce
布隆过滤器 和 HyperLogLog -- 有概率不正确，但是占用的内存空间十分少
SHA 算法 -- 局部敏感的散列函数
Simhash -- 局部不敏感的散列函数 -- 可用于检查两项内容的相似度
Diffie-Hellman / RSA 秘钥交换
线性规划 Simplex 算法 -- 用于在给定约束条件下最大限度地改善指定的指标
"""
def binary_search(arr, item):
"""二分查找"""
low = 0
high = len(arr) - 1
while low <= high:
mid = int((low + high) / 2) # 取小
guess = arr[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
def find_smallest(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 selection_sort(arr):
"""选择排序"""
new_arr = []
for i in range(len(arr)):
smallest = find_smallest(arr)
new_arr.append(arr.pop(smallest))
return new_arr
def quick_sort(arr):
"""
快速排序
递归条件的选择决定了算法的速度
平均情况：O(n log n)
最糟情况：O(n^2)
"""
if len(arr) < 2:
return arr # 基线条件
else:
pivot = arr[0] # 递归条件
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
def find_lowest_cost_node(costs, processed):
# 在未处理的节点中找出开销最小的节点
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
def dijkstra():
"""狄克斯特拉算法, Dijkstra's algorithm"""
# 初始化
infinity = float("inf")
graph = {
"start": {"a": 6, "b": 2},
"a": {"fin": 1},
"b": {"a": 3, "fin": 5},
"fin": {}
}
# 存储每个节点的开销
costs = {
"a": 6,
"b": 2,
"fin": infinity
}
# 存储父节点
parents = {
"a": "start",
"b": "start",
"fin": None
}
# 记录处理过的节点
processed = []
node = find_lowest_cost_node(costs, processed)
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, processed)
print(parents)
if __name__ == '__main__':
print(binary_search([1, 2, 3, 4, 5], 3))
print(selection_sort([4, 6, 1, 3, 7]))
print(quick_sort([10, 7, 3, 5, 9]))
dijkstra()