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 上调用时，添加和删除方法的复杂度为 O(1)，因为无需遍历给定索引。

Sample implementation of the askers method using ListIterator

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;
    }
}