Complexidade e vida real

(Atualizado em: 13 de outubro de 2016)

Sempre tive dificuldade de explicar para meus alunos de Classificação e Pesquisa de Dados a grande diferença entre a complexidade de um algoritmo e os problemas das implementações reais. No terceiro semestre a troca de contexto tratando o mesmo problema não parece evidente.  Estava lendo a Communications of the ACM quando encontrei um artigo muito bom para resolver meu problema 10 Optimizations on Linear Search Thomas A. Limoncelli, Communications of the ACM, Vol. 59 No. 9, Pages 44-48, DOI 10.1145/2980976. Em um texto bem humorado o autor começa com um problema trivial e desenvolve uma análise muito didática sobre a diferença entre a complexidade de um algoritmo em memória e a vida real em um ambiente de produção. Vale a pena a leitura!