פייתון/פייתון גרסה 3/סיבוכיות/סיבוכיות זמן/סיבוכיות לינארית

פעלות עם סיבוכיות לינארית $o(n)$

1. פעולות אריתמטיות $(+,-,*,/,\mathrm{\%})$
2. פעולות השוואה $(<,>,==,!=)$
3. הצהרה משתנה
4. פקודת השמה
5. שימוש במתודה או בפונקציה (ראה דוגמה 5)

דוגמא 1

נתבונן על הדוגמה הבאה:

def findmax(lst):

    curr_max = lst[0]

    for i in lst:
        if i > curr_max:
            curr_max = i

    return curr_max

1. זמן הרצת ה-$for$ - מאחר שאנו עוברים על כל איבר ברשימה אשר אורכה מסומנת ב-$n$ ומשווים איבר, איבר ברשימה לאיבר אחר, זמן ההרצה הינו $o(n)$
2. התנאי המותנה הוא $o(1)$ - קבועה שחשיבותו אינו נכלל בזמן הסיבוכיות.

דוגמא 2

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

def find_smallest(lst):

    curr_smallest = lst[0]

    for i in range(curr_smallest+1, len(lst)):
        if lst[i] < curr_smallest:
            curr_smallest = i

    return curr_smallest

דוגמא 3

תבנית:להשלים דוגמה עם while

דוגמה 4

חיפוש במערך הוא $o(n)$.

דוגמה 5

הוספה לרשימה באמצעות פונקצית Insert:

במקרה הרע ביותר נכניס איבר למיקום האחרון ולכן זמן הריצה הוא $o(n)$