Analise de Algoritmo

Centro Universitário do Sul de Minas – UNIS-MG
Unidade de Gestão da Educação Superior Presencial – GEP
Ciência da Computação

Complexidade de Algoritmos
Análise de Algoritmos

Professor Renan Levenhagen Bustamante Neves

Júlio Cezar Ferreira Rocha

Varginha
2013

1 - Complexidade de Algoritmos

Diferentes computadores, muitas vezes com hardware idênticos, podem levar tempos diferentes para processar um mesmo algoritmo. Quando trocamos algum, ou mais, itens de hardware, esta diferença tende a aumentar ainda mais, por tanto, avaliar o desempenho de um algoritmo com base apenas no tempo de execução deste, é ineficiente, surge então o conceito de complexidade de algoritmo, que é uma fração da complexidade computacional.
A complexidade de algoritmos estuda e define quanto eficiente é um algoritmo em relação ao número de operações (passos do algoritmo) necessários para finalizar a tarefa.
Apesar do hardware influenciar no tempo de execução de algoritmo, existe ainda um segundo parâmetro que pode também influenciar este tempo, "O conjunto de Dados".

1.1 - Por que Analisar a complexidade dos algoritmos.

A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes. Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência.
Mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção.

2 - Onde são usados

Em geral, algoritmos servem para processar conjuntos de dados com tamanho indeterminado:
Listas;
Filas;
Pilhas;
Tabelas;
Imagens;
Entre Outros.
Exemplo:

Para somar todos os elementos de uma lista:

Quando a lista tiver apenas 1 elemento:
Uma operação de soma.

Quando a lista tiver 1.000.000 de elementos:
1.000.000 de somas.

3 - O Padrão

Por padrão, para denotar o tamanho do conjunto de dados a ser processado, chamamos este número de dados de N.