Complexidade (informática)
Origem: Wikipédia, a enciclopédia livre.
Índice |
[editar] Definição
A Complexidade de um algoritmo consiste na quantidade de "trabalho" necessária para a sua execução, expressa em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados. É medida segundo um modelo matemático que supõe que este vai trabalhar sobre uma entrada (massa de dados) de tamanho N. O processo de execução de um algoritmo pode ser dividido em etapas elementares denominadas passos (número fixo de operações básicas, tempo constante, operação de maior freqüência chamada dominante). O número de passos de um algoritmo é considerado como o número de execuções da operação dominante em função das entradas, desprezando-se constantes aditivas ou multiplicativas.
[editar] Tipos
- Espacial: Este tipo de complexidade representa o espaço de memória usado para executar o algoritmo, por exemplo.
- Temporal: Este tipo de complexidade é o mais usado podendo dividir-se em dois grupos:
- Tempo (real) necessário à execução do algoritmo.
- Número de instruções necessárias à execução...
[editar] Perspectivas
São usadas três perspectivas no estudo da complexidade algorítmica.
[editar] Veja também
- Lista de termos referentes ao tema
- Análise de Complexidade
[editar] Referências
- Gonçalo Madeira (http://w3.ualg.pt/~hshah/algoritmos/aula8/Aula8.htm)
- Análise de Complexidade de Algoritmos