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

נוסף בית אחד ,  לפני 5 שנים
מ
אין תקציר עריכה
(←‏דוגמת הרצה: clean up, replaced: <u> ← ''' (17), </u> ← ''' (17) באמצעות AWB)
מאין תקציר עריכה
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד
עם זאת, לרוב המספרים נתונים בבסיס ידוע, כך שלכל בסיס שהוא מתקיים <math>\ d=O(1)</math> ולכן זמן הריצה יהיה <math>\ O(n*k)</math>.
 
אם גודל הקלט, כלומר מספר המספרים שיש למיין, הוא בסדר גודל גדול מזה של מספר הספרות (או: k זניח ביחס לnל-n), כלומר <math>\ k=o(n)</math>, זמן הריצה יהיה <math>\ O(k*n)=O(2n)=O(n)</math>, כאשר זמן הריצה המינימלי למיון <math>\ n</math> מספרים ללא הנחות ידועות על היחס בין גודל הקלט למספר הספרות המקסילי כלשהן הוא <math>\ O(nlog(n))</math>.
 
חשוב לשים לב שלא בכל המקרים <math>\ O(n*k)<O(n*log(n))</math>, והדבר תלוי ביחס שבין גודל הקלט למספר הספרות בכל מספר (לדוגמה, שני מספרים בעלי 10 ספרות עשרוניות ימוינו מהר יותר ב[[מיון מיזוג]] מאשר במיון בסיס).