Каково время работы фрагмента?

Question

for (int i = 0; i < n; i++)
    for (int j = i; j <= n; j++)
        for (int k = i; k <= j; k++)
            s1++;

for (int q = 0; q < n * n; q++ )
    for(int p = 0; p < q; p++)
        s1++;

это два o (n ^ 3), так что o (n ^ 6) верно?Я запускал программу, и она, кажется, o (n ^ 5)

Answer 1

Ваш первый цикл for повторяется n раза (от 0 до n - 1), поэтому его временная сложность составляет O (n) (постоянные значения опущены).

Второй повторяет также и n раз, но он делает это для каждой итерации первого цикла.
Это делает его O (n * n) всего пока.

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

Следующий блок является отдельным.Это время сложность не будет умножена на первое, оно будет добавлено вместо этого.
Его первый цикл имеет сложность O (n * n) из-за итерации, пока q < n * n.Для каждой из его итераций внутренний цикл выполняется и выполняется q раз, что составляет O (n * n - 1) = O (n * n) в худшем случае (последняя итерация).

Если мои расчеты верны (я не знаю, пожалуйста, просмотрите их и предложите внести изменения), тогда код имеет временную сложность

O (n ^ 3)+ O (n ^ 2 * n ^ 2) = O (n ^ 3) + O (n ^ 4) = O (n ^ 4)

Answer 2

Общая сложность приведенного выше фрагмента кода будет O (n ^ 3) + O (n ^ 4) = O (n ^ 4) [Сложность наихудшего случая в записи Big-O].

Answer 3

Первый кодовый блок имеет сложность O(n^3), но второй - O(n^4) из-за ограничений n*n.

Таким образом, общее время составляет O(n^3+n^4) = O(n^4)

Answer 4

Вот один из способов эмпирически продемонстрировать сложность этой программы.

• Общая сложность определяется количеством итераций цикла.

• Каждая итерация цикла увеличивается s1.

• Таким образом, значение из s1 в конце программы - это число итераций цикла.

Итак:

1. Добавьте оператор печати в конце и напечатайте s1.
2. Постройте график как функцию n.
3. Выработка - это кривая, подходящая для C * n^2, C * n^3 или любой другой кривой ... когда n становится больше.

---

Если вы хотитечтобы доказать сложность, проанализируйте ее, а затем сделайте некоторую алгебру / доказательство по индукции, чтобы получить аналитическую формулу для значения s1 как функции n.Затем определите класс сложности из аналитической формулы.

Подсказка: если формула является полиномом от n степени p, то класс сложности будет O(n^p).

---

Измерение времени может привести к вводящим в заблуждение результатам, поскольку существуют различные факторы, которые могут искажать время, включая эффекты разогрева JVM.

При печати значения s1 такой проблемы нет.

Answer 5

Каждый из циклов равен O(n^3), и два цикла выполняются один за другим, поэтому общая сложность равна O(2*n^3), что соответствует O(n^3).

Это

    for (int i = 0; i < n; i++)
        for (int j = i; j <= n; j++)
            for (int k = i; k <= j; k++)
                for (int q = 0; q < n * n; q++)
                    for (int p = 0; p < q; p++)
                        s1++;

будет O(n^6).