algorithm - 简化的三向分区排序的时间复杂度

Question

下面是我的算法，它是对通用列表的 Dijkstra 三向分区算法的简化:

static <T extends Comparable> void dutchSort(List<T> list, int left, int right) {
    if (left >= right) return;

    T pivot = list.get(left);

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right;

    // before sorting is completed, 'equal' is the current value
    // much like 'i' in a for-loop
    // O(N) time
    while (equal < larger) {
        if (list.get(equal).compareTo(pivot) < 0)
            Collections.swap(list, equal, ++smaller);
        else if (list.get(equal).equals(pivot))
            equal++;
        else
            Collections.swap(list, equal, --larger);
    }

    // recursively sort smaller subarray
    dutchSort(list, left, smaller+1);

    // recursively sort larger subarray
    dutchSort(list, equal, list.size());
}

这是O(1)空间，我想是O(N^N)时间，但我不确定。 Toptal's post on 3-way QuickSort说是 O(N^2)，但不同之处在于我的算法要幼稚得多。我的思考过程是:while 循环需要 O(N) 时间，在最坏的情况下(所有 N 个元素都不同？)问题被分解为 N 个大小为 1 的子数组。

我尝试了 Master Theorem，但我不确定任何变量值。我认为子问题的数量是 2，每次递归调用将问题减少 2 倍，合并子问题需要 O(1) 的工作量。

所有这些都只是有根据的猜测，我很可能不太了解，所以我真的很想严格地解决时间复杂度。

O(N^N) 时间是否正确？如果是这样，为什么？

非常感谢:)

Answer 1

因此 while 循环在初始调用时的复杂度为 O(n)。如果我们假设一个数组[1, 2, 3, 4, 5]，那么第一次通过循环list[equal] == pivot，我们增加等于。

第二次及后续循环 list[equal] > pivot，因此我们递减 larger 并与该元素交换。当循环结束时，您有 equal=1，并且 smaller 没有改变。您的递归调用变为:

dutchSort(list, 0, 0)
dutchSort(list, 1, n)

所以其中一件元素掉落了。

对更多的递归深度进行相同的心理练习，我想您会了解分区的工作原理。

要使您的算法成为 O(N^N)，它必须多次将每个元素与其他每个元素进行比较。但这并没有发生，因为在递归的每个级别上，您都将问题分成两部分。一旦某个东西被拆分到数组的左半部分，它就永远无法与移动到数组右半部分的东西进行比较。所以最坏的情况是每个元素都与其他元素进行比较。那将是 O(N^2)。

当所有元素都相等时，算法是O(N)。

我认为算法的复杂性是由唯一项的数量决定的。初始数组顺序似乎不会产生任何影响。