Para os pares de funções seguintes indique se é verdadeira ou falsa cada uma das seguintes afirmações: \(f(n) \in \mathcal{O}(g(n)\), \(f(n) = \Omega(g(n))\) e \(f(n) = \Theta(g(n))\). Explique sucintamente as suas opções.
| f(n) | g(n) | |
| (a) | \(5n^2 - 100n + 34\) | \(2n^3 - 97\) |
| (b) | \(54n + 100\) | \(6n - 24\) |
| (c) | \(2^n\) | \(6n^2\) |
| (d) | \(30\) | \(\log 30\) |
| (e) | \(n \log n + n\) | \(n^2\) |
| (f) | \(\sqrt{n}\) | \(\log n\) |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| F | T | F | F | F | T | F | T | F | F |
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:
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 \dots j]\) tal que \(0 \leq i \leq j \lt 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 possiveis for (int j=i; j<n; j++) { // Todas as posicoes finais possiveis int 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 detalhada com os resultados).
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 \ldots j])\) para \(soma(v[i \ldots 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 \ldots j+1]) = soma(v[i \ldots 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?
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)\)?
| \(i\) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| \(v[i]\) | 4 | -2 | 1 | 5 |
| \(best(i)\) | 4 | 2 | 3 | 8 |
\(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).
| \(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.