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

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

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) какого максимального значения может достичь k? 2) всегда ли будет выполняться внутренний цикл?

meowgoesthedog 31.10.2018 14:06
1
1
1 188
1

Ответы 1

Временная сложность алгоритма всегда измеряется в терминах определенного типа операции. Например, если ваш 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),
);

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

Другие вопросы по теме