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

80

Что такое O (log * N) и чем он отличается от O (log N)?

algorithm math complexity-theory logarithm iterated-logarithm Тимми
источник
Аналогичный вопрос: stackoverflow.com/questions/2307283/… КO(log* N) сожалению, ответа нет .
BalusC 05
1
Это вопрос о * после журнала или об обозначении O () в целом?
Барт ван Хекелом 05
1
Он находится в некоторых сложных структурах данных, хотя я слишком долго не учусь в школе, чтобы вспомнить, откуда оно взялось!
Ларри
1
Я думаю, не так продвинутый, просто вспомнил - Union Find с начальной нижней границей сжатия пути был установлен на O (n log * n), пока он не был понижен до O (A n), где A - обратная функция Аккермана ..
Ларри
1
Хех. На практике я думаю, что меня устроит оценка O (n) для этого. :-)
RBarryYoung 05

Ответы:

84

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

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

Ларри
источник
9
Это действительно интересная вещь, о которой я не слышал. Q + A +1 каждый. Я предполагаю, что O (log * N) для всех намерений и целей O (1). Круто.
Грег
1
@greg, no log (n) означает, что по мере увеличения количества элементов время медленнее. например. В 10 раз больше элементов приводит к тому, что функция занимает в 2 раза больше времени
Мартин Беккет
2
Я думаю, что впервые столкнулся с этим при анализе алгоритма Union-Find, когда он был O( N log* N )до того, как он был улучшен до O( A N ), где A - обратная функция Аккермана. Я до сих пор не понимаю последнего доказательства, но O( N log* N )алгоритм относительно хорошо читается.
Ларри
13
@Martin, но это log * (n), который безумно медленно растет, так что log * (2 ^ 65536 -1) = 5. Вы также можете назвать эту константу.
Грег
4
Извините, я не оценил разницу между логарифмическими звездами, спасибо - узнал что-то новое!
Мартин Беккет
25

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;
}
Дэн В
источник
2
Как это отвечает на вопрос?
Maroun
3
@MarounMaroun: Я отредактировал начало ответа, чтобы дать больше контекста. Код - это описание / определение, которое он просил.
Дэн В.
9

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

Маниш Кумар
источник