Enunciado distribuido na sala.
(para todo k entre 1 e n temos: k ≠ i → A[⌊ k/2 ⌋] ≥ A[k]) e (i < 1 ou A[⌊ i/2 ⌋] ≥ A[i] ou A[⌊ i/2 ⌋] < A[i])
Como na recorrência temos um termo independente n2, vale a pena tentar T(n) ≤ c n2 pelo método da substituição. Acaba dando certo, pois temos:
T(n) ≤ T(n/3) + T(2n/3) + n2 ≤ c n2/9 + c 4n2/9 + n2 = (5c/9 +1)n2.
Para fazer isto ser menor ou igual a c n2, basta tomar c ≥ 9/4.
(n/2)! vs. (n/3)n/2. Esta era difícil. Um jeito de resolver é o seguinte. Primeiro substituir n = 6k para obter (3k)! vs. (2k)3k. Depois observar que os dois lados são produtos envolvendo 3k fatores. Nestes produtos temos três partes: uma que vai de 1 a k, outra de k+1 a 2k, e a última de 2k+1 a 3k. Observe agora que a segunda função ganha ou empata nas primeiras duas partes, e só perde na terceira. Isto sugere que a segunda função é maior.
Para confirmar isto, juntamos a primeira parte com a terceira, tentando neutralizar, e deixar para a segunda parte decidir. De fato, primeira com terceira dá:
produtoi=1k i(3k-i+1) vs. (2k)2k
O máximo da expressão i(3k-i+1) ocorre quando i=(3k+1)/2, e este máximo não passa de 4k2, logo juntando as partes 1 e 3 a segunda função ganha ou empata.
A parte do meio é um produto de números menores que 1, sendo que os k/2 primeiros são menores que 0,75. Assim, a razão (3k)! / (2k)3k é menor que (0,75)k/2, que tende a zero com k → ∞. Assim concluimos que (3k)! = o((2k)3k).
Aqui era observar que lg*lg2n ≥ lg*lg n = lg* n - 1, o que supera lg2lg*n, pois k-1 supera lg2k.
9lg n = nlg 9 e n3n1/3 = n10/3. A questão então é saber quem é maior: lg 9 ou 10/3. Elevando 2 a ambos, temos: 9 vs. 210/3. Tomando o cubo de cada lado, temos: 93 vs. 210. Qualquer computeiro sabe que 210 = 1024. Como 9 ao cubo dá só 729, concluimos que a segunda função ganha.
| Algoritmo | C-Pior caso | C-Melhor caso | T-Pior caso | T-Melhor caso | Estável? | Local? |
|---|---|---|---|---|---|---|
| Insertion sort | n2 | n | n2 | 1 | sim | sim |
| Selection sort | n2 | n2 | n | 1 | sim | sim |
| Merge sort | n lg n | n lg n | n lg n | n lg n | sim | não |
| Heap sort | n lg n | n | n lg n | n | não | sim |
| Quick sort | n2 | n lg n | n2 | n lg n | não | sim |
Aqui a grande maioria falou algo sobre a chave de um nó ser maior (ou igual) que a chave de seus filhos. A diferença foi ao falar para que valores de i isto ocorria. O critério baseou-se no seguinte:
| vale para i apenas: | 1,0 ponto |
| vale para a sub-árvore com raiz i: | 1,7 ponto |
| vale para todo i entre x e n, para algum x: | 2,4 pontos |
| vale para todo j entre 1 e n, exceto talvez i: | 2,5 pontos |
Houve um colega que falou que A[ i ] seria maior (ou igual) a todos os A[ j ] com j entre i e n, o que é falso. Mas ganhou 1,5 ponto, pois é apenas um pouco pior que falar da sub-árvore.
A recorrência foi abordada de duas formas (não excludentes) pelos alunos: com árvore e por substituição. No quesito árvore, o critério foi o seguinte:
| acertou valor dos nós: | 0,5 pontos |
| acertou soma de cada nível: | 0,5 pontos |
| acertou altura: | 0,0 pontos (*) |
| mencionou que a árvore é desbalanceada: | 0,5 pontos |
| acertou a soma das folhas: | 0,5 pontos |
| acertou a soma total (níveis + folhas): | 0,5 |
(*) todos acertaram isto, não foi diferencial
Além disto, houve os que tentaram a substituição por alguma função para mostrar que era a solução (pelo menos para limite superior). Neste caso, o critério principal foi saber lidar com o c que aparece quando usamos c.f(n) para provar que a solução seria O(f(n)) (ou, em alguns raros casos nesta prova, para mostrar que era Ω(f(n))).
Quem não soube lidar com o c levou 0,0 pontos nesta parte. Quem soube lidar com o c, levou pontos de acordo com a f(n) escolhida:
| f(n) = n^2: | 2,5 pontos |
| outra f(n): | 1,5 pontos |
Aqui são três itens independentes. Vamos a cada um deles.
(n/2)! vs. (n/3)^(n/2): aqui o principal era ter usado que lg n! = Θ(n lg n). Embora isto não resolvesse a questão, já valia 0,5 pontos. Os outros 0,5 foram dados por vários motivos, por exemplo, dizer que só com isto não se podia resolver. Mas os alunos obtiveram entre 0,0 e 0,3 desta outra parte. Ninguém conseguiu mais que 0,8 nesta. Valia 1,0.
lg*lg^2 n vs. lg^2 lg*n: aqui o principal era reconhecer que lg*lg x = lg*x - 1, e quem mencionou isto já ganhou 0,5. A outra parte era usar isto para resolver a questão, e nesta parte os alunos obtiveram notas variadas entre 0,0 e 0,5.
9^lg n vs. n^3 n^(1/3): aqui o principal era reconhecer que esta questão recai numa comparação numérica entre lg 9 e 10/3, ou equivalente. Quem chegou a algo assim já ganhou 0,3. Os outros 0,2 foram para quem consegiu resolver esta relação numérica de forma correta sem apelar para chutes ou calculadoras. Os alunos obtiveram de 0,0 a 0,1 nesta segunda parte, pois ninguém conseguiu descrever claramente como chegou a um resultado correto.
Nesta questão simplesmente contaram-se os quadrinhos corretos e multiplicou-se por 0,1. Alguns quadrinhos tinham mais de uma resposta correta. Por exemplo, no heap sort aceitou-se tanto n como n lg n no melhor caso de comparações e de trocas. pois pode haver mais de uma interpretação do que seria o melhor caso: todos iguais ou decrescente.
© 2010 João Meidanis