复杂度实测与编写测试 · CS1602 计算导论

本次目标

亲手测出不同复杂度的实际差别
用记忆化把一个指数算法降到线性
正确使用 try / except / raise，分清异常和断言
写出第一套 pytest 测试

环境准备

python3 -m pip install pytest

题目

11-1 复杂度实测

写一个脚本，对下面每个操作测量在 n = 1000, 5000, 10000, 20000 时的耗时：

list.append(x) 执行 n 次
list.insert(0, x) 执行 n 次
x in list 在长度 n 的列表里查 100 次
x in set 在大小 n 的集合里查 100 次

把结果整理成一张表，在提交说明里回答：

n 翻倍时，每个操作的耗时大约翻几倍？
由此推断它们各自的复杂度是什么

11-2 字符串拼接

用同样的方法对比这两种写法在 n = 5000, 10000, 20000 时的耗时：

# 方法一
s = ""
for w in words:
    s += w

# 方法二
s = "".join(words)

在提交说明里给出耗时表，并解释为什么方法一慢。

11-3 给递归加记忆化

拿你在 Lab 7 写的 count_ways(amount, coins)（硬币组合计数），做三件事：

加一个计数器，测出 count_ways(100, [1, 2, 5, 10]) 需要多少次函数调用
用字典给它加上记忆化
再测一次调用次数，算出加速比

在提交说明里给出两个数字和比值。

11-4 安全的转换

实现三个函数，转换失败时返回默认值而不是崩溃：

def safe_int(text: str, default: int = 0) -> int: ...
def safe_float(text: str, default: float = 0.0) -> float: ...
def safe_div(a: float, b: float, default: float = 0.0) -> float: ...

要求：只捕获具体的异常类型，不许写裸的 except:。

在提交说明里写出每个函数你捕获了哪些异常，以及为什么是这些。

11-5 找出并修正错误的异常处理

下面这段代码有三个问题。找出来，改对，并在提交说明里逐条说明。

def load_config(filename):
    try:
        f = open(filename)
        data = f.read()
        config = {}
        for line in data.split("\n"):
            key, value = line.split("=")
            config[key] = int(value)
        return config
    except:
        return {}

11-6 自定义异常

给 Lab 9 的 Temperature 类改造：把”低于绝对零度”从”打印一句话返回 False”改成抛出自定义异常。

class TemperatureError(Exception):
    """温度不合法。"""
    ...

在提交说明里回答：什么情况下抛异常比返回 False 更好？什么情况下相反？

11-7 给别人的代码写测试

下面是一个”已经写好”的模块。你的任务不是改它，是给它写一套 pytest 测试。

# textstats.py
def word_count(text: str) -> int:
    """统计单词数。"""
    return len(text.split())

def longest_word(text: str) -> str:
    """返回最长的单词。长度相同时返回先出现的。"""
    words = text.split()
    return max(words, key=len)

def average_word_length(text: str) -> float:
    """返回平均单词长度。"""
    words = text.split()
    return sum(len(w) for w in words) / len(words)

写一个 test_textstats.py，要求：

每个函数至少 4 个测试
必须覆盖：正常情况、空字符串、单个单词、多个空格
至少用一次 pytest.raises

然后运行 python3 -m pytest -v，把输出贴到提交说明里。

最后回答：这三个函数里，有几个在空字符串上会出问题？分别是什么问题？

提交前自查

11-1、11-2 有完整的耗时表和复杂度推断
11-3 的记忆化键包含了所有变化的参数
11-4 没有裸的 except:
11-5 找出了三个问题
11-6 回答了”何时抛异常、何时返回值”
11-7 每个函数至少 4 个测试，用过 pytest.raises
11-7 回答了空字符串的问题
AI 使用声明写了