Para os pares de funções seguintes indique se é verdadeira ou falsa cada uma das seguintes afirmações: f(n) = O(g(n)), f(n) = \Omega(g(n)) e f(n) = \Theta(g(n)). Explique sucintamente as suas opções.
Para a implementação ArrayListIntSet (que usava um array como lista dos números do conjunto), qual a complexidade temporal de cada um dos seguintes métodos? (use notação \Theta, para ser mais preciso - espreite o slide 40 para um exemplo nos métodos de listas):
contains(int x)
add(int x)
remove(int x)
size()
clear()
Na aula #05 foi sugerida uma implementação usando um array de booleanos (ao invés de manter uma lista de números). Recordando o que foi pedido na sua essência:
- Manter um array isElem[] de valores booleanos (verdadeiro ou falso). isElem[i] diz-nos se o número i está ou não no conjunto. O tamanho do array determina o tamanho do número máximo. Manter numa outra variável size o número de elementos. Por exemplo, o conjunto {1,5,7} seria representado por isElem[]={F,T,F,F,F,T,F,T,F,F,F} e size=3
0
1
2
3
4
5
6
7
8
9
F
T
F
F
F
T
F
T
F
F
Para esta implementação com o array de booleanos, qual é a complexidade temporal de cada um dos 5 mesmos métodos do TAD IntSet? O que melhorou em relação ao ArrayListIntSet? Qual é o tradeoff? (ou seja, para conseguir melhor complexidade temporal, o que passamos a precisar em termos de memória? quais as limitações desta nova implementação?)
Exercício 3) Previsão do tempo de execução
[ver slides 35 a 37]
Imagine que tem um programa P implementado, que recebe como input n números. Ao experimentar executá-lo com testes aleatorizados, obteve os seguintes tempos de execução:
Com n=300 demorou 1.5 segundos
Com n=600 demorou 12.0 segundos
Com n=1200 demorou 1m36s
Qual será a complexidade temporal mais provável do programa P? Justifique.
Indique uma estimativa de quanto tempo demoraria o programa para um caso com 5000 números. Justifique.
Exercício 4) Problema do subarray contíguo de soma máxima
O objectivo deste exercício é ter algoritmos de diferentes complexidades para um mesmo problema e ir verificando a sua eficiência temporal. Começe por ler o enunciado do problema, disponível em [ED198] Um Jogo com Sequências (Volume 5).
Uma primeira solução com força bruta com tempo Θ(n3)
Quais são todas as subsequências contíguas possíveis? Seja v[] um array contendo a sequência e começado na posição 0. As sequências possíveis são então todos os subarrays v[i..j] tal que 0≤i≤j<n.
Uma solução exaustiva seria passar por todas estas subsequências e para cada uma delas calcular o valor da respectiva soma, escolhendo a melhor possível. Supondo que já temos a leitura feita para o array v[], uma maneira de fazer isto seria a indicada pelo código seguinte:
int maxSoFar = v[0];// porque é esta uma boa escolha para a melhor soma inicial?for(int i=0; i<n; i++)// Todas as posicoes iniciais possiveisfor(int j=i; j<n; j++){// Todas as posicoes finais possiveisint sum =0;for(int k=i; k<=j; k++)// Calcular soma entre posicoes i e j
sum += v[k];
System.out.println("Soma entre "+ i +" e "+ j +" = "+ sum);if(sum > maxSoFar) maxSoFar = sum;}
System.out.println(maxSoFar);
Perceba o que faz o código de cima, implemente a parte restante (leitura) e submeta-o no Mooshak. Veja quantos pontos obtém e porque motivo o programa falha nos testes maiores (basta clicar no resultado da submissão para ter acesso a uma tabela detalha com os resultados).
Melhorando a solução para Θ(n2)
Intuitivamente, olhando para o código anterior podemos notar que em cada soma estamos a repetir muitos cálculos. Quando passamos do cálculo de soma(v[i..j]) para soma(v[i..j+1]) não precisamos de voltar a recalcular tudo (começando novamente em i, e basta-nos adicionar v[j+1] à soma anterior!
Dito de outro modo, soma(v[i..j+1]) = soma(v[i..j]) + v[j+1]. Podemos utilizar isto para remover o terceiro ciclo com k que tínhamos na solução anterior.
Implemente esta nova solução e submeta-a. Quantos pontos passa a obter? Porque é que passa em mais testes?
Melhorando ainda mais para Θ(n)
Uma solução quadrática ainda não é suficiente e temos de a melhorar para tempo linear. Para isso vamos usar o algoritmo de Kadane.
Considere que best(i) representa o melhor subarray que termina na posição i. Sabemos como "caso base" que best(0) = v[0] (é o único subarray possível que termina na primeira posição).
Se soubermos o valor de best(i), como calcular o valor de best(i+1)?
Se best(i) for um valor positivo, então best(i+1) = best(i) + v[i+1] pois como os subarrays têm de ser contíguos, então se aproveitarmos algo "de trás", terá que ser o melhor possível a terminar na posição anterior. Imagine por exemplo o array [4,-2,1,5]:
i
0
1
2
3
v[i]
4
-2
1
5
best(i)
4
2
3
??
best(2) = 3, obtido através do subarray [4,-2,1].
best(3) = best(2) + v[3] = 3 + 5 = 8, obtido através subarray [4,-2,1,5] (estendeu-se o subarray anterior).
Se best(i) for um valor negativo, então best(i+1) = v[i+1], pois o que está "para trás" só pode fazer decrescer a soma do array a terminar na posição i+1. Imagine por exemplo o array [-5,2,-3,4]:
i
0
1
2
3
v[i]
-5
2
-3
4
best(i)
-5
2
-1
4
best(2) = -1, obtido através do subarray [2,-1].
best(3) = v[3] = 4, obtido através subarray [4] (não se estendeu o subarray anterior).
No final de tudo, o melhor subarray é o melhor valor de best(i) para um qualquer i (o melhor pode terminar em qualquer posição).
Para calcular isto basta-nos percorrer uma única vez o array v[] e em cada iteração calcular em tempo constante o valor da melhor soma a terminar na posição actual usando a melhor soma a terminar na posição anterior. A complexidade temporal fica portanto linear.
Implemente esta solução e submeta-a, verificando que já consegue passar todos os testes sem exceder o tempo limite.
Exercícios extra para consolidação de conhecimentos
Tem disponível no Volume 5 mais dois pequenos problemas onde a solução mais "bruta" em termos de complexidade temporal não passa e tem de fazer algo um pouco mais eficiente. Estes dois problema foram o problema mais fácil da qualificação (do respectivo ano) das Olimpíadas Nacionais de Informática um concurso para alunos do secundário:
[ED222] Salvando os Ruivacos
Para este problema uma solução "bruta" que tente todos os intervalos e para cada um deles percorra todos os seus elemento para verificar quantos são maiores ou iguais a T pode demorar Θ(N^2) (basta imaginar o caso onde K=N/2: teremos nesse caso N/2+1 intervalos, cada um com tamanho N/2 que temos de verificar). Isto não é suficiente para passar no tempo, e precisamos de uma solução melhor...
Imagine que já processou o intervalo [a,b] (entre as posições a e b, tendo obtido Qa, a quantidade de elementos maiores ou iguais a T nesse intervalo.
O próximo intervalo a considerar é o intervalo [a+1,b+1]. O que muda nesse intervalo? Apenas desaparece a posição a e é inserida a posição b+1. O (novo) valor de Qa+1 é portanto igual a Qa subtraindo 1 caso o valor da posição a seja ≥ T e somando 1 caso o valor da posição b+1 seja ≥ T.
Para cada novo intervalo precisamos então apenas de um número constante de operações (considerar o elemento a retirar e considerar o elemento a inserir). Em termos de eficiência, isto corresponde a um ciclo inicial para o primeiro intervalo de tamanho K e depois percorrer os restantes (N-K) intervalos, gastando em cada um tempo constante. Outra maneira de pensar no mesmo algorito é ver que cada elemento é adicionado uma vez ao intervalo actual, e retirado uma vez. Esta é portanto uma solução com tempo Θ(N) que passa em todos os casos e dá os 100 pontos.
Esta ideia de reutilizar o resultado do intervalo anterior para calcular mais rapidamente o intervalo atual chama-se sliding window, pois estamos a fazer "deslizar" a janela corrente ao longo do input.
[ED199] Tesouros de Kilmia
Para este problema uma solução "bruta" que simule todas as instruções pode demorar Θ(I*N), pois cada uma das I instruções pode obrigar a percorrer N posições no pior caso. Isto não é suficiente para passar no tempo, e precisamos de uma solução melhor...
É preciso pensar um pouco sobre o que está a acontecer no problema e assim fazer uma observação importante: o Daniel cobre sempre um intervalo contígo de posições. Se a posição mais à direita que o Daniel chegou foi a posição pd, então o Daniel teve que passar por todas as posições de B a pd, pois ele nunca "salta" posições. Analogamente, se a posição mais à esquerda que o Daniel chegou foi a posição pe, então o Daniel teve
que passar por todas as posições de pe a B.
Assim, sabendo pe e pd, basta fazer um ciclo a percorrer todas
as posições entre pe e pd e calcular quantos tesouros há nesse
intervalo. Para calcular pe e pd, basta calcular a posição após
seguir cada instrução e manter a menor e maior, respetivamente.
Em termos de eficiência, isto corresponde a um ciclo para processar
todas as instruções e calcular pe e pd, e a um segundo ciclo
para verificar as arcas entre pe e pd, o que corresponde a I + N operações.
Esta é portanto uma solução Θ(I + N) que passa em todos os casos e dá os 100 pontos.
Exercício de Desafio
O exercicio de desafio desta semana é um problema de uma fase de qualificação das Olimpíadas Nacionais de Informática, um concurso para alunos do secundário, e tem precisamente a ver com eficiência algorítmica. Deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak, no volume de Desafios:
[ONI_DO] Desorientados (Fase de Qualificação das Olimpíadas Nacionais de Informática'2019)
O problema não é muito complicado (era da fase de qualificação), mas uma solução "bruta" não passa no tempo. Ao pensarem numa solução procurem sempre perceber qual a complexidade do que estão a pensar para conseguirem "prever" se vai ou não passar.
Como é um mini-desafio, não vou dar mais dicas, mas se precisarem de alguma ajuda avisem. Fico à espera de ver os vossos programas :)