6 יעילותם של אלגוריתמים או איך עושים את זה בזול?

99 ~ ר . ~ r . רי אגייפ ~ ; , ; א ( לייא , ( 37 כאשר מתבקשים לבנות גשר , קל לבנות אותו " לא נכון " . הגשר עלול להיות צר מלהכיל את מספר הנתיבים הרצוי , חלש מכדי לשאת את התנועה בשעות העומס , או שהוא עלול לא להגיע כלל אל העבר האחר ! אולם , אפילו אם הגשר יינכון" , במובן זה שהוא עונה לחלוטין על כל דרישות הביצוע , לא כל הצעת תכנון עבורו תוכל להתקבל . ייתכן שביצוע התכנון המוצע דורש כוח אדם רב מדי , או אולי חומרים או מרכיבים רבים מדי . במלים אחרות , למרות שהתוצאה עשויה להיות גשר טוב , התכנון עלול להיות יותר מדי יקר . תחום האלגוריתמיקה חשוף לבעיות דומות . אלגוריתם עלול להיות יקר מדי ולכן בלתי קביל . וכ , ך בעוד שפרק 5 הוקדש להוכחה שאלגוריתמים ךא נכוניס הם רעים , ושנדרשות שיטות להוכחת נכונות אלגוריתמית , טוען פרק זה שגם אלגוריתם נכון אינו עונה בהכרח על כל הציפיות . הואיל וכוח אדם ועלויות אחרות הקשורות בו אינם מענייננו כאן , נותרים בידינו שני קריטריונים למדידת יעילות - חומרים וזמן . במדעי המחשב מכונים אלה מדדי סיבוכיות ( , complexity measures ) והחשובים שבהם הם זיכרון ( אשר נקרא לפעמים מקום ) וזמ...  אל הספר
האוניברסיטה הפתוחה