Obtenha a equação matemática referente á análise do pior e melhor caso do fragmento de código abaixo:
for (i = 0; i < N; i=i+2)
    printf("%d",i);

Passo 1

Neste exercício temos um laço for que faz i=0; i<N; i+=2 e chama printf. O conteúdo é análise de complexidade de tempo de execução, usando contagem de iterações e atribuição de custos constantes.

Passo 2

Em análise de algoritmos, cada operação de custo constante recebe uma letra: inicialização do for custa cinit, cada verificação de condição custa ccond, cada incremento custa cinc e cada execução de printf custa cbody. Nosso objetivo é expressar T(N) em função de N.

Passo 3

Precisamos contar quantas vezes o loop roda. Como i vai de 0 até de 2 em 2, o número de iterações do corpo é
k = lceil N2 rceil
E a condição do loop é avaliada k+1 vezes.

Passo 4

Somando todos os custos temos
T(N) = cinit + (k+1)cdot ccond + kcdot cbody + kcdot cinc
Substituindo k = lceil N/2rceil obteremos
T(N) = cinit + (lceil N/2rceil + 1),ccond + lceil N/2rceil,(cbody+cinc)
Essa expressão vale tanto para o melhor caso quanto para o pior caso, já que o número de iterações independe de como os dados chegam.

Resposta

Melhor caso: Tbest(N)=cinit+(lceil N/2rceil+1)ccond+lceil N/2rceil,(cbody+cinc)
Pior caso: Tworst(N)=cinit+(lceil N/2rceil+1)ccond+lceil N/2rceil,(cbody+cinc)

Exercícios relacionados