Obtenha a equação matemática referente á análise do pior e melhor caso do fragmento de código abaixo:
for (i = 1; i <= N; i=2*i)
2 printf("%d",i);
for (i = 1; i <= N; i=2*i)
2 printf("%d",i);
Passo 1
Estamos com o fragmento de código que faz um laço de repetição onde a variável
começa em 1 e, a cada iteração, é dobrada até ultrapassar
. O conteúdo é análise de complexidade temporal de algoritmos, e vamos precisar contar quantas vezes esse laço é executado.
Passo 2
Em cada iteração, o valor de
dobra. Se chamarmos de
o número de iterações completas até
ultrapassar
, teremos ao final da iteração
que
.
O laço continua enquanto . Então buscamos o maior
tal que
O laço continua enquanto
Passo 3
Para encontrar
, aplicamos o logaritmo de base 2 em ambos os lados:
Passo 4
Como
é inteiro, temos
.
O número total de iterações é esse mais a iteração inicial (quando
, correspondente a
), ou seja:
O número total de iterações é esse
Passo 5
Esse valor de
independe de casos de entrada diferentes, logo o melhor e o pior caso são iguais.
Resposta
Melhor caso:
. Pior caso:
.