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

קפיצה לניווט קפיצה לחיפוש
נוספו 14 בתים ,  לפני 10 שנים
מ
אין תקציר עריכה
מ (בוט מוסיף: ms:Teori kekompleksan pengiraan)
מ
דוגמה: לכיסוח דשא יש סיבוכיות לינארית, משום שהכפלת שטח הדשא מכפילה את הזמן הנחוץ להשלמת המשימה. לחיפוש במילון, לעומת זאת, יש סיבוכיות [[לוגריתם|לוגריתמית]] בבסיס 2: בהנחה שהמחפש מחפש במילון ב[[חיפוש בינארי]], הכפלת גודל המילון תוסיף רק צעד אחד - פתיחת המילון באמצעו - למספר הצעדים הנחוץ לביצוע החיפוש, משום שצעד זה מקטין לחצי את גודל הבעיה.
 
דוגמה זו ממחישה שלבעיות שונות עשויה להיות רמת סיבוכיות שונה. הטבלה הבאה מציגה רמות אחדות של סיבוכיות בסדר יעילות יורד (n הוא גודל הקלט, c הוא קבוע גדול מ-1):
 
{| class="wikitable"

תפריט ניווט