O que é o Big-O de um loop nested, em que o número de iterações no loop interno é determinado pela iteração atual do loop externo?

Qual é a complexidade de tempo Big-O dos seguintes loops nesteds:

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

Seria O (N ^ 2) ainda?

Sim, ainda é O (n ^ 2), tem um fator constante menor, mas isso não afeta a notação de O.

Sim. Lembre-se da definição de Big-O: O (f (n)) por definição diz que o tempo de execução T (n)kf (n) para alguma constante k . Nesse caso, o número de etapas será (n-1) + (n-2) + … + 0 , que será redefinido para a sum de 0 a n-1; isto é

T (n) = (n-1) ((n-1) + 1) / 2 .

Reorganize isso e você pode ver que T (n) será sempre ≤ 1/2 (n²); pela definição, assim T (n) = O (n²) .

É N ao quadrado se você ignorar o System.out.println. Se você assumir que o tempo gasto por isso será linear em sua saída (o que pode não ser, é claro), eu suspeito que você acaba com O ((N ^ 2) * log N).

Eu mencionei isto para não ser exigente, mas apenas para salientar que você não precisa apenas levar em consideração os loops óbvios quando estiver trabalhando com a complexidade – você precisa olhar para a complexidade do que você chama também.

Sim, seria N ao quadrado. O número real de passos seria a sum de 1 a N, que é .5 * (N – 1) ^ 2, se não me engano. Big O leva em conta apenas o maior exponente e nenhuma constante, e assim, isto ainda é N ao quadrado.

Se você tivesse N = 10, suas iterações seriam: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (isto é: dez iterações mais nove iterações mais oito iterações … etc.).

Agora, você precisa encontrar a adição quantas vezes você pode obter um N (10 no exemplo):

1: (10), 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Qual é 5 vezes … e repousa 5 iterações.

Agora você sabe que tem cinco dezenas + 5:

10 (5) + 5

Em termos de f (n) (ou N), podemos ver facilmente que isso seria:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 … esta é exatamente a complexidade desses ciclos nesteds.

Mas, considerando o comportamento assintótico de Big O, podemos nos livrar dos valores menos significativos de f (n), que são o único n e o denominador.

Resultado: O (n ^ 2)

AFAIL, sendo iniciada do loop interno através dos externos, é uma maneira adequada de calcular a complexidade do loop nested. insira a descrição da imagem aqui