Растет ли O(N(logN)^4) быстрее, чем O(N^3)?

#time-complexity #big-o

Вопрос:

Растет ли функция O(N(logN)^4) быстрее, чем функция O(N^3)? Я не могу по-настоящему понять это и не могу определить, что растет быстрее.

1. Создание некоторых графиков должно помочь вам угадать ответ. Тогда вы можете попытаться это доказать. Ваши навыки в математике могут быть полезны.

2. {«Log10″}» rel=»nofollow noreferrer»> диаграмма

Ответ №1:

O(N(logN)^4) < O(N^3)

Правило сравнения двух O обозначений состоит в том, чтобы определить соотношение и посмотреть, если n оно идет в бесконечность, куда идет соотношение.

В нашем примере: N(logN)^4/N^3 = log(N)^4/N^2 -> 0 так близко к бесконечности у вас будет N(logN)^4/N^3 < 1 ~ N(logN)^4 < N^3 . Это можно перевести на O(N(logN)^4) < O(N^3)

1. @JamoliddinNosirov пожалуйста, используйте методологию Lulupointu, чтобы вы понимали, как сравнивать, но в целом вы почти всегда можете предположить, что все, что имеет логин, будет меньше любой экспоненциальной функции. Логарифмические кривые приближаются к 1 в бесконечность — но никогда не достигают — значения до и после (даже экспоненты) просто добавляют к «1». Я не математик, поэтому, вероятно, есть места, где есть исключения, но в целом это будет так

2. Журнал не приближается к 1 в направлении бесконечности. Журнал переходит в бесконечность, когда его аргумент переходит в бесконечность. Однако попробуйте, чтобы log был «слабее» любой полиномиальной (а также экспоненциальной) функции, как это легко доказать путем изучения log(x)^a/x^b . Вы понимаете, что log(x)^a/x^b < 1 для определенного значения, которое означает, что log(x)^a/x^(c) < 1/x^e (при b=c-e, e настолько мало, насколько необходимо, чтобы b оставался положительным), которое идет от 0 к бесконечности, доказывая, что нам нужно.

3. это справедливое замечание к моему чрезмерно широкому заявлению! И напоминание о том, что мои занятия по математике были давным-давно.