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

что это O(log* N)?

Я знаю, большой-ой,log* неизвестно.

3 66
algorithm complexity-theory logarithm iterated-function

3 ответа:

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

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

75

The 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;
}
13

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).

7