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){
for(j = N-i; j >=0; j--){
if(V[i]< V[j]){
printf("%d",i);
}
}
}
for(i = 0; i < N; i=i+2){
for(j = N-i; j >=0; j--){
if(V[i]< V[j]){
printf("%d",i);
}
}
}
Passo 1
O enunciado pede pra gente analisar o custo do código em termos de N no melhor e no pior caso — basicamente é um exercício de contar iterações de loops e montar um somatório.
Passo 2
O loop externo faz valores possíveis para
.
i
ir de 0 até menos que N, de 2 em 2. Logo, ele executa cerca de N/2 iterações. Em notação, podemos dizer que há
Passo 3
Para cada valor de
, o loop interno faz
descer de
até 0, inclusive. Assim, quando
vale certo valor, o número de iterações internas é
Substituindo
pelos seus possíveis valores (0, 2, 4, …, 2
), montamos o somatório
Agora basta simplificar esse somatório:
Passo 4
Calculando o somatório
Passo 5
Como as comparações do vezes), mas isso só dobra o coeficiente, sem mudar a ordem.
if
ocorrem em todas as iterações, tanto o melhor quanto o pior caso têm o mesmo número de comparações. Se a gente contar também o printf
, no pior caso ele é chamado em cada comparação atendida (ou seja, em até
Passo 6
Logo, em termos de notação assintótica, tanto o melhor quanto o pior caso são
.
Resposta
Melhor caso:
Pior caso: considerando também as chamadas de
Pior caso: considerando também as chamadas de
printf
,