סיבוכיות

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

"בעיה" כאן היא קבוצה של שאלות דומות. כל שאלה ספציפית נקראת מופע של הבעיה.
לדוגמה, בעיית הפירוק לגורמים: נתון מספר שלם, מצא את הגורמים הראשוניים שלו.
מופע של הבעיה הוא שאלה כמו: כמה הם הגורמים של 15?

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

דוגמה פשוטה: כיסוח דשא הוא ליניארי, הגדלת השטח מכפילה את הזמן.
חיפוש במילון עם חיפוש בינארי הוא לוגריתמי, הגדלת המילון מכניסה רק צעד נוסף.
כך רמות סיבוכיות שונות מראות עד כמה בעיות דורשות משאבים.
כאשר סיבוכיות היא פולינומית מדובר בפתרון "יעיל".
לעומת זאת סיבוכיות מעריכית גדלה במהירות רבה; לדוגמה O(2^n) מכפילה את הזמן כאשר n גדל ב-1.

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

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

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

"בעיה" היא קבוצה של שאלות דומות. שאלה בודדת נקראת מופע.
לדוגמה, בעיית הפירוק: למצוא את הגורמים של מספר.
השאלה "למה 15 מתפרק?" היא מופע של הבעיה.

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

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

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

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