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

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
מ ←‏ראו גם: הפניה לפורטל
מ ←‏קישורים חיצוניים: תיקון קישור
שורה 62: שורה 62:


==קישורים חיצוניים==
==קישורים חיצוניים==
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo Complexity Zoo] - אינדקס מקיף של מחלקות סיבוכיות
* [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo] - אינדקס מקיף של מחלקות סיבוכיות


[[קטגוריה:סיבוכיות|*]]
[[קטגוריה:סיבוכיות|*]]

גרסה מ־12:37, 26 בדצמבר 2008

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

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

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

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

דוגמה זו ממחישה שלבעיות שונות עשויה להיות רמת סיבוכיות שונה. הטבלה הבאה מציגה רמות אחדות של סיבוכיות בסדר יעילות יורד (n הוא גודל הקלט, c הוא קבוע):

שם סימון
קבוע O(1)
לוגריתמי O(log(n))
לינארי O(n)
O(nlog(n))
פולינומי O(nc)
מעריכי O(cn)
עצרתי O(n!)


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

בעיות הכרעה

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

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

תורת הסיבוכיות מבחינה לעתים קרובות בין התשובה "כן" לתשובה "לא". דוגמה: הקבוצה NP היא קבוצת הבעיות שבהן התשובה "כן" ניתנת לבדיקה בזמן סביר. הקבוצה Co-NP היא קבוצת הבעיות שבהן התשובה "לא" ניתנת לבדיקה בזמן סביר. הקידומת Co היא קיצורה של המלה complement - משלים. המשלים של בעיה נתונה היא הבעיה שבה כל התשובות "כן" ו"לא" מוחלפות זו בזו. הבעיה "האם ראשוני" והבעיה "האם מורכב" (מספר מורכב הוא מספר שאינו ראשוני) משלימות זו את זו.

האם P=NP?

הקבוצה P היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות מכונה דטרמיניסטית בזמן פולינומי. הקבוצה NP היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות מכונה לא דטרמיניסטית בזמן פולינומי, או - לחליפין - לבדוק נכונות של פתרון נתון בזמן פולינומי. השאלה "האם הקבוצה P שווה לקבוצה NP" היא השאלה המרכזית במדעי המחשב. זו שאלה פתוחה, מכון קליי למתמטיקה מציע פרס של מיליון דולר לראשון שיפתור אותה.

ניתן יהיה להכריע בשאלה האם P=NP על ידי הכרעת השאלה האם יש בעיה NP-שלמה ב P.

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

סוגים שונים של סיבוכיות

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

ראו גם

עיינו גם בפורטל

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

קישורים חיצוניים

  • Complexity Zoo - אינדקס מקיף של מחלקות סיבוכיות

תבנית:Link FA