Diferença entre a notação Big-O e Little-O

Qual é a diferença entre Big-O notação O(n)e Pequeno-O notação o(n)?

f ∈ O (g) diz, essencialmente

Para pelo menos uma escolha de uma constante k > 0, é possível encontrar uma constante a tal que a desigualdade 0 <= f (x) <= kg (x) seja válida para todo x> a.

Observe que O (g) é o conjunto de todas as funções para as quais essa condição é válida.

f ∈ o (g) diz, essencialmente

Para cada escolha de uma constante k > 0, é possível encontrar uma constante a tal que a desigualdade 0 <= f (x) <kg (x) seja válida para todos os x> a.

Mais uma vez, observe que o (g) é um conjunto.

No Big-O, é necessário apenas encontrar um multiplicador específico k para o qual a desigualdade se mantém além de um mínimo de x .

Em Little-o, deve haver um x mínimo, após o qual a desigualdade se mantém, não importa quão pequeno você faça k , desde que não seja negativo ou zero.

Ambos descrevem os limites superiores, embora um pouco contra-intuitivamente, Little-o é a afirmação mais forte. Existe uma diferença muito maior entre as taxas de crescimento de f e g se f f o (g) do que se f ∈ O (g).

Uma ilustração da disparidade é a seguinte: f ∈ O (f) é verdadeiro, mas f ∈ o (f) é falso. Portanto, Big-O pode ser lido como "f ∈ O (g) significa que o crescimento assintótico de f não é mais rápido que g's", enquanto "f ∈ o (g) significa que o crescimento assintótico de f é estritamente mais lento que g's". É como <=versus <.

Mais especificamente, se o valor de g (x) é um múltiplo constante do valor de f (x), então f ∈ O (g) é verdadeiro. É por isso que você pode eliminar constantes ao trabalhar com notação big-O.

No entanto, para que f ∈ o (g) seja verdadeiro, g deve incluir uma potência mais alta de x em sua fórmula e, portanto, a separação relativa entre f (x) eg (x) deve realmente aumentar à medida que x aumenta.

Para usar exemplos puramente matemáticos (em vez de se referir a algoritmos):

O seguinte é verdadeiro para Big-O, mas não seria verdade se você usasse little-o:

• x² ∈ O (x²)
• x² ∈ O (x² + x)
• x² ∈ O (200 * x²)

O seguinte é verdadeiro para little-o:

• x² ∈ o (x³)
• x² (o (x!)
• ln (x) ∈ o (x)

Observe que, se f ∈ o (g), isso implica f ∈ O (g). por exemplo x² ∈ o (x³), portanto, também é verdade que x² ∈ O (x³), (novamente, pense em O como <=e o como <)

Big-O é tão pequeno quanto ≤é <. Big-O é um limite superior inclusivo, enquanto little-o é um limite superior estrito.

Por exemplo, a função f(n) = 3né:

• na O(n²), o(n²)eO(n)
• não em O(lg n), o(lg n)ouo(n)

Analogamente, o número 1é:

• ≤ 2,, < 2e≤ 1
• não ≤ 0, < 0ou< 1

Aqui está uma tabela, mostrando a ideia geral:

(Nota: a tabela é um bom guia, mas sua definição de limite deve ser em termos do limite superior, em vez do limite normal. Por exemplo, 3 + (n mod 2) oscila entre 3 e 4 para sempre. É O(1)apesar de não ter um limite normal, porque ainda tem a lim sup: 4.)

Eu recomendo memorizar como a notação Big-O se converte em comparações assintóticas. As comparações são mais fáceis de lembrar, mas menos flexíveis, porque você não pode dizer coisas como n ^{O (1)} = P.

Acho que, quando não consigo entender algo conceitualmente, pensar no porquê de alguém usar o X é útil para entender o X. (Para não dizer que você não tentou isso, estou apenas preparando o cenário).

[coisas que você sabe] Uma maneira comum de classificar algoritmos é por tempo de execução e, citando a grande complexidade de um algoritmo, você pode obter uma estimativa muito boa de qual é "melhor" - o que tiver a função "menor" no O! Mesmo no mundo real, O (N) é "melhor" que O (N²), exceto coisas tolas como constantes supermassas e coisas assim. [/ Coisas que você conhece]

Digamos que exista algum algoritmo que seja executado em O (N). Muito bom, né? Mas digamos que você (sua pessoa brilhante, você) _crie um algoritmo executado em O ( ^N ⁄ _{loglogloglogN} ). YAY! É mais rápido! Mas você se sentiria bobo escrevendo isso várias vezes quando estiver escrevendo sua tese. Então, você o escreve uma vez e pode dizer "Neste artigo, eu provei que o algoritmo X, anteriormente computável no tempo O (N), é de fato computável em o (n)".

Assim, todo mundo sabe que seu algoritmo é mais rápido - quanto não é claro, mas eles sabem que é mais rápido. Teoricamente. :)