הבדלים בין גרסאות בדף "לוגריתם חוזר"

נוספו 351 בתים ,  לפני 7 שנים
מ
אין תקציר עריכה
מ (בוט: מעביר קישורי בינויקי לויקינתונים - d:q2028293)
מ
 
הלוגריתם החוזר הוא דוגמה קיצונית לפונקציה בעלת גידול איטי: היא קטנה מ- 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 היא [[פונקציית אקרמן]].
 
[[קטגוריה:לוגריתמים]]
[[קטגוריה:סיבוכיות חישובית]]
8,258

עריכות