双对数图运行时间分析

Question

我正在对随机快速排序算法的实现进行运行时间分析。平均时间复杂度应为 O(n log n)。测试是在 2^20 到 2^30 的整数输入大小上完成的。我想将结果与 O(n log n) 理论线一起绘制在双对数图上，以检查一致性。

为了实现它，我使用这个Python代码：

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import linregress

# Data
input_sizes = [2**20, 2**21, 2**22, 2**23, 2**24, 2**25, 2**26, 2**27, 2**28, 2**29, 2**30]
times = [83.90, 167.00, 328.00, 673.60, 1390.50, 2863.40, 5895.60, 12253.70, 25269.50, 52770.60, 113618.54]

# Convert list to numpy arrays
input_sizes_np = np.array(input_sizes)
times_np = np.array(times)

# Create a log-log plot for the data points
plt.loglog(input_sizes_np, times_np, 'o-', label='Random Quick Sort (Integer)')

# Plot the theorical line
plt.loglog(input_sizes_np, input_sizes_np * np.log(input_sizes_np), label='Theoretical O(n log n)')

plt.xticks(input_sizes, [f'$2^{{{int(np.log2(size))}}}$' for size in input_sizes])

# Add labels
plt.xlabel('Input Size (n)')
plt.ylabel('Execution Time (ms)')

# Add a legend
plt.legend()

# Show the plot
plt.show()

我得到了附件中所示的表示法。我的理解是该算法与O(n log n)一致，因为两条线是平行的并且斜率接近0。我不明白的是两条线的接近度。算法一明显低于理论一。这是否意味着什么？如果是这样，为什么以及如何？这个程序正确吗？

Answer 1

如果每个操作需要一秒钟，您会期望操作数与秒数匹配。

缺乏邻近性是因为计算机的运行速度比这更快。