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 ++)
printf("%d",i);
for (i = 0; i < N; i ++)
printf("%d",i);
Passo 1
O enunciado pede para descobrir a função T(N) que descreve o tempo de execução do trecho de código dado, tratando separadamente melhor e pior caso. O conteúdo é Análise de Complexidade Temporal, e vamos usar a ideia de que cada operação básica (inicialização, comparação, incremento, printf) custa uma constante de tempo.
Passo 2
Cada passo do laço
for
(teste de condição, incremento de i
e a chamada a printf
) executa em tempo constante, que chamaremos de C. Além disso, há um custo constante C₀ para a inicialização i = 0
e um custo C₁ para a última verificação que faz o loop parar.Passo 3
O número de iterações do laço é N, pois
i
vai de 0 até N-1
. Assim, temos N testes de condição que entram no corpo e um teste extra que sai do laço, totalizando N+1 testes. Também há N incrementos de i
e N chamadas a printf
. Podemos agrupar os custos constantes em termos de N.Passo 4
Somando tudo, a função de tempo fica:
onde A = C_0 + C_1 + C_{teste} e B = C_{teste} + C_{incremento} + C_{printf}.
Como o laço sempre roda N vezes, independentemente dos dados de entrada, tanto o melhor caso quanto o pior caso têm a mesma expressão. Logo, a complexidade é linear.
Como o laço sempre roda N vezes, independentemente dos dados de entrada, tanto o melhor caso quanto o pior caso têm a mesma expressão. Logo, a complexidade é linear.
Passo 5
Em termos de notação assintótica: no melhor e no pior caso temos
Resposta
Melhor caso: T(N) = A + B,N = Θ(N)
Pior caso: T(N) = A + B,N = Θ(N)
Pior caso: T(N) = A + B,N = Θ(N)