Найти взаимосвязь между вводом и числом выполнений цикла.

Question

Учитывая этот код:

k = 1;
p = 0;
while (k < n){
  k *= 3;
  p++;
}

Определите, сколько раз строка 03 будет выполняться в терминах n, где n - это ввод. (Подсказка: выясните, как p и k связаны с n в конце цикла в строке 06. Выразите p в термах n и используйте это, чтобы ответить на этот вопрос.)

Пока что я выяснил, сколько раз p и k выполняются, связанные с этими значениями n:

• n = 1 -> k / p итераций = 1
• n = 3 -> k / p итераций = 3
• n = 10 -> k / p итераций = 3
• n = 30 -> k / p итераций = 4

Я изо всех сил пытаюсь выяснить, как определить отношение между n и количеством итераций для k/p. Если кто-то мог бы объяснить, как определить это, это будет с благодарностью.

Answer 1

Вы подошли к этой проблеме, попробовав несколько различных примеров и попытавшись выяснить, можете ли вы найти образец. Это разумный подход, но немного сложнее начать работать. Вместо этого вы можете захотеть посмотреть на значения, которые k принимает во время итерации цикла, и посмотреть, сможете ли вы работать оттуда.

Обратите внимание, что k растет экспоненциально в зависимости от числа итераций цикла: оно принимает значения 1, 3, 9, 27, 81, ... . Написано по-другому, это принимает значения

3 ⁰, 3 ¹, 3 ², 3 ³, 3 ⁴ и т. Д.

И, в более общем смысле, на итерации цикла i он принимает значение 3 ⁱ.

Учитывая, что этот цикл останавливается, как только k становится больше или равно n, мы можем определить, сколько будет итераций цикла, решив для наименьшего значения i, для которого 3 ⁱ ≥ n. Мы можем сделать это следующим образом:

3 ^я = n

я = лог ₃ н

Это число может не быть целым числом, поэтому мы округлим его до потолка и скажем, что число итераций равно " log ₃ n".

Вообще говоря, если вы видите какой-то процесс, который работает путем многократного роста с постоянным коэффициентом (всегда в три раза, или всегда в два раза, или всегда в 10 раз и т. Д.), Вы должны ожидать появления какого-то логарифмического термина, Это один из самых распространенных способов отображения O(log n).

Answer 2

Прежде всего, ваши наблюдения немного ошибочны.

Для разных значений n значения k и p после конца 6-й строки будут:

n = 1 => k = 1 and p = 0.

n = 3 => k = 3 and p = 1.

n = 9 => k = 9 and p = 2.

n = 10 => k = 27 and p = 3.

n = 27 => k = 27 and p = 3.

n = 30 => k = 81 and p = 4.

Теперь, в конце 6-й строки,

if n == k
  then 3^p == n
otherwise,
  3^(p-1) < n < 3^p