Это то, что я упорядочил функции в порядке возрастания асимптотических скоростей роста. Кроме того, я упростил некоторые функции, применив логарифмические правила.
Правилен ли этот порядок? Или я что-то упускаю?
O( A(n) ) < O( B(n) )
выполняется тогда и только тогда, когда A(n) / B(n)
приближается к 0
, когда n
уходит в бесконечность.
Вы можете проверить свою таблицу здесь: https://www.wolframalpha.com/input/?i=limit+log%28log%28n%29%29+%2F+sqrt%28log%28n%29%29%2C +n+до+бесконечности
Например
log(log(n)) / sqrt(log(n)) -> 0 for n -> inf
Отсюда O(log(log(n)) < O(sqrt(log(n))
.