Является ли lg * (n) временная сложность лучше, чем lg (n)?

Question

Я пытаюсь понять временную сложность lg * (n) [log * (n) base 2] по сравнению с lg (n), и мне интересно, какой из них быстрее ... кто-то может это объяснить, пожалуйста? Заранее спасибо.

Answer 1

Согласно Википедии, итеративный логарифм (log *) - одна из самых медленных растущих временных сложностей. Фактически, из всех обычно используемых сложностей, он является вторым самым медленным, побежденным только обратной функцией Аккермана. Это означает, что он растет значительно медленнее и в результате завершается намного быстрее, чем функция журнала.

Источник: https://en.wikipedia.org/wiki/Iterated_logarithm#Analysis_of_algorithms

Answer 2

Я никогда раньше не видел lg*(n) нотацию, но я предполагаю, что вы имеете в виду логарифмическую базу 2 против логарифмической базы 10. Получается, что log2(N) == log10(N) * 3.32192809489..., который представляет собой постоянную разницу коэффициентов, и мы отбрасываем постоянные коэффициенты при анализе алгоритмов c сложность. В результате все логарифмы считаются равными, и нам не нужно беспокоиться об определении базы в алгоритмах c сложность.

При изучении фактического времени выполнения, log10 (N) быстрее, чем log2 (N) , но очень редко разработчики действительно анализируют среды выполнения таким образом, они обычно делают это с помощью профилировщика.