时间复杂度和 add() 在列表中

Question

这是一个算法。由于它只是一个 for 循环，我会将其视为 O（N），但我被告知它是 O（N2）。有人告诉我这是因为 list.add，但这不会改变 N？那么，为什么会有时间复杂度的变化呢？

public static void mystery3(List<String> list) {
        for (int i = 0; i < list.size() - 1; i += 2) {
            String first = list.remove(i);
            list.add(i + 1, first);
        }
    }

Answer 1

如果你使用的是数组（Arraylist），remove(i)取O（n），add(...)取O（n）。这是因为在索引 i 处查找元素需要 O（1），而调整大小需要 O（n）。

如果使用链表，remove(i)取 O（n），而 'add（...） 取 O（n）。这是因为在索引 i 处查找元素需要 O（n），而删除需要 O（1）。

由于您调用方法 n/2 次，因此其整个运行时为 O（n^2）。