如何用Python+Matplotlib正确绘制O(log n)时间复杂度曲线？

我正在开展一个项目，使用Python和matplotlib绘制不同算法的运行时间随输入规模变化的曲线，但在绘制O(log n)时间复杂度算法的曲线时遇到困难。

第一版代码 #

import time
import numpy as np
import matplotlib.pyplot as plt

def run_algo(n, func):
    start_time = time.time()  # current time
    func(n)
    end_time = time.time()
    return end_time - start_time

def linear(n):
    for i in range(n):
        i

def quadratic(n):
    for i in range(n):
        for j in range(n):
            j

def quadratic2(n):
    for i in range(n): 
        for j in range(i): 
            j

def cubic(n):
    for i in range(n): 
        for j in range(n): 
            for k in range(n): 
                k

def log_n(n):
    low = 1
    high = n
    while low <= high:
        mid = (low + high) // 2
        if mid * mid == n:
            return mid
        elif mid * mid < n:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

numberOfPoints = [60, 60, 60, 60, 1000]
min_value = [500, 50, 50, 10, 10**50]
max_value = [100000, 1000, 1000, 100, 10**101]
list_of_functions_to_run = [linear, quadratic, quadratic2, cubic, log_n]
titles = ["O(n)", "O(n^2)", "O(n^2)", "O(n^3)", "O(log n)"]
degrees = [1, 2, 2, 3, 1]

for i, func in enumerate(list_of_functions_to_run):
    time_complexity = []
    n_values = np.linspace(min_value[i], max_value[i], numberOfPoints[i])
    for n in n_values:
        time_complexity.append(run_algo(int(n), func))
    # Smooth out the time complexity curve using a moving average
    window_size = 4
    moving_average = np.convolve(time_complexity, np.ones(window_size)/window_size, mode='valid')
    # Plot the time complexity curve and the smoothed curve
    plt.figure()
    plt.plot(n_values[len(n_values)-len(moving_average):], moving_average, label='Smoothed')
    # Find a polynomial fit 
    x_values_for_fit = n_values[len(n_values)-len(moving_average):]
    label='Polynomial Fit'
    if titles[i] == "O(log n)":
        x_values_for_fit = np.log(x_values_for_fit)
        label='Logarithmic Fit'
    polyfit = np.polyfit(x_values_for_fit, moving_average, deg=degrees[i])
    polyfit_fn = np.poly1d(polyfit)
    plt.plot(n_values, polyfit_fn(n_values), label=label,color='tab:blue', linestyle='--')
    # Set the title and axis labels
    plt.title(f"Time Complexity: {titles[i]}")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time Complexity")
    plt.legend()

# Show the plot
plt.show()

代码运行无报错，但O(log n)的曲线不符合预期，呈现为一条水平线，其余复杂度的曲线均正常。多次调整n值数量、最大/最小n值，问题未解决。

更新版代码（改用scipy.curve_fit） #

import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import curve_fit

def run_algo(n, func):
    start_time = time.time()  # current time
    func(n)
    end_time = time.time()
    return end_time - start_time

def linear(n):
    for i in range(n):
        i

def quadratic(n):
    for i in range(n):
        for j in range(n):
            j

def quadratic2(n):
    for i in range(n): 
        for j in range(i): 
            j

def cubic(n):
    for i in range(n): 
        for j in range(n): 
            for k in range(n): 
                k

def log_n(n):
    low = 1
    high = n
    while low <= high:
        mid = (low + high) // 2
        if mid * mid == n:
            return mid
        elif mid * mid < n:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1
    
def log_function(x, a, b):
    return a * np.log(x) + b

def polynom_function(x, a, b, n):
    return a *x**n + b

def linear_func(x, a, b):
    return polynom_function(x, a, b,1)

def quadratic_func(x, a, b):
    return polynom_function(x, a, b,2)

def cubic_func(x, a, b):
    return polynom_function(x, a, b,3)


numberOfPoints = [60, 60, 60, 60, 6000]
min_value = [500, 50, 50, 10, 2]
max_value = [100000, 1000, 1000, 100, 100]
list_of_functions_to_run = [linear, quadratic, quadratic2, cubic, log_n]
list_of_functions_to_fit = [linear_func, quadratic_func, quadratic_func, cubic_func, log_function]
titles = ["O(n)", "O(n^2)", "O(n^2)", "O(n^3)", "O(log n)"]

for i, func in enumerate(list_of_functions_to_run):
    time_complexity = []
    n_values = np.linspace(min_value[i], max_value[i], numberOfPoints[i])
    for n in n_values:
        time_complexity.append(run_algo(int(n), func))
    # Smooth out the time complexity curve using a moving average
    window_size = 4
    moving_average = np.convolve(time_complexity, np.ones(window_size)/window_size, mode='valid')
    # Plot the time complexity curve and the smoothed curve
    plt.figure()
    plt.plot(n_values[len(n_values)-len(moving_average):], moving_average, label='Smoothed')
    # Find a curve fit 
    x_values_for_fit = n_values[len(n_values)-len(moving_average):]
    y_values_for_fit = moving_average
    func_to_fit = list_of_functions_to_fit[i]
    popt, pcov = curve_fit(func_to_fit, x_values_for_fit, y_values_for_fit)
    y_fit = func_to_fit(x_values_for_fit, *popt)
    plt.plot(x_values_for_fit, y_fit, label='fit: a=%f, b=%f' % tuple(popt), color='tab:blue', linestyle='--')
    # Set the title and axis labels
    plt.title(f"Time Complexity: {titles[i]}")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time Complexity")
    plt.legend()

# Show the plot
plt.show()

但曲线仍出现异常尖峰。

请问如何解决该问题？如何在Python中使用matplotlib正确绘制O(log n)时间复杂度曲线？

1. 核心问题分析 #

O(log n)算法的运行时间变化极小，远低于time.time()的毫秒级精度，导致测量结果噪声极大，要么是0要么是随机小值，最终曲线呈现水平线或尖峰。同时原测试的输入规模范围太小，log n的变化幅度被进一步压缩；二分查找函数的提前返回也会导致运行时间不严格对应log n复杂度。

2. 针对性改进措施 #

(1) 提升计时精度并增加重复测试 #

改用精度更高的time.perf_counter()，同时对同一n值重复运行多次算法取平均，大幅降低噪声：

def run_algo(n, func, repeat=1000):
    total_time = 0
    for _ in range(repeat):
        start = time.perf_counter()
        func(n)
        end = time.perf_counter()
        total_time += end - start
    return total_time / repeat

可根据n的大小动态调整repeat值：n小时重复10^5次，n大时重复100次，平衡测试精度和耗时。

(2) 扩展输入规模并使用对数间隔采样 #

log n增长极慢，需要覆盖足够大的n范围才能看出变化。用对数间隔生成n值，让小n和大n都有足够采样点：

# 生成从10到10^7的对数间隔n值，共100个点
n_values = np.logspace(1, 7, 100, dtype=int)

(3) 修正二分查找函数的提前返回问题 #

强制完成所有二分迭代，确保运行时间严格对应log n复杂度：

def log_n(n):
    low = 1
    high = n
    # 不提前返回，完成所有二分步骤
    while low <= high:
        mid = (low + high) // 2
        if mid * mid < n:
            low = mid + 1
        else:
            high = mid - 1
    return -1

(4) 优化平滑与拟合逻辑 #

• 增大移动平均窗口尺寸（比如设为10）进一步平滑噪声；
• 拟合时使用底数为2的对数（二分查找实际是log₂n），让拟合更准确：

def log2_function(x, a, b):
    return a * np.log2(x) + b

3. 完整修正代码 #

import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import curve_fit

def run_algo(n, func, repeat=1000):
    total_time = 0
    for _ in range(repeat):
        start = time.perf_counter()
        func(n)
        end = time.perf_counter()
        total_time += end - start
    return total_time / repeat

def linear(n):
    for i in range(n):
        pass

def quadratic(n):
    for i in range(n):
        for j in range(n):
            pass

def quadratic2(n):
    for i in range(n): 
        for j in range(i): 
            pass

def cubic(n):
    for i in range(n): 
        for j in range(n): 
            for k in range(n): 
                pass

def log_n(n):
    low = 1
    high = n
    while low <= high:
        mid = (low + high) // 2
        if mid * mid < n:
            low = mid + 1
        else:
            high = mid - 1
    return -1
    
def log2_function(x, a, b):
    return a * np.log2(x) + b

def linear_func(x, a, b):
    return a * x + b

def quadratic_func(x, a, b):
    return a * x**2 + b

def cubic_func(x, a, b):
    return a * x**3 + b

# 各算法配置参数
algo_configs = [
    {"func": linear, "fit_func": linear_func, "title": "O(n)", "n_gen": lambda: np.linspace(100, 10000, 50, dtype=int), "repeat": 100},
    {"func": quadratic, "fit_func": quadratic_func, "title": "O(n^2)", "n_gen": lambda: np.linspace(10, 200, 50, dtype=int), "repeat": 10},
    {"func": quadratic2, "fit_func": quadratic_func, "title": "O(n^2) (triangular)", "n_gen": lambda: np.linspace(10, 200, 50, dtype=int), "repeat": 10},
    {"func": cubic, "fit_func": cubic_func, "title": "O(n^3)", "n_gen": lambda: np.linspace(5, 50, 50, dtype=int), "repeat": 2},
    {"func": log_n, "fit_func": log2_function, "title": "O(log n)", "n_gen": lambda: np.logspace(1, 7, 100, dtype=int), "repeat": 10000}
]

for config in algo_configs:
    func = config["func"]
    fit_func = config["fit_func"]
    title = config["title"]
    n_values = config["n_gen"]()
    repeat = config["repeat"]
    
    time_complexity = []
    for n in n_values:
        time_complexity.append(run_algo(n, func, repeat))
    
    # 平滑处理
    window_size = 5
    moving_average = np.convolve(time_complexity, np.ones(window_size)/window_size, mode='valid')
    x_smooth = n_values[window_size//2 : -window_size//2 +1]
    
    plt.figure(figsize=(8,5))
    plt.plot(x_smooth, moving_average, label='Smoothed')
    
    # 曲线拟合
    popt, pcov = curve_fit(fit_func, x_smooth, moving_average)
    fit_label = f'Fit: {popt[0]:.2e}*'
    if title == "O(log n)":
        fit_label += 'log2(n)'
    else:
        fit_label += f'n^{title.split("^")[-1][:-1]}'
    fit_label += f' + {popt[1]:.2e}'
    
    plt.plot(x_smooth, fit_func(x_smooth, *popt), label=fit_label, color='tab:blue', linestyle='--')
    
    plt.title(f"Time Complexity: {title}")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Average Time (seconds)")
    plt.legend()
    # log n图设置x轴为对数刻度，更直观展示趋势
    if title == "O(log n)":
        plt.xscale("log")

plt.show()

4. 效果说明 #

• 高重复次数+高精度计时有效降低了log n算法的时间测量噪声；
• 对数间隔的n值让曲线变化更明显；
• 强制完成二分迭代确保运行时间与log n严格对应；
• 对数x轴可清晰展示log n的缓慢增长趋势。

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