Big O для нескольких петель

Question

    count++;
    count++;
    count++;
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < i*i; j++)
        {
            for (int k = 0; k < j; k++)
            {
                count++;
                sum++;
            }
        }
    }
    count++;
    return count;
}

Попытка получить Большой О этой кодировки.Изо всех сил пытаясь понять, как петли взаимодействуют.Когда я запускаю его, я получаю n = 25 count = 898960. Я пробовал O (n) ^ 5 + 9 вплоть до O (n) ^ 5 / n

Все другие примеры этой проблемыне иметь дело с I используется во втором цикле (I * I) и J используется в третьем цикле

Answer 1

Почти всегда лучший способ вычисления сложностей своего рода циклов должен быть сделан с использованием сигма-записи.

PS Я не пишу необходимые + 1 в формулах, поскольку это не важно для обозначения Big-O и не влияет на максимальную мощностьчто 5.

Answer 2

Похоже, что O(n^5).

for (int i = 0; i < n; i++) // 0 to n -> O(n)
    for(int j = 0; j < i*i; j++) // 0 to n * n -> O(n^2) repeated n times -> O(n^3)
        for (int k = 0; k < j; k++) // 0 to n * n -> O (n^2) repeated O(n^3) times -> O(n^5)

В лучшем случае три вложенных цикла дадут вам O(n^3), но, поскольку у вас есть второй цикл, повторите (n^2) раз,это возведет в квадрат его сложность и третий цикл.Так что в простой математической записи это будет: (n) * (n * n) * (n * n) = n^5.