Python时空效率分析
困难3程序快不快？内存用多少？——时空效率入门
写程序就像做数学题，有的方法快，有的方法慢。我们关心两个事情：时间效率（运行速度）和空间效率（内存占用）。就像你写作业，同样一道题，用草稿纸计算和用心算，时间不同；用大书桌和用小桌面，空间不同。在编程中，我们要学会“计时”和“算内存”。
简单来说：
- 时间效率：程序从开始到结束花了多少时间，就像你吃一碗面是 5 分钟还是 20 分钟。
- 空间效率：程序运行时要占多少内存（也就是电脑的“临时记忆”），就像你的书包能装多少本书。
有时为了更快，需要多用点内存；有时为了省内存，程序会跑得慢一点。就像一个游戏，画面越精美占内存越大，但玩起来更爽。学好时空效率，能帮你写出又快又省内存的代码。
1. 时间效率怎么看？——像掐秒表一样
我们可以用 Python 的 time 模块来测量一段程序跑了多久。就像体育老师用秒表测你跑 100 米的时间一样。
1.1 生活中的例子：找名字
想象你要在一个全班同学的名单（按学号排好序）里找“张三”：
- 方法一（线性搜索）：从头看到尾，一个一个名字。如果张三在第一个，一下就找到；如果他在最后一个，就要看完整整 50 个名字。
- 方法二（二分搜索）：因为名单按学号排好序，先看中间那个，如果“张”在字母表里比中间靠前，就只看前半部分；如此反复，每次排除一半。最多看 6 次就能找到（因为 2⁶=64 > 50）。
明显二分搜索快得多，尤其是在名单很长的时候。
1.2 用代码测量时间
下面从 0 到 9999 的列表中查找数字 9999。我们用两种方法，并测量时间。
import time
# 线性搜索 —— 一个一个看
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# 二分搜索 —— 每次砍掉一半
def binary_search(lst, target):
left = 0 # 左边界索引
right = len(lst) - 1 # 右边界索引
while left <= right:
mid = (left + right) // 2 # 取中间位置
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1 # 目标在右边一半
else:
right = mid - 1 # 目标在左边一半
return -1
# 创建一个包含 0 到 9999 的有序列表
my_list = list(range(10000)) # 生成 10000 个连续整数
target = 9999 # 要查找的数（最后一个）
# 测量线性搜索的时间
start_time = time.time() # 记下开始时刻
linear_search(my_list, target)
end_time = time.time() # 记下结束时刻
print("线性搜索用时:", end_time - start_time, "秒")
# 测量二分搜索的时间
start_time = time.time()
binary_search(my_list, target)
end_time = time.time()
print("二分搜索用时:", end_time - start_time, "秒")
运行后你会发现，二分搜索可能比线性搜索快几百倍甚至更多。这就是时间效率的差别。更专业的说法是“时间复杂度”，我们后面会提到。
2. 空间效率怎么看？——算算占多少“脑容量”
空间效率就是程序用了多少内存。内存就像你的书桌桌面，能放的东西有限。如果程序太贪心，可能会让电脑变慢甚至卡死。
2.1 用 sys.getsizeof() 测量大小
Python 里每个变量都会占一定的内存。我们可以用 sys.getsizeof() 来查看它占了多少字节（1 字节大约能存一个英文字母）。
import sys
# 一个整数的内存
a = 100 # 一个整数变量
print("整数 100 占:", sys.getsizeof(a), "字节")
# 一个列表占的内存
my_list = list(range(100)) # 0 到 99 的列表
print("列表（100个数）占:", sys.getsizeof(my_list), "字节（仅列表本身）")
# 一个集合占的内存
my_set = set(range(100)) # 0 到 99 的集合
print("集合（100个数）占:", sys.getsizeof(my_set), "字节（仅集合本身）")
你会发现，集合比列表占的内存多很多，因为集合要记录更多的信息来实现快速查找。这就是“用空间换时间”的例子：集合查找比列表快，但占内存大。
2.2 生活中的例子：两种“找东西”方式
- 列表（线性搜索）：就像你把所有玩具整整齐齐排在地上，找的时候要一个一个看。空间浪费少（只占一点地板），但慢。
- 集合（哈希表）：就像你给每个玩具贴上编号，然后按编号放到不同的抽屉里。找的时候直接看编号去对应抽屉，快极了，但是需要做很多抽屉（多占空间）。
在选择数据结构时，我们经常要在速度和内存之间做取舍。
3. 新手容易犯的错误
3.1 忘记考虑时间，把简单问题写复杂
有的同学写程序只追求“能跑通”，不看效率。比如，在循环里重复做耗时操作：
# 错误示例：每次都在循环里排序
big_list = [5, 3, 9, 1, ...] # 假设有 1 万个数字
for i in range(len(big_list)):
big_list.sort() # 每循环一次就把整个列表排序一次（极其慢！）
# ... 其他操作
应该只在循环外排序一次。
3.2 滥用递归导致栈溢出
递归虽然代码简洁，但每次调用都会占用栈空间。比如计算斐波那契数列第 40 项，简单递归会重复计算大量子问题，而且栈深度达到 40，虽然不大，但如果算到 1000，就可能栈溢出或超时。
3.3 不考虑内存，一次性加载太大
比如处理一个 10 GB 的文件，有人直接全部读到内存中，导致电脑爆内存。应该按行或分块读取。
3.4 混淆时间单位和空间单位
时间常用秒、毫秒；空间常用字节、KB、MB。写代码时不要以为 1 秒和 1 MB 是一个概念。
4. 完整示例：对比两种查找的时空效率
下面我们写一个完整的程序，不仅测量时间，还测量一下两种搜索函数本身占用的内存（包括它们的代码和变量）。（注意：函数的内存很小，主要是数据结构的差别。）
import time
import sys
# ---------- 定义两种搜索函数 ----------
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
def binary_search(lst, target):
left = 0
right = len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# ---------- 创建数据 ----------
n = 100000 # 列表长度 10万
my_list = list(range(n)) # 生成 0 到 99999
target = n - 1 # 找最后一个数
# ---------- 测量时间 ----------
# 线性搜索
start = time.time()
linear_search(my_list, target)
t_linear = time.time() - start
print(f"线性搜索用时: {t_linear:.6f} 秒")
# 二分搜索
start = time.time()
binary_search(my_list, target)
t_binary = time.time() - start
print(f"二分搜索用时: {t_binary:.6f} 秒")
# ---------- 测量空间（仅演示列表和集合的大小） ----------
print("\n--- 空间对比 ---")
print(f"列表（{n}个整数）本身占: {sys.getsizeof(my_list)} 字节")
# 再创建一个等大的集合
my_set = set(range(n)) # 同样包含 0~99999 的集合
print(f"集合（{n}个整数）本身占: {sys.getsizeof(my_set)} 字节")
# 注意：列表和集合还包含内部元素占用的内存，这里只展示容器本身
# 想要更精确可以计算总大小，但小学生先理解“集合比列表占更多空间”即可
运行时会看到：
- 时间上，二分搜索几乎瞬间完成（不到 0.001 秒），而线性搜索可能要 0.01 秒（在 10 万数量上差别明显）。
- 空间上，集合占的字节数远大于列表。
5. 相关指引
- 大 O 符号：用“O(n)”、“O(log n)”等符号来描述时间或空间随数据规模增长的速度。比如线性搜索是 O(n)，二分搜索是 O(log n)。这是更专业的说法，可以进一步学习。
- 常见算法时间复杂度：循环嵌套常常带来 O(n²) 的时间（比如冒泡排序），而排序后二分搜索比线性搜索快很多。
- 优化技巧：能用公式就不用循环（比如求和用
(首+末)*个数/2），能用字典或集合就少用列表内查找，能用局部变量就少用全局变量等。 - 其他测量工具：
timeit模块可以更精确地测量小段代码，memory_profiler可以逐行分析内存使用。
学好时空效率，就像掌握了“做什么事最快最省材料”的本领，让你写的程序又快又稳定！
例题精讲
在Python中，删除列表第一个元素（例如 L=[1,2,3]; L.pop(0)）的时间复杂度是多少？
在Python中，使用生成器表达式（如 (x for x in range(10)) ）比列表推导式（如 [x for x in range(10)] ）更节省内存。
以下函数用于找出列表中出现次数最多的元素。请分析其时间复杂度，并补全注释中的复杂度描述。
def most_frequent(lst):
counter = {}
for item in lst:
counter[item] = counter.get(item, 0) + 1
best = max(counter, key=counter.get)
return best
# 时间复杂度: ___使用朴素递归计算斐波那契数列第n项（如 def fib(n): return n if n<2 else fib(n-1)+fib(n-2) ）的时间复杂度约为？
Python中，字典（dict）的键查找操作（如 d[key] ）的平均时间复杂度是O(1)。