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

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 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).

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

Ответ 4

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

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