Что значит "log *"?

Question

Я встретил термин O(log* N) в книге, которую я читаю о структурах данных.Что означает log*?Я не могу найти его в Google , а WolframAlpha тоже не понимает .

Answer 1

Это называется функция повторного логарифма . Это очень медленно растущая функция. Например:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5 / обратите внимание, что (2 ^ 65536) намного больше, чем число атомов в наблюдаемой вселенной /

Или в случае Big O это можно было бы считать постоянным временем.

Answer 2

Это повторный логарифм. См. здесь для описания множества различных временных сложностей и здесь для более подробной информации о самом итерированном логарифме.

Повторный логарифм - это количество раз, которое логарифм должен быть применен до того, как результат станет один или меньше.

Answer 3

log * (n) - «log Star n», известная как «повторный логарифм»

В простом слове вы можете принять log * (n) = log (log (log (..... (log * (n)))))

log * (n) очень мощный.

Пример:

1) Log * (n) = 5, где n = количество атомов во вселенной

2) раскраска дерева с использованием 3 цветов может быть выполнена в журнале * (n), в то время как раскраска дерева 2 достаточно, но тогда сложность будет O (n).

3) Нахождение триангуляции Делоне для набора точек, зная евклидово минимальное остовное дерево: случайное время O (n log * n).

Я надеюсь, что вы можете визуализировать Log * (n) вот так на WolframAlpha Проверьте здесь

Answer 4

log * - это количество раз, которое вам нужно применить функцию log, пока вы не достигнете значения, которое меньше или равно 1. Для экземпляра: log * (16) = 3, потому что log ₂ (журнал ₂ (журнал ₂ (16))) = 1.

В практических целях вы можете рассматривать это как константу, потому что эта функция растет очень медленно.