ראיתי באחד הספרים את השאלה-

נסו למצוא מהו היחס האסימפטוטי בין גודל המערך לבין כמות ההחלפות שיש לבצע כדי שיהיה ממוין בסדר עולה? הדרכה: תוכלו לבצע ניסוי על מערכים בגדלים שונים.

רציתי לדעת אם מישהו יוכל להסביר לי מה המשמעות של "יחס אסימפטוטי". ואם זה יעזור, עשיתי מדידות כנדרש בשאלה-

למערך בגודל 100 איברים: נדרשות 2336 החלפות.
למערך בגודל 300 איברים: נדרשות 21710 החלפות.
למערך בגודל 500 איברים: נדרשות 63664 החלפות.
למערך בגודל 700 איברים: נדרשות 126915 החלפות.
למערך בגודל 1000 איברים: נדרשות 244002 החלפות.
למערך בגודל 3000 איברים: נדרשות 2247703 החלפות.
למערך בגודל 5000 איברים: נדרשות 6261442 החלפות.
למערך בגודל 7000 איברים: נדרשות 12264130 החלפות.

תנסה פה:

אסימפטוטי

ואם המתמטיקה לא מובנת אני אנסה לעזור.

בינתיים, כמה עצות שאולי יעזרו לך:

1. קח בחשבון שמדידה על מערך אחד בגודל נתון לא בהכרח מייצגת - מה אם בחרת במקרה מערך שהוא כבר ממויין? או ממוין בסדר יורד? הייתי מנסה לכל גודל של מערך לבחור 10 פעמים ערכים אקראים, למדוד את מספר הפעולות ולקחת את הממוצע. אם תרצה אפילו 50 או 100 פעם - עוד יותר טוב.
2. אחרי שעשית את זה, נסה לפתוח את מספר האיברים מול מספר הפעולות ב-Excel. האם אתה רואה איזשהוא קשר? רמז: נסה להשתמש בפונקציית ה-log.