 |
|
 |
||
|
||||
 |
שימו לב למשהוא משעשע, הדרך הכי מהירה למיין היא הדרך הנאיבית! הסיבה לזה היא שאי אפשר לחפש ברשימה ממוינת במהירות של LOGn והסיבה לזה היא שאפילו אם אתה יודע במדויק את המיקום של איבר מסויים לוקח לך N צעדים להגיע אליו (הN פעולות הן "הזז את הראש הקורא צעד ימינה"). זהו... סתם רציתי שתדעו שכל מה שלמדתם על מחשבים לא תקף למכונות טיורינג :-) [כאתגר אתם מוזמנים לוודא שהאלגוריתם מיון מיזוג לוקח N בריבוע במכונת טיורינג...] |
 |
 |
 |
|
|
|
||
|
||||
|
[צ] "זהו... סתם רציתי שתדעו שכל מה שלמדתם על מחשבים לא תקף למכונות טיורינג" [/צ] תקף תחת מגבלות ידועות. כל מודלי החישוב ההגיוניים המוכרים, או שחלשים ממכונת טיורינג, או ששקולים לה פולינומית. דרגת הפולינום זה סיפור אחר, וזה ידוע. |
|
|
|
|
|
|
||
|
||||
|
מה שדורפל אמר. נראה לי שאתה לא מבין מה מכונת טיורינג באה לעשות, ולמה (וגם לא איך עובדים מחשבים ''אמיתיים''). | |
|
|
|
|
|
||
|
||||
|
בדיון הסטנדרטי על סיבוכיות של מיון, המדד שמדברים עליו הוא מספר ההשוואות שהאלגוריתם מבצע ולא זמן הריצה שלו, בדיוק כדי לא להיות תלויים במודל. גם החסם של nlogn לסיבוכיות של מיון הוא חסם רק על מספר ההשוואות. בדרך כלל מדגישים את זה בקורס מבני נתונים. קח כתרגיל הביתה להוכיח שבמכונת טיורינג מרובת סרטים (נגיד 3) כשהאיברים למיון שייכים לאלף-בית של המכונה אכן אפשר למיין בזמן ריצה nlogn. |
|
|
|
|
|
|
||
|
||||
|
טוב בסדר אז השוואות :-) (ואני לא מצליח להבין איך אתה מקבל את הLOG N גם אם 3 סרטים (וזה לא בגלל שאתה טועה זה כי בגלל שאני לא חכם מספיק)) |
|
|
|
|
|
|
||
|
||||
|
אם שלושה סרטים לא תקבל לוג, עם אולי כן. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |