线性结构

description

操作动态数组链表栈队列双端队列
随机访问O(1)O(n)不支持不支持不支持
末尾插入/删除O(1)*O(1)O(1)O(1), 仅插入O(1)
队首插入/删除O(n)O(1)不支持O(1), 仅删除O(1)
两端插入/删除O(n)O(1)不支持不支持O(1)
动态数组和链表是通用的数据结构，而栈、队列和双端队列是针对特定场景优化的抽象。
# 可迭代对象: 容器, 生成器, 迭代器
# 容器可以这样判空, 不过生成器和迭代器不能这样判空
if not container:
   print('empty')

数组 Array

Python 的 list 是动态数组。虽然在 Python 中我们通常将 list 视为一个通用的容器，但其底层实现实际上是基于 动态数组 的。以下是详细的解释：

什么是动态数组？

动态数组是一种可以在运行时动态调整大小的数组。与静态数组不同，动态数组的容量可以根据需要扩展或收缩。

  • 特点：
    • 支持随机访问（时间复杂度 O(1)）。
    • 当容量不足时，会分配更大的内存空间，并将现有元素复制到新数组中。
    • 插入和删除操作的时间复杂度取决于位置：
      • 在末尾插入：摊销时间复杂度为 O(1)。
      • 在中间或开头插入/删除：时间复杂度为 O(n)。

Python list

Python 的 list 是基于 动态数组 实现的，其底层使用了 C 语言的数组（在 CPython 中实现）。

特点

  1. 动态扩展：

    • 当 list 的容量不足时，Python 会自动分配更大的内存空间。
    • 新的容量通常是当前容量的 1.125 倍（即增长因子为 9/8），以减少频繁的内存分配操作。

  2. 连续内存：

    • Python 的 list 在内存中是连续存储的，因此支持快速的随机访问（O(1)）。

  3. 支持多种数据类型：

    • Python 的 list 是一个通用容器，可以存储任意类型的对象（包括混合类型）。

  4. 插入和删除：

    • 在末尾插入元素效率最高（摊销 O(1)）。
    • 在中间或开头插入/删除元素需要移动其他元素，时间复杂度为 O(n)。

动态扩展的示例

以下代码展示了 Python list 的动态扩展行为：

import sys
 
# 创建一个空列表
lst = []
print(f"初始容量: {sys.getsizeof(lst)} 字节")
 
# 不断添加元素，观察内存变化
for i in range(20):
    lst.append(i)
    print(f"添加元素 {i} 后，容量: {sys.getsizeof(lst)} 字节")

输出示例：

初始容量: 56 字节
添加元素 0 后，容量: 88 字节
添加元素 1 后，容量: 88 字节
添加元素 2 后，容量: 88 字节
添加元素 3 后，容量: 88 字节
添加元素 4 后，容量: 120 字节
添加元素 5 后，容量: 120 字节
添加元素 6 后，容量: 120 字节
添加元素 7 后，容量: 120 字节
添加元素 8 后，容量: 184 字节
...

可以看到，list 的容量会在需要时动态扩展，而不是每次添加元素都重新分配内存。

Python list 的操作复杂度

操作时间复杂度说明
随机访问（lst[i]）O(1)由于底层是连续内存，支持快速随机访问。
末尾插入（append）O(1)*摊销时间复杂度为 O(1)，扩展时需要重新分配内存，代价较高。
中间插入/删除O(n)需要移动其他元素。
遍历O(n)遍历所有元素的时间复杂度为 O(n)。
查找元素（in）O(n)需要遍历整个列表，最坏情况下时间复杂度为 O(n)。

动态数组与链表的对比

特性动态数组（Python list）链表（LinkedList）
内存分配连续内存非连续内存
随机访问O(1)O(n)
插入/删除（末尾）O(1)*O(1)
插入/删除（中间）O(n)O(1)
内存使用效率高较低（需要额外存储指针）

总结

  • Python 的 list 是动态数组，底层基于连续内存实现，支持快速随机访问和动态扩展。
  • 动态扩展：
    • 当容量不足时，list 会分配更大的内存空间，并将现有元素复制到新数组中。
    • 这种扩展机制使得 list.append 的摊销时间复杂度为 O(1)。
  • 适用场景：
    • 如果需要频繁随机访问或在末尾插入元素，list 是一个高效的选择。
    • 如果需要频繁在中间或开头插入/删除元素，可以考虑使用链表（LinkedList）。
# 翻转
arr = [1, 2, 3, 4]
arr[::-1]  # [4, 3, 2, 1]

素数

  • 素数的定义：大于 1 且只能被 1 和自身整除的整数。
  • 非素数（合数）的定义。

生成素数

埃拉托色尼筛法：

标记一定范围内的所有非素数，剩下的就是素数。

代码示例：

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): # i*i <= n
        if is_prime[i]: # e.g if 2 是素数
            for j in range(i * i, n + 1, i): # 那么 2*2, 2*3, 2*4... 都不是素数
                is_prime[j] = False
    return [x for x in range(2, n + 1) if is_prime[x]] # 这里从 0开始也行, 因为我们把索引为素数的位置标记为了 True
primes = sieve_of_eratosthenes(20)
print(primes)  # [2, 3, 5, 7, 11, 13, 17, 19]
时间复杂度
第二定理

切片优化

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): # i*i <= n
        if is_prime[i]: # e.g if 2 是素数
            is_prime[i*i:n+1:i] = [False] * len(is_prime[i*i:n+1:i]) # 那么 2*2, 2*3, 2*4... 都不是素数
    return [x for x in range(2, n + 1) if is_prime[x]] # 这里从 0开始也行, 因为我们把索引为素数的位置标记为了 True
# 一行实现, 不用看
def sieve_of_eratosthenes(n):
    return [x for x in range(2, n + 1) if all(x % i != 0 for i in range(2, int(x**0.5) + 1))]

下面这两个东西相等吗?

因为我看到有人写

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1): # i*i <= n
        if is_prime[i]: # e.g if 2 是素数
            is_prime[i*i::i] = [False] * ((n - i*i) // i + 1)
    return [x for x in range(2, n + 1) if is_prime[x]]

greedyAlgorithms

链表 Linked List

栈 Stack

后进先出 (LIFO) 的数据结构，表示一种“递归”或“回溯”的逻辑.

  • 函数调用栈：每次函数调用都会将当前函数的状态压入栈，函数返回时从栈中弹出。
  • 括号匹配：使用栈来检查括号是否匹配。
  • 深度优先搜索 (DFS)：使用栈来模拟递归过程。
  • 表达式求值：如中缀表达式转后缀表达式、后缀表达式求值。

python 没有专门提供 stack , 建议用 list 来模拟栈的操作, 因为需要的操作的时间复杂度差不多

# 创建栈
stack = []
stack.append(1)  # 栈变为 [1]
stack.append(2)  # 栈变为 [1, 2]
x = stack.pop()  # 弹出栈顶元素 2，栈变为 [1], x = 2
# 获取栈顶元素
print(stack[-1])  # 输出 1

队列 Queue

先进先出 (FIFO) 的数据结构, 表示一种 “排队” 或 “顺序处理” 的逻辑. \

  • 任务调度：如操作系统中的任务队列。
  • 广度优先搜索 (BFS)：使用队列来按层次遍历图或树。
  • 数据流处理：按顺序处理数据流中的元素。

python 提供了 collections.deque , 这是一个双端队列 将其当作队列使用即可

from collections import deque
 
# 创建队列
queue = deque()
 
# 尾部插入
queue.append(1)  # 队列变为 [1]
queue.append(2)  # 队列变为 [1, 2]
# 头部插入
queue.appendleft(3)  # 队列变为 [3, 1, 2]
 
# 头部删除
queue.popleft()  # 删除队首元素，队列变为 [1, 2]
# 尾部删除
queue.pop()  # 删除队尾元素，队列变为 [1]
# 长度
print(len(queue))  # 输出 1

双端队列 Deque

支持两端插入和删除，表示一种“灵活的队列”. \

  • 滑动窗口问题：在固定大小的窗口内高效地找到最大值或最小值。
  • 双端任务调度：如同时处理高优先级和低优先级任务。
  • 回文检查：从两端同时检查字符串是否为回文。