在线测试中的算法复杂度

Question

我必须完成实习的在线编程测试,并得到关于复杂性分析的问题.我回答了这个问题并且标记错了,我只想理解为什么,所以我可以改进.

问题:

当reverseOrder为true且为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 ^ 2)

您可以在reverseOrder为true时选择一个,为false时选择另一个.

我的答案:

• 当reverseOrder为真时:O(n ²)
• 当reverseOrder为false时:O(n ²)

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

• while循环将迭代n次数,因为它会继续,直到没有剩余的元素弹出
• Pop() 是 O(1)

• 在的情况下reverseOrder存在true,一个Insert到该列表的前面制成.由于List<T>是由数组支持,它被动态地调整大小和每一个元件向上移动一个空间,所述元件被插入在索引0.根据https://msdn.microsoft.com/en-us/library/sey5k5z4(v = vs.110).aspx:

  该方法是O(n)操作,其中n是Count.

• 在的情况下reverseOrder存在false,一个Add是由一个项目追加到列表的后面.由于items没有给出初始大小,Count是从来没有低于Capacity,产生一个调整大小,所以根据https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx:

  如果Count小于Capacity,则此方法为O(1)操作.如果需要增加容量以容纳新元素,则此方法变为O(n)操作,其中n为Count.

我此刻感到非常沮丧,因为这个错误导致我的分数直线下降,尽管我在测试中得到了所有其他问题.