Diferença entre notação Big-O e Little-O
-
21-09-2019 - |
Pergunta
Qual é a diferença entre Big-O notação O(n)
e Little-O notação o(n)
?
Solução
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 <
)
Outras dicas
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²)
, eO(n)
- não em
O(lg n)
,o(lg n)
, ouo(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 nO (1) = P.
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. :)