pandas 内连接、左连接和右连接的时间复杂度是 O(n) 吗？

Question

我在这个线程中读到：

pandas DataFrame.join 的运行时间是多少（大“O”顺序）？

内连接预计为 O(n)，而左连接和右连接预计为 O(n log n)。我一直在使用随机数据帧进行一些测试，例如：

df1 = pd.DataFrame({
        'user_id': range(1, size + 1),  # Unique user_id for df1
        'numeric_1': np.random.rand(size),
        'numeric_2': np.random.rand(size),
        'numeric_3': np.random.rand(size),
        'string_1': np.random.choice(['A', 'B', 'C', 'D'], size),
        'string_2': np.random.choice(['E', 'F', 'G', 'H'], size),
        'string_3': np.random.choice(['I', 'J', 'K', 'L'], size),
    })

df2 = pd.DataFrame({
        'user_id': range(size + 1, 2 * size + 1),  # Ensuring unique user_id for df2
        'numeric_4': np.random.rand(size),
        'numeric_5': np.random.rand(size),
        'numeric_6': np.random.rand(size),
        'string_4': np.random.choice(['M', 'N', 'O', 'P'], size),
        'string_5': np.random.choice(['Q', 'R', 'S', 'T'], size),
        'string_6': np.random.choice(['U', 'V', 'W', 'X'], size),
    })

我对每个样本大小进行了多次模拟，并对结果进行了平均，以减少由于计算机上的本地条件而导致的变化的影响。这是我得到的情节：

由于所有 3 条线都接近平行且线性（斜率约为 1.07），我认为这意味着所有 3 种连接类型都是 O(n^1.07)，非常接近 O(n)。这看起来正确吗？如果左/右连接是 O(n log n) ，我应该在图中看到什么？

如果需要的话，很高兴分享我的完整代码。

Answer 1

由于所有 3 条线都接近平行且线性（斜率约为 1.07），我认为这意味着所有 3 种连接类型都是 O(n^1.07)，非常接近 O(n)。这看起来正确吗？

如果仔细观察图中的 3 条线，对于较大的 n，“内部”线的斜率会变得略小于“左”和“右”的斜率，这与内部连接的 O(n) 一致左/右连接的复杂度为 O(n log n)，但这非常有限——所有 3 个连接都非常接近 O(n)。如果左/右确实是 O(n log n)，我预计会出现进一步的分歧，如果样本量进一步增加，我们可能会观察到这一点。

如果左/右连接是 O(n log n) ，我应该在图中看到什么？

我建议运行模拟来调查：

import numpy as np
import matplotlib.pyplot as plt

# Generate an extremely large range of sample sizes
n = np.logspace(1, 10, 10000)  # From 10^1 to 10^10
time_linear = n  # O(n)
time_nlogn = n * np.log(n)  # O(n log n)

# Plotting on a log-log scale using the updated API
plt.figure(figsize=(10, 6))
plt.loglog(n, time_linear, label='O(n)', base=10)
plt.loglog(n, time_nlogn, label='O(n log n)', base=10, linestyle='--')

plt.xlabel('Input size (n)')
plt.ylabel('Time')
plt.title('Time Complexity: O(n) vs. O(n log n) on a Log-Log Scale')
plt.legend()
plt.grid(True, which="both", linestyle='--')
plt.show()

产生这个：

如果要在线性标度上绘制相同的函数，O(n) 和 O(n log n) 之间的差异会更加明显，尤其是对于较大的 n，其中 log n 因子会导致 O(n log n) n) 图的增长速度明显快于 O(n) 图。

例如，对上面的代码稍作修改，我们就可以看到线性-线性和对数-线性图的样子：

对于对数线性：