Como provar a ordem assintótica de um algoritmo

Como provar a ordem assintótica de um algoritmo

3 de outubro de 2017 0 Por Ramos de Souza Janones

Como provar a ordem assintótica de um algoritmo utilizando a linguagem de programação Javascript com um exemplo prático e passo a passo.

Primeiro vamos ao problema:

Considerando um algoritmo como o abaixo:

function somaMatriz(matA, size)
  let soma = 0;                                        // 1
  for(let i = 0; i < size; i++){                       // n + 1
    for(let j = 0; j < size; j++){                     // n(n + 1)
      soma += a[i][j];                                 // (n.n)
    }
  }  
  return soma;                                         // 1 
}

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²

Recomendamos a leitura:
- 14 Hábitos de Desenvolvedores Altamente Produtivos eBook Kindle
- Kwai dá dinheiro aos usuários, como ganhar?

Lançamento do jogo Returnal para PlayStation 5
Guia de Compras em PC Gaming

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

Livros que recomendamos a leitura:
- Programando com Kotlin
- Inspirado: como criar produtos de tecnologia que os clientes amam
- Data science para negócios

Técnicas de Invasão: Aprenda as técnicas usadas por hackers em invasões reais
Python Fluente: Programação Clara, Concisa e Eficaz

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.

» Programação

votes
Article Rating
LEIA TAMBÉM:  Criptografia Hash de forma segura