לוגריתם חוזר

במדעי המחשב וחקר הסיבוכיות, פונקציית הלוגריתם החוזר היא מספר הפעמים שיש להפעיל את פונקציית הלוגריתם עד שהתוצאה אינה עולה עוד על 1. מכיוון שכך, אפשר להגדיר את הפונקציה באופן רקורסיבי:

$\log ^{*}n={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}$

פונקציית הלוגריתם הרגילה, $\ \log$, המופיעה בהגדרה, תלויה בקביעת הבסיס, ולכן גם הלוגריתם החוזר תלוי בבסיס. כדי שהפונקציה תהיה מוגדרת היטב, הבסיס חייב להיות גדול מ- $\ e^{1/e}\approx 1.444668$. במדעי המחשב מקובל להניח שהלוגריתם בינארי, כלומר, בסיסו 2.

הלוגריתם החוזר הוא דוגמה קיצונית לפונקציה בעלת גידול איטי: היא קטנה מ-5 לכל $\ n<2^{65536}$, ועולה ל-6 רק במספר $\ 2^{2^{65536}}$. למעשה, $\ \log ^{*}(n)\leq k$ אם ורק אם $\ n\leq 2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}$, כאשר במגדל החזקות מופיע המספר 2‏, k פעמים. לשם השוואה: הפונקציה $\ \log \cdots \log$ (חזרה m פעמים על פונקציית הלוגריתם הרגילה) מגיעה לערך k כאשר $\ n\leq 2^{2^{\cdot ^{\cdot ^{\cdot ^{2^{k}}}}}}$, וכאן יש במגדל החזקות m הופעות של 2. אם $\ m<k$, המספר הראשון גדול לאין שיעור.

הפונקציה מופיעה בחישובי סיבוכיות, אבל בחישובים מעשיים ניתן להתייחס אליה כאל קבוע, מאחר שהערך "5" מתקבל על ידי מספר הגדול בהרבה ממה שמחשבים בני ימינו מסוגלים להגיע.

הפונקציה היחידה רבת השימוש בתורת הסיבוכיות שגדלה לאט יותר מן הלוגריתם החוזר היא הפונקציה ההופכית של $\ f(n)=A(n,n)$ כאשר A היא פונקציית אקרמן.

לקריאה נוספת

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 55–56 of section 3.2.