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);

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.

Passo 5

Em termos de notação assintótica: no melhor e no pior caso temos
T(N) = A + B,N = Θ(N)

Resposta

Melhor caso: T(N) = A + B,N = Θ(N)
Pior caso: T(N) = A + B,N = Θ(N)

Exercícios relacionados