סיבוכיות זמן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

הסימון הרווח לזמן הריצה של אלגוריתמים הינו:

\Theta\left(f(n)\right) זמן ריצה פרופורציונלי, עד כדי קבוע, לפונקציה f\left(n\right).
O\left(f(n)\right) זמן ריצה שאינו עולה על הפונקציה f\left(n\right), עד כדי קבוע.
\Omega\left(f(n)\right) זמן ריצה שאינו פוחת מהפונקציה f\left(n\right), עד כדי קבוע.

הגדרות פורמליות ליותר למושגים אלו ניתן למצוא ב b:מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה

סדרי גודל נפוצים[עריכת קוד מקור | עריכה]

זמן ריצה לוגריתמי[עריכת קוד מקור | עריכה]

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

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

זמן ריצה לינארי[עריכת קוד מקור | עריכה]

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

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

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

זמן ריצה לינארי הוא בפרט פולינומי ועל כן נחשב חישוב יעיל.

זמן ריצה פולינומי[עריכת קוד מקור | עריכה]

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

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

זמן ריצה מעריכי[עריכת קוד מקור | עריכה]

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

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

זמן ריצה תת-מעריכי[עריכת קוד מקור | עריכה]

סיבוכיות זמן ריצה תת-מעריכית או תת-אקספוננציאלית, מוערכת על ידי \ L_n[\alpha,c], כאשר:

\ L_n[\alpha,c]=\mbox{exp}(c\log(n)^{\alpha}\log\log(n)^{1-\alpha})

\ \alpha הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-\ \alpha הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של \ \alpha, הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-\ c גדול יותר. לשם השוואה, \ L_n[1,c]=n^c היא סיבוכיות אקספוננציאלית, בעוד ש-\ L_n[0,c]=(\log(n))^c היא סיבוכיות פולינומית. על סולם זה, קל להעריך את מידת היעילות של האלגוריתם מתוך התבוננות בערך \ \alpha למשל \ L_n[1/2,c] נמצאת ב"אמצע הדרך" בין סיבוכיות אקספוננציאלית לפולינומית.

זמן הריצה של פתרון בעיית הפירוק לגורמים[עריכת קוד מקור | עריכה]

בעיית הפירוק של מספר שלם לגורמים נחשבה במשך שנים לבעיה אקספוננציאלית והיא עמדה על סיבוכיות משוערת מסדר גודל \ L_n[1/2,c] והושגו רק שיפורים מינוריים בערכו של הקבוע \ c. שיפור משמעותי הושג ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת נפת שדה מספרים המיוחדת לפירוק מספרים בעלי מבנה מיוחד כמספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה \ L_n[1/3,c] כשהקבוע \ c=(32/9)^{1/3}\approx1.526. כמספר שנים לאחר מכן, פותח האלגוריתם הכללי - "נפת שדה המספרים הכללית" המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-\ L_n[1/3,c], כשהקבוע \ c=(64/9)^{1/3}\approx1.923. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן מוכחות.

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

ראו גם[עריכת קוד מקור | עריכה]