מיון מנייה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←קישורים חיצוניים: ויקיזציה |
תיקון להשואה למיונים מבוססי השוואות |
||
שורה 16:
==סיבוכיות ותכונות==
[[סיבוכיות זמן|סיבוכיות הזמן]] של המיון תלויה לא רק במספר האיברים בקלט, אלא גם בטווח האפשרי שלהם, מכיוון שעוברים הן על כל הקלט, והן על כל המערך, שאורכו הוא כאורך הטווח האפשרי של איברי הקלט. אם <math>\ n</math> הוא מספר האיברים ו-<math>\ k</math> הוא הטווח, אז סיבוכיות הזמן היא <math>\ O(n+k)</math>. על כן, אם <math>\ k=O(n)</math>, כלומר הטווח הוא ליניארי בגודל הקלט או פחות מכך, אזי תהיה סיבוכיות הזמן של המיון <math>\ O(n)</math>. זו תוצאה העדיפה אסימפטוטית על זו של מיונים
אפשר ליישם את האלגוריתם בסיבוכיות <math>\ O(n)</math> גם כאשר טווח הערכים הוא <math>\ 1 , \dots , n^2</math>, כלומר לא ליניארי לגודל הקלט. למשל, עבור קלט בגודל <math>\ n</math> ותחום של <math>\ n^2</math>, ממירים את המספרים ל[[בסיס (אריתמטיקה)|בסיס]] <math>\ n</math>, כך שמספר הספרות המקסימלי הוא 2, ומספר התאים במערך <math>\ C</math> הוא בסך הכל <math>\ n</math>, ולכן <math>\ k</math> אינו <math>\ n^2</math> אלא <math>\ n</math>, ואז מיישמים [[מיון בסיס]].
| |||