c# - 在线测试中的算法复杂度

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 为 true 时选择一个，在它为 false 时选择另一个。

我的回答:

当 reverseOrder 为真时:O(n2)

当 reverseOrder 为 false 时:O(n2)

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

while 循环将迭代 n次，因为它会一直持续到没有元素可以弹出

Pop()是 O(1)

在reverseOrder的情况下正在 true , Insert到前面的列表是作出的。自 List<T>由数组支持，动态调整大小，每个元素向上移动一个空格，元素插入索引 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)。