פייתון/פייתון גרסה 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:

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


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