תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות) |
|||
שורה 50:
# חזור על התהליך עבור כל איברי המערך (כלומר - כעת עבור על כל איברי המערך פרט לראשון, חפש את המינימלי מביניהם והחלף עם השני, וכן הלאה).
כמה פעולות דורש המיון? עבור כל איבר במערך, מתבצעות כמה פעולות:
* מציאת המינימלי, שהיא פעולה שכרוכה במעבר על כל איברי המערך (ליתר דיוק - איברי המערך, מאיבר זה והלאה) - מחיר פעולה זו הוא <math dir="ltr">\displaystyle O(n)</math>. שימו לב שגם כאן אנו מתעלמים בחישוב מהעובדה שבכל פעם אנו עוברים על פחות ופחות איברים (אפשר לראות שהחיסכון הכולל מכך הוא <math dir="ltr">\displaystyle n/2</math> פעולות, אבל זה
* החלפת שני איברים היא פעולה שעלותה <math dir="ltr">\displaystyle O(1)</math>.
סך הכל, עבור כל איבר במערך (בו יש <math dir="ltr">\displaystyle n</math> איברים), מתבצעות פעולות שעלותן <math dir="ltr">\displaystyle O(n)</math>. לכן, העלות הכוללת של המיון היא <math dir="ltr">\displaystyle O(n^2)</math>.
=====חישובים כלליים=====
| |||