Какова будет временная сложность этого кода?

Question

Какова временная сложность этого кода?

i = n;
  while(i > 1) {
    j = i;
    while (j < n) {
      k = 0;
      while (k < n) {
        k = k + 2;
      }
      j = j * 2;
    }
    i = i / 2;
  }

Я попытался проанализировать этот код и получил сложность Log^2n * n Я переписал код в формате для l oop, чтобы сделать его легче увидеть, что получилось вот так.

for (i = n; i > 1; i = i / 2) // log2n + 1
  {
    for(j = i; j < n; j = j * 2) // log2n + 1
    {
      for (k = 0; k < n; k = k + 2)  // n + 1 times
      {
          cout << "I = " << i << " J = " << j << " and K = " << k << endl;
      }
      cout << endl;
    }
  }

Это правильно? Если нет, то почему? Я новичок в алгоритмах и пытаюсь понять, но не знаю, где еще спросить, извините.

Answer 1

Да, ваш ответ правильный. Переменная i делится пополам на каждом шаге, делая внешнюю l oop O (log n) . j удваивается на каждом шаге, что делает l oop O (log n) , а самый внутренний k l oop увеличивается линейно, что делает l oop O (n) . Умножение вместе дает O (n log² n) .