תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף

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