Как упорядочить функции в порядке роста скорости?Так что f (n) есть O (g (n))

Question

У меня есть следующие функции, которые необходимо упорядочить по скорости их роста.Но как мы можем показать, что функция g (n) следует сразу же за функцией f (n) в списке, тогда это должен быть случай, когда f (n) равно O (g (n))?

Я попытался ввести некоторые значения для n (например, 10, 1000, 5000), и оно приходит как 5 <4 <2 <1 <3, от 1000. </p>

Как я могу асимптотически доказать этот порядок?

Answer 1

Пожалуйста, смотрите ответ ниже, размещая в изображении из-за функций и полномочий.

Answer 2

Любая положительная полиномиальная функция растет быстрее, чем любая полилогарифмическая функция, то есть lg ^ b (n) = o (n ^ a) для любого a> 0 (обратите внимание на маленькое o)

Это подразумевает f2 >> f4 .

Все остальное (экспоненциально) растет быстрее, чем f2.

Сравнить f1 = 10 ^n и f3 = n ^ n Возьмите журнал с обеих сторон, чтобы сравнить nlog10 с nlogn .Ясно, что f3 >> f1 (log10 - это константа).

Сравните f3 = n ^ n и f5 = 2 ^ (log ^ 1 /2 (n)) Возьмите журнал с обеих сторон, чтобы сравнить nlogn с (log ^ 1/2 (n)) log2 . f3 >> f5 (возведите в квадрат обе стороны или используйте тот факт, что: любая положительная полиномиальная функция растет быстрее, чем любая полилогарифмическая функция)

Осталось только сравнить f5 = 2 ^ (log ^ 1/2 (n)) и f1 = 10 ^ n .Возьмите журнал с обеих сторон, чтобы сравнить (log ^ 1/2 (n)) log2 с nlog10 . f1 >> f5 .

Используя все эти факты, можно сделать вывод, что f4 << f2 << f5 << f1 << f3 </strong>.В качестве альтернативы, как отмечали другие, вы можете сравнить их, рассчитав пределы.