Что такое O(log* N) и чем оно отличается от O(log N)?
Что такое O(log*N)?
Ответы (3)
O( log* N ) это "повторный логарифм":
В информатике повторный логарифм n, записываемый как log * n (обычно читается как «логарифмическая звезда»), представляет собой количество раз, которое функция логарифма должна многократно применяться, прежде чем результат станет меньше или равен 1.
person
Larry
schedule
05.03.2010
Это действительно интересно, о чем я не слышал. Q+A +1 каждый. Я предполагаю, что O (log * N) для всех целей и задач O (1). Прохладно.
- person Greg; 05.03.2010
@greg, отсутствие журнала (n) означает, что по мере увеличения количества элементов время увеличивается медленнее. например. В 10 раз больше элементов только увеличивает время выполнения функции в 2 раза.
- person Martin Beckett; 05.03.2010
Кажется, я впервые столкнулся с ним при анализе алгоритма Union-Find, когда он был
O( N log* N ) до того, как его улучшили до O( A N ), где A — обратная функция Аккермана. Я до сих пор не понимаю последнее доказательство, но алгоритм O( N log* N ) читается относительно хорошо.
- person Larry; 05.03.2010
@Martin, но это log*(n), который безумно медленно растет, так что log*(2^65536 -1) = 5. С таким же успехом можно назвать эту константу.
- person Greg; 05.03.2010
Извините, не оценил разницу в лог-звездах, спасибо - узнал что-то новое!
- person Martin Beckett; 05.03.2010
@MartinBeckett Если хотите, возьмите
log*(x)=10 или 2^2^2^2^2^2^2^2^2^2, это число, которое, если бы вся Вселенная была заполнена электронами, я уверен, что их количество не достигнет половины этого числа. Постоянный? математически - нет, а практически - да.
- person Chayim Friedman; 12.06.2020
Бит 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;
}
person
Dan W
schedule
10.05.2015
Как это отвечает на вопрос?
- person Maroun; 10.05.2015
@MarounMaroun: я отредактировал начало ответа, чтобы дать больше контекста. Код — это описание/определение, которое он просил.
- person Dan W; 10.05.2015
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).
person
Manish Kumar
schedule
03.05.2014
O(log* N)ответа нет. - person BalusC schedule 05.03.2010lg*следует точно такому же шаблону, как и обычные функцииlg,division, поэтому это не искусственная функция, даже если она так выглядит. - person Elrond_EGLDer schedule 19.12.2015