Блог

Интересно, каково время выполнения строки list.set(i, list.get(j)); в нотации big O. Это O (n ^ 2) или O (2n). Связанный список имеет большую временную сложность O (n) для метода get и O (n) для метода set в java.

 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 способов выбрать одно из действий».

Однако я не уверен, что то, что происходит в строке 5 для методов get() и set(), можно считать независимым или просто не происходит одновременно.

Другими словами, является ли время выполнения строки 5 O (n ^ 2) или O (2n) = O (n n)?

Это O (n) .

Во-первых, O (2n) и O (n) одинаковы. Необычно писать O (2n), но это не является неправильным.

Код в строке 5 вызывает функцию get один раз. Третья функция получает значение. В момент времени O(n) он получает значение j-го элемента. После этого он вызывает set один раз, и с помощью этой функции, во время O(n), он устанавливает значение i-го элемента.

Таким образом, его сложность заключается в

2O(n) = O(n).

И если я могу предположить, ваш алгоритм имеет сложность O (n ^ 3). Вы могли бы сделать это в O(n ^ 2), если вы используете операции next и prev на итераторе вместо итерации целых чисел i и j.