Что такое O(log* N)?

Question

Что такое O(log* N)?

Я знаю, о-о, log* неизвестно

Answer 1

O( log* N ) это " повторный логарифм":

В информатике повторный логарифм n, записанный как log* n (обычно читаемый как "log star"), - это число раз, которое функция логарифма должна быть применена итеративно, прежде чем результат станет меньше или равен 1.

Answer 2

log* N бит - это повторяющийся алгоритм, который растет очень медленно, намного медленнее, чем просто log N, По сути, вы просто продолжаете "регистрировать" ответ, пока он не станет ниже единицы (например, log(log(log(...log(N)))), и сколько раз вам пришлось log() это ответ.

В любом случае, это пятилетний вопрос о Stackru, но без кода?(!) Давайте исправим это - вот реализации как для рекурсивных, так и для итеративных функций (они оба дают одинаковый результат):

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}

Answer 3

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

Проще говоря, вы можете принять log * (n) = log (log (log (..... (log * (n))))

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

Пример:

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

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

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