Найти количество инструкций алгоритма

Question

Учитывая этот алгоритм (a> 0, b> 0):

while(a>=b){
   k=1;
   while(a>=k*b){
      a = a - k*b;
      k++;
   }
}

Мой вопрос : мне нужно найти временную сложность этого алгоритма и сделать это, яЯ должен найти количество инструкций, но я не смог его найти.Есть ли способ найти это число, а если нет, то как мне определить его временную сложность?

Что я сделал : Прежде всего я попытался найти количество итерацийпервый цикл, и я нашел шаблон: a_i = a - (i (i + 1) / 2) * b, где i - количество итераций.Я потратил часы на некоторые манипуляции с ним, но не смог найти ничего подходящего (я нашел странные результаты, например q² <= a / b <q² + q, где q - количество итераций). </p>

Answer 1

Вы правильно рассчитали, что значение a после i -ой итерации внутреннего цикла:

Гдеa_j0 - это значение a в начале j -го внешнего цикла.Условие остановки для внутреннего цикла:

, которое можно решить как квадратное неравенство:

Следовательно, внутренний цикл составляет примерно O(sqrt(a_j0 / b)).Начальное значение next a удовлетворяет:

Масштабирование примерно как sqrt(2b * a_j0).Было бы довольно утомительно точно вычислять сложность времени, поэтому давайте применим приведенные выше приближения с этого момента:

Где a_n заменяет a_j0 и t_n - это время выполнения внутреннего цикла - и, конечно, общая сложность времени - это всего лишь сумма t_n.Обратите внимание, что первый член задан как n = 1, а входное значение a определено как a_0.

Перед непосредственным решением этого повторения, обратите внимание, что, поскольку второй член t_2уже пропорционально корню квадратному из первого t_1, последний доминирует над всеми другими слагаемыми в сумме.

Таким образом, общая сложность времени составляет всего O(sqrt(a / b)).

---

Обновление: числовые тесты.

Обратите внимание, что, поскольку все изменения значения a пропорциональны b, а все условия цикла также пропорциональныдо b, функция может быть «нормализована» путем установки b = 1 и только с изменением a.

Тестовая функция Javascript, которая измеряет количество раз, которое внутренний циклвыполняет:

function T(n)
{
   let t = 0, k = 0;
   while (n >= 1) {
      k = 1;
      while (n >= k) {
          n -= k;
          k++; t++;
      }
   }
   return t;
}

Участок sqrt(n) против T(n):

Убедительная прямая линия, которая подтверждает, чтосложность времени действительно наполовину мала.