Primeiro vamos entender de onde veio o termo "otimização prematura:
Premature optimization is the root of all evil -- Donald Knuth
Você pode ver a citação na Wikiquote (e veja que a origem é na verdade do Tony Hoare).
Eu vou dizer que citação pela metade é a raiz de todo o mal :P
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil
Veja o artigo na na Wikipedia sobre otimização.
Otimização prematura significa apenas que você não deve perseguir pequenos ganhos e principalmente ganhos incertos. E ganhos incertos é o que mais existe. As pessoas supõem algum comportamento e programam em cima desta suposição. O que você está otimizando possivelmente está criando um gargalo em outro lugar onde a otimização seria mais útil.
De acordo com a citação, 3% do tempo você deve otimizar (mesmo para pequenos ganhos). Ok, este número pode ser meio chutado, mas convenhamos que não é um número desprezível. Se a otimização é necessária, ela deve ser feita. E feita por quem sabe como alcançar o resultado desejado. Você pode gastar tempo otimizando código, pode deixar o código complexo para obter os ganhos de performance, desde que sejam absolutamente necessários.
A preocupação com o exagero na tentativa de otimização é mais com a ineficácia da ação do que com a produtividade, embora esta possa ser uma preocupação legítima também. Está relacionado um pouco a não tornar o código complexo e "sujo" desnecessariamente, mas porque isto pode se voltar contra o objetivo.
A parte ruim desta citação é que ela acabou por se transformar em "nunca otimize" e vemos softwares sem nenhuma preocupação com performance.
Os erros cometidos
Design correto é útil e importante
Muitos programadores não se preocupam em aprender sequer a identificar complexidade de algoritmo e entender a Big O notation (tabela de complexidades) e criam rotinas exponenciais por acidente ou abusam dos algoritmos lineares quando um logaritmo ou constante são facilmente obtidos. Ou ainda não entendem que constante O(1) nem sempre significa mais rápido. Muitas vezes o programador até sabe um pouco sobre o assunto mas faz suposições que se mostram falsas na prática. Um dos perigos de entender muito deste assunto (claro que a solução não é ignorá-los) é se apaixonar pela teoria. E é nesta hora que a otimização prematura ocorrerá. Falo mais deste assunto nessa resposta.
É importante entender o problema e dar soluções reais de otimização onde é necessário o mais cedo possível quando você sabe com base em dados realistas que ela será necessária. Só a experiência qualificada permite fazer isto com competência. Mesmo assim é algo difícil, mesmo os melhores programadores vão ter dificuldade em identificar os gargalos cedo. Então a estratégia é não se apegar à otimização como se ela fosse a coisa mais importante a fazer. Entender que em determinado momento é melhor deixar para depois e deixar possibilidades que permitam e facilitam isto. É necessário evitar um design que dificulte a otimização posterior. Mas tenha em mente que resolver problema de performance depois é mais difícil do que resolver antes.
Outro erro comum que não deixa de ser de design é na escolha da linguagem ou tecnologia adotada. Na maioria das vezes isto não importa para a performance mas há casos que a escolha correta é fundamental. Achar que fazer em Assembly garante o melhor resultado é tão bobo quanto achar que tudo pode ser feito em Ruby impunemente.
O design envolve a parte estratégica e tática da aplicação. Envolve a arquitetura, escolha das tecnologias, estruturas de dados e algoritmos utilizados.
Não estamos mais evoluindo em poder computacional do processador como ocorria antes. Não podemos mais contar que a evolução consertará certos problemas de performance.
Gastar o tempo do usuário normalmente custa mais que o gasto adicional para fazer boas otimizações. Ter um produto com performance ruim é mais caro que desenvolver a otimização. Performance é feature e não bug. Parece óbvio mas muitos programadores aprenderam que otimizar é criar código errado, bugado.
Micro-otimização é ruim.
Nas outras respostas fica bem óbvio onde não se deve otimizar: não faça micro-otimizações. Muitas vezes isto é usado como desculpa para não otimizar onde deve. Elas podem ser feitas se forem necessárias, obtenham ganhos mensurados e não prejudiquem o código.
Isso não significa optar por qualquer forma. Se você tem duas formas "limpas" de fazer, não há desvantagens, e uma delas é realmente mais rápida que a outra, não existe razão para optar pela mais lenta.
Um dos erros que vejo nestas avaliações é que o programador não se preocupa com um ganho pequeno em um método inofensivo, e em geral não é para se preocupar exageradamente mesmo, mas ele esquece que este método será usado em um algoritmo com um problema exponencial que executará trilhões de vezes. Avaliou bem o micro e esqueceu do macro. Neste caso a solução macro passa pela solução micro. Pequenas otimizações são muito úteis quando se sabe onde e porquê.
Na maioria das vezes uma micro-otimização deve vir depois da verificação e avaliação correta que ela é necessária. Esta é a parte operacional do desenvolvimento.
Reinventar a roda costuma ser micro-otimização. A não ser quando não é :)
Conclusão
Preocupar-se com otimização é algo bom, até mesmo a otimização antecipada. Preocupar-se exageradamente, ficar obcecado, não saber onde otimizar, onde investir seu tempo, não saber priorizar, não entender o problema, não ter comprometimento é algo ruim.
Falta conhecimento aos programadores para evitar que as otimizações venham por acidente, assim como uma otimização teórica se transforme em prejuízo.
Otimização esperada é diferente de otimização prematura. Se todo mundo entende uma construção otimizada (com resultados reais) isto não pode ser considerado otimização prematura. Há muito preciosismo nestes discursos pró código limpo (não entenda errado, código limpo é algo bom, faço isto antes de existirem livros sobre o assunto).
Fontes:
- THE FALLACY OF PREMATURE OPTIMIZATION (é realmente um texto muito bom que eu concordo 100%)
- The ‘premature optimization is evil’ myth