17-02-2014, 10:40
|
|
|
|
חבר מתאריך: 23.09.03
הודעות: 12,132
|
|
60 שניות על סיבוכיות:
כשרוצים לאמוד זמן ריצה של אלגוריתם משתמשים במושג סיבוכיות. לא מדובר ב"זמן ריצה" שלו כי זה משתנה כמובן ממחשב למחשב, או אפילו באותו מחשב בריצות שונות (כתלות של עומס על המחשב בנקודות זמן מסויימת).
האומדן נעשה כמספר הפעולות שהאלגוריתם מבצע כתלות בגודל הקלט. אני לא אכנס כרגע להגדרות מתמטיות של חסמים עליונים ותחתונים, אבל בדר"כ משתמשים בסימון [tex]\Theta[/tex] שמסמן "חסם הדוק" (גם חסם תחתון וגם חסם עליון).
לדוגמא, כאשר [tex]n[/tex] הוא גודל הקלט:
סריקת מערך, איבר-איבר: [tex]\Theta (n)[/tex]
מיון מערך בעזרת bubble-sort: [tex]\Theta (n^2)[/tex] (בלי להתייחס למקרה הטוב ביותר, בו המערך כבר ממויין, ואז מדובר ב [tex]O(n)[/tex])
בנוגע לשאלה שלך:
בגלל שרשימה מקושרת לא בהכרח יושבת באופן רציף בזיכרון, גם אם אתה יודע את האינדקס שאתה רוצה למחוק, המחשב עדיין צריך לרוץ על כל האיברים בה, מהראשון עד לאינדקס הרצוי, לכן גם מדובר ב- [tex]\Theta (n)[/tex]
_____________________________________
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rick Cook
נערך לאחרונה ע"י DeepSpace בתאריך 17-02-2014 בשעה 10:51.
|