בתשובה למתן ליבוביץ, 20/01/08 18:04
 |
|
 |
||
|
||||
 |
בדיון הסטנדרטי על סיבוכיות של מיון, המדד שמדברים עליו הוא מספר ההשוואות שהאלגוריתם מבצע ולא זמן הריצה שלו, בדיוק כדי לא להיות תלויים במודל. גם החסם של nlogn לסיבוכיות של מיון הוא חסם רק על מספר ההשוואות. בדרך כלל מדגישים את זה בקורס מבני נתונים. קח כתרגיל הביתה להוכיח שבמכונת טיורינג מרובת סרטים (נגיד 3) כשהאיברים למיון שייכים לאלף-בית של המכונה אכן אפשר למיין בזמן ריצה nlogn. |
 |
 |
 |
|
|
|
||
|
||||
|
טוב בסדר אז השוואות :-) (ואני לא מצליח להבין איך אתה מקבל את הLOG N גם אם 3 סרטים (וזה לא בגלל שאתה טועה זה כי בגלל שאני לא חכם מספיק)) |
|
|
|
|
|
|
||
|
||||
|
אם שלושה סרטים לא תקבל לוג, עם אולי כן. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |