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

Question

В настоящее время я читаю об алгоритмическом анализе и читаю, что определенный алгоритм (взвешенное быстрое объединение со сжатием пути) имеет порядок N + M lg * N. Очевидно, что это линейно, поскольку lg * N является постояннойвселенная.Какая математическая операция упоминается здесь.Я не знаком с обозначением LG * N.

Answer 1

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

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

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

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

Answer 2

Рекурсивное определение lg * n Джейсоном эквивалентно lg * n = m при 2 II m <= n <2 II (m + 1) </em> где
2 II m = 2 ^ 2 ^ ... ^ 2 (повторное возведение в степень, m копий из 2)
является двойной нотацией стрелки Кнута. Таким образом
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} </em>. Функция lg * n очень медленно приближается к бесконечности. (Быстрее, чем обратная функция Аккермана A (n, n) , которая включает n-2 стрелки вверх.)

Стивен

Answer 3

Я предполагаю, что вы говорите об алгоритме, проанализированном на слайде 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.

Answer 4

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

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

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

Answer 5

lg - это «LOG» или обратная экспонента.lg обычно относится к базе 2, но для алгоритмического анализа база обычно не имеет значения.

Answer 6

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

РЕДАКТИРОВАТЬ: Основание логарифма не имеет значения при выполнении асимптотического анализа сложности.