Como provar a ordem assintótica de um algoritmo

mm

Ramos de Souza Janones

Janones, é um empreendedor brasileiro apaixonado por empreendedorismo e tecnologia. Ao longo dos anos trabalhando com o desenvolvimento de softwares desktop desde a linguagem Clipper, passando pelo Delphi e atualmente com Java.

Optou pela formação de Publicidade e Marketing por sua segunda empresa de tecnologia ter participado do "boom" da internet nos anos 90 e na procura de melhorar seus conhecimentos em negócios.

Em razão da principal formação e profundos conhecimentos em programação e banco de dados, é capaz de realizar o desenvolvimento de aplicativos web, desktop e mobile com maior criatividade e inovação que profissionais de desenvolvimento com uma formação única e mais especifica, dedicada somente ao desenvolvimento de softwares.

Com toda sua experiência com empresas de software, sua formação e paixão por negócios escreveu o livro "Marketing para Empresas e Profissionais de Software", publicado pela editora carioca Ciência Moderna em 2012. Além de outros livros sobre programação.
mm

Primeiro vamos ao problema:

Considerando um algoritmo como o abaixo:

Numa análise um pouco detalhada — considerando custo unitário e uniforme — a expressão referente ao custo seria algo como:

T(n) = 3 + 2n + 2n²

No entanto, pode-se notar facilmente que T(n) pertence a O(n²).

Eu sei que a ordem assintótica não quer dizer literalmente que esta função (neste caso, ) domina a função original (neste caso, 3 + 2n + 2n²), mas sim que existem uma constante — que chamarei de c — e um valor “inicial” de n — que chamarei de m — tais que:

Considerando  como f(n) e 3 + 2n + 2n² como g(n).

cf(n) domine assintoticamente g(n) a partir de um determinado m.

No caso do exemplo, pode-se ver isso bem facilmente. Tomando c como 3 e m como 4, tem-se:

3 + 2 * 4 + 2 * 4² = 43

e

3 * 4² = 48

E, a partir disto (n ≥ 4), para qualquer possível valor de n a função cf(n) domina g(n).

Mas como isso pode ser provado matematicamente?

Vamos tentar responder:

Provar que uma função c.g(n) domina f(n) a partir de um determinado n e c.

Sendo f(n) uma função quadrática como o exemplo dado, 5n^2 + 3n, podemos formalmente defini-la como:

inserir a descrição da imagem aqui

Então sabemos que ela será sempre igual ou inferior a:

inserir a descrição da imagem aqui

Logo podemos transformar numa inequação e ir manipulando:

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Por isso temos a certeza que a partir de um c de A+B+C a função c.g(n) domina f(n) para todo o n >= 1.

Pegando no 5n² + 3n de exemplo e aplicando a lógica temos a certeza que um c de 8, vindo de (5+3+0), é suficiente para dominar a função, o que não implica que não haja um c mais baixo que também a domine!

Provar que f(n) que pertence ao conjunto de O(g(n))

Neste caso temos que usar a formula:

inserir a descrição da imagem aqui

Em que irá pertencer ao conjunto se c for um número real finito maior ou igual a .

Aplicando ao mesmo exemplo, e tomando f(n) como 5n² + 3n e g(n) como  temos:

inserir a descrição da imagem aqui

Como c é 5, prova que 5n² + 3n pertence a O(n²)

Podemos ainda generalizar esta prova para qualquer função quadrática, na forma de inserir a descrição da imagem aqui :

inserir a descrição da imagem aqui

Como a é um coeficiente, logo uma constante, automaticamente prova que todas as funções quadráticas pertencem a O(n²) a menos que este seja negativo, o que para uma analise de complexidade de um algoritmo não poderá ser.

Ambas as provas podem naturalmente ser extrapoladas para funções que não sejam quadráticas, generalizando uma solução para esse tipo de funções.

 

Compartilhe.

PinIt
Top
%d blogueiros gostam disto: