为什么Python非常适合学习数据结构与算法（DSA）
在掌握数据结构与算法（DSA）时，选择合适的编程语言可以产生巨大的影响。Python作为最佳选择之一，原因如下。
🧠 简洁的语法，清晰的逻辑
Python的干净且易读的语法使得我们更容易专注于逻辑，而不是在语言中迷失。无论是二叉树、图遍历还是动态规划，你编写的代码行数更少，且一眼就能理解。
🎯 面试的完美选择
在编码面试中，时间是宝贵的。Python的自然语言结构帮助你清晰地解释你的思路。与冗长的语言如Java或C++相比，使用Python编写的解决方案更容易让面试官理解。
🔧 内置强大功能
Python提供了强大的内置数据结构，如列表、集合和字典，使你能够快速原型化和测试想法，而无需重新发明轮子。
🚀 快速编写，易于调试
快速迭代和最小的样板代码使得Python非常适合高效地解决多个问题，同时为面试或竞赛做准备。
简而言之：Python让你专注于像一个问题解决者思考——而不仅仅是一个程序员。这正是面试所测试的内容。
接下来，我将根据遇到的重要笔记，附加关于在数据结构与算法（DSA）中使用Python的内容。
Python的递归限制
在Python中编写递归解决方案时，一个常见的陷阱——尤其是对于深度优先搜索（DFS）或树遍历等问题——是达到递归深度限制。与其他一些语言不同，Python的默认递归限制相对较低（通常约为1000），对于深层递归调用很容易超过这个限制。
import sys
sys.setrecursionlimit(10**6) # 使用时请谨慎！
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(1000)) # 这可能会引发 RecursionError如果不小心，这可能会导致 RecursionError: maximum recursion depth exceeded。始终考虑递归解决方案是否是最佳方法——或者它是否可以被重写为迭代形式，或者通过记忆化或尾递归进行优化（Python 默认不优化尾递归）。
当然！这是你整理过的、格式良好且简洁的迷你博客，主题是 看似 O(n) 但实际上不是（或反之）的 Python 操作——重复信息已删除，部分结构更为清晰：
🧠 理解 Python 的时间复杂度：看似 O(n) 但实际上不是的操作
在使用 Python 进行数据结构与算法（DSA）时，了解常见操作的 真实 时间复杂度可以帮助你编写更优化的代码——并在面试中更好地解释它！一些操作可能 看起来 像是线性时间，但实际上是常数时间（或反之亦然）。让我们来探讨这些微妙的情况：
🔍 in 操作符 — list vs set/dict
✅ in 在 set 或 dict 上: O(1) 平均 ⚠️ in 在 list 上: O(n)
# O(n): 列表
print(3 in [1, 2, 3, 4, 5])
# O(1): 集合或字典
print(3 in {1, 2, 3, 4, 5})
Python 使用 哈希表 来实现集合和字典，从而实现常量时间的查找。
➕ list.append(x)
✅ 看起来是: O(n)
实际上: 摊销 O(1)
Python 列表是动态数组。它们偶尔会调整大小，但 append() 是摊销常量时间。
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
| 操作 | 时间复杂度 | 注意事项 |
|---|---|---|
x in list |
O(n) | 使用set/dict进行O(1)查找 |
list.append(x) |
摊销O(1) | 调整大小偶尔会发生 |
list.pop(0) / insert(0,x) |
O(n) | 建议使用deque |
list.remove(x) |
O(n) | 先搜索然后移动元素 |
copy list via [:] |
O(n) | 每个元素都会被复制 |
list.sort() / sorted() |
O(n log n) | 内部使用Timsort |
s += word in loop |
O(n²) | 使用''.join()可以达到O(n) |
dict insert/lookup |
摊销O(1) | 偶尔调整大小可能会飙升至O(n) |
在Python的在Python中，sorted()和.sort()中使用比较器函数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)。
