בתשובה להאייל האלמוני, 19/01/08 1:07
 |
|
 |
||
|
||||
 |
מדידת הסיבוכיות היא בד''כ על פי המקרה הגרוע ביותר מבין אלו שהאלגוריתם אמור לפעול עליהם. כלומר, אם אתה יודע תמיד איפה הדיסקית, בוודאי שהסיבוכיות של כל העניין טריוויאלי - וגם הבעיה טריוויאלית. אם לעומת זאת הדיסקית יכולה להיות בכל מקום והאלגוריתם לא יודע איזה, אז לצורך בדיקת המקרה הגרוע ביותר אפשר להניח שיש ''יריב ערמומי'' שרואה את הפתרון שלך, ושם דיסקית במקום שיגרום הכי הרבה ''נזק''. |  |
 |
 |
|
|
|
||
|
||||
|
אז לא מחשיבים את Quicksort כאלגוריתם שפועל ב nlonn יותר? | |
|
|
|
|
|
||
|
||||
|
לא החשיבו אותו כך אף פעם, כשמדברים על המקרה הגרוע. לכן לעתים קרובות מלמדים אותו בד בבד עם ניתוחי סיבוכיות על פי המקרה הממוצע. | |
|
|
|
|
|
||
|
||||
|
רק במקרה הממוצע (או אם משתמשים באלגוריתם ליניארי למציאת חציון כדי למצוא את הפיבוט). | |
|
|
|
|
|
||
|
||||
|
כמובן. הבעיה היא לא בP כי אין לאלגוריתם דטרמיניסטי דרך לפתור אותה בזמן פולינומי (נובע מההוכחה על האנוי), אבל בהינתן הפתרון, וידוא שלו (רק במהלך הראשון) כן נעשה בזמן פולינומי, לכן היא בNP, מה שהיה מפריך את P=NP אם הבעיה היתה תקפה. השאלה שלי היא למה בדיוק הבעיה לא תקפה ? |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח מה הכוונה ב"לא תקפה". על כל פנים, שים לב שיש כמה הבדלים מהותיים בינה לבין בעיות חישוביות "רגילות" - בפרט, זו בעיה של חיפוש, לא של תשובת "כן/לא", אבל בעיקר (וזה ההבדל המהותי) - היא מבוססת על קלט *חלקי*, שיש בו מידע מוסתר - בעצם, מעין "קופסה שחורה" שצריך להתמודד איתו. הכוונה היא שיכולים להיות שני קלטים שנראים זהה למכונה, ובכל זאת "מתנהגים" שונה (על סמך מהי הדיסקית המסומנת). נראה לי שכאן נמצא ההבדל המרכזי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |