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

נוספו 91 בתים ,  לפני 7 שנים
מ
+תמונה
מ (+תמונה)
[[קובץ:Complexity subsets pspace.svg|שמאל|ממוזער|250px|מחלקות סיבוכיות]]
'''סיבוכיות''' (complexity) היא ענף של [[מדעי המחשב]] שבמסגרתו נבחנים המשאבים הנחוצים לפתרון בעיה נתונה באמצעות [[מחשב]], ומושווית יעילותם של [[אלגוריתם|אלגוריתמים]] שונים לפתרון בעיה זו. המשאב העיקרי הנבחן הוא '''[[סיבוכיות זמן|זמן הריצה]]''', כלומר נבחן משך הזמן הנחוץ לשם ביצוע האלגוריתם. משאב נוסף הוא ה'''[[סיבוכיות מקום|זיכרון]]''' הנחוץ לשם ביצוע האלגוריתם. ניתן להביא בחשבון משאבים נוספים, כגון כמה [[מעבד|מעבדים]]ים נחוצים לשם פתרון הבעיה ב[[עיבוד מקבילי]]. ענף הסיבוכיות נבדל מענף ה[[חישוביות]], שבו נבחנת השאלה האם ניתן בכלל לפתור בעיה נתונה, בלא קשר לכמות המשאבים הנחוצה.
 
==מאפייני הסיבוכיות==
|style="direction: ltr;"|O(n!)
|}
 
 
כאשר רמת הסיבוכיות של בעיה היא [[פולינום|פולינומית]] (או פחות מזה) הבעיה נחשבת כבעלת פתרון "[[חישוב יעיל|יעיל]]", משום שהגדלת אורך הקלט אינה מביאה לשינוי דרמטי בזמן הנחוץ לפתרון הבעיה. לעומת זאת, כאשר לבעיה סיבוכיות [[פונקציה מעריכית|מעריכית]] (אקספוננציאלית), שינוי קטן באורך הקלט מביא לשינוי מהותי בזמן הנחוץ לפתרון הבעיה. לדוגמה, כאשר הזמן הנחוץ לפתרונה של בעיה הוא <math>\ O(2^n)</math> (סיבוכיות מעריכית) הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה.