Exercícios resolvidos: complexidade de algoritmos

Explicação

Identificação das variáveis

O tamanho da entrada é $n$, pois o arranjo possui count elementos.

A variável $e$ informa quantas vezes o corpo do if executa. Logo:

$$0 \le e \le n$$

Trace do laço

Considere count = 4. Cada linha abaixo representa uma avaliação de index < count:

Avaliação	index antes do teste	Teste	Resultado	O que acontece depois
1	0	0 < 4	verdadeiro	O corpo executa e index++ produz 1.
2	1	1 < 4	verdadeiro	O corpo executa e index++ produz 2.
3	2	2 < 4	verdadeiro	O corpo executa e index++ produz 3.
4	3	3 < 4	verdadeiro	O corpo executa e index++ produz 4.
5	4	4 < 4	falso	O laço termina. O corpo e o incremento não executam.

Os quatro elementos produzem quatro testes verdadeiros. O laço precisa de mais um teste, agora falso, para descobrir que deve terminar. Portanto, para $n$ elementos, index < count é avaliado $n+1$ vezes. O corpo e index++ executam somente $n$ vezes.

Contagem de cada operação

total = 0L                         1 vez
index = 0U                         1 vez
index < count                      n + 1 vezes
index++                            n vezes
values[index] % 2 == 0             n vezes
total += values[index]             e vezes
return total                       1 vez

Construção de $T(n,e)$

Somando as quantidades:

$$T(n,e) = 1 + 1 + (n+1) + n + n + e + 1$$

Agrupando os termos:

$$T(n,e) = 3n + e + 4$$

Melhor e pior caso

O melhor caso ocorre quando nenhum valor é par. Nesse caso, $e=0$:

$$T(n,0) = 3n + 0 + 4 = 3n + 4$$

O termo dominante é $n$. Portanto:

$$T(n,0) = \Theta(n)$$

O pior caso ocorre quando todos os valores são pares. Nesse caso, $e=n$:

$$T(n,n) = 3n + n + 4 = 4n + 4$$

O termo dominante continua sendo $n$. Portanto:

$$T(n,n) = \Theta(n)$$

Cálculo para $n=7$ e $e=3$

$$T(7,3) = 3 \cdot 7 + 3 + 4$$ $$T(7,3) = 21 + 3 + 4 = 28$$

Resposta esperada

1. $T(n,e)=3n+e+4$.
2. No melhor caso, $e=0$ e $T(n,0)=3n+4$.
3. No pior caso, $e=n$ e $T(n,n)=4n+4$.
4. $T(7,3)=28$.
5. O melhor e o pior caso pertencem a $\Theta(n)$.

Explicação

O que deve ser contado

O enunciado pede somente as chamadas de process. Uma chamada ocorre para cada par (left, right) em que o laço alcança o corpo, isto é, quando right < left é verdadeiro.

Trace em forma de matriz

Considere $n=5$. As linhas representam left e as colunas representam right. O símbolo X marca uma chamada de process. O símbolo · indica que process não é chamado naquela combinação. Ele não significa que a condição foi necessariamente avaliada.

left / right	0	1	2	3	4	Chamadas
0	·	·	·	·	·	0
1	X	·	·	·	·	1
2	X	X	·	·	·	2
3	X	X	X	·	·	3
4	X	X	X	X	·	4

Os X formam o triângulo estritamente inferior da matriz, abaixo da diagonal em que right = left. Na linha left, existem exatamente left símbolos X e, portanto, left chamadas de process.

Soma das chamadas

$$C(n) = 0 + 1 + 2 + \cdots + (n-1)$$

O termo zero não altera a soma. Essa é a soma dos inteiros de $1$ até $n-1$, cuja fórmula é:

$$C(n) = \frac{n(n-1)}{2}$$

Expandindo a expressão:

$$C(n) = \frac{n^2-n}{2}$$

Chamadas de process e avaliações da condição não são a mesma contagem

Para cada valor de left, o teste right < left ocorre left vezes com resultado verdadeiro e mais uma vez com resultado falso. Esse último teste falso encerra o laço interno. Assim, a quantidade total de avaliações da condição é:

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Esse valor não responde ao enunciado, pois a avaliação falsa não chama process. A contagem solicitada inclui somente os X da matriz, isto é, $\frac{n(n-1)}{2}$ chamadas.

Cálculo para $n=9$

$$C(9) = \frac{9(9-1)}{2}$$ $$C(9) = \frac{9 \cdot 8}{2} = 36$$

Classificação do tempo e do espaço

O termo dominante de $(n^2-n)/2$ é $n^2$. A constante $1/2$ e o termo $-n$ não alteram a classe assintótica:

$$C(n) = \Theta(n^2)$$

O fragmento usa apenas os índices left e right, além dos parâmetros. A quantidade de variáveis não cresce com $n$:

$$S(n) = \Theta(1)$$

Resposta esperada

1. Para cada valor de left, ocorrem left chamadas de process.
2. $C(n)=0+1+2+\cdots+(n-1)$.
3. $C(n)=\frac{n(n-1)}{2}$.
4. $C(9)=36$.
5. O tempo pertence a $\Theta(n^2)$ e o espaço auxiliar pertence a $\Theta(1)$.

1. Cálculo de $T_A(16)$

$$T_A(16)=7\cdot16+30$$ $$T_A(16)=112+30=142$$

2. Cálculo de $T_B(16)$

Como $2^4=16$, temos $\log_2 16=4$:

$$T_B(16)=2\cdot16\cdot4+10$$ $$T_B(16)=128+10=138$$

3. Cálculo de $T_C(16)$

$$T_C(16)=\frac{16^2}{2}$$ $$T_C(16)=\frac{256}{2}=128$$

Para $n=16$, a ordem concreta é:

$$T_C(16) < T_B(16) < T_A(16)$$

4. Classes assintóticas

Em $T_A(n)=7n+30$, o termo dominante é $n$:

$$T_A(n)=\Theta(n)$$

Em $T_B(n)=2n\log_2 n+10$, o termo dominante é $n\log n$:

$$T_B(n)=\Theta(n\log n)$$

Em $T_C(n)=n^2/2$, o termo dominante é $n^2$:

$$T_C(n)=\Theta(n^2)$$

As taxas de crescimento ficam nesta ordem:

$$\Theta(n) < \Theta(n\log n) < \Theta(n^2)$$

O custo quadrático foi o menor para $n=16$ por causa dos coeficientes das funções. Isso não altera o fato de que $n^2$ cresce mais rapidamente quando $n$ aumenta.

5. Limites de $F(n)$

Em $F(n)=6n^2+3n+12$, o termo dominante é $n^2$. Usando a mesma ordem dominante nos três limites:

$$F(n)=O(n^2)$$ $$F(n)=\Omega(n^2)$$ $$F(n)=\Theta(n^2)$$

Resposta: para $n=16$, os custos são $142$, $138$ e $128$. Assintoticamente, as classes são $\Theta(n)$, $\Theta(n\log n)$ e $\Theta(n^2)$.

Procedimento A

Duas chamadas com tamanho $n/2$ produzem:

$$2T\left(\frac{n}{2}\right)$$

Três percursos completos executam $3n$ operações. Como o fator $3$ é constante:

$$3n=\Theta(n)$$

A recorrência pode preservar o coeficiente exato:

$$T(1)=\Theta(1)$$ $$T(n)=2T\left(\frac{n}{2}\right)+3n$$

Na forma assintótica do trabalho local:

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)$$

Procedimento B

Uma chamada com tamanho $n/4$ produz:

$$T\left(\frac{n}{4}\right)$$

Duas operações formam um custo constante:

$$2=\Theta(1)$$

Logo:

$$T(1)=\Theta(1)$$ $$T(n)=T\left(\frac{n}{4}\right)+2$$

ou:

$$T(n)=T\left(\frac{n}{4}\right)+\Theta(1)$$

Procedimento C

Quatro chamadas com tamanho $n/2$ produzem:

$$4T\left(\frac{n}{2}\right)$$

O enunciado informa trabalho local quadrático. Portanto:

$$T(1)=\Theta(1)$$ $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$

ou:

$$T(n)=4T\left(\frac{n}{2}\right)+\Theta(n^2)$$

Resposta: os termos recursivos representam a quantidade e o tamanho das chamadas. O termo após a soma representa somente o trabalho local da chamada atual.

1. Três primeiras expansões

A primeira aplicação da recorrência é:

$$T(n)=T\left(\frac{n}{3}\right)+2$$

Na segunda aplicação, use a mesma regra com entrada $n/3$:

$$T\left(\frac{n}{3}\right)=T\left(\frac{n}{9}\right)+2$$

Substituindo na expressão original:

$$T(n)=\left[T\left(\frac{n}{9}\right)+2\right]+2$$ $$T(n)=T\left(\frac{n}{9}\right)+4$$

Na terceira aplicação:

$$T\left(\frac{n}{9}\right)=T\left(\frac{n}{27}\right)+2$$

Logo:

$$T(n)=T\left(\frac{n}{27}\right)+6$$

Cada aplicação divide o tamanho por $3$ e acrescenta $2$.

2. Padrão após $k$ expansões

$$T(n)=T\left(\frac{n}{3^k}\right)+2k$$

3. Quantidade de expansões

A expansão termina quando a entrada chega a $1$:

$$\frac{n}{3^k}=1$$

Multiplicando os dois lados por $3^k$:

$$n=3^k$$

Aplicando logaritmo de base $3$:

$$k=\log_3 n$$

4. Fórmula final

Substituindo $k=\log_3 n$ no padrão:

$$T(n)=T(1)+2\log_3 n$$

Como $T(1)=4$:

$$T(n)=4+2\log_3 n$$

O termo dominante é logarítmico:

$$T(n)=\Theta(\log n)$$

5. Cálculo para $n=729$

Como $729=3^6$:

$$\log_3 729=6$$ $$T(729)=4+2\cdot6=16$$

Resposta: $T(n)=4+2\log_3 n=\Theta(\log n)$ e $T(729)=16$.

1. Caso base

A recorrência informa:

$$T(1)=2$$

A proposta para $n=1$ fornece:

$$3\cdot1-1=2$$

O valor proposto coincide com o caso base.

2. Hipótese de indução

Suponha que a proposta seja válida para $n-1$:

$$T(n-1)=3(n-1)-1$$

Simplificando:

$$T(n-1)=3n-3-1$$ $$T(n-1)=3n-4$$

3. Substituição na recorrência

A recorrência é:

$$T(n)=T(n-1)+3$$

Substituindo a hipótese $T(n-1)=3n-4$:

$$T(n)=(3n-4)+3$$ $$T(n)=3n-1$$

O resultado coincide com a proposta.

4. Conclusão

O caso base é válido e a hipótese para $n-1$ produz a expressão para $n$. Portanto:

$$T(n)=3n-1$$

O termo dominante é $n$:

$$T(n)=\Theta(n)$$

Resposta: a proposta $T(n)=3n-1$ foi verificada e pertence a $\Theta(n)$.

1. Interpretação da recorrência

Em uma chamada com entrada de tamanho $x$:

• o termo $2T(x/2)$ cria duas chamadas com metade da entrada;
• o termo $2x$ representa o trabalho local da chamada atual;
• uma folha custa $T(1)=2$.

2. Níveis para $n=16$

Nível 0:  1 nó  de tamanho 16    custo por nó: 32    custo do nível: 32
Nível 1:  2 nós de tamanho 8     custo por nó: 16    custo do nível: 32
Nível 2:  4 nós de tamanho 4     custo por nó: 8     custo do nível: 32
Nível 3:  8 nós de tamanho 2     custo por nó: 4     custo do nível: 32
Nível 4: 16 folhas de tamanho 1  custo por folha: 2  custo do nível: 32

Existem quatro níveis internos, numerados de $0$ a $3$. O nível $4$ contém os casos base.

3. Custo exato para $n=16$

Os quatro níveis internos custam $32$ cada:

$$4\cdot32=128$$

As $16$ folhas custam $2$ cada:

$$16\cdot2=32$$

Somando:

$$T(16)=128+32=160$$

4. Generalização do nível $i$

No nível interno $i$:

$$\text{quantidade de nós}=2^i$$ $$\text{tamanho por nó}=\frac{n}{2^i}$$

O custo local de um nó com entrada $n/2^i$ é:

$$2\cdot\frac{n}{2^i}$$

Multiplicando a quantidade de nós pelo custo de cada nó:

$$2^i\cdot2\cdot\frac{n}{2^i}=2n$$

Todos os níveis internos custam $2n$.

5. Altura e custo total

A árvore alcança o caso base quando:

$$\frac{n}{2^k}=1$$

Logo:

$$k=\log_2 n$$

Existem $\log_2 n$ níveis internos. O custo interno é:

$$2n\log_2 n$$

Existem $n$ folhas, cada uma com custo $2$. O custo das folhas é $2n$:

$$T(n)=2n\log_2 n+2n$$

Portanto:

$$T(n)=\Theta(n\log n)$$

Resposta: $T(16)=160$. Cada nível interno custa $2n$, e o custo total pertence a $\Theta(n\log n)$.

1. Interpretação da recorrência

Cada chamada com entrada $x$:

• cria quatro chamadas com entrada $x/2$;
• executa $2x$ unidades de trabalho local;
• termina com custo $1$ quando $x=1$.

2. Níveis para $n=8$

Nível 0:  1 nó  de tamanho 8     custo por nó: 16    custo do nível: 16
Nível 1:  4 nós de tamanho 4     custo por nó: 8     custo do nível: 32
Nível 2: 16 nós de tamanho 2     custo por nó: 4     custo do nível: 64
Nível 3: 64 folhas de tamanho 1  custo por folha: 1  custo do nível: 64

3. Custo exato para $n=8$

$$T(8)=16+32+64+64$$ $$T(8)=176$$

4. Generalização do custo interno

No nível interno $i$:

$$\text{quantidade de nós}=4^i$$ $$\text{tamanho por nó}=\frac{n}{2^i}$$ $$\text{custo local por nó}=2\cdot\frac{n}{2^i}$$

O custo total do nível é:

$$4^i\cdot2\cdot\frac{n}{2^i}$$

Como $4^i/2^i=2^i$:

$$\text{custo do nível}=2n\cdot2^i$$

O custo dobra a cada descida na árvore.

5. Quantidade de folhas

A altura $k$ satisfaz:

$$\frac{n}{2^k}=1$$ $$k=\log_2 n$$

Como a quantidade de nós é multiplicada por $4$ em cada nível:

$$\text{folhas}=4^k$$

Substituindo $k=\log_2 n$:

$$4^k=(2^2)^k=(2^k)^2=n^2$$

As folhas custam $1$ cada. Logo, o último nível custa $n^2$.

6. Custo assintótico

Os custos aumentam geometricamente em direção às folhas. Vistos de baixo para cima, os níveis anteriores formam frações sucessivas do custo dominante:

$$n^2+\frac{n^2}{2}+\frac{n^2}{4}+\cdots$$

A soma dos níveis anteriores é menor que outro $n^2$:

$$n^2 \le T(n) < 2n^2$$

Portanto:

$$T(n)=\Theta(n^2)$$

O fator $\log n$ não aparece porque os níveis não possuem o mesmo custo. O último nível domina a soma.

Resposta: $T(8)=176$, existem $n^2$ folhas e $T(n)=\Theta(n^2)$.

1. Parâmetros

A forma do método mestre é:

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

Comparando com a recorrência do exercício:

a = 8      porque existem oito subproblemas
b = 2      porque cada subproblema recebe n/2
f(n) = n²  porque esse é o trabalho local

2. Expoente de referência

$$p=\log_b a$$ $$p=\log_2 8=3$$

Portanto:

$$n^p=n^3$$

3. Comparação dos expoentes

O trabalho local é:

$$f(n)=n^2$$

O expoente local é $c=2$, enquanto o expoente de referência é $p=3$:

$$c<p$$ $$2<3$$

O trabalho local possui uma potência menor. Portanto, as folhas dominam e o caso 1 se aplica.

4. Resultado

No caso 1:

$$T(n)=\Theta(n^p)$$

Substituindo $p=3$:

$$T(n)=\Theta(n^3)$$

Resposta: $a=8$, $b=2$, $f(n)=n^2$, $p=3$, o caso 1 se aplica e $T(n)=\Theta(n^3)$.

Recorrência A: identificação dos parâmetros

a = 9
b = 3
f(n) = n²

O expoente de referência é:

$$p=\log_3 9=2$$

Logo:

$$n^p=n^2$$

O trabalho local também é $f(n)=n^2$. Portanto, o expoente local $c=2$ é igual a $p=2$:

$$c=p$$

Os níveis são equilibrados e o caso 2 se aplica:

$$T(n)=\Theta(n^p\log n)$$

Substituindo $p=2$:

$$T(n)=\Theta(n^2\log n)$$

Recorrência B: identificação dos parâmetros

a = 2
b = 2
f(n) = n³

O expoente de referência é:

$$p=\log_2 2=1$$

Logo:

$$n^p=n$$

O trabalho local possui expoente $c=3$:

$$c>p$$ $$3>1$$

Antes de usar o caso 3, é necessário verificar a regularidade:

$$a\cdot f\left(\frac{n}{b}\right)\le q\cdot f(n), \quad q<1$$

Substituindo $a=2$, $b=2$ e $f(n)=n^3$:

$$2\cdot f\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^3$$ $$2\left(\frac{n^3}{8}\right)=\frac{n^3}{4}$$

Como $f(n)=n^3$:

$$\frac{n^3}{4}=\frac{1}{4}f(n)$$

Podemos usar $q=1/4$, que é menor que $1$. A regularidade é satisfeita.

No caso 3, o trabalho local domina:

$$T(n)=\Theta(f(n))$$ $$T(n)=\Theta(n^3)$$

Resposta: a recorrência A usa o caso 2 e resulta em $\Theta(n^2\log n)$. A recorrência B usa o caso 3, satisfaz a regularidade com $q=1/4$ e resulta em $\Theta(n^3)$.

Recorrência A

O método exige subproblemas com tamanho $n/b$, em que $b>1$ é constante.

Na recorrência A, a entrada diminui por subtração:

$$n-2$$

Não existe uma divisão por um fator constante $b$. Portanto, a recorrência não possui a forma exigida.

Decisão: rejeitar o método mestre apresentado na aula.

Recorrência B

O método exige que todos os subproblemas tenham o mesmo tamanho $n/b$.

Nesta recorrência, os tamanhos são diferentes:

$$\frac{n}{4}$$

e:

$$\frac{3n}{4}$$

Não é possível representar as duas chamadas por um único termo $aT(n/b)$.

Decisão: rejeitar o método mestre apresentado na aula.

Recorrência C

Os parâmetros iniciais são:

a = 4
b = 2
p = log₂ 4 = 2
nᵖ = n²
f(n) = n² / log n

O trabalho local é menor que $n^2$, mas a diferença ocorre somente pelo fator logarítmico $1/\log n$. O caso 1 apresentado na aula exige uma diferença por potência:

$$f(n)=O(n^{p-\varepsilon})$$

para alguma constante $\varepsilon>0$.

O fator $1/\log n$ não fornece essa diferença de potência. O caso 2 também não serve porque $f(n)$ não pertence a $\Theta(n^2)$.

Decisão: rejeitar os três casos apresentados na aula. Uma versão ampliada do método pode tratar essa recorrência, mas ela não faz parte do conteúdo utilizado nesta lista.

Recorrência D

Os parâmetros são:

a = 2
b = 2
f(n) = n²
p = log₂ 2 = 1

O expoente local é $c=2$ e o expoente de referência é $p=1$:

$$c>p$$

É necessário verificar a regularidade:

$$2\cdot f\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2$$ $$2\cdot\frac{n^2}{4}=\frac{n^2}{2}$$ $$\frac{n^2}{2}=\frac{1}{2}f(n)$$

Existe $q=1/2<1$. Portanto, a regularidade é satisfeita e o caso 3 se aplica:

$$T(n)=\Theta(f(n))=\Theta(n^2)$$

Decisão: usar o caso 3. O resultado é $\Theta(n^2)$.

Resposta: rejeitar o método nas recorrências A, B e C pelos motivos indicados. Na recorrência D, usar o caso 3 e obter $\Theta(n^2)$.

1. Pior caso da inserção

$$C_I(n)=\frac{n(n-1)}{2}$$

Substituindo $n=200\,000$:

$$C_I(200\,000)=\frac{200\,000\cdot199\,999}{2}$$

Primeiro, divida $200\,000$ por $2$:

$$C_I(200\,000)=100\,000\cdot199\,999$$ $$C_I(200\,000)=19\,999\,900\,000$$

O pior caso exige quase vinte bilhões de comparações no modelo fornecido.

2. Escala da intercalação

$$C_M(n)\approx n\log_2 n$$ $$C_M(200\,000)\approx200\,000\cdot17{,}61$$ $$C_M(200\,000)\approx3\,522\,000$$

Esse valor representa a escala informada no enunciado. Ele não é uma contagem exata de todas as instruções da implementação.

3. Tamanho do buffer

Cada um dos $200\,000$ registros ocupa $48$ bytes:

$$B=200\,000\cdot48$$ $$B=9\,600\,000\text{ bytes}$$

Convertendo para MiB:

$$B=\frac{9\,600\,000}{1\,048\,576}\text{ MiB}$$ $$B\approx9{,}16\text{ MiB}$$

Como $9{,}16<12$, o buffer cabe na memória disponível.

4. Verificação das restrições

Estabilidade da inserção:      atendida
Estabilidade da intercalação:  atendida
Memória da inserção:           atendida
Memória da intercalação:       9,16 MiB < 12 MiB, atendida

As duas alternativas atendem à estabilidade. A intercalação também atende ao limite de memória.

5. Decisão

A comparação de escala fornece:

Inserção no pior caso:  19 999 900 000 comparações
Intercalação:               3 522 000 unidades proporcionais
Buffer da intercalação:         9,16 MiB
Memória disponível:             12 MiB

A intercalação possui crescimento $\Theta(n\log n)$, atende à estabilidade e seu buffer cabe na memória. A inserção economiza memória, mas seu pior caso quadrático é muito maior para a entrada fornecida.

Resposta: escolher a intercalação, considerando somente o modelo e as restrições declaradas no exercício.