В інформатиці, повторний логарифм або ітерований логаритм від n, записується як (зазвичай читається як "лог зірка"), це необхідна кількість повторних логарифмувань перед тим як результат стає меншим або рівним 1. Найпростіше формальне визначення цієї рекурсивної функції:
На додатних дійсних числах, неперервний суперлогарифм (обернена тетрація) по суті тотожний:
але на від'ємних дійсних числах, є 0, тоді як для додатних x, отже, дві функції різняться на від'ємних числах.
В інформатиці часто використовують для позначення двійкового повторного логарифма, який повторює двійковий логарифм. Повторний логарифм переводить будь-яке додатне число в ціле. Графічно, це можна уявити як кількість зигзагів потрібних, щоб досягти проміжку на осі x.
Математично, повторний логарифм однозначно означений не тільки для основ 2 і e, але для будь-якої основи більшої ніж .
Аналіз алгоритмів Повторний логарифм стає в пригоді в аналізі алгоритмів і складності обчислень, з'являючись у часових і просторових границях складності таких як:
Знаходження тріангуляції Делоне множини вершин відомих як евклідове мінімальне кістякове дерево: увипадковлений час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.
Повторний алгоритм надзвичайно повільно зростає, набагато повільніше ніж сам логарифм. Для значень n значимих для підрахунку швидкодії алгоритмів втілених на практиці (тобто, що значно більше ніж кількість атомів у відомому всесвіті), повторний логарифм з основою 2 має значення не більше 5.
x (−∞, 1] 0 (1, 2] 1 (2, 4] 2 (4, 16] 3 (16, 65536] 4 (65536, 265536] 5
Більші основи дають менші логарифми. Насправді, єдина відома функція часто використовувана у теорії складності, що зростає повільніше це обернена функція Акермана.
Примітки