时间戳

首页 > 解决方案 > 为什么分而治之的反转计数为 n*log(n)？

algorithm - 为什么分而治之的反转计数为 n*log(n)？

问题描述

我看过的很多资源都说分而治之的反转计数方法的运行时间为 nlog(n) 但我不明白为什么。我知道合并排序有 nlog(n) 时间，因为在基本情况下划分数组的数量是 log(n) 并且每次我们需要合并两个数组时合并的运行时间是 (n)。

但是当我们在合并排序之上“捎带”时，我们需要比较数组的两半：

[a,b,c] and [d,e,f]

对于左侧数组中的所有元素，“a”需要与“d”和“e”和“f”最坏情况等进行比较。所以似乎仅此一项就会有 n^2/4 的运行时间，所以分而治之反转算法的运行时间不是 n^2log(n) 吗？

标签： algorithmsorting

解决方案

[a,b,c] 和 [d,e,f]

"a" 需要与 "d" 和 "e" 和 "f" 最坏情况进行比较

循环

while (not at end of A && not at end of B)

无论比较结果如何，总是有 O(|A|+|B|) 步。Merge-and-Count 没有最好的情况也没有最坏的情况。

排序和计数（L）

if list L has one element
    return (0, L)

Divide the list into two halves A and B
(rA, A) ← Sort-and-Count(A)
(rB, B) ← Sort-and-Count(B)
(rC, L) ← Merge-and-Count(A, B)
r = rA + rB + rC
return (r, L)

合并计数 (A, B)

    curA = 0; curB = 0;
    count = 0;
    mergedList = empty list

    while (not at end of A && not at end of B)
        a = A[curA]; b = B[curB];
        if (a < b)                             // only one comparison
            append a to mergedList;
            curA++;
        else
            append b to mergedList;
            curB++;
            count = count + num elements left in A

    if (at end of A) 
        append rest of B to mergedList;
    else
        append rest of A to mergedList;

    return (count, mergedList);

推荐阅读