java - 复杂度等级

Question

这个问题的大 O 表示法是什么？为什么？我认为这是 O(N)，因为我们这里有一个循环，但我不确定。

public static void mystery(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

时间复杂度为 O(n^2)。

循环将执行 floor(n/2) 次。List.add(int i) 和 list.remove(int i) 平均都是 O(n) （请参阅下面的注释）。这导致 O(n*n/2)，即 O(n^2)。

关于内置 List 实现的一些说明

在 ArrayList 上调用 List.add(int i, element) 或 List.remove(int i) 时，必须移动列表中的元素以插入或删除元素（当不在列表末尾时）必要的班次是 n。因此添加和删除操作都是 O(n)。

List.add(int i, element) 和 List.remove(int i) 在 LinkedList 上调用时也是 O(n)。这是由于需要遍历给定索引才能删除/添加元素。

当我们知道对给定列表的添加/删除将是连续的时，我们可以做得更好。使用 LinkedList 的 ListIterator 可用于将时间复杂度降低到 O(n)。在 LinkedLists ListIterator 上调用 add 和 remove 方法是 O(1)，因为不需要遍历给定的索引。

使用 ListIterator 的 askers 方法的示例实现

public static void mystery(List<String> list){
    ListIterator<String> iterator = list.listIterator();
    int i = 0;
    while (i < list.size()-1) {
        String first = iterator.next();
        // Remove first
        iterator.remove();
        // Skip an element
        iterator.next();
        // insert at i+1
        iterator.add(first);
        i+=2;
    }
}

Answer 2

看起来它是O（n ^ 2）。它遍历一个列表，并且对于每次迭代，它调用list.remove()也运行在 O(n) 中。因此这个函数的时间复杂度应该是 O(n^2)。

Answer 3

运行此方法时，它将执行：

remove 0
append 1
remove 1
append 2
...

假设列表是数组列表：

假设最后总是删除所有元素所以：n/2 * (2*n + n) = 3 * n^2 /2 => O(n^2)

假设所有删除元素总是在顶部。所以：n/2 * (n + n) => O(n^2)

所以。因为最坏情况和最好情况总是 O(n^2)，所以，不仅是 Big-O，而且复杂度也会是 o(n^2)。