סיבוכיות זמן
בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם כפונקציה של גודל הקלט.
אין בוחנים את זמן הריצה ביחידות זמן (כגון שניות), משום שמשך הזמן לביצוע פעולה תלוי במודל החישובי ובמחשב שעליו רץ האלגוריתם. למשל, ייתכן שבמודל או בארכיטקטורה מסוימת ניתן לחלק מספר אחד בחברו בצעד אחד, ואילו במודל או ארכיטקטורה אחרת יידרשו לאותה פעולה מספר צעדים. משום כך, בניתוח הסיבוכיות של אלגוריתם מקובל להביא בחשבון רק את סדרי הגודל, ולהתעלם מקבועים. למשל, אלגוריתם המבצע פעולות על קלט בגודל הוא בעל "זמן ריצה ליניארי".
הסימון הרווח לזמן הריצה של אלגוריתמים הוא:
| זמן ריצה פרופורציוני, עד כדי קבוע, לפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} . | |
| הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(f(n))} | זמן ריצה שאינו עולה על הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} , עד כדי קבוע. |
| הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(f(n))} | זמן ריצה שאינו פוחת מהפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} , עד כדי קבוע. |
הגדרות פורמליות יותר למושגים אלו ניתן למצוא בקורס בויקיספר.
סדרי גודל נפוצים
זמן ריצה לוגריתמי
אלגוריתם בעל זמן ריצה לוגריתמי מסתיים תוך זמן פרופורציוני ללוגריתם של גודל הקלט. אין צורך לציין את בסיס הלוגריתם, משום שהחלפת בסיס שקולה לכפל בקבוע, ולכן אם זמן הריצה פרופורציוני לגודל הקלט לפי בסיס לוגריתם כלשהו, הוא פרופורציוני לגודל הקלט גם לפי כל בסיס לוגריתם אחר.
לדוגמה, חיפוש ברשימה ממוינת (בשיטת החצייה) מתבצע בזמן ריצה לוגריתמי. תפקידו של האינדקס בבסיס נתונים הוא לאפשר זמן ריצה לוגריתמי בחיפושים, כאשר ללא אינדקס זמן הריצה הוא ליניארי.
זמן ריצה ליניארי
נאמר על אלגוריתם שזמן ריצתו ליניארי אם זמן הריצה שלו חסום על ידי פונקציה ליניארית בגודל הקלט, או – באופן שקול – פרופורציוני לאורך הקלט.
לדוגמה, אלגוריתם המחפש את המספר הגדול ביותר ברשימת מספרים נתונה על ידי מעבר סדרתי על הרשימה הוא בעל זמן ריצה ליניארי, שכן אם גודל הקלט הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} האלגוריתם יבצע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} צעדים.
מאידך, אלגוריתם מיון הממיין רשימת מספרים על ידי בחירת המספר הגדול ביותר והסרתו מהרשימה, בחירת השני בגודלו והסרתו, וכן הלאה, אינו בעל זמן ריצה ליניארי. זאת משום שאם גודל הקלט הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , האלגוריתם מבצע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} שלבים, ובכל שלב מבצע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} צעדים (מעבר על כל המספרים שנותרו) ולכן זמן הריצה יהיה ריבועי (פולינום ממעלה שנייה).
זמן ריצה ליניארי הוא בפרט פולינומי ועל כן נחשב חישוב יעיל.
זמן ריצה פולינומי
לאלגוריתם נתון ישנו זמן ריצה פולינומי אם קיים פולינום כך שזמן הריצה של האלגוריתם עבור קלטים בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} חסום על ידי ערך הפולינום עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . אלגוריתמים אשר זמן ריצתם אינו חסום על ידי פולינום, כגון אלגוריתמים בעלי זמן ריצה מעריכי, נקראים לעיתים "סופר-פולינומיים".
מקובל לקשר זמן ריצה פולינומי עם חישוב יעיל, כך שאלגוריתם ייחשב יעיל אם זמן הריצה שלו פולינומי. מעשית, לא כל זמן ריצה פולינומי מעיד על יעילות, שכן קיימים פולינומים בעלי חזקות גבוהות – בעת פיתוח אלגוריתם נעדיף זמן ריצה פולינומי מסדר נמוך, כגון זמן ליניארי או ריבועי.
זמן ריצה מעריכי (אקספוננטי)
סיבוכיות זמן הריצה של אלגוריתם היא מעריכית אם ורק אם פונקציית זמן הריצה שלו חסומה על ידי פונקציה מעריכית (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k^n} ) כפול קבוע, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>1} .
על פי רוב, אלגוריתמים בעלי זמן ריצה מעריכי אינם נחשבים ליעילים, וזאת משום שהפונקציה המעריכית "גדלה מהר מאוד" ביחס לקלט; לכן, מועדף השימוש באלגוריתמים מזמני ריצה טובים יותר. דוגמה לאלגוריתם שכזה: אלגוריתם לפתרון בעיית מגדלי האנוי.
זמן ריצה תת-מעריכי
סיבוכיות זמן ריצה תת-מעריכית או תת-אקספוננטית, מוערכת על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[\alpha,c]} , כאשר:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[\alpha,c]=\exp\bigl(c\log(n)^{\alpha}\log(\log(n))^{1-\alpha}\bigr)}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} גדול יותר. לשם השוואה, היא סיבוכיות מעריכית, בעוד ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[0,c]=\log(n)^c} היא סיבוכיות פולינומית. על סולם זה, קל להעריך את מידת היעילות של האלגוריתם מתוך התבוננות בערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[0.5,c]} נמצאת ב"אמצע הדרך" בין סיבוכיות מעריכית לפולינומית.
![{\displaystyle L_{n}[1,c]=n^{c}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a33054ae4ae22d5824b44222906094eaae7810c)
זמן ריצה עצרתי
מונח זה מתאר אלגוריתמים שזמן הריצה שלהם חסום על ידי פונקציית עצרת. בדומה לאלגוריתמים בעלי זמן ריצה מעריכי, אלגוריתם שפועל בזמן ריצה עצרתי נחשב ללא-יעיל במיוחד כאשר מדובר בקלטים גדולים. האלגוריתם המדויק הידוע לפתרון בעיית הסוכן הנוסע נחשב לאלגוריתם בעל זמן ריצה שכזה.
זמן הריצה של פתרון בעיית הפירוק לגורמים
בעיית הפירוק לגורמים של מספר שלם נחשבה במשך שנים לבעיה מעריכית והיא עמדה על סיבוכיות משוערת מסדר גודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[0.5,c]} והושגו רק שיפורים מינוריים בערכו של הקבוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} . שיפור משמעותי הושג ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת נפת שדה מספרים המיוחדת לפירוק מספרים בעלי מבנה מיוחד כמספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[1/3,c]} כשהקבוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=(32/9)^{1/3}\approx1.526} . כמספר שנים לאחר מכן, פותח האלגוריתם הכללי – "נפת שדה המספרים הכללית" המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n[1/3,c]} , כשהקבוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=(64/9)^{1/3}\approx1.923} . בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות – אך אינן מוכחות.
מומחים הראו שעל ידי אלגוריתם קוונטי המבוצע במחשב קוונטי, כגון אלגוריתם שור, ניתן להפחית את זמן הריצה של בעיית הפירוק לגורמים לזמן ריצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log(n)^3)} הנמוך משמעותית.
ראו גם
סיבוכיות זמן38340314Q2393193