Blog of AgioPan
0%

数据结构与算法自学笔记（1）- 二进制&位运算&排序算法&二分搜索

Posted on Edited on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了class002 -> class 007的内容，涵盖了社会实验模拟、位运算、基础排序算法、算法验证方法、二分搜索以及复杂度分析等核心内容。

原代码是java版，我改成了python

002【入门】从社会实验到入门提醒

基尼系数的理论基础

基尼系数是经济学中衡量收入分配不平等程度的重要指标，其数学定义为：

$$
G = \frac{\sum_{i=1}^{n}\sum_{j=1}^{n}|x_i - x_j|}{2n\sum_{i=1}^{n}x_i}
$$

其中 $x_i$ 表示第 $i$ 个个体的财富值，$n$ 为总人数。

基尼系数的经济学意义

  • G = 0：完全平等，所有人财富相同
  • G = 1：完全不平等，一人拥有全部财富
  • G = 0.4-0.5：国际公认的贫富差距警戒线
  • G > 0.5：社会可能面临动荡风险

财富分配模拟实验

通过计算机模拟研究在完全随机的财富转移过程中，社会财富分配的自然演化规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import numpy as np
import random

def calculate_gini(wealth):
    """
    计算基尼系数的函数
    参数: wealth - 财富分布列表
    返回: 基尼系数值
    """
    n = len(wealth)                        # 获取人数
    sum_of_wealth = sum(wealth)            # 计算总财富
    sum_of_absolute_differences = 0        # 初始化财富差异总和
    
    # 计算所有个体间财富差异的绝对值之和
    for i in range(n):
        for j in range(n):
            sum_of_absolute_differences += abs(wealth[i] - wealth[j])
    
    # 根据基尼系数公式计算并返回结果
    return sum_of_absolute_differences / (2 * n * sum_of_wealth)

def experiment(n, t):
    """
    财富分配模拟实验
    参数: n - 人数, t - 模拟轮数
    """
    wealth = [100] * n                     # 初始化每人财富为100
    
    for _ in range(t):                     # 进行t轮模拟
        has_money = [w > 0 for w in wealth]  # 判断每个人是否有钱可转
        transfers = []                     # 记录本轮转账列表
        
        for j in range(n):                 # 遍历每个人
            if has_money[j]:               # 如果该人有钱
                other = j                  # 初始化接收者为自己
                while other == j:          # 确保接收者不是自己
                    other = random.randint(0, n - 1)  # 随机选择其他人
                transfers.append((j, other))          # 记录转账关系
        
        # 统一执行所有转账，避免执行顺序影响结果
        for giver, receiver in transfers:
            wealth[giver] -= 1             # 转出者财富减1
            wealth[receiver] += 1          # 接收者财富加1
    
    wealth.sort()                          # 按财富排序便于观察分布
    
    # 输出结果分析
    print("财富分布(从贫穷到富有):")
    for idx, w in enumerate(wealth):
        print(int(w), end=' ')
        if idx % 10 == 9:                  # 每10个数换行
            print()
    print()
    print("社会基尼系数:", calculate_gini(wealth))

实验意义与启示

  1. 随机性中的必然性：即使在完全公平的随机转移规则下，财富差距仍会自然产生
  2. 马太效应：财富分配存在自然的分化趋势
  3. 社会政策启示：需要主动的调节机制来维护社会公平

003【入门】二进制和位运算

计算机数值表示系统

正数的二进制表示

正数采用标准的二进制表示法，最高位为符号位（0表示正数）。

负数的补码表示

负数采用补码（Two’s Complement）表示：

  • 原码按位取反
  • 结果加1

$$
\text{负数补码} = \sim(\text{原码}) + 1
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def print_binary(num):
    """
    打印32位二进制表示
    参数: num - 要打印的整数
    """
    s = ''                                 # 初始化二进制字符串
    for i in range(31, -1, -1):           # 从最高位到最低位遍历
        # 通过位与运算判断第i位是否为1
        s += '1' if (num & (1 << i)) != 0 else '0'
    print(s)                              # 输出32位二进制表示

# 演示正负数的二进制表示
if __name__ == "__main__":
    a = 78                                # 正数示例
    print(f"正数{a}的二进制表示:")
    print_binary(a)
    
    b = -6                                # 负数示例  
    print(f"负数{b}的二进制表示:")
    print_binary(b)
    
    # 验证补码计算
    print(f"~{a} + 1 = {~a + 1}")        # 计算a的相反数
    print_binary(~a + 1)

核心位运算操作

基本位运算符详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def bitwise_operations_demo():
    """位运算操作演示"""
    '''0b 是Python中表示二进制数字的前缀。'''
    g = 0b0001010                         # 二进制字面量：10
    h = 0b0001100                         # 二进制字面量：12
    
    print("操作数g:", bin(g))
    print("操作数h:", bin(h))
    
    # 按位或运算：有1则1
    print("g | h  =", bin(g | h))         # 0b1110 = 14
    
    # 按位与运算：全1则1  
    print("g & h  =", bin(g & h))         # 0b1000 = 8
    
    # 按位异或运算：不同则1
    print("g ^ h  =", bin(g ^ h))         # 0b0110 = 6

def shift_operations_demo():
    """移位运算演示"""
    i = 0b0011010                         # 二进制：26
    print(f"原数: {i}, 二进制: {bin(i)}")
    
    # 左移运算：相当于乘以2的幂次
    print(f"{i} << 1 = {i << 1}")        # 26 * 2 = 52
    print(f"{i} << 2 = {i << 2}")        # 26 * 4 = 104  
    print(f"{i} << 3 = {i << 3}")        # 26 * 8 = 208
    
    # 右移运算：相当于除以2的幂次（向下取整）
    k = 10
    print(f"{k} >> 1 = {k >> 1}")        # 10 / 2 = 5
    print(f"{k} >> 2 = {k >> 2}")        # 10 / 4 = 2
    print(f"{k} >> 3 = {k >> 3}")        # 10 / 8 = 1

逻辑运算与位运算的重要区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def return_true():
    print("执行了return_true函数")
    return True

def return_false():
    print("执行了return_false函数") 
    return False

def logical_vs_bitwise():
    """演示逻辑运算与位运算的区别"""
    print("=== 位运算测试 ===")
    # 位运算：两个函数都会被调用
    test1 = return_true() | return_false()
    print(f"位运算结果: {test1}")
    
    print("=== 逻辑运算测试 ===") 
    # 逻辑运算：存在短路求值，第二个函数可能不被调用
    test2 = return_true() or return_false()
    print(f"逻辑运算结果: {test2}")

位运算的实际应用

  1. 快速乘除法：左移代替乘法，右移代替除法
  2. 奇偶性判断：num & 1 == 0 判断偶数。这是因为：num & 1 只保留 num 的二进制最低位，其余全部变成0。
  3. 集合操作：用位掩码表示集合的并、交、差运算
  4. 状态压缩：在动态规划中压缩状态空间

004【入门】选择、冒泡、插入排序

理解python中的class：什么是“实例化类”？

  • 类（class）：可以理解为一个“模具”或者“模板”，描述一类对象应该有哪些属性和行为。
  • 实例（instance）：就是根据这个“模具”制造出来的一个具体的“物品”。
  • 实例化：把类变成实例（对象）的过程，叫做实例化。

选择排序（Selection Sort）

算法思想

每次从未排序部分选择最小（或最大）元素，将其放置到已排序部分的末尾。

时间复杂度分析

  • 比较次数：$\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} = O(n^2)$
  • 交换次数：$O(n)$
  • 总体复杂度：$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class SortingAlgorithms:
    
    @staticmethod
    def swap(arr, i, j):
        """
        交换数组中两个位置的元素
        参数: arr - 数组, i,j - 要交换的索引
        """
        arr[i], arr[j] = arr[j], arr[i]  # Python的元组赋值交换
    
    @staticmethod
    def selection_sort(arr):
        """
        选择排序实现
        时间复杂度: O(n²), 空间复杂度: O(1)
        不稳定排序
        """
        if arr is None or len(arr) < 2:   # 边界条件检查
            return
        
        # 外层循环控制已排序部分的边界
        for i in range(len(arr) - 1):
            min_index = i                  # 假设当前位置为最小值
            
            # 内层循环在未排序部分寻找真正的最小值
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[min_index]:  # 找到更小的元素
                    min_index = j           # 更新最小值索引
            
            # 将找到的最小值与当前位置交换
            SortingAlgorithms.swap(arr, i, min_index)

冒泡排序（Bubble Sort）

算法思想

重复遍历数组，比较相邻元素并在必要时交换，使得大元素逐渐”冒泡”到数组末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@staticmethod
def bubble_sort(arr):
    """
    冒泡排序实现
    时间复杂度: O(n²), 空间复杂度: O(1)  
    稳定排序
    """
    if arr is None or len(arr) < 2:   # 边界条件检查
        return
    
    # 外层循环控制未排序部分的右边界
    for end in range(len(arr) - 1, 0, -1):
        # 内层循环进行相邻元素比较和交换
        for i in range(end):
            if arr[i] > arr[i + 1]:    # 如果前面元素大于后面元素
                SortingAlgorithms.swap(arr, i, i + 1)  # 交换位置
                # 经过一轮后，最大元素"冒泡"到末尾

冒泡排序的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@staticmethod  
def bubble_sort_optimized(arr):
    """
    优化版冒泡排序：添加提前终止条件
    如果某轮遍历中没有发生交换，说明数组已有序
    """
    if arr is None or len(arr) < 2:
        return
        
    for end in range(len(arr) - 1, 0, -1):
        swapped = False               # 标记本轮是否发生交换
        for i in range(end):
            if arr[i] > arr[i + 1]:
                SortingAlgorithms.swap(arr, i, i + 1)
                swapped = True        # 发生了交换
        
        if not swapped:               # 如果本轮没有交换
            break                     # 数组已有序，提前结束

插入排序（Insertion Sort）

算法思想

将数组分为已排序和未排序两部分，依次将未排序元素插入到已排序部分的正确位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@staticmethod
def insertion_sort(arr):
    """
    插入排序实现
    时间复杂度: 最坏O(n²), 最好O(n), 平均O(n²)
    空间复杂度: O(1)
    稳定排序，对小规模或近似有序数据效率高
    """
    if arr is None or len(arr) < 2:   # 边界条件检查
        return
    
    # 从第二个元素开始，逐个插入到已排序部分
    for i in range(1, len(arr)):
        # 从当前位置向前比较，寻找插入位置
        for j in range(i - 1, -1, -1):
            if arr[j] > arr[j + 1]:    # 如果前面元素大于后面元素
                SortingAlgorithms.swap(arr, j, j + 1)  # 交换位置
            else:
                break                  # 找到正确位置，提前结束内层循环

插入排序的另一种实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@staticmethod
def insertion_sort_v2(arr):
    """
    插入排序的另一种实现：先保存要插入的元素，然后移动其他元素
    减少交换次数，提高效率
    """
    if arr is None or len(arr) < 2:
        return
        
    for i in range(1, len(arr)):
        key = arr[i]                  # 保存要插入的元素
        j = i - 1                     # 从已排序部分的末尾开始
        
        # 向右移动大于key的元素
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # 元素后移
            j -= 1
        
        arr[j + 1] = key              # 插入key到正确位置

排序算法性能对比

算法 时间复杂度(最好) 时间复杂度(平均) 时间复杂度(最坏) 空间复杂度 稳定性
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定

005【入门】对数器-验证的重要手段

对数器的理论基础

对数器（Logarithmic Validator）是一种系统性验证算法正确性的重要工具，通过大量随机测试用例来检验算法实现的可靠性。

对数器设计的六个核心原则

  1. 确定待测算法a：需要验证正确性的高效算法
  2. 实现简单算法b：复杂度可能不优但逻辑简单、容易验证正确的算法
  3. 构建随机样本生成器：能够产生各种边界情况的测试数据
  4. 对比验证：在相同输入下比较两种算法的输出结果
  5. 错误定位：当发现不一致时，人工分析并修正错误
  6. 大规模验证：通过大量测试建立对算法正确性的信心

对数器实现框架（以上节课的三种排序方法为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import random

class AlgorithmValidator:
    """算法验证器类"""
    
    @staticmethod
    def random_array(n, v):
        """
        生成随机数组
        参数: n - 数组长度, v - 元素值域[1,v]
        返回: 长度为n的随机数组
        """
        # 使用列表推导式生成随机数组
        return [random.randint(1, v) for _ in range(n)]
    
    @staticmethod
    def copy_array(arr):
        """
        数组深拷贝
        参数: arr - 原数组
        返回: 原数组的副本
        """
        return arr[:]                     # 切片操作创建新列表
    
    @staticmethod  
    def arrays_equal(arr1, arr2):
        """
        比较两个数组是否相等
        参数: arr1, arr2 - 待比较的数组
        返回: 布尔值表示是否相等
        """
        if len(arr1) != len(arr2):        # 长度不等直接返回False
            return False
        
        # 逐元素比较
        for a, b in zip(arr1, arr2):
            if a != b:
                return False
        return True
    
    @staticmethod
    def comprehensive_sort_test():
        """
        排序算法综合测试
        使用对数器方法验证多种排序算法的正确性
        """
        # 测试参数配置
        N = 200                          # 数组最大长度
        V = 1000                         # 元素最大值
        test_times = 50000               # 测试次数
        
        print("算法验证开始...")
        
        for test_round in range(test_times):
            # 生成随机测试用例
            n = random.randint(0, N - 1)  # 随机数组长度
            arr = AlgorithmValidator.random_array(n, V)
            
            # 创建多个数组副本用于不同算法测试
            arr_selection = AlgorithmValidator.copy_array(arr)
            arr_bubble = AlgorithmValidator.copy_array(arr)  
            arr_insertion = AlgorithmValidator.copy_array(arr)
            arr_builtin = AlgorithmValidator.copy_array(arr)
            
            # 应用不同排序算法
            SortingAlgorithms.selection_sort(arr_selection)
            SortingAlgorithms.bubble_sort(arr_bubble)
            SortingAlgorithms.insertion_sort(arr_insertion)
            arr_builtin.sort()            # Python内置排序作为标准答案
            
            # 结果一致性验证
            if not (AlgorithmValidator.arrays_equal(arr_selection, arr_builtin) and
                    AlgorithmValidator.arrays_equal(arr_bubble, arr_builtin) and  
                    AlgorithmValidator.arrays_equal(arr_insertion, arr_builtin)):
                
                # 发现错误时输出详细信息
                print("发现算法错误!")
                print(f"测试轮次: {test_round + 1}")
                print(f"原始数组: {arr}")
                print(f"选择排序: {arr_selection}")
                print(f"冒泡排序: {arr_bubble}")
                print(f"插入排序: {arr_insertion}")
                print(f"内置排序: {arr_builtin}")
                return False
                
            # 每完成1000次测试输出进度
            if (test_round + 1) % 1000 == 0:
                print(f"已完成 {test_round + 1} 次测试...")
        
        print("所有测试通过！算法实现正确。")
        return True

对数器方法的优势

  1. 自动化验证：减少人工测试的工作量和错误率
  2. 覆盖边界情况：随机生成能够触及各种极端情况
  3. 置信度建立：大量测试通过后可以高度确信算法正确性
  4. 错误定位：一旦发现问题能够提供具体的错误样例

006【入门】二分搜索

二分搜索的数学基础

二分搜索基于分治思想，每次将搜索空间减半，时间复杂度为 $O(\log n)$。

设数组长度为 $n$，经过 $k$ 次二分后搜索空间大小为 $\frac{n}{2^k}$，当搜索空间减小到1时：

$$\frac{n}{2^k} = 1 \Rightarrow k = \log_2 n$$

基础二分搜索

问题：判断有序数组中是否存在目标值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binary_search_exist(arr, target):
    """
    在有序数组中查找目标值是否存在
    参数: arr - 有序数组, target - 目标值
    返回: True/False 表示是否存在
    时间复杂度: O(log n), 空间复杂度: O(1)
    """
    if arr is None or len(arr) == 0:      # 边界条件：空数组
        return False
    
    left, right = 0, len(arr) - 1         # 初始化搜索边界[left, right]
    
    while left <= right:                  # 搜索空间非空时继续
        # 防止整数溢出的中点计算方法
        mid = left + (right - left) // 2   # 等价于 (left + right) // 2
        
        if arr[mid] == target:            # 找到目标值
            return True
        elif arr[mid] > target:           # 目标值在左半部分
            right = mid - 1               # 收缩右边界
        else:                             # 目标值在右半部分  
            left = mid + 1                # 收缩左边界
    
    return False                          # 搜索完毕未找到

暴力验证方法

1
2
3
4
5
6
7
8
9
def linear_search_exist(arr, target):
    """
    线性搜索验证方法
    用于对数器验证二分搜索的正确性
    """
    for element in arr:                   # 遍历数组每个元素
        if element == target:             # 找到目标值
            return True
    return False                          # 未找到目标值

二分搜索的边界查找变种

查找左边界：>=target的最左位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def binary_search_left_bound(arr, target):
    """
    在有序数组中查找 >= target 的最左位置
    参数: arr - 有序数组, target - 目标值
    返回: 满足条件的最左索引，不存在返回-1
    """
    if arr is None or len(arr) == 0:
        return -1
    
    left, right = 0, len(arr) - 1
    ans = -1                              # 记录答案，初始化为-1表示未找到
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] >= target:            # 当前元素满足条件
            ans = mid                     # 更新答案
            right = mid - 1               # 继续在左半部分寻找更左的位置
        else:                             # 当前元素小于target
            left = mid + 1                # 在右半部分继续搜索
    
    return ans

def linear_search_left_bound(arr, target):
    """线性搜索验证：查找>=target的最左位置"""
    for i in range(len(arr)):             # 从左到右遍历
        if arr[i] >= target:              # 找到第一个满足条件的位置
            return i
    return -1                             # 未找到

查找右边界：<=target的最右位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def binary_search_right_bound(arr, target):
    """
    在有序数组中查找 <= target 的最右位置
    参数: arr - 有序数组, target - 目标值  
    返回: 满足条件的最右索引，不存在返回-1
    """
    if arr is None or len(arr) == 0:
        return -1
    
    left, right = 0, len(arr) - 1
    ans = -1                              # 记录答案
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:            # 当前元素满足条件
            ans = mid                     # 更新答案
            left = mid + 1                # 继续在右半部分寻找更右的位置
        else:                             # 当前元素大于target
            right = mid - 1               # 在左半部分继续搜索
    
    return ans

def linear_search_right_bound(arr, target):
    """线性搜索验证：查找<=target的最右位置"""
    for i in range(len(arr) - 1, -1, -1): # 从右到左遍历
        if arr[i] <= target:              # 找到第一个满足条件的位置
            return i
    return -1                             # 未找到

峰值元素查找

问题定义

在数组中找到任意一个峰值元素（比左右邻居都大的元素），假设边界外的元素为负无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def find_peak_element(arr):
    """
    查找数组中的峰值元素
    参数: arr - 整数数组（相邻元素不相等）
    返回: 任意峰值元素的索引
    时间复杂度: O(log n)
    """
    n = len(arr)
    
    # 边界情况处理
    if n == 1:                            # 单元素数组
        return 0
    if arr[0] > arr[1]:                   # 第一个元素是峰值
        return 0  
    if arr[n-1] > arr[n-2]:              # 最后一个元素是峰值
        return n - 1
    
    # 在 [1, n-2] 范围内二分搜索
    left, right = 1, n - 2
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid-1] > arr[mid]:         # 左邻居更大，峰值在左半部分
            right = mid - 1
        elif arr[mid] < arr[mid+1]:       # 右邻居更大，峰值在右半部分  
            left = mid + 1
        else:                             # arr[mid-1] < arr[mid] > arr[mid+1]
            return mid                    # 找到峰值
    
    return -1                             # 理论上不会到达这里

峰值查找的正确性证明

定理：在满足相邻元素不相等的数组中，上述算法一定能找到峰值。

证明：

  1. 边界已处理端点峰值。
  2. 二分查找时，每次都能缩小到含有峰值的半区。
  3. 因为每次都“爬坡”，必然最终会达到一个峰值。
  4. 相邻元素不等消除了平台的歧义。
  5. 因此，算法在O(log n)时间内一定能找到一个峰值。

二分搜索验证框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def test_binary_search_algorithms():
    """二分搜索算法综合测试"""
    N = 100                               # 数组最大长度
    V = 1000                              # 元素值域
    test_times = 500000                   # 测试次数
    
    print("二分搜索算法测试开始...")
    
    for _ in range(test_times):
        # 生成随机有序数组
        n = random.randint(0, N - 1)
        arr = [random.randint(1, V) for _ in range(n)]
        arr.sort()                        # 确保数组有序
        
        target = random.randint(0, V - 1) # 随机目标值
        
        # 验证基础二分搜索
        if binary_search_exist(arr, target) != linear_search_exist(arr, target):
            print("基础二分搜索错误!")
            return False
        
        # 验证左边界查找    
        if binary_search_left_bound(arr, target) != linear_search_left_bound(arr, target):
            print("左边界查找错误!")
            return False
            
        # 验证右边界查找
        if binary_search_right_bound(arr, target) != linear_search_right_bound(arr, target):
            print("右边界查找错误!")
            return False
    
    print("所有二分搜索测试通过!")
    return True

007【入门】时间复杂度和空间复杂度

时间复杂度的数学基础

渐近记号系统

设 $f(n)$ 和 $g(n)$ 为定义在正整数集上的函数：

  • 大O记号 $O(g(n))$：$f(n) = O(g(n))$ 当且仅当存在正常数 $c$ 和 $n_0$，使得对所有 $n \geq n_0$ 有 $f(n) \leq c \cdot g(n)$
  • 大Ω记号 $\Omega(g(n))$：$f(n) = \Omega(g(n))$ 当且仅当存在正常数 $c$ 和 $n_0$，使得对所有 $n \geq n_0$ 有 $f(n) \geq c \cdot g(n)$
  • 大Θ记号 $\Theta(g(n))$：$f(n) = \Theta(g(n))$ 当且仅当 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$

其实和泛函的函数的范数有点像，也就是这个映射算是有界的那种感觉。

常见复杂度级别

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$$

复杂嵌套循环分析

等差数列型循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quadratic_complexity_demo(N):
    """
    演示O(n²)时间复杂度
    等差数列求和：1 + 2 + ... + n = n(n+1)/2 = O(n²)
    """
    operations = 0                        # 记录操作次数
    
    for i in range(1, N + 1):            # 外层循环：i从1到N
        for j in range(i, N + 1):        # 内层循环：j从i到N
            operations += 1               # 模拟一次基本操作
            # 当i=1时，内层执行N次
            # 当i=2时，内层执行N-1次  
            # ...
            # 当i=N时，内层执行1次
            # 总计：N + (N-1) + ... + 1 = N(N+1)/2
    
    print(f"N={N}, 总操作次数={operations}, 理论值={N*(N+1)//2}")
    return operations

调和级数型循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def n_log_n_complexity_demo(N):
    """
    演示O(n log n)时间复杂度  
    调和级数：1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n) = O(log n)
    """
    operations = 0                        # 记录操作次数
    
    for i in range(1, N + 1):            # 外层循环：i从1到N
        j = i                             # 内层循环起始值
        while j <= N:                     # 按i的倍数递增
            operations += 1               # 模拟一次基本操作
            j += i                        # j = i, 2i, 3i, ...
            # 当i=1时，内层执行N次（N/1）
            # 当i=2时，内层执行N/2次
            # 当i=3时，内层执行N/3次
            # ...
            # 总计：N(1 + 1/2 + 1/3 + ... + 1/N) = N·H_N ≈ N log N
    
    print(f"N={N}, 总操作次数={operations}")
    return operations

复杂度实验验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import time

def complexity_benchmark():
    """
    通过实际运行时间验证复杂度分析
    """
    test_sizes = [1000, 2000, 4000, 8000]   # 测试规模
    
    print("=== 复杂度实验验证 ===")
    print("规模\tO(n²)时间\tO(n log n)时间\t比率")
    
    for N in test_sizes:
        # 测试O(n²)算法
        start_time = time.time()
        quadratic_complexity_demo(N)
        quadratic_time = time.time() - start_time
        
        # 测试O(n log n)算法  
        start_time = time.time()
        n_log_n_complexity_demo(N)
        n_log_n_time = time.time() - start_time
        
        ratio = quadratic_time / n_log_n_time if n_log_n_time > 0 else float('inf')
        print(f"{N}\t{quadratic_time:.4f}s\t{n_log_n_time:.4f}s\t{ratio:.2f}")

单循环冒泡排序的复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def single_loop_bubble_sort(arr):
    """
    使用单个循环实现冒泡排序
    虽然只有一个while循环，但时间复杂度仍然是O(n²)
    """
    if arr is None or len(arr) < 2:
        return
    
    n = len(arr)
    end = n - 1                           # 未排序部分的右边界
    i = 0                                 # 当前比较位置
    
    while end > 0:                        # 外层逻辑：控制轮次
        if arr[i] > arr[i + 1]:          # 相邻元素比较
            arr[i], arr[i + 1] = arr[i + 1], arr[i]  # 交换
        
        if i < end - 1:                   # 当前轮次未结束
            i += 1                        # 移动到下一个比较位置
        else:                             # 当前轮次结束
            end -= 1                      # 缩小未排序范围
            i = 0                         # 重置比较位置
            # 虽然是单循环，但逻辑上等价于双层嵌套
            # 时间复杂度仍为O(n²)

空间复杂度分析

动态数组的均摊复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def dynamic_array_analysis():
    """
    动态数组扩容的均摊复杂度分析
    """
    arr = []                              # 初始空数组
    operations = []                       # 记录每次操作的代价
    
    for i in range(16):                   # 插入16个元素
        old_capacity = len(arr)           # 当前容量
        arr.append(i)                     # 插入元素
        
        # 模拟扩容过程
        if len(arr) > old_capacity:       # 发生了扩容
            # Python的list实际扩容策略比较复杂，这里简化为2倍扩容
            cost = old_capacity            # 扩容代价：复制所有旧元素
        else:
            cost = 1                      # 普通插入代价
        
        operations.append(cost)
        print(f"插入元素{i}, 当前大小={len(arr)}, 本次代价={cost}")
    
    total_cost = sum(operations)
    average_cost = total_cost / len(operations)
    print(f"总代价={total_cost}, 平均代价={average_cost:.2f}")
    
    # 数学分析：
    # 扩容发生在容量为1,2,4,8,...时
    # 总扩容代价：0 + 1 + 2 + 4 + 8 + ... < 2n
    # 总插入代价：n  
    # 均摊代价：(2n + n) / n = 3 = O(1)

递归算法的空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def recursive_space_analysis(n):
    """
    递归算法空间复杂度分析
    计算阶乘的递归实现
    """
    if n <= 1:                           # 基础情况
        return 1
    
    # 每次递归调用占用O(1)空间
    # 最大递归深度为n，所以空间复杂度为O(n)
    return n * recursive_space_analysis(n - 1)

def iterative_space_analysis(n):
    """
    迭代版本的阶乘计算
    空间复杂度为O(1)
    """
    result = 1                           # 只使用常数额外空间
    for i in range(1, n + 1):
        result *= i
    return result

复杂度分析的实用技巧

主定理（Master Theorem）

对于递归关系 $T(n) = aT(\frac{n}{b}) + f(n)$，其中 $a \geq 1, b > 1$：

  • 如果 $f(n) = O(n^{\log_b a - \epsilon})$，则 $T(n) = \Theta(n^{\log_b a})$
  • 如果 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \log n)$
  • 如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$，则 $T(n) = \Theta(f(n))$

均摊分析方法

  • 聚合分析：分析一系列操作的总代价
  • 核算法：为每种操作分配均摊代价
  • 势能法：定义势能函数分析代价分布

实际性能考虑因素

1
2
3
4
5
6
7
8
9
10
11
def practical_performance_factors():
    """
    影响实际性能的因素
    """
    print("影响算法实际性能的因素：")
    print("1. 常数因子：O(n)算法的常数可能很大")
    print("2. 数据规模：小规模时简单算法可能更快")  
    print("3. 内存访问模式：缓存友好的算法性能更好")
    print("4. 分支预测：减少条件分支可提高性能")
    print("5. 编译器优化：现代编译器能显著优化代码")
    print("6. 硬件特性：利用SIMD等特性可大幅提速")