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

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 i começando em 0, indo até i<N e aumentando de 2 em 2 (ou seja, i=0,2,4,\dots).
  • Para cada valor de i o laço interno define j=N-i e decrementa até j\ge 0 com passo -1.
  • Dentro do laço interno há uma comparação V[i] < V[j] e, se verdadeira, um \texttt{printf} (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 N? (isso é a medida típica de complexidade)
  • Qual a expressão exata (quando possível) e a forma assintótica (big- \Theta) para melhor e pior caso?

Passo 2

Contagem do número de iterações do laço externo:
  • O laço externo percorre i em passos de 2 a partir de 0 até menor que N. O número de iterações do externo é
m=\left\lceil \frac{N}{2} \right\rceil.
Aqui \lceil \cdot \rceil é o teto (arredondamento para cima). Por exemplo, se N é par N=2q então m=q; se N é ímpar N=2q+1 então m=q+1.

Passo 3

Contagem das iterações do laço interno para um i fixo:
  • Para um dado i o laço interno inicializa j=N-i e vai até j=0 inclusive com passo -1. O número de iterações do interno é
\text{itens}(i)= (N-i) - 0 + 1 = N-i+1.
Observação: esse número é independente do conteúdo de V; depende só de i e N.

Passo 4

Somando sobre todos os i do laço externo:
  • Como i toma os valores 0,2,4,\dots (um total de m valores), podemos indexar por k=0,\dots,m-1 com i=2k. Assim o total de execuções da comparação (ou do corpo interno) é
T(N)=\sum_{k=0}^{m-1} \bigl(N - 2k + 1\bigr).
Agora vamos calcular essa soma de forma algébrica.

Passo 5

Cálculo da soma (explicando cada passo):
  • Primeiro escrevemos
T(N)=\sum_{k=0}^{m-1} (N+1) \;-\; 2\sum_{k=0}^{m-1} k.
  • A soma de uma constante repetida m vezes dá m(N+1).
  • A soma dos primeiros m-1 inteiros é \sum_{k=0}^{m-1} k = \dfrac{m(m-1)}{2}.
  • Substituindo:
T(N)=m(N+1) - 2\cdot \frac{m(m-1)}{2} = m(N+1) - m(m-1).
  • Simplificando:
T(N)=m\bigl(N+1 - (m-1)\bigr)=m\bigl(N+2 - m\bigr).
Essa é a expressão exata em termos de m=\left\lceil \dfrac{N}{2}\right\rceil.

Passo 6

Expressões alternativas para N par e ímpar (para ver forma sem teto):
  • Se N é par, N=2q e m=q=\dfrac{N}{2}. Então
T(N)=\frac{N}{2}\Bigl(N+2-\frac{N}{2}\Bigr)=\frac{N}{2}\Bigl(\frac{N}{2}+2\Bigr)=\frac{N^2}{4}+N.
  • Se N é ímpar, N=2q+1 e m=q+1=\dfrac{N+1}{2}. Então
T(N)=\frac{N+1}{2}\cdot\frac{N+3}{2}=\frac{(N+1)(N+3)}{4}=\frac{N^2+4N+3}{4}.
Em ambas as fórmulas a ordem de grandeza principal é N^2/4.

Passo 7

Interpretação para melhor e pior caso:
  • A contagem T(N) acima conta o número de vezes que a comparação V[i]<V[j] (e, portanto, o corpo do laço interno) é executada. Essa quantidade NÃO depende dos valores do vetor V; depende só de N. 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 é T(N)=m(N+2-m) com m=\left\lceil \dfrac{N}{2}\right\rceil, e assintoticamente
T(N)=\Theta(N^2).
  • (Observação adicional: o número de vezes que o \texttt{printf} efetivamente imprime depende dos valores de V. No melhor caso para o número de impressões pode ser 0 se nunca houver V[i]<V[j], e no pior caso o número de impressões é no máximo o número de comparações menos os casos onde j=i — mas isso não altera a complexidade assintótica, que permanece quadrática.)

Resposta

Melhor caso (número de comparações): T(N)=m\bigl(N+2-m\bigr) com m=\left\lceil \dfrac{N}{2}\right\rceil. Assintoticamente T(N)=\Theta(N^2).
Pior caso (número de comparações): T(N)=m\bigl(N+2-m\bigr) com m=\left\lceil \dfrac{N}{2}\right\rceil. Assintoticamente T(N)=\Theta(N^2).

Exercícios relacionados