Ferramentas de Site


algoritmo:complexo

Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

Links para esta vista de comparação

Ambos os lados da revisão anterior Revisão anterior
Próxima revisão
Revisão anterior
algoritmo:complexo [2007/09/28 00:14]
pedrotuga
algoritmo:complexo [2018/05/14 21:37] (Atual)
Linha 1: Linha 1:
-FIXME Passar as expressões matematicas para mathML e escapar alguns caracteres. O texto em si não precisa de ser revisto. 
- 
 ====== Noções elementares de complexidade computacional ====== ====== Noções elementares de complexidade computacional ======
  
 +A complexidade computacional é uma ferramenta teórica para medir a velocidade de um algoritmo.
  
-A complexidade computacional é uma ferramenta teórica para medir a velocidade de um [[http://wiki.portugal-a-programar.org/index.php?title=Algoritmia|algoritmo]]. +Muitas vezes como programadores costumamos dizer que um dado algoritmo é "pesado", ou lento. O que vou explicar aqui pretende dar uma ideia de como se pode matematicamente classificar a velocidade de um algoritmo, isto pode parecer inútil mas é na verdade extremamente importante quando quisermos fazer qualquer aplicação onde a eficiência e a rapidez sejam importantes, visto que nesta situação temos de saber escolher o algoritmo correcto de entre as várias opções.
-Muitas vezes como programadores costumamos dizer que um dado algoritmo é "pesado", ou lento. O que vou explicar aqui pretende dar uma ideia de como se pode matemáticamente classificar a velocidade de um algoritmo, isto pode parecer inútil mas é na verdade extremamente importante quando quisermos fazer qualquer aplicação onde a eficiência e a rapidez sejam importantes, visto que nesta situação temos de saber escolher o algoritmo correcto de entre as várias opções.+
  
- +Consideremos por exemplo um algoritmo de ordenação simples como o //Selectionsort//. Quão rápido é este algoritmo? É mais rápido ou mais lento que o //Heapsort// (por exemplo)?
-Consideremos por exemplo um algoritmo de ordenação simples como o selection sort. Quão rápido é este algoritmo? É mais rápido ou mais lento que o //heapsort// (por exemplo)?+
  
 Certamente alguns dirão que isso depende da velocidade dos computadores se os algoritmos forem testados em máquinas diferentes, outros dirão que depende de quantos programas estavam a correr concorrentemente. Tudo isso é verdade, porém a complexidade computacional permite classificar um algoritmo independentemente destes factores. Como? Certamente alguns dirão que isso depende da velocidade dos computadores se os algoritmos forem testados em máquinas diferentes, outros dirão que depende de quantos programas estavam a correr concorrentemente. Tudo isso é verdade, porém a complexidade computacional permite classificar um algoritmo independentemente destes factores. Como?
  
- +Olhemos para o código do simplista //Selectionsort// (aqui apresentado em pseudo-código estilo C): 
-Olhemos para o código do simplista **Selection Sort** (aqui apresentado em pseudo-código estilo C): +<code c> 
- +funcao seleciontSort(int[[]] a, int ultimoElemento) { 
- funcao seleciontSort(int[[]] a,int ultimoElemento){ +    int posicaoMinimo; 
-  int posicaoMinimo; +    int minimo; 
-  int minimo; +    int iterador; 
-  int iterador; +    int novaPosMinimo=0; 
-  int novaPosMinimo=0; +    for ( ; novaPosMinimo < ultimoElemento; novaPosMinimo++) { 
-  for( ; novaPosMinimo<ultimoElemento; novaPosMinimo++){ +        minimo=a[[novaPosMinimo]]; 
-  minimo=a[[novaPosMinimo]]; +        posicaoMinimo=novaPosMinimo; 
-  posicaoMinimo=novaPosMinimo; +        for ( iterador = novaPosMinimo + 1; iterador < ultimoElemento; iterador++) { //Percorrer o array todo à procura do mínimo 
-  for( iterador=novaPosMinimo+1 ; iterador<ultimoElemento ; iterador++){   //Percorrer o array todo à procura do mínimo +            if( a[[iterador]] < minimo) { //Se este elemento for mais pequeno que o mínimo 
-  if( a[[iterador]] < minimo){ //Se este elemento for mais pequeno que o mínimo  +                posicaoMinimo = iterador; //já encontrado, entao este passa a ser o mínimo. 
-  posicaoMinimo=iterador; //já encontrado, entao este passa a ser o mínimo. +                minimo=a[[iterador]]; 
-  minimo=a[[iterador]]; +            
-  }  +        } 
-  //já percorremos o array todo e já sabemos qual é o mínimo +             
-  //logo, metemo-lo na posicao 0 do array, ie, a primeira posicao do array +        //já percorremos o array todo e já sabemos qual é o mínimo 
-  //e metemos o que estava na posicao 0 na antiga posicao do minimo+        //logo, metemo-lo na posição 0 do array, ie, a primeira posição do array 
-  temp = a[[posicaoMinimo]]; +        //e metemos o que estava na posição 0 na antiga posição do mínimo
-  a[[novaPosMinimo]] = minimo; +        temp = a[[posicaoMinimo]]; 
-  a[[posicaoMinimo]]= temp; +        a[[novaPosMinimo]] = minimo; 
-  +        a[[posicaoMinimo]]= temp; 
- } +    
 +
 +</code>
  
 Este algoritmo funciona da seguinte maneira: Este algoritmo funciona da seguinte maneira:
  
-Percorrer o array todo á procura do mais pequeno elemento  de todos.+<code> 
 +Percorrer o //array// todo á procura do mais pequeno elemento  de todos.
 Trocar esse elemento com o que está na primeira posição do array. Trocar esse elemento com o que está na primeira posição do array.
-Percorrer o array todo (excepto o primeiro valor) á procura do elemento mais pequeno de todos. (estamos na realidade a    procurar o 2º mais pequeno)+Percorrer o //array// todo (excepto o primeiro valor) á procura do elemento mais pequeno de todos. 
 +(estamos na realidade a procurar o 2º mais pequeno)
 Trocar esse elemento com o que está na segunda posição do array. Trocar esse elemento com o que está na segunda posição do array.
- +E assim sucessivamente até só termos de percorrer o último elemento do array. 
-etc.. até só termos de percorrer o último elemento do array.+</code>
  
 Como foi visto este algoritmo é trivialmente implementado usando um ciclo e umas variáveis de controlo. Como foi visto este algoritmo é trivialmente implementado usando um ciclo e umas variáveis de controlo.
- 
  
 Agora a grande questão: Como podemos medir a velocidade deste algoritmo? Agora a grande questão: Como podemos medir a velocidade deste algoritmo?
  
 A maneira mais simples de fazer tal cálculo é contar o número de elementos que o algoritmo compara. A maneira mais simples de fazer tal cálculo é contar o número de elementos que o algoritmo compara.
-Vamos fazer isso (consideremos que o array tem N elementos): +Vamos fazer isso (consideremos que o //array// tem N elementos): 
-* Na 1ª iteração comparamos N elementos. +  * Na 1ª iteração comparamos N elementos. 
-* Na 2ª iteração comparamos (N-1) elementos +  * Na 2ª iteração comparamos (N-1) elementos 
-* Na 3ª iteração comparamos (N-2) elementos +  * Na 3ª iteração comparamos (N-2) elementos 
-* ... +  * ... 
-* Na (N-1)ª iteração comparamos apenas 1 elemento.+  * Na (N-1)ª iteração comparamos apenas 1 elemento.
  
 +Se somarmos tudo temos <m>N + (N-1) + (N-2) + ... + 1</m> que segundo uma fórmula dá <m>(N+1)*N/2 = (1/2)*N^2*N</m>, mas como estamos a fazer uma análise no limite, podemos esquecer o facto de <m>N^2</m> estar multiplicado por <m>(1/2)*N</m>, de facto, se o resultado desse uma expressão com várias parcelas em //N//, apenas interessaria a parcela mais "forte".
  
-Se somarmos tudo temos N + (N-1) + (N-2) + .... + 1 que segundo uma fórmula dá (N*1)*N/2 = (1/2)N^2, mas como estamos a fazer uma análise no limite, podemos esquecer facto de N^2 estar multiplicado por 1/2de facto, se resultado desse uma expressão com várias parcelas em N, apenas interessaria parcela mais "forte".+Ou seja, trocado por miúdos, temos que este algoritmo para ordenar um //array// com //N// números tem de "olhar" para <m>N^2</m> númerosisto significa que se tempo de olhar para um número for um dado valor //X//, então para olhar para <m>N^2</m> números eu preciso de <m>X*N^2</m>. Este valor //X// de facto depende da velocidade da máquina em que o algoritmo está a correr e dos recursos disponíveis na alturae ainda temos de considerar tempo de "trocar" os números de sítio mais o tempo de executar o código auxiliar como actualizar as variáveis de controlo etc, no entanto, mesmo que fizessem as contas todas, iam chegar a uma expressão em que só aparecem constantes ou //N//s elevados ao quadrado. Agorasem entrar em grande detalhe matemático olham para expressão e extraem o valor de //N// mais elevado (neste caso como aparece um <m>N^2</m> algures, é esse valor que extraímos) e podemos dizer com toda a exactidão matemática que este algoritmo tem ordem <m>N^2</m> (representa-se <m>O(N^2)</m> ). Isto significa que este algoritmo no limite precisa de um tempo inferior ou igual a <m>N^2</m>.
  
-Ou seja, trocado por miudos temos que este algoritmo para ordenar um array com N números tem de "olhar" para N^2 números, isto significa que se o tempo de olhar para um número for um dado valor X, entao para olhar para N^2 números eu preciso de X*N^2. Este valor X de facto depende da velocidade da máquina em que o algoritmo está correr e dos recursos disponíveis na altura, e ainda temos de considerar o tempo de "trocar" os números de sítio mais o tempo de executar o código auxiliar como actualizar as variáveis de controlo etc, no entanto, mesmo que fizessem as contas todasiam chegar a uma expressão em que só aparecem constantes ou N's elevados ao quadrado. Agora, sem entrar em grande detalhe matemático olham para a expressão e extraem valor de N mais elevado (neste caso como aparece um N^2 algures, é esse valor que extraimose podemos dizer com toda a exactidão matemática que este algoritmo tem ordem N^2 (representa-se O(N^2) ). Isto significa que este algoritmo no limite precisa de um tempo inferior ou igual a N^2.+Agora para que é que toda esta parafernália matemática serve? Para comparar algoritmos! Não vou fazer demonstração porque penso que é desnecessáriamas se vos disser que o //heapsort// tem uma ordem de crescimento (ou complexidade computacional//O(N*lg(N))// conseguem perceber porque é que o //heapsort// é quase sempre mais rápido que o //selection sort//. 
 +Eu disse quase sempre, ele só não é mais rápido quando os //arrays// ordenar são muito pequenos, por exemplo, //N// é muito baixo, tipo 10 números.
  
 +Se mesmo assim não entenderam porque é que o //heapsort// é mais rápido comparem o //selection sort// com um //magic sort// (que não existe) que teria uma ordem //N//. Mesmo que não gostem de matemática penso que é conhecimento comum que //N// cresce mais lentamente para infinito do que <m>N^2</m>, logo este //magic sort// seria mais rápido que o //selection sort//.
  
-Agora para que é que toda esta parafernália matemática serve? Para comparar algoritmos! Não vou fazer a demonstração porque penso que é desnecessária mas se vos disser que o //heapsort// tem uma ordem de crescimento (ou complexidade computacional) O(N*lg(N)) conseguem perceber porque é que o heapsort é quase sempre mais rápido que o //selection sort//. +Para terminar com os algoritmos de ordenação, talvez seja importante saber que é impossível um algoritmo de ordenação baseado em comparações tenha uma ordem menor que <m>N*lg(N)</m>.((http://planetmath.org/encyclopedia/LowerBoundForSorting.html))
-Eu disse quase sempre, ele só não é mais rápido quando os arrays a ordenar são muito pekeninos, ie, N é muito baixo, tipo 10 números.+
  
-Se mesmo assim não entenderam porque o //heapsort// e mais rápido comparem o //selection sort// com um //magic sort// (que não existe) que teria uma ordem N. Mesmo que nao gostem de matemática penso que é conhecimento comum que N cresce mais lentamente para infinito do que N^2... Logo este //magic sort// seria mais rápido que o selection sort. 
- 
- 
-Para terminar com os algoritmos de ordenação, talvez seja importante saber que até à data nunca foi inventado um algoritmo de ordenação baseado em comparações que tenha uma ordem menor que N*lgN , e acredita-se que tal algoritmo não exista. 
 Algoritmos de ordenamento amplamente estudados com esta ordem de crescimento são: Algoritmos de ordenamento amplamente estudados com esta ordem de crescimento são:
-quicksort +  //Quicksort// 
-heapsort +  //Heapsort// 
-mergesort+  //Mergesort//
  
 Outros mais lentos mas possivelmente mais fáceis de implementar são: Outros mais lentos mas possivelmente mais fáceis de implementar são:
-bubblesort +  //Bubblesort// 
-selectionSort +  //Selectionsort//
  
 Para quem é preguiçoso e não quer aprender a fazer tais cálculos apresento de seguida algumas ordens que aparecem muitas vezes em algoritmos e a sua explicação (obviamente quanto mais baixa a ordem melhor): Para quem é preguiçoso e não quer aprender a fazer tais cálculos apresento de seguida algumas ordens que aparecem muitas vezes em algoritmos e a sua explicação (obviamente quanto mais baixa a ordem melhor):
  
-**O(1)**   O algoritmo demora sempre o mesmo tempo independentemente do número de objectos a processar. +  //O(1)// - O algoritmo demora sempre o mesmo tempo independentemente do número de objectos a processar. 
-**O(N)**   O algoritmo demora um tempo proporcional ao número de elementos a processar. +  //O(N)// - O algoritmo demora um tempo proporcional ao número de elementos a processar. 
-**O(N^2)**   alg. demora um tempo proporcional ao quadrado do número de elementos a processar. +  //O(N<sup>2</sup>)// - algoritmo demora um tempo proporcional ao quadrado do número de elementos a processar. 
-* ... +  * ... 
-**O(N!)**   O tempo que o algoritmo demora é proporcional ao factorial do nº de eleemntos a processar. +  //O(N!)// - O tempo que o algoritmo demora é proporcional ao factorial do nº de elementos a processar. 
-**O(N^N)**   Um algoritmo deste tipo é diabólicamente lento,ie, a não ser que o N seja muito pequeno um algoritmo com tal ordem    vai demorar semanas, meses ou anos a terminar. +  //O(N<sup>N</sup>)// - Um algoritmo deste tipo é diabolicamente lento, i.e., a não ser que o //N// seja muito pequeno um algoritmo com tal ordem vai demorar semanas, meses ou anos a terminar.
  
 Esta análise da ordem de crescimento pode ser feita para os 3 casos possíveis: Esta análise da ordem de crescimento pode ser feita para os 3 casos possíveis:
-* O melhor caso possível, +  * O melhor caso possível, 
-* O caso médio, +  * O caso médio, 
-* O pior caso possível.+  * O pior caso possível.
  
-O **melhor caso possível** para um algoritmo de ordenação é quando a rotina já recebe um array ordenado. Pode parecer    estúpido que um algoritmo faça qualquer coisa neste caso, mas por exemplo o selection sort leva o mesmo tempo se    receber um array já ordenado ou não.+O **melhor caso possível** para um algoritmo de ordenação é quando a rotina já recebe um //array// ordenado. Pode parecer estúpido que um algoritmo faça qualquer coisa neste caso, mas por exemplo o //Selectionsort// leva o mesmo tempo se receber um //array// já ordenado ou não.
  
-O **pior caso possível** depende muito do algoritmo, ie, aquele caso específico em que o algoritmo faz muito mais    cálculos.+O **pior caso possível** depende muito do algoritmo, por exemplo, aquele caso específico em que o algoritmo faz muito mais cálculos.
  
-O **caso médio** engloba todos os outros casos, ie, no âmbito dos algoritmos de ordenação é o caso em que ele recebe um    array randomizado.+O **caso médio** engloba todos os outros casos, por exemplo, no âmbito dos algoritmos de ordenação é o caso em que ele recebe um //array// com elementos aleatórios.
  
 No entanto, excepto para situações muito específicas vocês querem comparar algoritmos no caso médio pois é o caso que a vossa aplicação vai encontrar mais vezes (pelo menos teoricamente). No entanto, excepto para situações muito específicas vocês querem comparar algoritmos no caso médio pois é o caso que a vossa aplicação vai encontrar mais vezes (pelo menos teoricamente).
  
 +Esta //teoria// não serve apenas para comparar velocidades mas também por exemplo a memória ocupada pelo algoritmo, e que não se aplica apenas a algoritmos de ordenação, de facto aplica-se a qualquer algoritmo seja ele iterativo ou recursivo.
  
-Esta //teoria// não serve apenas para comparar velocidades mas também por exemplo a memória ocupada pelo algoritmo, e que não se aplica apenas a algoritmos de ordenação, de facto aplica-se a <u>qualquer</u> algoritmo seja ele iterativo ou recursivo.+{{tag>algoritmo}}
algoritmo/complexo.1190938440.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)