MAC5711 - Análise de Algoritmos

Um exercício interessante para o consumo de tempo médio do Quicksort (slide 120) sería:

Dada a recorrência T( n ) = T(an) + T(bn) + n, com T(1) =1, 0<a,b<1, onde a+b=1. Mostrar que T( n ) = O(n lg n).

Um resultado bem conhecido é para a=b=1/2.

Alguém recomenda algum livro além do Cormen, preferencialmente com bastante exemplos, que dê uma heurística de como adivinhar a solução das recorrências? O assunto ainda está não-determinístico demais para mim.

Pessoal, eu estou interessado na aula extra sugerida pelo Professor.

Quem mais está interessado?

Professor, haveria alguma sugestão sua de um horário melhor (que não atrapalhe suas outras atividades)?

Se você resolveu um exercício com base em dicas e informações obtidas em algum livro, revista, ou página na internet, você deve citar essas fontes!

É obrigatório dar o nome do autor do livro ou artigo, o título da obra, o número da página, a URL na internet, etc.  Se sua solução foi baseada em uma discussão com outra pessoa, dê o nome dessa pessoa!

Atualizei as páginas "Ordens O, Omega e Theta" e "Recorrências" do sítio http://www.ime.usp.br/~pf/analise_de_algoritmos.

Inscreva-se em AA-2008-1 para participar do fórum.

Use o fórum para fazer perguntas, discutir dúvidas, dar dicas e trocas idéias.