《算法图解》第二版 学习笔记

算法学习报告

本文基于书中提供的算法代码，整理并总结了常见算法的实现与应用。算法按照相关性进行分类与排序，从基础的数据处理算法到复杂图搜索与优化算法，逐步递增复杂度。

1. 基础数据处理算法

1.1 二分查找

描述：二分查找是一种高效的搜索算法，适用于已排序数组，通过不断将搜索范围折半来定位目标元素，时间复杂度为 O(log n)。

应用场景：常用于查找有序数据，如数据库索引、快速定位元素。

代码实现：

def binary_search(arr, aim):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        if guess == aim:
            return mid
        elif guess < aim:
            low = mid + 1 
        else:
            high = mid - 1
    return -1
print(binary_search([1, 2, 3, 4, 5], 3))

分析：代码通过维护两个指针（low 和 high）不断缩小搜索范围，适用于静态有序数据集。若目标不存在，返回 -1。

1.2 递归算法

描述：递归通过函数自身调用解决问题，分解 unitary 为更小的子问题。提供的代码展示了递归在求阶乘、斐波那契数列、列表求和、计数及找最大值中的应用。

应用场景：递归适合树形结构处理、数学计算及分治法问题。

代码实现：

# 求阶乘
def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)
print(fact(5))

# 斐波那契数列
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))

# 列表求和
def summ(lt):
    if not lt:
        return 0
    else:
        return lt[0] + summ(lt[1:])
print(summ([1, 5, 7, 2]))

# 列表计数
def ct(lt: list):
    if not lt:
        return 0
    else:
        return 1 + ct(lt[1:])
print(ct([1, 5, 7, 8, 9]))

# 列表求最大值
def fd_max(lt):
    if len(lt) == 2:
        return lt[0] if lt[0] > lt[1] else lt[1]
    sub_max = fd_max(lt[1:])
    return lt[0] if lt[0] > sub_max else sub_max
print(fd_max([1, 5, 7, 8, 3]))

分析：递归需明确基线条件和递归条件。例如，斐波那契数列的递归效率较低（O(2^n)），可通过动态规划优化；列表操作的递归清晰但需注意栈溢出风险。

2. 排序算法

2.1 选择排序

描述：选择排序通过每次从未排序部分选出最小元素，放置到已排序部分，时间复杂度为 O(n²)。文件提供了两种实现：方法1创建新数组，方法2原地排序。

应用场景：适合小规模数据或对空间要求不高的场景。

代码实现：

# 方法1：创建新数组
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 = []
    copiedarr = list(arr)
    for i in range(len(copiedarr)):
        smallest = findsmallest(copiedarr)
        newarr.append(copiedarr.pop(smallest))
    return newarr
print(selectionsort([5, 3, 6, 2, 10]))

# 方法2：原地排序
def selection_sort(nums: list[int]):
    n = len(nums)
    for i in range(n-1):
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j
        nums[i], nums[k] = nums[k], nums[i]
    return nums
print(selection_sort([5, 3, 6, 2, 10]))

分析：方法1占用额外空间（O(n)），方法2空间复杂度为 O(1)。两者均简单但效率低于快速排序。

2.2 快速排序

描述：快速排序采用分治法，选择基准（pivot）将数组分为两部分递归排序，平均时间复杂度为 O(n log n)。

应用场景：适用于大多数排序场景，尤其是大数据量。

代码实现：

def quick_sort(arr: list):
    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)
print(quick_sort([9, 12, 5, 23]))

分析：代码使用列表推导式生成子数组，空间复杂度较高（O(n)）。实际应用中可采用原地分区优化空间。

3. 图与搜索算法

3.1 广度优先搜索（BFS）

描述：BFS 使用队列逐层遍历图结构，适合寻找最短路径或层次关系。文件展示了 BFS 在查找芒果销售商及目录遍历中的应用。

应用场景：社交网络分析、路径规划、文件系统遍历。

代码实现：

# 查找芒果销售商
from collections import deque

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]
    searched = set()
    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.add(person)
    return False

def person_is_seller(name):
    return name[-1] == 'm'

search("you")

# 目录遍历
from os import listdir
from os.path import isfile, join
from collections import deque

def print_names(start_dir):
    search_queue = deque()
    search_queue.append(start_dir)
    while search_queue:
        dir = search_queue.popleft()
        for file in sorted(listdir(dir)):
            fullpath = join(dir, file)
            if isfile(fullpath): 
                print(file)
            else:
                search_queue.append(fullpath)

print_names("机器学习")

分析：芒果销售商搜索通过队列和集合避免重复访问，时间复杂度为 O(V+E)（V 为节点数，E 为边数）。目录遍历展示了 BFS 在文件系统中的实用性。

3.2 深度优先搜索（DFS）

描述：DFS 通过递归或栈深入探索图结构，适合拓扑排序或检测连通性。文件展示了 DFS 在目录遍历中的应用。

应用场景：迷宫求解、依赖关系分析。

代码实现：

from os import listdir
from os.path import isfile, join

def print_names(dir):
    for file in sorted(listdir(dir)):
        fullpath = join(dir, file)
        if isfile(join(dir, file)):
            print(file)
        else:
            print_names(fullpath)
print_names("音乐爬取")

分析：DFS 代码简洁，利用递归实现，适合深度优先的场景，但可能因递归深度导致栈溢出。

3.3 迪杰斯特拉算法

描述：迪杰斯特拉算法用于加权有向图中寻找从起点到所有节点的最短路径，适用于非负权边，时间复杂度为 O(V²)（可通过优先队列优化至 O((V+E)log V)）。

应用场景：导航系统、网络路由、物流路径规划。

代码实现：

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

parents = {}
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("Cost from the start to each node:")
print(costs)

分析：代码通过维护成本表和父节点表，逐步更新最短路径。使用数组查找最低成本节点效率较低，实际应用中可采用最小堆优化。

4. 贪婪算法与精确算法

4.1 贪婪算法

描述：贪婪算法通过每次选择局部最优解逼近全局最优，文件展示了集合覆盖问题的贪婪解法。

应用场景：调度问题、资源分配。

代码实现：

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()
while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    states_needed -= states_covered
    final_stations.add(best_station)
print(final_stations)

分析：贪婪算法效率高（O(n²)），但不保证最优解，适合近似解场景。

4.2 精确算法

描述：精确算法通过穷举所有可能解保证最优解，文件展示了集合覆盖问题的组合遍历解法。

应用场景：小规模问题求最优解。

代码实现：

import itertools

all_states = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
stations = {
    "kone": set(["id", "nv", "ut"]),
    "ktwo": set(["wa", "id", "mt"]),
    "kthree": set(["or", "nv", "ca"]),
    "kfour": set(["nv", "ut"]),
    "kfive": set(["ca", "az"])
}

station_names = stations.keys()
for subset_size in range(1, len(station_names) + 1):
    for subset in itertools.combinations(station_names, subset_size):
        covered = set()
        for station in subset:
            covered.update(stations[station])
        if covered.issuperset(all_states):
            print("最优解为：", subset)
            exit()

分析：精确算法时间复杂度为 O(2^n)，适合小规模问题，确保最优解但效率低。

总结

本文从基础的二分查找和递归算法入手，逐步介绍排序算法（选择排序、快速排序），再到图搜索算法（BFS、DFS、迪杰斯特拉算法），最后探讨贪婪与精确算法在优化问题中的应用。这些算法涵盖了数据处理、排序、搜索及优化等核心领域，展示了从简单到复杂的算法设计思路。未来学习可深入动态规划、平衡树等高级算法，以应对更复杂场景。