Em informática, um argumento comumente usado por defensores de linguagens interpretadas (mais lentas), é: "se seu programa é lento, troque de algoritmo, não de linguagem!". Às vezes isso é válido, às vezes não, vai depender do algoritmo em uso.
Por incrível que pareça, a definição de algoritmo não é perfeitamente definida. classicamente é uma sequência bem-definida de operações elementares, que pode ser realizado por uma máquina. Muito bem, mas definir o que é "bem-definido" e "elementar" ainda está por ser feito :) O mais próximo de uma máquina elementar teórica é a Máquina de Turing. Nenhuma outra máquina ou computador é mais poderoso que a máquina de Turing, no sentido de que poderia resolver algoritmos "mais avançados".
A complexidade, ou eficiência, de um algoritmo qualquer, é costumeiramente fornecida como "big O", ou "grande O". A idéia do "grande O" é a seguinte: dar uma noção aproximada da complexidade do algoritmo, proporcionalmente ao número de elementos que ele vai manipular.
Pegando um exemplo, a rotina Bubble Sort, que ordena uma matriz, expressa em linguagem Python:
n = len(matrix) for x in range(0, n): for y in range(x, n)): if matrix[x] > matrix[y] # ok, sei que tem jeito mais eficiente de swapar temp = matrix[x] matrix[x] = matrix[y] matrix[y] = temp
Esse algoritmo funciona perfeitamente, apesar de ficar lento para grandes matrizes. O número necessário de comparações para fazer a ordenação é n + n-1 + n-2 + ... 1, o que dá n(n-1)/2, ou seja, 0.5 n**2 - 0.5 n - um polinômio do 2o grau. O número de comparações cresce quadraticamente em função do tamanho da matrix; é isso que torna-o lento.
ERRATA: Conforme o andrunko me apontou, a maioria dos livros sobre algoritmos executa o bubble sort de forma um pouco diferente, com o loop externo andando a matriz do fim para o início. Da forma como está o algoritmo acima, ele pode ser confundido com o Selection sort. Mas pode crer que é Bubble Sort :)
Na notação "grande O", o algoritmo tem complexidade O(n**2); os monômios de ordem inferior, bem como as constantes, são desprezados no grande O.
Isso não torna automaticamente o Bubble Sort um algoritmo ruim. Ele fica ruim na medida que sabemos que outros algoritmos têm complexidades menores:
Shell Sort: O(n**1.2) QuickSort: O(n log n)
Dentre os algoritmos disponíveis, é natural escolhamos aquele com menor complexidade "grande O", pois será o mais rápido. Dificilmente haverá alguma razão que nos faça escolher voluntariamente um algoritmo pior.
No caso específico de ordenação, alguns algoritmos "ruins" têm comportamento excelente quando lidam com matrizes "quase" ordenadas; nesse caso talvez pudéssemos, relutantemente, escolher tal algoritmo.
Supondo agora que não houvesse outro algoritmo de ordenação fora o Bubble Sort, e uma determinada implementação fosse lenta (digamos, por ser feita em Python). Neste caso a única solução seria reimplementar em C ou assembler. Isto não muda o "grande O" do algoritmo, mas empurra o problema um pouco para a direita: n**2 passa a ser, digamos, (0,1 n)**2.
A maioria dos algoritmos ótimos para cada problema tem complexidade abaixo da quadrática: O(n log n), O(n), O(log n), e os melhores de todos, O(1), que significa "tempo constante".
Em muitos programas, não é factível usar linguagem interpretada em lugar de compilada simplesmente porque ele executa uma série imutável de passos, ou seja, O(1), e o único jeito do programa ser rápido, é executando mais rapidamente cada passo individual.
No entanto, os computadores estão ficando sempre mais rápidos, de modo que já um grande número de tarefas O(1) executam com desempenho tão satisfatório em C quanto Java, Python...
Existem problemas cujos algoritmos ótimos são teimosamente irredutíveis, e ficam na casa do O(n**2), O(n**3), ou mesmo O(n**5). Quando o "grande O" do algoritmo é polimonial, como esses que citei, apesar de tudo o problema que o algoritmo resolve, é considerado TRATÁVEL.
Por outro lado, quando o "grande O" de um problema é exponencial, por exemplo O(2**n), ou seja, "n" vai para o lado do expoente, tal problema é considerado INTRATÁVEL, pois nenhum computador resolve-o num tempo satisfatório, a não ser que o número "n" seja ridiculamente baixo.
Os problemas tratáveis também são comumente denominados "P" (Polinomiais), enquanto os intratáveis são denominados "NP" (Não-Polinomiais).
Apesar de tanto o conjunto de problemas P quanto os NP serem, a rigor, infinitos, o número de problemas NP é muito maior que o número de problemas P. Ou seja, o infinito-NP é "maior" que o infinito-P. Isso soa meio estranho, mas é matematicamente provado. Essa mesma diferença de cardinalidade entre "infinitos" ocorre entre números inteiros e números reais - ambos são infinitos, mas há "mais" números reais.
Dentre os problemas NP, existe um conjunto especial, denominado NP-completo. Essa expressão deve soar familiar a quem trabalha com informática, mesmo que não tenha formação na área. Mas muitos confundem NP com NP-completo, achando que é a mesma coisa. Não é.
A definição de problema NP-completo é meio estranha. Um problema é NP-completo se ele puder ser provado igual aos demais problemas NP-completos já conhecidos :) Parece uma definição recursiva... E quem definiu o *primeiro* problema NP-completo, afinal? Bem, os problemas NP-completos compartilham de algumas características peculiares:
1) O algoritmo que acha a solução ideal é Não-Polinomial, portanto intratável;
2) São problemas onde soluções não ideais (sub-ótimas) costumam ser úteis;
3) Tais soluções não-ideais, mas ainda assim úteis, podem ser achadas por algoritmos Polinomiais, ou por tentativa e erro (tentativas aleatórias), ou uma mistura das duas técnicas.
Exemplos clássicos de problemas NP-completos:
1) Caixeiro viajante. Um vendedor precisa visitar todas as cidades de uma região. Baseando-se nas distâncias entre cada cidade e suas vizinhas, determinar a rota de menor distância.
2) Grade de aulas. Dado um número de professores, aulas e turmas, e que cada professor tem limitações (um joga futebol na terça, outro viaja na sexta, etc.), gerar a grade de aulas de uma escola, ou avisar que é impossível.
3) Mochileiro: Um mochileiro pode carregar no máximo um certo peso. Há diversos pacotes, com pesos diferentes e conhecidos. Escolher o conjunto de pacotes que aproxime o peso máximo permitido.
Note que, apesar de serem problemas NP, ainda assim os vendedores não deixam de viajar, e as escolas não deixam de criar as grades :) Possivelmente uns e outros usam soluções sub-ótimas, mas "suficientes" para tocar o barco.
Se subtrairmos do conjunto NP os problemas NP-completos, sobram os problemas NP-difíceis. Nestes, não há algoritmos P nem mesmo para achar soluções sub-ótimas.
Um problema NP-difícil é otimização puramente relacional de consultas SQL; não é tratável, e não vai adiantar ficar tentando diferentes soluções para ver qual é menos pior.
Isso pode ter sido uma surpresa desagradável para muitos, mas (felizmente), na prática dos SGBDs, uma série de truques é utilizada para fugir desse problema NP-difícil.
Em primeiro lugar, o modelo puramente relacional pressupõe que o otimizador tenha de descobrir *tudo* sobre as tabelas sozinho: inclusive qual campo é a chave primária, baseando-se na cardinalidade do campo. Num banco de dados "normal", os campos que são chaves primárias ou chaves estrangeiras são explicitamente nomeados, o que facilita o trabalho do otimizador. E apenas os campos com índices têm sua cardinalidade calculada, o que restringe os campos a serem levados em conta no processo de otimização. Isto é suficiente para que o problema da otimização volte a ser tratável.
(Em tempo: cardinalidade, ou melhor, grau de cardinalidade, éo grau de univocidade dos valores de um campo, ou seja, o quanto eles variam para cada registro. Por exemplo, CPF tem cardinalidade muito alta, éem geral diferente para cada registro, o que inclusive sugere seu uso para chave primária. Já um campo "masculino/feminino" tem baixa cardinalidade pois seu campo é de apenas 2 valores. Um campo como CEP tem cardinalidade intermediária.
Ainda assim, um otimizador pode demorar para resolver uma consulta com grande número de tabelas, correndo ainda o risco de sair com uma solução ruim. Para resolver esse problema, os próprios usuários podem dar "dicas" explícitas ao otimizador. A linguagem SQL tem algumas provisões para isso, que ainda por cima costumam ser estendidas em cada SGBD.
Apenas um banco de dados patologicamente mal arquitetado poderia tornar novamente intratável a otimização: usando-se inúmeras tabelas pequenas (para aumentar o número de elementos a serem levados em conta, e portanto o número "n"), criando índices para todos os campos (sobrecarregando o otimizador com informações de cardinalidade dos campos), e não indicando que campos são as chaves (forçando o otimizador a efetivamente escolher o campo com base nas cardinalidades).