Question

Como podemos modificar quase que qualquer algoritmo para ter um bom tempo de execução para o melhor caso

Answer 1

Boa pergunta.

Algoritmos tem algo de jogada em jogo de xadrez. Meu pai sempre dizia "quando você bolar uma boa jogada, procure um pouco mais pois tem outra melhor"

A mesma coisa com algoritmos. Quando você bola um algoritmo que é eficiente, esforce-se um pouco mais e encontrará uma forma de torná-lo ainda melhor.

O que fazer para melhorar um algoritmo ? Primeiro, pense no problema de forma matemática, utilizando lógica booleana, álgebra de conjuntos. Sim, se você analisar bem vai chegar a conclusão que um algoritmo na verdade é uma função que recebe um conjunto de dados e produz outro conjunto de dados. Na essência, um programa é isso.

Podemos então otimizar laços de repetiçao, armazenamento de dados usando tipos de dados que ocupam menos memória e portanto são mais rápidos. Podemos fazer uma conta que equivale a uma iteração, por exemplo:
Some os números pares de 1 até 100
Podemos fazer um loop de 1 até 100 e testar para cada número se é par. Se for, somamos ele.
ou ... 
podemos fazer o cálculo direto da soma dos 50 primeiros termos de uma progressão aritmética de razão 2 com termo inicial 2. Calcula direto e é infinitamente mais rápido.

Por isso que é bom pensar.