如何用Python绘图分析二分查找的运行时间？

我编写了如下递归实现的二分查找代码，但不清楚如何通过绘图获取它的运行时间：

def binary_search(array, lower, higher, x):
    if higher >= lower:
        middle = (higher + lower) // 2
        if array[middle] == x:
            return middle
        elif array[middle] > x:
            return binary_search(array, lower, middle - 1, x)
        else:
            return binary_search(array, middle + 1, higher, x)
    else:
        return -1

arr = [2, 3, 4, 10, 20]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
print(result)

实现步骤 #

要绘制运行时间曲线，需完成计时、生成测试数据、收集数据、绘图四个核心步骤，具体操作如下：

1. 导入必要库

需要用到计时模块、绘图库和随机数生成工具：

import time
import matplotlib.pyplot as plt
import random

2. 给二分查找添加计时逻辑

为减少偶然误差，对每个测试用例多次运行取平均耗时：

def binary_search(array, lower, higher, x):
    if higher >= lower:
        middle = (higher + lower) // 2
        if array[middle] == x:
            return middle
        elif array[middle] > x:
            return binary_search(array, lower, middle - 1, x)
        else:
            return binary_search(array, middle + 1, higher, x)
    else:
        return -1

def measure_avg_time(array, x, runs=100):
    total_time = 0
    for _ in range(runs):
        start = time.perf_counter()
        binary_search(array, 0, len(array)-1, x)
        end = time.perf_counter()
        total_time += (end - start)
    return total_time / runs  # 返回多次运行的平均耗时

3. 生成不同规模的测试数组

生成一系列长度递增的有序数组，模拟不同数据量的场景：

# 定义测试的数组长度范围（从1000到100000，步长1000）
sizes = range(1000, 100001, 1000)
avg_times = []

for size in sizes:
    # 生成有序数组
    test_arr = list(range(size))
    # 随机选取一个存在于数组中的目标元素
    target = random.randint(0, size-1)
    # 计算当前规模下的平均耗时
    current_avg = measure_avg_time(test_arr, target)
    avg_times.append(current_avg)
    print(f"数组长度: {size}, 平均耗时: {current_avg:.8f} 秒")

4. 绘制运行时间曲线

用matplotlib可视化数组长度与运行时间的关系：

plt.figure(figsize=(10, 6))
plt.plot(sizes, avg_times, marker='o', color='blue', label='二分查找平均耗时')
plt.xlabel('数组长度')
plt.ylabel('平均运行时间（秒）')
plt.title('二分查找运行时间与数组长度的关系')
plt.legend()
plt.grid(True)
plt.show()

结果说明 #

二分查找的时间复杂度为O(log n)，绘图后会看到曲线增长极为平缓——数组长度翻倍时，耗时仅小幅增加，完全符合对数级别的增长特性。

内容的提问来源于stack exchange，提问作者OrcaZep