Повторний логарифм
В інформатиці, повторний логарифм або ітерований логаритм[1] від n, записується як (зазвичай читається як "лог зірка"), це необхідна кількість повторних логарифмувань перед тим як результат стає меншим або рівним 1. Найпростіше формальне визначення цієї рекурсивної функції:
На додатних дійсних числах, неперервний суперлогарифм (обернена тетрація) по суті тотожний:
але на від'ємних дійсних числах, є 0, тоді як для додатних x, отже, дві функції різняться на від'ємних числах.
В інформатиці часто використовують для позначення двійкового повторного логарифма, який повторює двійковий логарифм. Повторний логарифм переводить будь-яке додатне число в ціле. Графічно, це можна уявити як кількість зигзагів потрібних, щоб досягти проміжку на осі x.
Математично, повторний логарифм однозначно означений не тільки для основ 2 і e, але для будь-якої основи більшої ніж .
Повторний логарифм стає в пригоді в аналізі алгоритмів і складності обчислень, з'являючись у часових і просторових границях складності таких як:
- Знаходження тріангуляції Делоне множини вершин відомих як евклідове мінімальне кістякове дерево: увипадковлений час[2]
- Алгоритм Фюрера для множення цілих:
- Знаходження приблизного максимуму (елемент не менше медіани): до паралельних операцій[3]
Повторний алгоритм надзвичайно повільно зростає, набагато повільніше ніж сам логарифм. Для значень n значимих для підрахунку швидкодії алгоритмів втілених на практиці (тобто, що значно більше ніж кількість атомів у відомому всесвіті), повторний логарифм з основою 2 має значення не більше 5.
x | |
---|---|
(−∞, 1] | 0 |
(1, 2] | 1 |
(2, 4] | 2 |
(4, 16] | 3 |
(16, 65536] | 4 |
(65536, 265536] | 5 |
Більші основи дають менші логарифми. Насправді, єдина відома функція часто використовувана у теорії складності, що зростає повільніше це обернена функція Акермана.
- ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 3.2: Стандартні позначення та поширені функції. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
- ↑ 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.
- ↑ Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.