Как обсудить коэффициенты в нотации big-O

10

Какая нотация используется для обсуждения коэффициентов функций в нотации big-O?

У меня есть две функции:

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

Очевидно, что обе функции , на самом деле , но это не позволяет сравнивать дальше. Как мне обсудить коэффициенты 7 и 3. Уменьшение коэффициента до 3 не меняет асимптотическую сложность, но все же имеет существенное значение для времени выполнения / использования памяти.Θ ( x 2 )O(x2)Θ(x2)

Это неправильно сказать , что является и является ? Есть ли другие обозначения, которые учитывают коэффициенты? Или как лучше обсудить это?O ( 7 х 2 ) г O ( 3 х 2 )fO(7x2)gO(3x2)

Рафаэль
источник
Это не неправильно, это просто избыточно, потому что . O(7x2)=O(x2)
Смотрите также наш справочный вопрос .
Рафаэль

Ответы:

9

Big- и big- & thetas нотации скрыть коэффициенты ведущего члена, поэтому если у вас есть две функции , которые являются как thetas ; ( п 2 ) вы не можете сравнить их абсолютные значения , не смотря на самих функций. Само собой разумеется, что 7 x 2 + 4 x + 2 = Θ ( 7 x 2 ) , но это не информативно, потому что 7 x 2 + 4 x + 2 = Θ ( 3 x 2 )OΘΘ(n2)7x2+4x+2=Θ(7x2)7x2+4x+2=Θ(3x2)также верно (и, фактически, это для любой положительной константы k ).Θ(kx2)k

Есть и другие обозначения, которые вы можете использовать вместо этого. Так , например, обозначения гораздо сильнее , чем требование big- & thetas :Θ

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

Например, , но утверждение 7 x 2 + 4 x + 2 3 x 2 будет ложным. Вы можете думать о тильде обозначений thetas ; обозначения , что сохраняет ведущие коэффициенты, которые , кажется, что вы ищете , если вы заботиться о ведущей коэффициенте срока доминирующего роста.7x2+4x+27x27x2+4x+23x2Θ

templatetypedef
источник
Тильда нотация это то, что я ищу. Я был уверен, что было что-то, что я просто не мог вспомнить, как это называлось, и поиски оказались бесплодными. Спасибо!
6

Тильда - это один из подходов. Если вы хотите придерживаться , вы могли бы сказать,О

ие(Икс)знак равно7Икс2+О(Икс)

.г(Икс)знак равно3Икс2+О(Икс)

Рафаэль
источник
Еще лучше: скажем, f (x) = 7x ^ 2 + o (x ^ 2), используя нотацию little-o, чтобы уточнить, что то, что осталось, асимптотически меньше, чем x ^ 2.
templatetypedef
2
O (x) строго меньше, чем o (x ^ 2), поэтому его использование будет менее понятным, чем использование big-O. С другой стороны, использование little-o определенно более распространено, когда вы хотите сказать, что у вас правильный первый термин, потому что тогда вам не нужно беспокоиться о следующем. (И если мы хотим быть полностью ясными, то нам нужно объяснить, почему мы просто не записываем 7x ^ 2 + 4x + 2 в первую очередь, поскольку это совершенно правильно.
Вы абсолютно правы ... мои извинения!
templatetypedef
е(Икс)знак равно7Икс2+г(Икс)г(Икс)О(Икс)е(Икс)знак равно7Икс2+4Икс+О(1)~