O que é o Big-O de um loop aninhado, onde o número de iterações do ciclo interior é determinada pela iteração corrente do laço externo?

Question

O que é o Big-O tempo de complexidade dos seguintes laços aninhados:

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?

Answer 1

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

Answer 2

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 . Neste caso, o número de passos serão (n-1) + (n-2) + ... + 0 , que reorganiza para a soma de 0 a n-1; este é

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

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

Answer 3

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

Digo isto não para ser exigente, mas apenas salientar que você não só precisa tomar os laços óbvios em conta quando se trabalha fora complexidade -. Você precisa olhar para a complexidade do que você chama assim

Answer 4

Sim, seria N ao quadrado. O número real de passos seria a soma de 1 a N, que é 0,5 * (N - 1) ^ 2, se não estou enganado. O grande só leva em conta a maior exponant e há constantes, e assim, isso ainda é N ao quadrado.

Answer 5

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

Agora, você precisa encontrar para 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). Que é 5 vezes ... e descansa 5 iterações.

Agora você sabe que você tem cinco dezenas + 5:

10 (5) + 5

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

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... isso é exatamente a complexidade destes loop aninhado.

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 eo denominador.

Resultado: O (n ^ 2)

Answer 6

AFAIL, sendo iniciada a partir de circuito interno através de mais externos é forma adequada para o cálculo de complexidade loop aninhado.