לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

אלגוריתם

[עריכה]

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

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

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

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

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

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

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

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

ראה גם

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