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

Question

Я пытался вычислить 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, и это было мое первое задание, поэтому приношу извинения за любые основные ошибки, которые я, возможно, допустил.

Answer 1

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)$.