c# - 用 IEnumerable 实现的快速排序的复杂度是多少？

Question

我想知道 this post 中实现的快速排序的复杂性.

Stuart Marks 说它是 O(N^2 log N)。但真的如此吗？我不明白这些话:

It seems to me -- and once again, I'm not a C# or .NET expert -- that this will cause certain innocuous-looking calls, such as pivot selection via ints.First(), to be more expensive than they look. At the first level, of course, it's O(1). But consider a partition deep in the tree, at the right-hand edge. To compute the first element of this partition, the entire source has to be traversed, an O(N) operation. But since the partitions above are lazy, they must be recomputed, requiring O(lg N) comparisons. So selecting the pivot would be an O(N lg N) operation, which is as expensive as an entire sort.

为什么 ints.First() 是一个复杂度为 O(N) 的操作？我认为它总是 O(1)。为什么必须重新计算 IEnumerables 树中的上述分区？这对我来说也没有任何意义。 IEnumerable.Where 不返回一个新的 IEnumerable 吗？在我看来，该算法的时间复杂度仍然是 O(N log N)，但空间复杂度也是 O(N log N)，而不仅仅是我们就地排序的 O(N)。

总而言之，Stuart Marks 是对的还是我对的？

Answer 1

IEnumerable<>不缓存。如果它有一个集合支持(比如新的 int[5].AsEnumerable() )那么你可以重复使用它多少次，但是 IEnumerable<>理论上可以生成 piecemail，一次一个元素，在内存中你将只有当前元素，而以前的元素被遗忘。不能保证枚举两次 IEnumerable<>将返回相同的数据，也不可能将其枚举两次。您链接的问题非常愚蠢，表明张贴者不知道他在说什么。

QuickSort(IEnumerable<int> ints)建议有个参数IEnumerable<int> ints .该方法没有任何外部保证 IEnumerable<int> ints可以枚举两次，或者即使访问一次也不会导致 O(N) 操作。

现在... .First()可能是一个 O(N) 操作，甚至更糟，例如，如果必须订购后备集合......如果你 QuickSort(new[] { 5, 4, 3, 2, 1}.OrderBy(x => x)) , 然后 pars.First()执行后需要等待 OrderBy()将被执行，并且 OrderBy()必须先看全靠背IEnumerable<> (new[] { }) 对其进行排序(所以至少 O(N))

First() 的“有趣”示例这是 IEnumerable<> 上的 O(N)每次执行都会给出不同的结果。

private static int seed = 0;
public static IEnumerable<int> GetSomeInts()
{
    var rnd = new Random(seed++);

    for (int i = 0; i < 10; i++)
    {
        Console.Write(".");
        yield return rnd.Next(100000);
    }
}

for (int i = 0; i < 10; i++)
{
    Console.WriteLine(GetSomeInts().OrderBy(x => x).First());
}

你可以看到 O(N)从“.”的数量打印。尝试删除 OrderBy()并观察结果。关于 IEnumerable<> 的事实每次执行都会返回不同的结果...嗯...有一个for循环 :-) 尝试查看结果。