top of page

COMPUTAÇÃO

Disciplina: Análise de Sistemas

(Eficiência ou Ordem de Complexidade: Introdução - Definição e Notação)

 

 

 

Costuma-se analisar um algoritmo em termos de tempo e espaço (ou memória). Para o tempo, diversas medidas são em princípio possíveis:

 

                                  1. Tempo absoluto (em minutos, segundos, etc.) - não é interessante por depender da máquina.

                                  2. Número de operações consideradas relevantes (por exemplo comparações, operações aritméticas,

                                      movimento de dados, etc.)

 

Três casos podem ser considerados: o melhor caso, o caso médio e o pior caso. O estudo do caso médio depende do conhecimento ou suposição da distribuição das entradas ao problema. Em geral o pior caso é o mais fácil de se analisar. Por exemplo, se temos 2 métodos para resolver um mesmo problema, cuja entrada tem tamanho n, podemos ter:

Notação: O (Ordem de Complexidade do Algoritmo)

Para estudarmos o comportamento assintótico - para n grande - interessa-nos o termo de ordem superior:

A notação O pode ser formalizada como se segue:

Dizemos que                           se existirem inteiro m e constante c tais que

 

 

Isto é, para valores de n sufcientemente grandes, T(n) não cresece mais rapidamente que f(n).

A importância da complexidade pode ser observada pelo seguinte exemplo, que mostra 5 algoritmos A1 a A5 para resolver um mesmo problema, de complexidades diferentes. Supomos que uma operação leva 1 ms (milésimo de segundos) para ser efetuada. A Tabela seguinte dá o tempo necessário para cada um dos algoritmos. (Sempre suporemos logaritmos na base 2.)

Podemos muitas vezes melhorar o tempo de execução de um programa (que implementa um algoritmo dado) fazendo otimizações locais (por exemplo, usar x + x ao invés de 2x, em máquinas em que a multiplicação é mais demorada que a adição).

Entretanto, melhorias substanciais são muitas vezes obtidas se usarmos um algoritmo diferente com outra complexidade de tempo, por exemplo obter um algoritmo de                                            Para se certificar disso, basta que se compare os tempos computacionais das duas colunas A2A3 da Tabela acima (0.064s < 0.256s; 0.16s < 1s; 9s < 4m 22s)

              

Logo, daremos um exemplo prático de Análise de Complexidade de Algoritmos. Tal exemplo será o de calcular a Ordem de Complexidade do Algoritmo SIMPLEX utilizado em Programação Linear

 

(Ver Programação Linear)

Fonte: Texto copiado na íntegra!

MAC 5710 - Estruturas de Dados e sua Manipulação

URL - http://www.ime.usp.br/song/mac5710.html

Eficiência ou Complexidade de Algoritmos

Siang  005

  A partir de 20 Out de 2020

Você é o Visitante de Número

bottom of page