时间戳

首页 > 解决方案 > 简化的 3 路分区排序的时间复杂度

algorithm - 简化的 3 路分区排序的时间复杂度

问题描述

下面是我的算法，它是对通用列表的 Dijkstra 的 3 路分区算法的简化：

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 在 3-way QuickSort 上的帖子说它是 O(N^2)，但不同的是我的算法更加天真。我的思考过程是：while循环需要 O(N) 时间，在最坏的情况下（所有 N 个元素都是不同的？）问题被分解为 N 个大小为 1 的子数组。

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

所有这一切都只是有根据的猜测，我很可能很迷茫，所以我真的很想严格解决时间复杂度。

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

非常感谢 ：）

标签： algorithmsortingtime-complexityspace-complexitymaster-theorem

解决方案

所以while循环在初始调用时是 O(n)。如果我们假设一个数组[1, 2, 3, 4, 5]，那么第一次通过循环list[equal] == pivot，我们递增equal。

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

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

所以其中一件物品掉了下来。

对更多的递归深度做同样的心理练习，我想你会了解分区是如何工作的。

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

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

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

推荐阅读