הצגת המקור של הדף "לוגריתם חוזר"

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

:<math>
  \log^* n =
  \begin{cases}
    0                  & \mbox{if } n \le 1; \\
    1 + \log^*(\log n) & \mbox{if } n > 1
   \end{cases}
 </math>

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

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

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

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

==לקריאה נוספת==
<div class="mw-content-ltr">
* 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.
</div>

{{בקרת זהויות}}

[[קטגוריה:לוגריתמים]]
[[קטגוריה:סיבוכיות חישובית]]