סיבוכיות – הבדלי גרסאות

נוספו 4 בתים ,  לפני 3 חודשים
מ
←‏מאפייני הסיבוכיות: קישורים פנימיים
(הוספת ״באנגלית״)
תגיות: עריכה חזותית עריכה ממכשיר נייד עריכה דרך האתר הנייד עריכה מתקדמת מהנייד
מ (←‏מאפייני הסיבוכיות: קישורים פנימיים)
'''בעיה''', בהקשר זה, היא [[קבוצה (מתמטיקה)|קבוצה]] של שאלות בעלות קשר הדוק. דוגמה: בעיית ה[[פירוק לגורמים של מספר שלם|פירוק לגורמים]] היא: כאשר נתון מספר שלם כלשהו, הצג את כל ה[[מספר ראשוני|גורמים הראשוניים]] שלו. שאלה ספציפית קרויה '''מופע''' של הבעיה. דוגמה: השאלה "הצג את הגורמים של המספר 15" היא מופע של בעיית הפירוק לגורמים.
 
'''סיבוכיות הזמן''' של בעיה נתונה היא מספר הצעדים הנחוצים לפתרון מופע שלה כפונקציה של גודל הקלט של מופע זה, תוך שימוש באלגוריתם היעיל ביותר למטרה זו. אם לפתרונו של מופע שאורך הקלט שלו הוא <math> n</math> [[סיבית|סיביות]] נחוצים <math> n^2</math> צעדים, סיבוכיות הזמן שלו היא <math> n^2</math>. מספר הצעדים המדויק תלוי במחשב המסוים שישמש לפתרון הבעיה. כדי להימנע מהתייחסות למחשב מסוים נהוג להשתמש במודל מתמטי עבור מחשב: [[מכונת טיורינג]]. בנוסף, כדי להימנע מחישובים טכניים מדי ומכיוון שעיקר העניין הוא הקצב שבו כמות המשאבים הנדרשים גדלה ככל שהקלט לבעיה גדל, נהוג לסמן את סיבוכיות הזמן באמצעות [[סימון אסימפטוטי]] שמייצג '''סדר גודל''' של זמן הריצה, ולמדוד את זמן הריצה על פי מספר הביצועים של פעולות בסיסיות (כמו ביצוע [[פעולה אריתמטית]], קריאת ערך של תא בזיכרון וכדומה). בצורה זו סיבוכיות הזמן מייצגת את הזמן הנחוץ לפתרונה בכל מחשב מסוים (עד כדי הכפלה או הוספה של קבוע שתלוי ברמת הביצועים של המחשב המסוים הזה), כך שהסיבוכיות המוצגת אינה תלויה במחשב שישמש לפתרון הבעיה ואינה מציגה את הזמן הדרוש לפתרון הבעיה ב[[שנייה|שניות]], אלא מייצגת את סדר הגודל של הזמן הנחוץ לפתרון הבעיה כפונקציה של אורך הקלט.
 
דוגמה: לכיסוח דשא יש סיבוכיות ליניארית, משום שהכפלת שטח הדשא מכפילה את הזמן הנחוץ להשלמת המשימה. לחיפוש במילון, לעומת זאת, יש סיבוכיות [[לוגריתם|לוגריתמית]] בבסיס 2: בהנחה שהמחפש מחפש במילון ב[[חיפוש בינארי]], הכפלת גודל המילון תוסיף רק צעד אחד - פתיחת המילון באמצעו - למספר הצעדים הנחוץ לביצוע החיפוש, משום שצעד זה מקטין לחצי את גודל הבעיה.