Obtenha a equação matemática referente a 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 para obter a equação matemática que descreve a análise do pior e do melhor caso do trecho de código fornecido. As informações do código relevantes são:
- O laço externo itera com a variável
começando em , indo até e aumentando de em (ou seja, ). - Para cada valor de
o laço interno define e decrementa até com passo . - Dentro do laço interno há uma comparação
e, se verdadeira, um (operações de custo constante).
As perguntas que vamos responder:
- Quantas vezes a comparação (ou, equivalentemente, o corpo do laço interno) é executada em função de
? (isso é a medida típica de complexidade) - Qual a expressão exata (quando possível) e a forma assintótica (big-
) para melhor e pior caso?
Passo 2
Contagem do número de iterações do laço externo:
- O laço externo percorre
em passos de a partir de até menor que . O número de iterações do externo é
Aqui
é o teto (arredondamento para cima). Por exemplo, se
é par
então
; se
é ímpar
então
.
Passo 3
Contagem das iterações do laço interno para um
fixo:
- Para um dado
o laço interno inicializa e vai até inclusive com passo . O número de iterações do interno é
Observação: esse número é independente do conteúdo de
; depende só de
e
.
Passo 4
Somando sobre todos os
do laço externo:
- Como
toma os valores (um total de valores), podemos indexar por com . Assim o total de execuções da comparação (ou do corpo interno) é
Agora vamos calcular essa soma de forma algébrica.
Passo 5
Cálculo da soma (explicando cada passo):
- Primeiro escrevemos
- A soma de uma constante repetida
vezes dá . - A soma dos primeiros
inteiros é . - Substituindo:
- Simplificando:
Essa é a expressão exata em termos de
.
Passo 6
Expressões alternativas para
par e ímpar (para ver forma sem teto):
- Se
é par, e . Então
- Se
é ímpar, e . Então
Em ambas as fórmulas a ordem de grandeza principal é
.
Passo 7
Interpretação para melhor e pior caso:
- A contagem
acima conta o número de vezes que a comparação (e, portanto, o corpo do laço interno) é executada. Essa quantidade NÃO depende dos valores do vetor ; depende só de . Logo o número de comparações é o mesmo no melhor e no pior caso. - Portanto, tanto no melhor quanto no pior caso a expressão exata é
com , e assintoticamente
- (Observação adicional: o número de vezes que o
efetivamente imprime depende dos valores de . No melhor caso para o número de impressões pode ser se nunca houver , e no pior caso o número de impressões é no máximo o número de comparações menos os casos onde — mas isso não altera a complexidade assintótica, que permanece quadrática.)
Resposta
Melhor caso (número de comparações):
com
. Assintoticamente
.
Pior caso (número de comparações): com
. Assintoticamente
.
Pior caso (número de comparações):