Какая нотация используется для обсуждения коэффициентов функций в нотации big-O?
У меня есть две функции:
Очевидно, что обе функции , на самом деле , но это не позволяет сравнивать дальше. Как мне обсудить коэффициенты 7 и 3. Уменьшение коэффициента до 3 не меняет асимптотическую сложность, но все же имеет существенное значение для времени выполнения / использования памяти.Θ ( x 2 )
Это неправильно сказать , что является и является ? Есть ли другие обозначения, которые учитывают коэффициенты? Или как лучше обсудить это?O ( 7 х 2 ) г O ( 3 х 2 )
Ответы:
Big- и big- & thetas нотации скрыть коэффициенты ведущего члена, поэтому если у вас есть две функции , которые являются как thetas ; ( п 2 ) вы не можете сравнить их абсолютные значения , не смотря на самих функций. Само собой разумеется, что 7 x 2 + 4 x + 2 = Θ ( 7 x 2 ) , но это не информативно, потому что 7 x 2 + 4 x + 2 = Θ ( 3 x 2 )О Θ Θ ( н2) 7 х2+ 4 х + 2 = Θ ( 7 х2) 7 х2+ 4 х + 2 = Θ ( 3 х2) также верно (и, фактически, это для любой положительной константы k ).Θ ( к х2) К
Есть и другие обозначения, которые вы можете использовать вместо этого. Так , например, обозначения гораздо сильнее , чем требование big- & thetas :~ Θ
Например, , но утверждение 7 x 2 + 4 x + 2 ∼ 3 x 2 будет ложным. Вы можете думать о тильде обозначений thetas ; обозначения , что сохраняет ведущие коэффициенты, которые , кажется, что вы ищете , если вы заботиться о ведущей коэффициенте срока доминирующего роста.7 х2+ 4 х + 2 ∼ 7 х2 7 х2+ 4 х + 2 ∼ 3 х2 Θ
источник
Тильда - это один из подходов. Если вы хотите придерживаться , вы могли бы сказать,О
ие( х ) = 7 х2+ O ( х )
.г( х ) = 3 х2+ O ( х )
источник