top of page

PESQUISA OPERACIONAL

Disciplina: Teoria dos Grafos

Ordem de Complexidade de um Algoritmo

 

 

1. Introdução:

Analisar um algoritmo significa predizer os recursos computacionais que o algoritmo requer quando da sua execução, como por exemplo, memória e tempo computacional. Em geral, existem vários algoritmos para solucionar um problema e a análise é capaz de identificar qual é o mais eficiente.

 

Particularmente estamos interessados em obter uma expressão ou fórmula matemática que represente o tempo de execução de um algoritmo. Tal fórmula deve ser simples no sentido de omitir detalhes não relevantes, e ao mesmo tempo deve mostrar o comportamento do algoritmo, quando executado.

 

Os aspectos mais importantes da análise de tempo são:

 

  • quantidade de elementos a processar;

  • forma como os elementos estão dispostos na entrada.

 

Geralmente escrevemos o tempo de execução de um algoritmo como uma função f(n), onde n é o tamanho da entrada. O tamanho da entrada, por sua vez, depende do problema computacional em questão. Tal função f deve expressar o número de operações fundamentais, ou passos, executados pelo algoritmo. Veja a seguir o exemplo 1.

 

Exemplo 1: Considere o seguinte problema: dadas duas matrizes A=(aij) e B=(bij), ambas n × n, determinar as matrizes C=A + B e D=A × B. Cada um dos elementos cij e dij podem ser calculados da segunite forma:

Algoritmo: SOMA

O algoritmo Soma acima executa a linha 3 exatamente n² vezes. Assim, se o custo de uma soma (que é a operação fundamental da linha 3) for igual a uma constante c1, então dizemos que o tempo de execução, ou o custo do algoritmo Soma é TS(n)=c1 · n². Ou seja, Soma tem complexidade quadrática (função quadrática) em n.

Algoritmo: PRODUTO

Suponha agora que o custo de uma multiplicação seja c2. Então, como a linha 5 é executada n³ vezes, temos que o custo total do algoritmo Mult é dado por TM(n)=c2 · n³. Note que estamos considerandode custo nulo a operação executada na linha 3 deste algoritmo. O tempo de execução ou a complexidade de tempo de um algoritmo tem por objetivo avaliar sua eficiência. Estamos interessados em contar o número de passos que o algoritmo executa em seu pior caso, ou seja, para a entrada mais desfavorável. Esta complexidade fornece um limitante superior para o número de passos que o algoritmo pode efetuar em qualquer caso. Por isso tal medida é a mais utilizada. Em qualquer dos algoritmos vistos no exemplo 1, temos que o número de passos executados sobre qualquer entrada de tamanho n é o mesmo. Obviamente este não é o caso geral. Considere, por exemplo, o problema que tem como entrada as duas matrizes, como no exemplo 1, mais um parâmetro binário x. Dependendodo valor de x, deve-se calcular a soma ou o produto das duas matrizes. Assim, deveremos levar em conta, como parâmetro de entrada, o valor de x. Temos então um caso em que o algoritmo terá tempos diferentes de execução, dependendo de x. O pior caso é quando o valor de x determina que o algoritmo calcule o produto de duas matrizes e, portanto, tenha custo c · n³, onde c é o custo de uma multiplicação.

2. Notação assintótica:

O mais importante na determinação do custo de um algoritmo é a identificação do termo dominante da expressão que descreve sua complexidade. Este termo dominante, sem as constantes multiplicativas e as parcelas menores, descreve a ordem de crescimento assintótico desta expressão, quando consideramos o tamanho da entrada relativamente grande. Mais formalmente, estamos interessados em obter uma função que é um limitante superior assintótico para a nossa expressão.

Definição 1: 

Para uma dada função g(n), denotamos por O(g(n)) o conjunto das funções O(g(n))={f(n) : existem constantes positivas c e n0 tais que 0 ≤ f(n) ≤ cg(n), para todo n ≥ n0}.

 

 

Exemplo 2:

f(n)=n² − 1=O(n²). Devemos mostrar que existem constantes positivas c e n0 tais que 0 ≤ n² − 1 ≤ cn², ∀n ≥ n0. Isto vale para c=2 e n0=1. Portanto, n² − 1 ∈ O(n²). Costumamos denotar n² − 1=O(n²).

 

Exemplo 3:

f(n)=n² − 1=O(n³). Devemos mostrar que existem constantes positivas c e n0 tais que 0 ≤ n² − 1 ≤ cn³, ∀n ≥ n0. Isto vale para c=1 e n0=1. Portanto, n² − 1=O(n³).

Mais exemplos:

 

 

 

 

 

 

Assim, como a notação O é útil para descrever limitantes superiores asintóticos, a notação Ω, definida a seguir, é empregada para limitantes inferiores assintóticos.

 

 

Definição 2:

Para uma dada função g(n), denotamos por Ω(g(n)) o conjunto das funções Ω(g(n))={f(n) : existem constantes positivas c e n0 tais que 0 ≤ cg(n) ≤ f(n), para todo n ≥ n0}.

 

 

Exemplo 4:

f(n)=n² − 1=Ω(n²). Devemos mostrar que existem constantes positivas c e n0 tais que 0 ≤ cn² ≤ n² − 1, ∀n ≥ n0. Isto vale para c=1/2 e n0=2. Portanto, n² − 1=Ω(n²).

 

 

Mais exemplos:

Definição 3:

Se f=O(g) e f=Ω(g), então f =Θ(g).

3. Algoritmos eficientes:

Um algoritmo é dito ser eficiente para um problema de tamanho n se seu tempo de execução é limitado por um polinômio p(n). Dizemos então que o algoritmo é polinomial em n. Um algoritmo de Ω(    ) não é eficiente, pois a função      (exponencial) cresce mais rapidamente que qualquer polinômio em n. Os algoritmos de soma e multiplicação de matrizes vistos acima são, portanto, eficientes. Existem, no entanto, alguns problemas para os quais não se conhece algoritmo eficiente para resolvê-los.

 

 

4. Algorimos Ótimos:

Seja P um problema. Um limitante inferior para P é uma função ψ tal que a complexidade de pior caso de qualquer algoritmo que resolve P é Ω(ψ). Isto é, todo algoritmo que resolve P executa no mínimo Ω(ψ) passos. Assim, se existir algum algoritmo A que resolve P em tempo O(ψ), então A é dito ser um Algoritmo Ótimo para P. Intuitivamente, um algoritmo ótimo é aquele que apresenta a menor complexidade dentre todos aqueles que resolvem o mesmo problema.

 

Existem limitantes inferiores naturais para determinados problemas. Qualquer algoritmo para somar duas matrizes n × n, por exemplo, deverá, antes de qualquer coisa, ler as matrizes. Assim, um limitante inferior para este problema é Ω(n²). Portanto, podemos concluir que o algoritmo Soma é ótimo para este problema. Um outro exemplo é o problema de multiplicação de matrizes. Novamente temos um limitante Ω(n²). Por outro lado, vimos que o algoritmo Mult tem complexidade O(n³). A pergunta então é: Mult é um algoritmo ótimo para o problema de multiplicação de matrizes? A princípio nada podemos dizer sobre isso. No entanto, sabemos que existem algoritmos para o mesmo problema com complexidade inferior. Portanto, podemos dizer que Mult não é ótimo.

 

 

 

 

 

 

 

_________________________________

Autores: Fábio Henrique V. Martinez e Nalvo Franco de Almeida Jr.

Copyright © DCT/UFMS Abril, 1999

  A partir de 11 Set de 2020

Você é o Visitante de Número

Nosso CANAL

bottom of page