双调排序（计算复杂度）

Question

所以基本上我试图了解应该如何计算双调排序的时间复杂度，以及最好和最坏的情况是使用成本和时间来决定，然后将值相加和相乘。

举个例子：我先尝试计算插入排序的复杂度。

        void sort(int A[]){                             Cost        Time

        for (int i = 1; i < A.length; i++)              c1          n
        {
            int key = A[i];                             c2          n-1
            int j = i-1;                                c3          n-1
            while (j >= 0 && A[j] > key){               c4          Σ (j=2 to n) of t_j
                A[j+1] = A[j];                          c5          Σ (j=2 to n) of (t_j-1)
                j = j-1;                                c6          Σ (j=2 to n) of (t_j-1)
            }
            A[j+1] = key;                               c7          n-1
        }
    }

t_j - 是"while"循环执行的次数。

T(n) = c1*n + c2(n-1) + c3(n-1) + c4(Σ (j=2 to n) of t_j) +

+c5(Σ (j=2 到 n) of (t_j-1)) + c6(Σ (j=2 to n) of (t_j-1)) + c7(n-1)

所以在最好的情况下 t_j = 1，那么：T(n) = an + b； (a, b - 常量)

在最坏的情况下t_j = j，则：T(n) = an^2 + bn + c;

所以 - O(n) - 最好的情况？ O(n^2) - 更坏的情况 ?

但是我真的不明白双调排序方法等操作的成本和时间应该是多少，例如这样的代码：

   public class BitonicSorter implements Sorter
{
    private int[] a;
    private final static boolean ASCENDING=true, DESCENDING=false;

    public void sort(int[] a)
    {
        this.a=a;
        bitonicSort(0, a.length, ASCENDING);
    }

    private void bitonicSort(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            bitonicSort(lo, m, ASCENDING);
            bitonicSort(lo+m, m, DESCENDING);
            bitonicMerge(lo, n, dir);
        }
    }

    private void bitonicMerge(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            for (int i=lo; i<lo+m; i++)
                compare(i, i+m, dir);
            bitonicMerge(lo, m, dir);
            bitonicMerge(lo+m, m, dir);
        }
    }

    private void compare(int i, int j, boolean dir)
    {
        if (dir==(a[i]>a[j]))
            exchange(i, j);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}

也许有人曾经尝试过计算这种排序算法的复杂度，并且可以举一个成本和时间的例子？或参考了解应归因于哪些成本和时间？

P.S我是新手，不太了解它应该如何"calculated"，所以请随时提出建议。欣赏。

Answer 1

要分析递归过程，您需要编写并解决递归问题。在这里，设 S(n) 为排序 n 元素的比较次数，M(n) 为合并 n 元素的比较次数。

           S(1) = 0
for n > 1, S(n) = 2 S(n/2) + M(n)
           M(1) = 0
for n > 1, M(n) = 2 M(n/2) + n/2

我们可以使用Master Theorem的Case 2来解决这些问题。

M(n) = Theta(n log n)
S(n) = 2 S(n/2) + Theta(n log n) = Theta(n (log n)^2)

Answer 2

@DavidEisenstat 的是正确的，但是 - 为了让事情更容易看，假设我们替换了：

private void compare(int i, int j, boolean dir)
{
    if (dir==(a[i]>a[j]))
        exchange(i, j);
}

在您的代码中

private void compare(int i, int j, boolean dir)
{
     // assuming i < j
     int lower = min(a[i], a[j]);         
     int upper = max(a[i], a[j]);         
     a[i] = lower;
     a[j] = upper;
}

现在整个过程绝对没有分支；完全是 non-adaptive，最好和最坏的情况是一样的。（好吧，基本上；我忽略了诸如 CPU 分支预测之类的事情，以及对 min() 和 max() 的 branch-free 实现的需求等等）。这是双调排序的优点之一，这使得它对硬件实现具有吸引力 - 并且使其 worst-case 更易于分析。

双调排序（计算复杂度）

Bitonic Sort (Calculating complexity)

algorithm

sorting

time-complexity

asymptotic-complexity