Notações assintóticas e análise a priori
Na concepção de Algoritmo, a análise da complexidade de um algoritmo é um aspecto essencial. Principalmente, a complexidade algorítmica se preocupa com seu desempenho, quão rápido ou lento ele funciona.
A complexidade de um algoritmo descreve a eficiência do algoritmo em termos da quantidade de memória necessária para processar os dados e o tempo de processamento.
A complexidade de um algoritmo é analisada em duas perspectivas: Time e Space.
Complexidade de tempo
É uma função que descreve a quantidade de tempo necessária para executar um algoritmo em termos do tamanho da entrada. "Tempo" pode significar o número de acessos à memória realizados, o número de comparações entre inteiros, o número de vezes que algum loop interno é executado ou alguma outra unidade natural relacionada ao tempo real que o algoritmo levará.
Complexidade do Espaço
É uma função que descreve a quantidade de memória que um algoritmo leva em termos do tamanho da entrada para o algoritmo. Freqüentemente falamos de memória "extra" necessária, sem contar a memória necessária para armazenar a própria entrada. Novamente, usamos unidades naturais (mas de comprimento fixo) para medir isso.
A complexidade do espaço às vezes é ignorada porque o espaço usado é mínimo e / ou óbvio, mas às vezes se torna uma questão tão importante quanto o tempo.
Notações assintóticas
O tempo de execução de um algoritmo depende do conjunto de instruções, velocidade do processador, velocidade de E / S do disco, etc. Portanto, estimamos a eficiência de um algoritmo de forma assintótica.
A função de tempo de um algoritmo é representada por T(n), Onde n é o tamanho de entrada.
Diferentes tipos de notações assintóticas são usados para representar a complexidade de um algoritmo. As seguintes notações assintóticas são usadas para calcular a complexidade do tempo de execução de um algoritmo.
O - Grande Oh
Ω - Grande ômega
θ - Big theta
o - pequeno oh
ω - pequeno omega
O: Limite superior assintótico
'O' (Big Oh) é a notação mais comumente usada. Uma funçãof(n) pode ser representado é a ordem de g(n) isso é O(g(n)), se houver um valor de número inteiro positivo n Como n0 e uma constante positiva c tal que -
$ f (n) \ leqslant cg (n) $ para $ n> n_ {0} $ em todos os casos
Portanto, função g(n) é um limite superior para a função f(n), Como g(n) cresce mais rápido que f(n).
Exemplo
Vamos considerar uma determinada função, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 3 $,
$ f (n) \ leqslant 5.g (n) $ para todos os valores de $ n> 2 $
Portanto, a complexidade de f(n) pode ser representado como $ O (g (n)) $, ou seja, $ O (n ^ 3) $
Ω: Limite inferior assintótico
Dizemos que $ f (n) = \ Omega (g (n)) $ quando existe constante c que $ f (n) \ geqslant cg (n) $ para todos os valores suficientemente grandes de n. Aquiné um número inteiro positivo. Significa funçãog é um limite inferior para a função f; depois de um certo valor den, f nunca irá abaixo g.
Exemplo
Vamos considerar uma determinada função, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.
Considerando $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ para todos os valores de $ n> 0 $.
Portanto, a complexidade de f(n) pode ser representado como $ \ Omega (g (n)) $, ou seja, $ \ Omega (n ^ 3) $
θ: Limite Tight Assintótico
Dizemos que $ f (n) = \ theta (g (n)) $ quando existem constantes c1 e c2 que $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ para todos os valores suficientemente grandes de n. Aquin é um número inteiro positivo.
Isso significa função g é um limite estreito para a função f.
Exemplo
Vamos considerar uma determinada função, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ para todos os grandes valores de n.
Portanto, a complexidade de f(n) pode ser representado como $ \ theta (g (n)) $, ou seja, $ \ theta (n ^ 3) $.
O - Notação
O limite superior assintótico fornecido por O-notationpode ou não ser assintoticamente apertado. O limite $ 2.n ^ 2 = O (n ^ 2) $ é assintoticamente restrito, mas o limite $ 2.n = O (n ^ 2) $ não é.
Nós usamos o-notation para denotar um limite superior que não é assintoticamente rígido.
Nós definimos formalmente o(g(n)) (pouco-oh de g de n) como o conjunto f(n) = o(g(n)) para qualquer constante positiva $ c> 0 $ e existe um valor $ n_ {0}> 0 $, tal que $ 0 \ leqslant f (n) \ leqslant cg (n) $.
Intuitivamente, no o-notation, a função f(n) torna-se insignificante em relação a g(n) Como naproxima-se do infinito; isso é,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$
Exemplo
Vamos considerar a mesma função, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ {4} $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$
Portanto, a complexidade de f(n) pode ser representado como $ o (g (n)) $, ou seja, $ o (n ^ 4) $.
ω - Notação
Nós usamos ω-notationpara denotar um limite inferior que não é assintoticamente rígido. Formalmente, no entanto, definimosω(g(n)) (pequeno-ômega de g de n) como o conjunto f(n) = ω(g(n)) para qualquer constante positiva C > 0 e existe um valor $ n_ {0}> 0 $, tal que $ 0 \ leqslant cg (n) <f (n) $.
Por exemplo, $ \ frac {n ^ 2} {2} = \ omega (n) $, mas $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. A relação $ f (n) = \ omega (g (n)) $ implica que existe o seguinte limite
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$
Isso é, f(n) torna-se arbitrariamente grande em relação a g(n) Como n se aproxima do infinito.
Exemplo
Vamos considerar a mesma função, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considerando $ g (n) = n ^ 2 $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$
Portanto, a complexidade de f(n) pode ser representado como $ o (g (n)) $, ou seja, $ \ omega (n ^ 2) $.
Análise Apriori e Apostiari
A análise a priori significa que a análise é realizada antes de executá-la em um sistema específico. Esta análise é uma fase em que uma função é definida a partir de algum modelo teórico. Portanto, determinamos a complexidade de tempo e espaço de um algoritmo apenas olhando para o algoritmo, em vez de executá-lo em um sistema específico com uma memória, processador e compilador diferentes.
A análise Apostiari de um algoritmo significa que realizamos a análise de um algoritmo somente depois de executá-lo em um sistema. Depende diretamente do sistema e das mudanças de sistema para sistema.
Em uma indústria, não podemos realizar a análise Apostiari, pois o software geralmente é feito para um usuário anônimo, que o executa em um sistema diferente dos existentes na indústria.
A priori, é a razão de usarmos notações assintóticas para determinar a complexidade do tempo e do espaço à medida que mudam de computador para computador; entretanto, assintoticamente, eles são os mesmos.