Что такое Big-O вложенного цикла, где количество итераций во внутреннем цикле определяется текущей итерацией внешнего цикла?

Question

Какова временная сложность Big-O следующих вложенных циклов:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

Будет ли это О(Н^2) все еще?

Answer 1

Да, это по-прежнему O(n^2), у него меньший постоянный коэффициент, но это не влияет на обозначение O.

Answer 2

Да.Напомним определение Big-O: О (е (п)) по определению говорит, что время выполнения Т(н) ≤ кф(н) для некоторой константы к.В этом случае количество шагов будет (n-1)+(n-2)+...+0, который преобразуется в сумму от 0 до n-1;Это

Т(п)=(п-1)((п-1)+1)/2.

Переставьте это, и вы увидите это. Т(н) всегда будет ≤ 1/2(n²);по определению, таким образом Т(п) = О(п²).

Answer 3

Это N в квадрате, если вы игнорируете System.out.println.Если вы предполагаете, что затраченное на это время будет линейным на выходе (что, конечно, может быть и не так), я подозреваю, что в итоге вы получите O ( (N^2) * log N).

Я упоминаю об этом не из придирчивости, а просто для того, чтобы указать на то, что вам не нужно просто учитывать очевидные циклы при определении сложности — вам нужно также учитывать сложность того, что вы вызываете.

Answer 4

Да, это будет N в квадрате.Фактическое количество шагов будет равно сумме от 1 до N, что составляет 0,5*(N - 1)^2, если я не ошибаюсь.Большой O учитывает только самый высокий показатель степени и не учитывает константы, поэтому это все равно N в квадрате.

Answer 5

Если бы у вас было N = 10, ваши итерации были бы:10+9+8+7+6+5+4+3+2+1.(Это:десять итераций плюс девять итераций плюс восемь итераций...и т. д.).

Теперь вам нужно найти в сложении, сколько раз вы можете получить N (10 в примере):

1:(10), 2:(9+1), 3:(8+2), 4:(7+3), 5:(6+4).Это в 5 раз...и отдыхает 5 итераций.

Теперь вы знаете, что у вас пять десятков + 5:

10(5) + 5

С точки зрения f(n) (или N) мы легко можем увидеть, что это будет:

f(n) = n(n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2...именно в этом и заключается сложность этих вложенных циклов.

Но, учитывая асимптотическое поведение большого О, мы можем избавиться от менее значимых значений f(n), которыми являются единственное n и знаменатель.

Результат:О(п^2)

Answer 6

AFAIL, начиная с внутреннего цикла и заканчивая внешними, является подходящим способом расчета сложности вложенного цикла.