Para todo o problema há uma solução, não é o que se diz? Assim sendo, porquê preocuparmo-nos tanto? Existem até, em muitos casos, várias soluções para o mesmo problema. E para esses casos será acertado dizermos: para toda a solução há um problema. Vendo as coisas desta maneira, diria que quanto mais soluções existirem, mais difícil é resolver o problema, afinal, qual a melhor solução a escolher?
Um caso tão geral como o anterior que podemos particularizar para o mundo da programação e da algoritmia. São diversos os problemas com que nos deparamos e também várias as maneiras que temos de os resolver. Se pretendemos pesquisar informação o que será melhor, sequential search, binary search ou outro? E se quisermos calcular o caminho mais curto entre dois pontos, será mais vantajoso recorrer ao algoritmo de Djikstra ou ao algoritmo de Bellman-Ford?
Porquê que é que existem tantos algoritmos para um mesmo problema, porque não definir um algoritmo padrão e aplicar sempre o mesmo? Acontece que na área da informática (e não só, mas é o que nos interessa aqui) a performance é muito importante, e bons programadores e engenheiros não se preocupam apenas com a validade de um algoritmo, mas também a sua rapidez de execução e a sua eficiência na utilização dos recursos do computador. Assim sendo, a eficiência de um algoritmo deve ser medida tanto em termos temporais como em termos espaciais. Posto tudo isto, podemos definir a complexidade de um algoritmo como a medida de tempo - complexidade temporal - ou espaço em memória - complexidade espacial - requerida pelo algoritmo em questão para um input de tamanho (n).
The Big O Notation
Uma boa questão que poderíamos colocar por esta altura: será a medida do tempo de execução uma das variáveis mais importantes a ter em conta aquando da escolha do algoritmo, estando ele tão dependente de factores externos? Sim, é verdade, o tempo de execução de um algoritmo para o mesmo input de tamanho (n) depende não só da estrutura do código mas também da rapidez do processador, da rapidez do disco, o tipo de compilador, etc. Desse modo, deve-se estimar a eficiência de um algoritmo assimptoticamente, medindo o tempo T(n) como o número de passos elementares realizados, onde cada passo leva um tempo constante a correr. FIX ME!
A complexidade de um algoritmo passa agora a ser expressa pela notação O-grande (big O notation), uma medida da ordem de grandeza da função para inputs grandes ( (n) grande, daí ser assimptótico ).
Por ser uma notação que lida com n grande (assimptótica), a complexidade de uma função O(n + c), onde c é uma constante, é a mesma que O(n), pois considera-se o termo da função que mais rapidamente cresce, isto é, o que tem a maior ordem de grandeza). Pela mesma razão se considera O(cn) igual a O(n); ambas possuem o mesmo ritmo de crescimento e para n infinitamente grande terão a mesma ordem de grandeza.
No gráfico abaixo representado encontram-se traçadas as principais ordens de complexidade algorítmica de onde podemos discernir claramente a taxa de crescimento de cada uma.
Definição
f(n) é O(g(n)) se existirem valores c e N0 tais que f(n)≤cg(n) para todo o n≥N0
Intuitivamente, a função f(n) não cresce mais que a função cg(n), com c > 0, a partir de um dado valor N0 > 0, para um n a tender para o infinitamente grande. Graficamente:
Melhor Caso, Pior Caso e Caso Médio
Voltando a olhar para os exemplos apresentados acima sobre análise de complexidade podemos perguntar-nos: e se não forem percorridas n iterações (por exemplo, pela existência de uma condição que o justifique)? A complexidade passaria a ser outra diferente? Por norma a complexidade de um algoritmo é referente ao seu pior caso (worst case) - quando o algoritmo tem de fazer o maior número de operações possível -, mas pode ser útil conhecer os seus comportamentos e complexidade para casos mais simples.
Temos exactamente o oposto, isto é, quando o algoritmo tem de fazer o mínimo de operações, que é chamado o melhor caso(best case). Acontece, por exemplo, quando queremos pesquisar a ocorrência de um número num dado input e ele ser logo o primeiro elemento.
No meio temos ainda o caso médio(average case), onde o número de operações difere para cada execução. É por isso o mais difícil de determinar dos três casos por estar dependente de uma maior quantidade de testes e de uma posterior análise estatística para determinar o número médio de operações efectuadas pelo algoritmo.
Um Caso Prático
Vamos pegar numa operação tão comum como o ordenamento de dados, utilizando um dos algoritmos mais simples de implementar, o Insertion Sort, para ilustrar como cada tipo de input influencia o tempo de execução e a correspondente complexidade para cada caso.
Foram usados inputs de 100 000 elementos e os resultados, em milissegundos, estão apresentados na tabela abaixo; o melhor caso corresponde a um array ordenado, o pior caso a um array ordenado ao contrário (do maior para o menor) e o caso médio à média de vários arrays com os elementos aleatórios.
Para os mesmos inputs corremos o algoritmo de ordenamento QuickSort, e estes foram os resultados:
Através desta análise experimental mostramos que não podemos só depender da complexidade O(n) de um algoritmo para determinar se é o melhor a usar ou não. Apesar do Quicksort apresentar uma complexidade O(nlog(n)), inferior à O(n2) do Insertion, vimos que claramente há situações específicas em que o Insertion seria uma melhor aposta. É por estas mesmas razões que várias optimizações de algoritmos consistem em utilizar um algoritmo auxiliar quando detectamos que o input é de um determinado tipo mais favorável a esse mesmo auxiliar.
Se achas que percebeste, não terás problemas em descobrir a complexidade nos seguintes casos:
Um caso tão geral como o anterior que podemos particularizar para o mundo da programação e da algoritmia. São diversos os problemas com que nos deparamos e também várias as maneiras que temos de os resolver. Se pretendemos pesquisar informação o que será melhor, sequential search, binary search ou outro? E se quisermos calcular o caminho mais curto entre dois pontos, será mais vantajoso recorrer ao algoritmo de Djikstra ou ao algoritmo de Bellman-Ford?
Porquê que é que existem tantos algoritmos para um mesmo problema, porque não definir um algoritmo padrão e aplicar sempre o mesmo? Acontece que na área da informática (e não só, mas é o que nos interessa aqui) a performance é muito importante, e bons programadores e engenheiros não se preocupam apenas com a validade de um algoritmo, mas também a sua rapidez de execução e a sua eficiência na utilização dos recursos do computador. Assim sendo, a eficiência de um algoritmo deve ser medida tanto em termos temporais como em termos espaciais. Posto tudo isto, podemos definir a complexidade de um algoritmo como a medida de tempo - complexidade temporal - ou espaço em memória - complexidade espacial - requerida pelo algoritmo em questão para um input de tamanho (n).
The Big O Notation
Uma boa questão que poderíamos colocar por esta altura: será a medida do tempo de execução uma das variáveis mais importantes a ter em conta aquando da escolha do algoritmo, estando ele tão dependente de factores externos? Sim, é verdade, o tempo de execução de um algoritmo para o mesmo input de tamanho (n) depende não só da estrutura do código mas também da rapidez do processador, da rapidez do disco, o tipo de compilador, etc. Desse modo, deve-se estimar a eficiência de um algoritmo assimptoticamente, medindo o tempo T(n) como o número de passos elementares realizados, onde cada passo leva um tempo constante a correr. FIX ME!
A complexidade de um algoritmo passa agora a ser expressa pela notação O-grande (big O notation), uma medida da ordem de grandeza da função para inputs grandes ( (n) grande, daí ser assimptótico ).
Por ser uma notação que lida com n grande (assimptótica), a complexidade de uma função O(n + c), onde c é uma constante, é a mesma que O(n), pois considera-se o termo da função que mais rapidamente cresce, isto é, o que tem a maior ordem de grandeza). Pela mesma razão se considera O(cn) igual a O(n); ambas possuem o mesmo ritmo de crescimento e para n infinitamente grande terão a mesma ordem de grandeza.
No gráfico abaixo representado encontram-se traçadas as principais ordens de complexidade algorítmica de onde podemos discernir claramente a taxa de crescimento de cada uma.
Definição
f(n) é O(g(n)) se existirem valores c e N0 tais que f(n)≤cg(n) para todo o n≥N0
Intuitivamente, a função f(n) não cresce mais que a função cg(n), com c > 0, a partir de um dado valor N0 > 0, para um n a tender para o infinitamente grande. Graficamente:
Melhor Caso, Pior Caso e Caso Médio
Voltando a olhar para os exemplos apresentados acima sobre análise de complexidade podemos perguntar-nos: e se não forem percorridas n iterações (por exemplo, pela existência de uma condição que o justifique)? A complexidade passaria a ser outra diferente? Por norma a complexidade de um algoritmo é referente ao seu pior caso (worst case) - quando o algoritmo tem de fazer o maior número de operações possível -, mas pode ser útil conhecer os seus comportamentos e complexidade para casos mais simples.
Temos exactamente o oposto, isto é, quando o algoritmo tem de fazer o mínimo de operações, que é chamado o melhor caso(best case). Acontece, por exemplo, quando queremos pesquisar a ocorrência de um número num dado input e ele ser logo o primeiro elemento.
No meio temos ainda o caso médio(average case), onde o número de operações difere para cada execução. É por isso o mais difícil de determinar dos três casos por estar dependente de uma maior quantidade de testes e de uma posterior análise estatística para determinar o número médio de operações efectuadas pelo algoritmo.
Um Caso Prático
Vamos pegar numa operação tão comum como o ordenamento de dados, utilizando um dos algoritmos mais simples de implementar, o Insertion Sort, para ilustrar como cada tipo de input influencia o tempo de execução e a correspondente complexidade para cada caso.
Foram usados inputs de 100 000 elementos e os resultados, em milissegundos, estão apresentados na tabela abaixo; o melhor caso corresponde a um array ordenado, o pior caso a um array ordenado ao contrário (do maior para o menor) e o caso médio à média de vários arrays com os elementos aleatórios.
Através desta análise experimental mostramos que não podemos só depender da complexidade O(n) de um algoritmo para determinar se é o melhor a usar ou não. Apesar do Quicksort apresentar uma complexidade O(nlog(n)), inferior à O(n2) do Insertion, vimos que claramente há situações específicas em que o Insertion seria uma melhor aposta. É por estas mesmas razões que várias optimizações de algoritmos consistem em utilizar um algoritmo auxiliar quando detectamos que o input é de um determinado tipo mais favorável a esse mesmo auxiliar.
Teste
