时间复杂度和列表中的 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)。