测试数组append方法时间复杂度时高效实现显示O(1)问题排查
问题分析
- 核心错误1:测试逻辑未每次重置列表实例
你在测试两类append的外层循环中,仅在循环外初始化了一次列表,每次迭代测试i个元素append时,是在上一次迭代已经有元素的列表基础上继续追加,并不是测试「从空列表追加i个元素的总耗时」,测试逻辑本身不成立。 - 核心错误2:测试量级过小,计时精度不足
你仅测试了最多300次追加的场景,Python内置list的append本身耗时极短,默认的time.time()计时精度不足以捕捉到微秒级的耗时变化,大部分测试结果的耗时都在误差范围内,所以看起来近似水平直线。 - 认知补充:Python内置list的append是*摊销O(1)*操作,连续n次追加的总时间复杂度确实是O(n),和你理论推导的结论一致,只是测试方法有问题没有复现出来。
修正方案
- 每次外层循环开始前,重新初始化你的
PyListInef或者PyList实例,保证每次测试都是从空列表开始。 - 将测试的最大n调整到10000以上,放大耗时差异。
- 用精度更高的
time.perf_counter()代替time.time()做计时,更适合短耗时场景的测试。
修正后的核心测试代码示例
# 高效append测试修正后示例 time_dict_ef = dict() max_n = 10000 series = np.linspace(1, max_n+1, max_n) for i in range(max_n): lst = PyList() # 每次都重置为空列表 starttime = time.perf_counter() for j in range(i): lst.append(series[j]) elapsed_time = time.perf_counter() - starttime time_dict_ef[i] = elapsed_time * 100000
修正后你就能看到高效版的耗时随元素数量线性增长,符合O(n)的总时间复杂度特征,低效版则是明显的二次曲线增长。
内容的提问来源于stack exchange,提问作者Renan de Oliveira Pereira
相关产品推荐
相关产品推荐

