Как найти асимптотический порядок функции?

Question

Я должен расположить несколько функций, таких как n.logn, log (log (n)) и т. Д., В асимптотическом порядке, я понятия не имею, как это сделать. Может кто-нибудь помочь мне?

Я знаю, что это не форум "сделай домашнее задание", но я был бы очень признателен, если бы кто-нибудь мог помочь мне сделать это! Спасибо.

Answer 1

Порядок функции описывает, как требования к функции масштабируются по мере увеличения размера ввода. Таким образом, log (log (n)) будет лучше масштабироваться (быть более эффективным) для больших n, чем n.log (n), поскольку log (log (n))

Полезную таблицу можно найти здесь: http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

Answer 2

Возьмите отношения функций и вычислите пределы отношений, когда n стремится к бесконечности.Вы можете использовать правило L'Hopital, если это не сразу видно из соотношения.

http://en.wikipedia.org/wiki/L%27Hôpital%27s_rule

Затем вы также можете выполнить числовые проверки, чтобы увидеть, имеет ли ваш результат смысл.

Для приведенного выше примера предел (log (log (n))) / (n log (n)) равен нулю, поэтому n log (n) растет намного быстрее!

Answer 3

интересная ссылка для вас, чтобы начать с ...

• постоянное время - O (1) (например, определение, является ли целое число (представленное в двоичном коде) четным или нечетным
• логарифмическое время - O (log n) (например, бинарный поиск)
• квадратичное время - O (n2) (например, сортировка по пузырькам; сортировка по вставкам)
• и т.д ...