linkedlist方法shuffle中第5行的运行时

dffbzjpn  于 2021-07-08  发布在  Java
关注(0)|答案(1)|浏览(408)

不知行list.set(i,list.get(j))的运行时是什么;在大o符号是。是o(n^2)还是o(2n)。在java中,链表的o时间复杂度很大,get方法为o(n),set方法为o(n)。

public <T> void shuffle(LinkedList<T> list){               //(1)
     for(int i =0; i < list.size(); i++){                  //(2)
          for (int j = i + 1; j < list.size(); j++){       //(3)
                T temp = list.get(i);                      //(4)
                list.set(i, list.get(j));                  //(5)
                list.set(j, temp);                         //(6)

我知道最外面的循环运行n次,最里面的循环运行n-1次。我知道,当你有嵌套的循环时,你会将它们相乘(我的结论是,根据离散数学的乘积法则,因为循环是相互独立的)。离散数学中的求和法则告诉我,有“a做某事的方法和b做另一件事的方法,我们不能同时做这两件事,那么有a+b的方法来选择其中一个动作”。
但是,我不确定get()和set()方法在第5行发生的事情是独立的还是不同时发生。
换句话说,第5行的运行时间是o(n^2)还是o(2n)=o(n+n)?

c0vxltue

c0vxltue1#

是o(n)。
首先,o(2n)和o(n)是相同的。写o(2n)是不寻常的,但并不是不正确的。
第5行调用函数get once中的代码。第三个函数获取值。在o(n)的时间内得到第j个元素的值。之后,它调用set一次,通过这个函数,在o(n)的时间内,它设置第i个元素的值。
所以,它的复杂性是
2o(n)=o(n)。
如果我可以建议的话,你的算法的复杂性是o(n^3)。如果在迭代器上使用next和prev操作而不是迭代整数i和j,则可以在o(n^2)中实现。

相关问题