Асимптотическое сравнение функций - PullRequest
Новая
       13

Асимптотическое сравнение функций

0 голосов
/ 02 сентября 2011

Я хочу сравнить следующие функции асимптотически, а затем расположить их в порядке возрастания.Также запрашивается правильное объяснение lg ((√n)!), Lg (SquareRoot (n!)), SquareRootlg (n!), (Lg (√n)) !, (SquareRoot (lg n)) !, SquareRoot (LG N)!

1 Ответ

0 голосов
/ 09 января 2012

Если вас интересует «общее решение» , и вы много следите за сравнениями асимптотических функций.Вот что я рекомендую:

Использовать определение предела для обозначения BigO , если вы знаете: 

f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf

Вы можете использовать Система компьютерной алгебры Например, с открытым исходным кодом Maxima , здесь находится Документация Maxima по пределам .

Итак, проверка lg(n)*lg(n) = O(sqrt(n)) может быть датчанином - проверка ограничения (lg(n)lg(n))/sqrt(n): 

(%i1) limit( (log(n)^2) / (sqrt(n)), n, inf);
(%o1)                                  0

Если хотите, более длинное, более информативное обозначение: 

(%i1) f(n) := log(n)^2 ;
                                           2
(%o1)                           f(n) := log (n)
(%i2) g(n) := sqrt(n) ;
(%o2)                           g(n) := sqrt(n)
(%i3) limit(f(n)/g(n), n, inf);
(%o3)                                  0
...