Что такое 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(), является ответом.

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

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 цветов * (n), в то время как достаточно раскрасить цвета дерева 2, но тогда сложность будет O (n).

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