Действительно запутался в этих фрагментах, основанных на сложности времени

#java #time #time-complexity #complexity-theory

#Ява #время #временная сложность #теория сложности

Вопрос:

Привет, ребята, у меня долгое время была путаница по времени сложности для двух фрагментов кода

Например , давайте возьмем список, в котором есть n элементов, но в следующей строке я инициализирую его новым экземпляром ArrayList.

 Listlt;Integergt; temp = List.of(1,2,3,4,5);  temp = new ArrayListlt;gt;(); // I believe the time complexity is O(1)

Итак, ребята, в приведенном выше фрагменте это действительно O(1), потому что он создает новый объект экземпляра и указывает на него, или я здесь ошибаюсь?

Другой фрагмент-это

 int counter = any value;  for(int i = 0;ilt;n;i*=counter)// I guess its O(n)

В приведенном выше фрагменте я предполагаю, что его счетчик O(n) является переменным и может иметь любое случайное значение, которое не является фиксированным, или это log(n) ?

Пожалуйста, пролейте немного света на это, ребята, спасибо.

1. «Я полагаю, что временная сложность равна O(1)» вы спрашиваете о временной сложности обеих линий вместе или просто о переназначении?

2. «Я предполагаю, что его O(n)» это выполняется бесконечно, если n lt; 0 только . Если вы хотите инициализировать i = 1 , то это логарифмически.

3. Только переназначение , теперь мое замешательство устранено, спасибо 🙂

Ответ №1:

Итак, ребята, в приведенном выше фрагменте это действительно O(1), потому что он создает новый объект экземпляра и указывает на него, или я здесь ошибаюсь?

Строка 1 Listlt;Integergt; temp = List.of(1,2,3,4,5) -это O(n). Под капотом Java фактически перебирает элементы, чтобы выполнить проверку на нуль, прежде чем помещать их в базовый массив, хранящийся в списке.

Строка 2 temp = new ArrayListlt;gt;() -это O(1). Время, необходимое для инициализации нового списка, является постоянным; здесь нет переменной.

Когда вы рассматриваете весь фрагмент в целом (строки 1 2 вместе), это O(n), потому что мы всегда берем самую высокую сложность в алгоритме.

В приведенном выше фрагменте я предполагаю, что его счетчик O(n) является переменным и может иметь любое случайное значение, которое не является фиксированным, или это log(n) ?

Учитывая, что вы инициализировали цикл как i = 1 вместо, и что оба n и counter являются переменными, а не константами, временная сложность будет O(счетчик журнала_n).

В цикле количество оставшихся итераций уменьшается(делится) на коэффициент counter после каждой итерации. Следовательно, временная сложность логарифмическая. Вы можете думать о «log _c n» как о «начиная с n того , сколько раз вам нужно рекурсивно делить c на, чтобы достичь 1″.

Однако, если бы вы действительно хотели инициализировать цикл как i = 0 , он просто выполнялся бы бесконечно.