A Complexidade de um Algoritmo
Está relacionada com a 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.
A quantidade de "trabalho" também pode variar dependendo dos dados de entrada e não somente do volume de dados.
Sabemos que um algoritmo serve para resolver um determinado problema, e todos os problemas têm sempre uma entrada de dados. Ocorre que o tamanho dessa entrada (N) tem geralmente efeito direto no tempo de resposta de um algoritmo.
Dependendo do problema a ser resolvido, já existem algoritmos prontos ou que podem ser adaptados. Um exemplo disso são os algoritmos de ordenação que foram vistos até agora. Outro exemplo, são os chamados padrões de projeto que são amplamente utilizados na programação orientada a objetos.
Entre tantas opções de algoritmos prontos surge o problema: qual algoritmo escolher?
Como podemos comparar algoritmos para determinar qual o melhor para um problema?
Por exemplos, vamos considerar duas soluções para localizar um elemento em um vetor: LIN e BIN
Temos dois computadores diferentes, A e B, sendo A um Core 2 Duo e B um Celeron.
Qual dos algoritmos é o melhor? LIN ou BIN?
Se aumentarmos o tamanho dos dados de entrada temos o seguinte resultado:
Classificação da complexidade de algoritmos
Podemos falar de dois tipos de complexidade de algoritmos :
Complexidade Espacial: Quantidade de recursos utilizados para resolver o problema;
Complexidade Temporal: Quantidade de tempo utilizado.
Pode ser vista também como o número de instruções necessárias para resolver um determinado problema;
Em ambos os casos, a complexidade é medida de acordo com o tamanho dos dados de entrada (n)
Estamos mais interessados em calcular a Complexidade Temporal de um algoritmo! Quanto tempo o algoritmo leva para resolver o problema.
Os três casos de uma análise de complexidade
Existem três perspectivas para análise de complexidade:
Melhor Caso
Caso Médio
Pior Caso
Nos três casos, a função f(n) retorna a complexidade de um algoritmo com entrada de tamanho n
Análise do melhor caso
Definido pela letra grega Ω (Ômega)
Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n
É pouco usado, por ter aplicação em poucos casos.
Exemplo:
O algoritmo de pesquisa sequêncial em um vetor tem complexidade f(n) = Ω(1)
A análise assume que o número procurado seria o primeiro selecionado na lista.
Esta também é chamada de Abordagem otimista!
Análise do Pior Caso
Representado pela letra grega ômicron maiúscula O
Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n
É o método mais fácil de se obter.
Exemplo:
O algoritmo de pesquisa sequêncial em um vetor tem complexidade f(n) = O(n)
No pior caso será necessário visitar todos os n elementos do vetor até encontrar o elemento procurado
Também chamada de Abordagem pessimista!
A NOTAÇÃO O
Tempo (ou espaço) é contabilizado em número de passos do algoritmo (unidade de armazenamento)
A Análise do algoritmo é feita por uma função que depende do tamanho da entrada n.
10n3 + 4n -10
À medida que n aumenta, o termo cúbico começa a dominar
A constante do termo cúbico tem relativamente a mesma importância que a velocidade da CPU
Cálculo da Complexidade de um Algoritmo
Foi visto que, para calcular a complexidade de um algoritmo, deve-se analisar o pior caso
A análise deve ser feita de acordo com a tabela a seguir
Número de Operações Complexidade
f(n) O(f(n))
c x f(n) O(f(n))
f(n) + f(n) O(f(n))
f(n) + g(n) O(max(f(n),g(n))
f(n) x g(n) O(f(n) x g(n))
Exemplo:
ROTINA fw(Inteiro[1..n,1..n] grafo) # Inicialização VAR Inteiro[1..n,1..n] dist := grafo VAR Inteiro[1..n,1..n] pred PARA i DE 1 A n PARA j DE 1 A n SE dist[i,j] < Infinito ENTÃO pred[i,j] := i # Laço principal do algoritmo PARA k DE 1 A n PARA i DE 1 A n PARA j DE 1 A n SE dist[i,j] > dist[i,k] + dist[k,j] ENTÃO dist[i,j] = dist[i,k] + dist[k,j] pred[i,j] = pred[k,j] RETORNE dist
Cálculo da Complexidade:
1 + 1 + 1 + n * ( n * ( n * ( 1 + 1 + 1 + 3 ) ) )
3 + n * n * n * 6
3 + 6n3
O(n3)