Как рассчитать временную сложность вложенных циклов? - PullRequest
Новая
       12

Как рассчитать временную сложность вложенных циклов?

0 голосов
/ 31 октября 2018

Как рассчитать временную сложность следующего алгоритма? 

for(i=1;i<=n;i++)
  for(k=i;k*k<=n;k++)
   {
     Statements;
   }

Из того, что я знаю, сложность времени для вложенных циклов for равна количеству выполнений самого внутреннего цикла. Так что здесь самый внутренний цикл выполняется n*n раз, следовательно, это O(n^2).

Может ли это быть O(n) в зависимости от условия k*k<=n, заданного во втором цикле?

Спасибо!

1 Ответ

0 голосов
/ 31 октября 2018

Временная сложность алгоритма всегда измеряется в терминах определенного типа операции. Например, если ваша Statements; имеет неизвестную временную сложность, которая зависит от n, то было бы неправильным описывать сложность времени в первую очередь.

Но, вероятно, вам нужно знать сложность времени в терминах Statements; операций . Если Statements; - операция с постоянным временем, это становится особенно значимым. И в этом случае нам нужно просто посчитать, сколько раз выполнено Statements;. Если это число, скажем, 3 * n, то сложность по времени будет O (n).

Чтобы ответить на этот вопрос, давайте разберем ваш вложенный цикл. Внешний цикл повторяется от (и включая) от 1 до n, поэтому он будет выполняться ровно n раз, независимо от чего-либо.

Для каждой итерации внешнего цикла внутренний цикл будет выполняться один раз. Он начинается с k = i и повторяется до k*k > n или k > sqrt(n). Обратите внимание, что всякий раз, когда i > sqrt(n), он вообще не запускается. Мы видим, что в среднем он будет работать на

O(sqrt(n) + sqrt(n)-1 + sqrt(n)-2 + ... + 0) / n

итераций. По формуле суммирования вы можете найти здесь , это равно

O( sqrt(n) * (sqrt(n) + 1) / 2 ) = O( (n + sqrt(n))/2 ) = O( n + sqrt(n) ) = O(n).

Так что да, сложность времени в этом случае составляет O(n), как вы предложили.

Вы можете увидеть это в действии, написав простой скрипт, который имитирует ваш алгоритм и подсчитывает число Statements;. Ниже в JavaScript, поэтому он может быть запущен как фрагмент: 

// Simulation
function f(n) {
  let res = 0;
  for(let i=1;i<=n;i++)
    for(let k=i;k*k<=n;k++)
      ++res;
  return res;
}

// Estimation
function g(n) {
  return ~~((n + Math.sqrt(n))/2);
}

console.log(
  f(10),
  f(100),
  f(1000),
  f(10000),
);
console.log(
  g(10),
  g(100),
  g(1000),
  g(10000),
);

Надеюсь, вы нашли это полезным.

...