O Knuth é um dos mais prolíficos autores do século XX, atuando nas áreas mais diversas. Todo mundo o conhece pelo seu trabalho na computação, mas ele também é matemático, organista e humorista (seu primeiro trabalho publicado foi na revista MAD. Sim, aquela revista MAD). Escolher um dos teoremas do Knuth é difícil, porque ele tem muitos trabalhos memoráveis, mas eu acabei escolhendo o mais seminal deles: o paper "Ordered Hash Tables", publicado pela primeira vez The Computer Journal #17 (1974).
O problema é simples: qual é o tempo médio para inserir um valor em uma hash table (com open addressing)? Pergunte isso para qualquer estudante ingênuo e ele vai te responder que é O(1). Mas essa não é a resposta correta! O tempo O(1) só vale no caso em que o número de inserções é muito menor que a tabela, de modo que não tenham colisões.
Mas, na vida real, colisões acontecem. Essa é a essência do teorema do aniversário: em uma hash table de 365 posições, você tem 50% de chance de ter uma colisão após 23 inserções, e essa chance sobe com o número de inserções.
Então, qual o valor real do tempo médio? Apesar do enunciado ser relativamente simples, por anos ninguém sabia resolver o problema, até o Knuth achou a solução em 1974. O povo se perguntava: como analisar, se eu não sei qual a função de hash que você vai considerar? A resposta do Knuth foi: considere todas ao mesmo tempo! Se a sua tabela tem M posições e você vai fazer N inserções, então existem M^N funções de hash diferentes, e o que o Knuth fez foi calcular a média sobre todas elas.
Se você quiser ver a solução, ela está no Art of Computer Programming vol.3. O Knuth, sempre piadista, deixou a demonstração como exercício para o leitor (LOL). Mas não é complicado, em três páginas de contas você resolve, se tiver paciência e conhecimento de análise combinatória.
O resumo da solução é que o número médio de consultas à tabela de tamanho M após N inserções é:
Esse valor do Knuth é exato, mas não te dá muita intuição sobre o algoritmo. Se você assumir que N é razoalmente menor que M, então tem um assintótico mais simples:
Nesse assintótico fica mais claro. Ele realmente é O(1) na primeira inserção, quando N=0; mas depois esse tempo vai subindo. E no limite, quando a tabela está cheia, é infinito? Nope, esse assintótico só vale quando N<<M; intuitivamente, não tem como ter mais que M-1 colisões numa tabela de tamanho M.
Porém, se você colocar N=M e usar a função Q de Ramanujan (um clássico para quem, como eu, sofreu fazendo o curso de Analytic Combinatorics no coursera), então você consegue o valor limite:
Agora, se alguém perguntar, você pode responder com propriedade: a inserção é O(1) quando a tabela está vazia, e vai crescendo até chegar em O(sqrt(N)) quando a tabela está cheia.
Bônus 1: foto de quando encontrei o Knuth.
Bônus 2: eu e a revista MAD que tem o primeiro artigo do Knuth
Bônus 3: Minha biblioteca de livros do Knuth. Os quatro Art of Computer Programming (sendo que o vol.4 está autografado e com dedicatória!), o Concrete Mathematics (que é o melhor livro de Matemática ever), três fascículos do Art of Computer Programming em japonês (que foram presente do Carlos Duarte Do Nascimento), e quatro volumes da série de Selected Papers (obras super legais que pouca gente conhece).
Bônus 4: se você ficou curioso com a função Q de Ramanujan, então talvez queira ver minha apostila de Analytic Combinatorics. No exercício 4.71 eu resolvi o assintótico da função P de Ramanujan, que é parente da função Q: http://www.ricbit.com/temp/analytic.pdf
Nenhum comentário:
Postar um comentário