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

Question

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

Answer 1

f ∈ O (g) diz, essencialmente

Por pelo menos um Escolha de uma constante k > 0, você pode encontrar uma constante uma de modo que a desigualdade 0 <= f (x) <= kg (x) é mantida para todos os x> a.

Observe que o (g) é o conjunto de todas as funções para as quais essa condição se mantém.

f ∈ O (g) diz, essencialmente

Por todo Escolha de uma constante k > 0, você pode encontrar uma constante uma de modo que a desigualdade 0 <= f (x) <kg (x) é mantida para todos os x> a.

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

No Big-O, é necessário apenas que você encontre um multiplicador específico k para o qual a desigualdade tem além de algum mínimo x.

Em Little-O, deve ser que exista um mínimo x após o que a desigualdade vale, não importa o quão pequeno você faça k, desde que não seja negativo ou zero.

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

Uma ilustração da disparidade é a seguinte: f ∈ O (f) é verdadeira, mas f ∈ O (f) é falso. Portanto, o 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 o de G". É como <= contra <.

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

No entanto, para f ∈ O (g) ser verdadeiro, G deve incluir um maior potência de x em sua fórmula e, portanto, a separação relativa entre f (x) e g (x) deve realmente aumentar à medida que X aumenta.

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

Os seguintes são verdadeiros para o Big-O, mas não seriam verdadeiros 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³), então também é verdade que x² ∈ O (x³), (novamente, pense em O como <= e O como <)

Answer 2

Big-O é para Little-O como ≤ é para <. O BIG-O é um limite superior inclusivo, enquanto Little-O é um limite superior estrito.

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

• dentro O(n²), o(n²), e O(n)
• não em O(lg n), o(lg n), ou o(n)

Analogamente, o número 1 é:

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

Aqui está uma mesa, 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. Está dentro O(1) Apesar de não ter um limite normal, porque ainda tem um 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.

Answer 3

Acho que quando não consigo entender conceitualmente algo, pensando em Por que alguém usaria x é útil entender X. (Para não dizer que você não tentou isso, estou apenas preparando o cenário.)

Coisas que você conhece] Uma maneira comum de classificar os algoritmos é por tempo de execução e, citando a complexidade de um algoritmo de grande no O! Mesmo no mundo real, O (n) é "melhor" do que O (n²), exceto coisas tolas como constantes super-massivas e coisas do gênero. [/Coisas que você conhece

Digamos que exista algum algoritmo que seja executado em O (n). Muito bom, hein? Mas digamos que você (sua pessoa brilhante, você) crie um algoritmo que corre em O (^N⁄_{LogLogLogLogn}). YAY! É mais rápido! Mas você se sentiria bobo escrevendo isso repetidamente quando está escrevendo sua tese. Então você escreve uma vez e pode dizer "neste artigo, 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-por quanto não está claro, mas eles sabem que é mais rápido. Teoricamente. :)