python-quick-start

Appearance

第1章：算法基础 ​

1.1 什么是算法：定义、五大特性与正确性 ​

算法是解决特定问题的明确、有限的步骤序列。它是计算机科学的核心概念，为程序设计提供了理论基础。

算法的五大特性 ​

1. 有穷性（Finiteness）

  • 算法必须在有限步骤内终止
  • 不能陷入无限循环
  • 每个操作都应在合理时间内完成

2. 确定性（Definiteness）

  • 每个步骤都有明确无歧义的定义
  • 相同输入总是产生相同输出
  • 不存在模糊或随机的指令

3. 输入（Input）

  • 算法可以有零个或多个输入
  • 输入来自特定的数据集合
  • 输入为算法提供处理的原始数据

4. 输出（Output）

  • 算法至少产生一个输出
  • 输出与输入存在特定关系
  • 输出是问题的解决方案

5. 可行性（Effectiveness）

  • 每个步骤都可通过基本操作实现
  • 操作在现有计算模型下可执行
  • 步骤具有实际可操作性

算法正确性验证方法 ​

  • 数学归纳法：证明算法对所有可能输入都正确
  • 循环不变式：验证循环结构的正确性
  • 测试驱动：通过大量测试用例验证
  • 形式化验证：使用数学逻辑严格证明

1.2 时间复杂度：基本操作计数与大O表示法 ​

时间复杂度描述算法执行时间随输入规模增长的趋势，是评估算法效率的关键指标。

基本概念 ​

基本操作：算法中最频繁执行且耗时相对固定的原子操作

  • 算术运算（+、-、×、÷）
  • 比较操作（<、>、==）
  • 赋值操作
  • 数组/指针访问

渐进分析：关注输入规模n趋向无穷大时的性能表现

大O表示法规则 ​

  1. 忽略常数因子：O(2n) = O(n)
  2. 保留最高阶项：O(n² + n) = O(n²)
  3. 加法规则：O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
  4. 乘法规则：O(f(n)) × O(g(n)) = O(f(n) × g(n))

常见时间复杂度分析 ​

python
# O(1) - 常数时间
def access_array_element(arr, index):
    return arr[index]  # 单次数组访问

# O(log n) - 对数时间
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# O(n) - 线性时间
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# O(n log n) - 线性对数时间
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

# O(n²) - 平方时间
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

1.3 常见复杂度阶：O(1)、O(log n)、O(n)、O(n log n)、O(n²) ​

复杂度阶详细对比 ​

复杂度增长率典型算法适用场景
O(1)常数哈希表操作、数组索引需要快速访问的场景
O(log n)对数二分查找、平衡树操作有序数据的高效查找
O(n)线性线性搜索、单次遍历需要检查每个元素的情况
O(n log n)线性对数归并排序、快速排序高效排序和分治算法
O(n²)平方冒泡排序、简单嵌套循环小规模数据或简单实现

实际性能差异示例 ​

假设处理n个元素所需的基本操作次数：

nO(1)O(log n)O(n)O(n log n)O(n²)
10131033100
1001710066410,000
1,0001101,0009,9661,000,000
10,00011310,000132,877100,000,000

复杂度选择原则 ​

  • 优先选择低复杂度算法：O(1) > O(log n) > O(n) > O(n log n) > O(n²)
  • 考虑实际数据规模：小数据集时高复杂度算法可能更简单
  • 权衡实现复杂度：有时简单但稍慢的算法更易维护

1.4 空间复杂度：辅助空间与原地算法 ​

空间复杂度衡量算法执行过程中所需的额外存储空间，同样重要于时间复杂度。

空间复杂度分类 ​

1. 原地算法（In-place Algorithm）

  • 空间复杂度：O(1)
  • 仅使用常数级别的额外空间
  • 直接在输入数据上进行修改

2. 非原地算法（Out-of-place Algorithm）

  • 空间复杂度：O(n) 或更高
  • 需要额外的存储空间
  • 保持输入数据不变

空间复杂度实例分析 ​

python
# O(1) 空间复杂度 - 原地反转
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# O(n) 空间复杂度 - 非原地反转
def reverse_out_of_place(arr):
    return arr[::-1]  # 创建新数组

# O(log n) 空间复杂度 - 递归快排
def quicksort_recursive(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort_recursive(arr, low, pi - 1)   # 左子数组
        quicksort_recursive(arr, pi + 1, high)  # 右子数组
    # 递归深度平均为O(log n)

# O(n) 空间复杂度 - 迭代快排（显式栈）
def quicksort_iterative(arr):
    stack = [(0, len(arr) - 1)]
    while stack:
        low, high = stack.pop()
        if low < high:
            pi = partition(arr, low, high)
            stack.append((low, pi - 1))
            stack.append((pi + 1, high))
    # 栈空间最坏情况下为O(n)

时间-空间权衡策略 ​

策略时间复杂度空间复杂度应用场景
缓存/记忆化降低增加重复子问题
原地操作可能增加降低内存受限环境
预处理增加预处理时间增加多次查询场景
流式处理可能增加显著降低大数据处理

实践建议 ​

  1. 明确约束条件：根据内存限制选择合适的算法
  2. 考虑数据特性：利用数据的特殊性质优化空间使用
  3. 平衡时间空间：在时间和空间之间找到最佳平衡点
  4. 避免过早优化：先确保正确性，再考虑优化