Como discutir coeficientes na notação big-O

10

Que notação é usada para discutir os coeficientes de funções na notação big-O?

Eu tenho duas funções:

  • f(x)=7x2+4x+2
  • g(x)=3x2+5x+4

Obviamente, ambas as funções são , de fato , mas isso não permite uma comparação além disso. Como discuto os coeficientes 7 e 3. Reduzir o coeficiente para 3 não altera a complexidade assintótica, mas ainda faz uma diferença significativa no uso do tempo de execução / memória.Θ ( x 2 )O(x2)Θ(x2)

É errado dizer que é e é ? Existe outra notação que leva em consideração os coeficientes? Ou qual seria a melhor maneira de discutir isso?O ( 7 x 2 ) g O ( 3 x 2 )fO(7x2)gO(3x2)

Rafael
fonte
Não está errado, é apenas redundante, porque . O(7x2)=O(x2)
Veja também nossa pergunta de referência .
Raphael

Respostas:

9

Grande- e grande- q notações esconder coeficientes do termo de liderança, por isso, se você tem duas funções que são ao mesmo tempo Θ ( n 2 ) você não pode comparar seus valores absolutos, sem olhar para as próprias funções. Não é errado dizer que 7 x 2 + 4 x + 2 = Θ ( 7 x 2 ) , mas não é informativo porque 7 x 2 + 4 x + 2 = Θ ( 3 x 2 )OΘΘ(n2)7x2+4x+2=Θ(7x2)7x2+4x+2=Θ(3x2)também é verdadeiro (e, de fato, é para qualquer constante positiva k ).Θ(kx2)k

Existem outras notações que você pode querer usar. Por notação é uma reivindicação muito mais forte do grande- Θ :Θ

f(x)g(x)limxf(x)g(x)=1

Por exemplo, , mas a reivindicação 7 x 2 + 4 x + 2 ~ 3 x 2 seria falso. Você pode pensar em til notação como Θ notação que preserva os coeficientes de líderes, o que parece ser o que você está procurando se você se preocupam com o líder coeficiente do termo de crescimento dominante.7x2+4x+27x27x2+4x+23x2Θ

templatetypedef
fonte
Notação til é o que estou procurando. Eu tinha certeza de que havia algo que simplesmente não conseguia lembrar como era chamado e as pesquisas se mostraram infrutíferas. Obrigado!
6

O til é uma abordagem. Se você quer ficar com , pode dizerO

ef(x)=7x2+O(x)

.g(x)=3x2+O(x)

Rafael
fonte
Melhor ainda: diga f (x) = 7x ^ 2 + o (x ^ 2), usando pouca notação para esclarecer que o que resta é assintoticamente menor que x ^ 2.
Templatetypedef
2
O (x) é estritamente menor que o (x ^ 2), portanto, usar isso seria menos claro do que usar big-O. Por outro lado, usar little-o é definitivamente mais comum quando você quer dizer que obteve o primeiro termo certo, porque não precisa se preocupar com o próximo. (E se quisermos ser completamente claros, precisaríamos explicar por que não anotamos 7x ^ 2 + 4x + 2 em primeiro lugar, pois está exatamente correto.
Você está absolutamente certo ... minhas desculpas!
templatetypedef
f(x)=7x2+g(x)g(x)O(x)f(x)=7x2+4x+O(1)