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

נוספו 39 בתים ,  לפני 9 חודשים
מ
(←‏דוגמת הרצה: הסרת י' מיותרים)
מ (←‏זמן ריצה: הגהה)
 
==זמן ריצה==
עקרונית, זמן הריצה של האלגוריתם הוא <math>\ O(k* \cdot (n + d))</math>, כאשר n הוא כמות המספרים בקלט, k הוא מספר הספרות המקסימלי בכל מספר ו-d הוא הבסיס בו המספרים נתונים.
עם זאת, לרוב המספרים נתונים בבסיס ידוע, כך שלכל בסיס שהוא מתקיים <math>\ d = O(1)</math> ולכן זמן הריצה יהיה <math>\ O(n* \cdot k)</math>.
 
אם גודל הקלט, כלומר מספר המספרים שיש למיין, הוא בסדר גודל גדול מזה של מספר הספרות (או: k זניח ביחס ל-n), כלומר <math>\ k = o(n)</math>, זמן הריצה יהיה <math>\ O(k* \cdot n)=O(2n)=O(n)</math>, כאשר זמן הריצה המינימלי למיון <math>\ n</math> מספרים ללא הנחות ידועות על היחס בין גודל הקלט למספר הספרות המקסימלי כלשהן הוא <math>\ O(nlogn \log(n))</math>.
 
חשוב לשים לב שלא בכל המקרים <math>\ O(n* \cdot k)<O(n* \cdot \log(n))</math>, והדבר תלוי ביחס שבין גודל הקלט למספר הספרות בכל מספר (לדוגמה, שני מספרים בעלי 10 ספרות עשרוניות ימוינו מהר יותר ב[[מיון מיזוג]] מאשר במיון בסיס).
 
==ראו גם==
24

עריכות