代码效率低下

Question

我这里有代码：

import java.util.*;

public class AddElements {

    public static void main(String[] args) {

        ArrayList<Integer> a = new ArrayList<Integer>();
        for(int i=1; i<=5; i++){
          a.add(i);
        }
        System.out.println(a);
        // [1, 2, 3, 4, 5]

        addElementAtBeginning(a, -1, 4);
        System.out.println(a);
        // [-1, -1, -1, -1, 1, 2, 3, 4, 5]    

       addElementAtBeginning(a, -2, 7);
        System.out.println(a);
        // [-2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, 1, 2, 3, 4, 5]
    }

    public static <T> void addElementInBeginning1(ArrayList<T> a, T fillElem, int nFills){
          for(int fills=0; fills<nFills; fills++){
               a.add(fillElem);
               for(int i=a.size()-1; i>0; i--){
               a.set(i, a.get(i-1));
          }
          a.set(0, fillElem);
        }
    }

    public static <T> void addElementAtBeginning2(ArrayList<T> a, T fillElem, int nfills){
        for(int i = 0; i < nfills; i++){
            a.add(0, fillElem);
        }
    }
}

两种方法产生相同的结果。问题在于它们的效率。我只想确保第一种方法 addElementAtBeginning1() 采用 O(N^2) 而 addElementAtBeginning2() 采用 O(N)。我说得对吗？

Answer 1

这是不正确的：您的两种方法都需要 O(F * (N+F)) 时间，其中 N 是列表中的元素数，F 是您的 nFills 变量.

addElementInBeginning1 需要 O(F *(N+F)) 的原因很简单：它有两个嵌套循环，一个在 nFills 上，另一个在 N 上，嵌套循环执行 O(1) 操作。运算结束时数组列表的大小为N+F.

addElementInBeginning2 花费 O(F *(N+F)) 的原因取决于实现中使用的数据结构：执行 nFills 次的循环的每次迭代都需要时间数据结构上。对于 ArrayList ，插入零的时间是 O(N)。对于链表，时间为 O(1)，因此链表的总时间为 O(F)。

代码效率低下

Inefficiency of the code

java

big-o