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);
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
, cada verificação de condição custa
, cada incremento custa
e cada execução de printf custa
. Nosso objetivo é expressar
em função de
.
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 é
E a condição do loop é avaliada
vezes.
Passo 4
Somando todos os custos temos
Substituindo
obteremos
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:
Pior caso: