使用Python进行数据结构与算法 – 原因、优缺点及最佳实践

import sys

sys.setrecursionlimit(10**6)  # 使用时请谨慎！

def factorial(n):

if n == 0:
    return 1
return n * factorial(n - 1)

print(factorial(1000))  # 这可能会引发 RecursionError

✅ in 在 set 或 dict 上: O(1) 平均 

# O(n): 列表
print(3 in [1, 2, 3, 4, 5])

# O(1): 集合或字典
print(3 in {1, 2, 3, 4, 5})

nums = [1, 2]
nums.append(3)  # 平均 O(1)

🧹 list.pop(0) 与 deque.pop()

⚠️ list.pop(0): O(n)

✅ deque.pop()（任一端）：O(1)

from collections import deque

# O(n)：移动所有元素
lst = [1, 2, 3]
lst.pop(0)

# O(1)：deque
dq = deque([1, 2, 3])
dq.pop()

使用 deque 进行高效的队列操作。

↔️ list.insert(0, x) 和 list.remove(x)

• insert(0, x) 将所有元素向右移动 → O(n)
• remove(x) 搜索 + 移动 → 也是 O(n)

nums = [1, 2, 3]

nums.insert(0, 0)  # 在开始位置插入: O(n)

nums.remove(2)     # 移除特定值: O(n)

🧩 复制列表

new_list = old_list[:]  # 或者 list(old_list)

虽然看起来微不足道，复制一个列表的时间复杂度是 O(n)，因为它会复制每一个元素。

🔀 list.sort() / sorted(list)

✅ 看起来是: O(n)

实际上: O(n log n)

nums = [4, 1, 3]
nums.sort()  # 使用 Timsort: O(n log n)

Python 使用 Timsort，这种排序算法经过优化，但在最坏情况下仍为 O(n log n)。

✂️ 循环中的字符串连接

s = ""
for word in words:
    s += word  # 总体时间复杂度为 O(n²)!

每次 += 操作都会创建一个 新字符串，如果重复执行，会导致时间复杂度为二次方。

✅ 更好的方法: ''.join(words) → O(n) 总体时间复杂度。

⚙️ 字典调整大小

Python中的字典提供摊销时间复杂度为O(1)的插入操作。但偶尔，内部表会进行调整大小并重新哈希所有键，这时时间复杂度会飙升至O(n)。

✅ TL;DR

在Python的 sorted() 和 .sort() 中使用比较器函数 在Python中，sorted() 函数和 .sort() 方法都用于对集合进行排序。虽然它们非常相似，但在用法和功能上略有不同。Python还允许您提供一个比较器函数以自定义排序顺序。

🔄 sorted() 与 .sort()

• sorted(): 从任何可迭代对象的元素中返回一个新的排序列表。

• .sort(): 就地 对列表进行排序，并返回 None。

💡 使用比较器函数

Python使用键函数而不是传统的比较器。键函数在比较之前转换每个元素，这在效率上更高，并且在Python中更受欢迎。然而，您可以使用 functools.cmp_to_key() 来模拟比较器的效果。

注意： cmp_to_key 是 functools 库的一部分，该库是 内置于 Python 中的，因此您不需要单独安装它。

示例 1：使用 sorted() 和比较器

from functools import cmp_to_key

# 比较器函数
def compare(x, y):
    return x - y  # 按升序排序（模拟比较器）

lst = [5, 2, 9, 1]

sorted_lst = sorted(lst, key=cmp_to_key(compare))  # 使用比较器函数
print(sorted_lst)

示例 2：使用 .sort() 和比较器

from functools import cmp_to_key

# 比较函数
def compare(x, y):
    return y - x  # 按降序排序（模拟比较器）
lst = [5, 2, 9, 1]
lst.sort(key=cmp_to_key(compare))  # 使用比较函数
print(lst)

🧠 内部算法

sorted() 和 .sort() 都在内部使用Timsort 算法，这是一种混合排序算法，源自归并排序和插入排序。它针对现实世界的数据进行了优化，平均和最坏情况下的时间复杂度为O(n log n)。