在线测试中的算法复杂度

Question

我必须完成一个实习的在线编程测试，并且得到了一个关于复杂性分析的问题。我回答了这个问题，它被标记为错误，我只是想了解为什么，以便我改进。

问题：

Give the complexity for the following algorithm when reverseOrder is true and when it is false:

List<int> stackToList(Stack<int> stack, bool reverseOrder) {
    List<int> items = new List<int>();

    while (stack.Count > 0) {
        int item = stack.Pop();

        if (reverseOrder) {
            items.Insert(0, item);
        } else {
            items.Add(item);
        }
    }

    return items;
}

编辑： 是多选题，可能的答案是：

O(1)
O(nlogn)
O(n)
O(n^2)

当 reverseOrder 为真时，您可以选择一个，当它为假时，您可以选择另一个。

我的回答：

当reverseOrder为真时：O(n²)
当reverseOrder为false时：O(n²)

我通过以下方式得到了这个答案：

while 循环将迭代 n 次，因为它会一直持续到没有元素要弹出为止
Pop() 是 O(1)
在 reverseOrder 为 true 的情况下，在列表前面创建一个 Insert。由于 List<T> 由数组支持，因此它会动态调整大小并且每个元素向上移动一个 space，并且该元素被插入到索引 0 处。根据 https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx ：

This method is an O(n) operation, where n is Count.
在 reverseOrder 为 false 的情况下，Add 用于将项目附加到列表的后面。由于 items 没有给出初始大小，因此 Count 永远不会小于 Capacity，导致调整大小，因此根据 https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx ：

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

此刻我感到很沮丧，因为我做错了这道题导致我的分数直线下降，尽管我在测试中的所有其他问题都答对了。

Answer 1

你需要问写测试的人。这里的任何答案都将严格基于意见，因为我们没有完整的上下文，即什么会导致测试作者以与您不同的方式描述算法的复杂性。

也就是说，我同意测试作者对 reverseOrder == false 场景的看法。虽然您确实可能在调用 Add() 期间进行调整大小操作，但随着新大小加倍，调整大小操作最坏情况下会引入 log N 成本每次调整大小。

你没有说正确答案应该是什么，但我会给出 O(N log N)。

Answer 2

您的假设是每次添加项目时容量都会增加 - 这是不正确的。该文档似乎没有提到确切的算法，但我相信每次容量增加时它都会翻倍。您可以在您链接的文档中关于恐龙的样本中看到 - 他们添加了 5 只恐龙，容量报告为 8 只。

Answer 3

查看

的第 6669 行

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

很明显，在列表的开头插入会强制复制列表中的所有内容。所以每次插入都需要 N 步。 O(N^2) 在我看来。

Answer 4

stackToList(堆栈，true) = O(n)。大多数时候，此调用的时间复杂度为 O(1)。但是，当 List.Add 函数必须扩展到超过其容量时，需要将数组复制到容量是前一个的两倍的新数组，并迭代之前的项以将它们存储在新数组中。因此，我们可以将 excel 中的实际操作表示为 IF(nLOG(n,2)(n/2)/INT(nLOG(n,2)(n/2)) = 1, n, 1)。如果没有资源瓶颈，如果此算法在 10 秒内完成 1000 万个项目，要完成 1 亿个项目，您预计需要大约 10(10) 秒。实际上，我们知道它会比 Big O Notation 预测的稍微差一点，因为 O(n) 操作将需要大量 O(1) 操作才能从中恢复。

放大，您可以看到累积操作如何受到 List.Copy() 的影响

缩小，您可以看到与 O(n) 操作相比，它并没有真正影响比例。

stackToList(堆栈，false) = O(n^2)。列表的插入函数执行数组复制，必须将列表中的所有元素移动到新列表。当指针开始遍历父堆栈时，操作数从 0 开始，然后增长直到达到 n。平均而言，它会出现 n/2 次。 Big O Notation 中的常量 2 被删除，剩下 n。如果没有资源瓶颈，如果此算法在 10 秒内完成 1000 万个项目，要完成 1 亿个项目，您预计需要大约 10(10^2) 秒。实际上，我们知道第二种情况的扩展性会比 Big O Notation 预测的更好，因为它实际上是 n*(n-1)，但它的扩展性不会比 O(n*Log(n)) 好，下一步吃下。

操作分解：

List<int> stackToList(Stack<int> stack, bool reverseOrder) {
    List<int> items = new List<int>(); // O(1)

    while (stack.Count > 0) {        //  O(n): For every int in the supplied stack
        int item = stack.Pop();        // O(1): https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,222

        if (reverseOrder) {            // O(1)
            items.Insert(0, item);     // O(n^2): https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,669
        } else {
            items.Add(item);           // O(Slightly more than 1): https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,220
        }
    }
    return items;
}

在线测试中的算法复杂度

Algorithm complexity in online test

c#

asymptotic-complexity