פייתון/פייתון גרסה 3/סיבוכיות

אלגוריתםעריכה

כל אלגוריתם מציע מספר צעדים לפתרון בעיה מסוימת.

כל אלגוריתם ניתן לייצג כפונקציה על גרף.

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

קיימים שני מדדים לבדיקת יעילות אלגוריתם ביחס לאלגוריתם אחר:

  1. סיבוכיות זמן - זמן ריצה, כמות הזמן הנדרשת לתכנית לרוץ במקרה הרע ביותר.
  2. סיבוכיות מקום - מקום בזיכרון שתוספת התכנית.

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

לדוגמה אם הסיבוכיות של אלגוריתם הוא נתייחס אל הסיבוכיות של האלגוריתם כאילו היה לכאורה

  1. אוסף דוגמאות

ראה גםעריכה

  1. מבני נתונים ואלגוריתמים - מחברת קורס
  2. ויקי-פיתון