Algoritmo otimo

INTRODUÇÃO A COMPLEXIDADE DE ALGORITMOS

ALGORITMO ÓTIMO


Quando conseguimos determinar o menor custo possível (limite inferior) para resolver problemas de uma determinada classe: temos a medida da dificuldade inerente para resolver tais problemas. Quando o custo de um algoritmo (limite superior) é igual ao menor custo possível então o algoritmo é ótimo para a medida de custo considerada.



ALGORITMO ÓTIMO implica PROBLEMA FOI RESOLVIDO EFICIENTEMENTE que implica

LIMITE INFERIOR (PROBLEMA) = LIMITE SUPERIOR (ALGORITMO)

EXEMPLO 1: Máximo de um conjunto vet[1: n], n > 1
(int) função MAX (var vet: Vetor); var i, Temp: int; INICIO Temp = vet[1]; PARA i := 2 ATÉ n SE vet[i] > Temp ENTÃO Temp = vet[i] FIM-PARA Max = Temp; FIM

Matematicamente,,,EXEMPLO 1: Máximo de um conjunto vet[1: n], n > 1 Seja f a função de complexidade tal que f(n) é o número de comparações entre os elementos de vet se vet tiver n elementos. Neste caso f(1) = 0 f(n) = n - 1, para n > 1

Vamos provar que MAX é ótimo!

Teorema:
Qualquer algoritmo para encontrar o maior elemento de um conjunto com n elementos, faz pelo menos n-1 comparações.

Prova:
Cada um dos n - 1 elementos tem que ser mostrado, através de comparações, que é menor do que algum outro elemento, logo n-1 comparações são necessárias.

Concluindo: para o problema de encontrar o maior (ou o menor) elemento de um conjunto...
MELHOR CASO = CASO MÉDIO = PIOR CASO n-1 comparações Complexidade: O(n)

EXEMPLO 2 : Pesquisa Seqüencial
MELHOR CASO
Ocorre quando o registro procurado é o primeiro consultado. Apenas 1 comparação (custo 1)

PIOR CASO
Ocorre quando o registro procurado é o último a ser consultado, ou então não está presente no arquivo. n comparações ou n+1 comparações Complexidade: O(n)

ANÁLISE DO CASO MÉDIO
Se pi for a probabilidade de que o i-ésimo registro seja procurado, e considerando que para recuperar o i-ésimo registro sejam necessárias i comparações, então: f(n) = 1p1, + 2