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.