Какова функция роста и порядок в этом коде?

Question

Я пытаюсь понять функцию роста этого кода.

 for (int count=0; count < n; count++) {
   for (int count2=1; count2 < n; count2=count2*2) {
     System.out.println(count + ", " + count2);
   }
 }

Answer 1

Внешний l oop является линейным, поскольку вы увеличиваете единицу каждый раз. Внутренняя l oop - это log (n), поскольку ваша верхняя граница должна будет экспоненциально увеличиваться, чтобы не отставать от роста переменной count2, поэтому вся вложенная итерация равна nlog (n).

Answer 2

Хороший способ решить эти проблемы, когда вы только начинаете узнавать о росте и порядке, - это думать об этом визуально. См. Диаграмму и пояснения ниже:

Предположим, что n = 8, а печать - операция с постоянным временем.

Посмотрите на сначала циклы по отдельности.

Внешний l oop довольно тривиален: мы начинаем с отсчета 0 и увеличиваем count на 1 каждый раз, пока не достигнем n = 8. Поэтому мы должны увеличивать 8 / 1 = 8 раз, чтобы завершить l oop. Обобщенный к n, l oop будет работать n раз.

Внутренний l oop немного более сложен: мы начинаем со счета 1 и увеличиваем его от умножения 2 до count2, пока не получим достичь n = 8. Таким образом, count2 увеличивается в 2 раза на каждой итерации, и его значение можно определить как 2 ^ k, где k - количество итераций. Чтобы выяснить, сколько итераций потребуется, чтобы достичь n = 8, решите 2 ^ k = 8 или k = log2 (8) = 3. Обобщая n, l oop будет выполняться для log2 (n) раз.

Сочетая эти два факта, внутренний l oop будет запускаться для каждой итерации внешнего l oop, так что в целом для запуска потребуется n * log2 (n). Следовательно, сложность времени выполнения O (nlog (n))