Что за большая часть этого маленького фрагмента кода?

Question

for i := 1 to n do
  j := 2;
  while j < i do
    j := j^4;

Я действительно смущен, когда дело доходит до записи Big-O, поэтому я хотел бы знать, если это O (n log n).Это моя интуиция, но я не могу доказать это.Я знаю, что цикл while, вероятно, быстрее, чем log n, но я не знаю, на сколько!

Редактировать: каретка обозначает показатель степени.

Answer 1

Проблема заключается в количестве итераций, в то время как цикл while выполняется для данной i.

На каждой итерации j:= j^4 и в начале j := 2, поэтому после x итераций j = 24^x

j < i эквивалентно x < log_4(log_2(i))

Я бы рискнул заявить, что сложность составляет O(n * log_4(log_2(n)))

Вы можете избавиться от постоянных факторов в обозначениях Big O.log_4(x) = log(x) / log(4) и log(4) - это константа.Точно так же вы можете изменить log_2(x) на log(x).Сложность может быть выражена как O(n*log(log(n)))

Answer 2

С манжеты, я думаю, это O ( n slog ₄ n ), где slog представляет инверсию оператора тетрации .Тетрация - следующая операция после возведения в степень.Точно так же, как умножение - это итеративное сложение, а возведение в степень - это итеративное умножение, тетрация - это итеративное возведение в степень.

Я рассуждаю так: если бы вы умножали j на 4 каждой итерации, то функция была бы O ( n log ₄ n ).Но поскольку вы возводите это в степень на каждой итерации, вам нужен соответственно более мощный оператор, чем log: slog .