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

פעלות עם סיבוכיות לינארית

עריכה
  1. פעולות אריתמטיות  
  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. זמן הרצת ה-  - מאחר שאנו עוברים על כל איבר ברשימה אשר אורכה מסומנת ב-  ומשווים איבר, איבר ברשימה לאיבר אחר, זמן ההרצה הינו  
  2. התנאי המותנה הוא   - קבועה שחשיבותו אינו נכלל בזמן הסיבוכיות.

דוגמא 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

עריכה

חיפוש במערך הוא  .


פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.



דוגמה 5

עריכה

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

במקרה הרע ביותר נכניס איבר למיקום האחרון ולכן זמן הריצה הוא  


פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.