Значение lg * N в алгоритмическом анализе

Ответ 1

Ответы, приведенные здесь до сих пор, неверны. lg* n (read "log star" ) - это повторный логарифм. Он определяется как рекурсивно, как

         0             if n <= 1
lg* n =
         1 + lg*(lg n) if n > 1 

Еще один способ подумать - это количество раз, которое вы должны перебирать логарифм до того, как результат меньше или равен 1.

Он растет очень медленно. Вы можете больше узнать о Wikipedia, который включает в себя некоторые примеры алгоритмов, для которых lg* n появляется в анализе.

Ответ 2

Я предполагаю, что вы говорите об алгоритме, проанализированном на слайде 44 этой лекции: http://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf

Где они говорят: "lg * N - постоянная в этой вселенной", я считаю, что они не являются буквальными буквами. lg * N, по-видимому, увеличивается с N по таблице на правой стороне слайда; это просто происходит с такой медленной скоростью, что его нельзя рассматривать гораздо больше (N = 2 ^ 65536 → log * n = 5). По сути, они говорят, что вы можете просто игнорировать log * N как константу, потому что она никогда не будет увеличиваться настолько, чтобы вызвать проблему.

Я мог ошибаться. Это просто, как я его прочитал.

edit: это может помочь заметить, что для этого уравнения они определяют "lg * N" как 2 ^ (lg * (N-1)). Значит, что N-значение 2 ^ (2 ^ (65536)) [гораздо большее число] даст lg * N = 6, например.

Ответ 3

Рекурсивное определение lg * n по Джейсону эквивалентно lg * n = m, когда 2 II m <= n < 2 II (m + 1) где
2 II m = 2 ^ 2 ^... ^ 2 (повторное возведение в степень, m копий 2)
это обозначение стрелки Knuth double вверх. Таким образом
   lg * 2 = 1, lg * 2 ^ 2 = 2, lg * 2 ^ {2 ^ 2} = 3, lg * 2 ^ {2 ^ {2 ^ 2}} = 4, lg * 2 ^ { 2 ^ {2 ^ {2 ^ 2}}} = 5.
Следовательно, lg * n = 4 для 2 ^ {16} <= n < 2 ^ {65536}. Функция lg * n очень медленно приближается к бесконечности. (Быстрее, чем обратная функция Аккермана A (n, n), которая включает в себя n-2 стрелки вверх.)

Стивен

Ответ 4

Logarithm обозначается log или lg. В вашем случае я предполагаю, что правильная интерпретация N + M * log (N).

EDIT: основание для логарифма не имеет значения при анализе асимптотической сложности.

Ответ 5

lg - "LOG" или инверсная экспоненциальная. lg обычно относится к основанию 2, но для алгоритмического анализа база обычно не имеет значения.

Ответ 6

lg n относится к базе данных n. Это ответ на уравнение 2 ^ x = n. В анализе сложности Big O база для журнала не имеет значения. Силы из 2 уроков в CS, поэтому неудивительно, что нам нужно выбрать базу, это будет база 2.

Хорошим примером того, где он появляется, является полностью двоичное дерево высотой h, которое имеет 2 ^ h-1 узлов. Если мы будем обозначать n числом узлов, то это отношение - это дерево lg n с n узлами. Алгоритм, пересекающий это дерево, принимает не более lg n, чтобы увидеть, сохранено ли значение в дереве.

Как и следовало ожидать, wiki имеет дополнительную дополнительную информацию.