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

אלגוריתם

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

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

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

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

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

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

לדוגמה אם הסיבוכיות של אלגוריתם הוא $n^{2}+2$ נתייחס אל הסיבוכיות של האלגוריתם כאילו היה לכאורה $n^{2}$

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

ראה גם

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