Повторний логарифм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

В інформатиці, повторний логарифм або ітерований логаритм[1] від n, записується як (зазвичай читається як "лог зірка"), це необхідна кількість повторних логарифмувань перед тим як результат стає меншим або рівним 1. Найпростіше формальне визначення цієї рекурсивної функції:

На додатних дійсних числах, неперервний суперлогарифм (обернена тетрація) по суті тотожний:

але на від'ємних дійсних числах, є 0, тоді як для додатних x, отже, дві функції різняться на від'ємних числах.

Демонстрація lg* 4 = 2

В інформатиці часто використовують для позначення двійкового повторного логарифма, який повторює двійковий логарифм. Повторний логарифм переводить будь-яке додатне число в ціле. Графічно, це можна уявити як кількість зигзагів потрібних, щоб досягти проміжку на осі x.

Математично, повторний логарифм однозначно означений не тільки для основ 2 і e, але для будь-якої основи більшої ніж .

Аналіз алгоритмів

[ред. | ред. код]

Повторний логарифм стає в пригоді в аналізі алгоритмів і складності обчислень, з'являючись у часових і просторових границях складності таких як:

Повторний алгоритм надзвичайно повільно зростає, набагато повільніше ніж сам логарифм. Для значень n значимих для підрахунку швидкодії алгоритмів втілених на практиці (тобто, що значно більше ніж кількість атомів у відомому всесвіті), повторний логарифм з основою 2 має значення не більше 5.

x
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 265536] 5

Більші основи дають менші логарифми. Насправді, єдина відома функція часто використовувана у теорії складності, що зростає повільніше це обернена функція Акермана.

Примітки

[ред. | ред. код]
  1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 3.2: Стандартні позначення та поширені функції. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
  2. Olivier Devillers, "Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.". International Journal of Computational Geometry & Applications 2:01 (1992), pp. 97–111.
  3. Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.