Как рассчитать временную сложность следующего алгоритма?
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
, заданного во втором цикле?
Спасибо!
Временная сложность алгоритма всегда измеряется в терминах определенного типа операции. Например, если ваш 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.info(
f(10),
f(100),
f(1000),
f(10000),
);
console.info(
g(10),
g(100),
g(1000),
g(10000),
);
Надеюсь, вы нашли это полезным.
Подсказки: 1) какого максимального значения может достичь
k
? 2) всегда ли будет выполняться внутренний цикл?