Как рассчитать большую сложность следующего алгоритма?
-
29-09-2020 - |
Вопрос
Я пытался вычислить Big-O следующего алгоритма, и у меня получилось O (n ^ 5).Я не знаю, каков правильный ответ, но большинство моих коллег получают O (n ^ 3).
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
Что я сделал, так это начал с самого внутреннего цикла.Итак, я подсчитал, что самый внутренний цикл будет выполняться n/2
раз, затем я перешел ко второму вложенному циклу for, который будет выполняться i^2
раз и из самого внешнего цикла будет выполняться i
раз, когда i
варьируется от 1
к n
.Это означало бы, что второй вложенный цикл for будет выполняться в общей сложности Sigma(i^2) from i=1 to i=n
таким образом, в общей сложности n*(n+1)*(2n+1)/6
раз.Таким образом, общая сумма, которую должен был выполнить код, оказалась в порядке n^5
итак, я пришел к выводу, что порядок должен быть O(n^5)
.Есть ли что-то неправильное в этом подходе и ответе, который я рассчитал?
Я только начал работать с DSA, и это было мое первое задание, поэтому приношу извинения за любые основные ошибки, которые я, возможно, допустил.
Решение
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
Цикл с тройным вложением эквивалентен суммированию $$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$
С точки зрения фактический эффективность кода, поскольку x=y+z
является инвариантным в цикле, любой хороший оптимизирующий компилятор извлечет инструкцию из цикла (говоря языком компилятора, переместит инструкцию в предварительный загрузчик цикла), следовательно, заставляя скомпилированный код выполняться в $O(1)$.