complexity-theory - 复杂性和大 O

Question

假设项目有足够的未使用空间而无需重新调整大小，以下两种算法的最坏情况时间复杂度是多少？我最初的猜测是 A 会运行得更慢，因为它必须移动每个元素才能在索引 [0] 处添加新元素。我认为 B 在最坏的情况下是 O(N^2) 但不确定。

一个。

    for (int i = 0; i < N; i++)
        items.add(0, new Integer(i));

和 B。

    for (int i = 0; i < N; i++)
        items.add(new Integer(i));

Answer 1

它实际上取决于用于存储项目的底层数据结构。如果您使用链表，则插入 A 需要恒定时间，即 O(1)，而如果您使用数组，它将是 O(n)，因为您必须将每个元素向左移动 1 位以腾出空间新项目。因此，如果使用链表，则循环复杂度为 O(n)，如果使用数组，则复杂度为 O(n^2)。

对于 B，不清楚你想如何实现 add 函数，因此不能说它的复杂性。当您使用链表、数组或平衡树时，复杂性会有所不同。