פונקציות מעריכיות

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

קל להוכיח שמספר הגרגרים הכולל על הלוח יהיה 1 – 2⁶⁴, שזה 18,446,744,073,709,551,615.

מספר הגרגרים על המשבצת שמספרה N הוא 2^N-1, כלומר שתים כפול בעצמו N–1 פעמים. פונקציה כזו נקראת אקספוננציאלית, או מעריכית, ותכונה מרכזית שלה היא שערכה גדל מהר מאד עם עליית הערך של N.

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

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

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

בעיה אחרת המתקשרת לנושא היא בעיית הפירוק: נכון להיום אין אלגוריתם מוּכָּר לפירוק מספר שלם לגורמיו הראשוניים בזמן פולינומי. שיטות הצפנה מסוימות מסתמכות על ההנחה (שלא הוכחה) שלא ניתן לבצע פירוק לגורמים בזמן פולינומי. אבל פה, להבדיל מבעיית מגדלי האנוי, אין מניעה עקרונית שיום אחד יפותח אלגוריתם יעיל.

כדי להתרשם מהמהירות של צמיחה מעריכית, לחצו על החיצים שלהלן.