为什么归并排序性能是线性的？

Question

我正在研究比较 Python 中的排序算法。我已经实现了这些算法和一个测试函数，该函数根据不同的输入大小评估每个算法，最大输入大小可达数十万。保存执行时间以供以后绘图。正如预期的那样，选择排序表现出二次行为，其图表也反映了这一点。然而，我遇到了合并排序的问题 – 它的图表看起来是线性的，而不是预期的 nlogn 行为！！

这是我的合并排序的实现：

def merge_sort(A):
    merge_sort_aux(A, 0, len(A) - 1)

# Merge Sort Helper Function
# (Recursive)
def merge_sort_aux(A, p, r):
    if p < r:
        q = (p + r) // 2  # Integer division
        merge_sort_aux(A, p, q)
        merge_sort_aux(A, q + 1, r)
        merge(A, p, q, r)

def merge(A, p, q, r):
    # Calculate the sizes of the two sublists
    n1 = q - p + 1
    n2 = r - q

    # Create two NumPy arrays initially initialized to 0 
    # They are of type float to support sentinels
    L = np.zeros(n1 + 1, dtype=float)
    R = np.zeros(n2 + 1, dtype=float)

    # Copy data into NumPy arrays
    L[:n1] = [A[p + i] for i in range(n1)]
    R[:n2] = [A[q + 1 + j] for j in range(n2)]

    # Sentinels
    L[n1] = np.inf
    R[n2] = np.inf

    i = j = 0

    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1  # Increment the index of the left sublist to preserve the loop invariant
        else:
            A[k] = R[j]
            j += 1  # Increment the index of the right sublist

这是我用来运行测试的函数

def test_algo(algo_function, maxRange=TEST_MAX_DIMENSION, minRange=2, step=TEST_STEP):
    """
    Test the execution time of the given algorithm function for various input sizes.

    Parameters:
    - algo_function: The algorithm function to be tested.
    - maxRange: The maximum input size to be tested.
    - minRange: The minimum input size to start the testing.
    - step: The step size between different input sizes.

    Returns:
    - results: A dictionary to store the execution times for each input size.
    """

    results = {}  # Dictionary to store execution times for each input size

    for i in range(minRange, maxRange, step):
        A = random_list(i)  # Assuming you have a function 'random_list' generating a list of size i
        start = timer()
        algo_function(A)
        end = timer()
        results[i] = end - start

    return results

任何建议或解释将不胜感激！

编辑

我测试了多达 300 万个值的列表

Answer 1

我认为你的 mergeSort 函数有一个错误。您为左右子数组创建了 NumPy 数组。在我看来，这是额外且不必要的步骤。

试试这个

def mergeSort(A, p, q, r): n1 = q - p + 1 n2 = r - q

L = A[p:p + n1]
R = A[q + 1:q + 1 + n2]

i = j = 0
k = p  

while i < n1 and j < n2:
    if L[i] <= R[j]:
        A[k] = L[i]
        i += 1
    else:
        A[k] = R[j]
        j += 1
    k += 1

while i < n1:
    A[k] = L[i]
    i += 1
    k += 1

while j < n2:
    A[k] = R[j]
    j += 1
    k += 1

Answer 2

问题不在于归并排序具有线性增长，而是 O(n log n) 和 O(n) 在有界范围内很难在视觉上区分。除非对结果进行缩放以考虑主导趋势效应并联合绘制，如下所示，否则人眼不会注意到少量的曲率。

即使使用线性回归等统计工具也会产生非常高的 R² 值，该值衡量垂直轴上的变化有多少是由水平轴上的值解释的。

我们通常不知道如何缩放线性或

n log n

值以便能够并排绘制它们，但是一旦您接受缩放的想法，就有一个简单的替代方案。您可以按候选复杂度（例如

n

、

n log n

、

n**2

等）缩放实验结果，并根据

n

（如果范围很大，则为

log n

）绘制缩放结果。如果生成的情节

• 增加超过

  n

  => 推测的复杂度太低；
• 减少超过

  n

  => 猜想太高；
• 收敛到一个常数 => 已确定正确的复杂性。

要看到即使实际复杂性中涉及低阶项，该方法也能起作用，请考虑以下示例，其中

t(n) = c1 * n**2 + c2 * n + c3

具有未知常数

c1

、

c2

和

c3

。如果我们错误地缩放了

n

，我们会得到

t(n) / n = (c1 * n**2 / n) + (c2 * n / n) + (c3 / n)
         = c1 * n + c2 + (c3 / n)

随着

n

的增加而增加。如果我们过度缩放

n**3

，我们会得到：

t(n) / n**3 = (c1 * n**2 / n**3) + (c2 * n / n**3) + (c3 / n**3)
            = (c1 / n) + (c2 / n**2) + (c3 / n**3)

将渐近收敛于零。当我们按金发姑娘的复杂性进行缩放时

n**2

:

t(n) / n**2 = (c1 * n**2 / n**2) + (c2 * n / n**2) + (c3 / n**2)
            = c1 + (c2 / n) + (c3 / n**2)

低阶项迅速收敛到零，并且缩放时间将收敛到

c1

。

我在 2018 年发表的一篇论文（DOI: 10.1002/qre.2424）中使用了这种方法来表明最佳解决方案（或无法确定最佳时最佳确定的可行解决方案）的增长率大于 O (n²) 但小于 O(n³):