0

Estou aprendendo a calcular a complexidade de algoritmos, usando a notação Big-O, porém estou com dificuldades no algoritmo abaixo:

a=0
for(int i = n; i>0; i -=2){
    for(int j = i+1; j<=n;j+=1){
        a++;
    }
}

Se puderem me explicar como resolver, eu agradeço.

1

1 Resposta 1

3

Para cada loop em lote, costumamos assumir um fator na notação assintótica e é claro que o impulso nos leva a crer que casos como esse são O(n*n)=O(n²), como se cada loop aplicasse um fator linear, mas há vezes que não é assim.

Por exemplo, aplicar o quicksort em loops (e não recursões) resulta num comportamento predominantemente O(n*log(n)), mesmo podendo implementar com dois loops e no pior caso sendo O(n²). Mais ainda, o mergesort em loops bem implementado sempre é O(n*log(n)), quer seja com dois loops em lote, quer seja com três. Sendo assim, vamos analisar.

No loop de i, encontramos que ele executa 1x se n=1 ou n=2, 2x se n=3 ou n=4, daí em diante linearmente, pois caminha de duas em duas unidades por ciclo até uma fixa condição de parada. Se n<=0, executa 0x. Quer dizer, o número de ciclos do loop de i é max(0,ceil(n/2)), para simplificar é entendido como n/2.

Já no loop de j, o número de vezes que executa é simplesmente (n-i)x, pois na primeira ele executa 0x, na segunda, 2x, na terceira, 4x e daí em diante, até o fim dos loops em 'i' que reduzem esse índice de dois em dois. O número de ciclos em j é n-i.

Sendo assim, a série é n+(n-2)+(n-4)+...+3+1 (se n for ímpar) ou n+(n-2)+(n-4)+...+4+2 (se n for par). Isso resulta nas duas fórmulas:

inserir a descrição da imagem aqui

quando n é par ou

inserir a descrição da imagem aqui

quando n é ímpar.
Ambos resultam na mesma fórmula assintótica, que é a da complexidade do algoritmo: O(n²).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .