פייתון/פייתון גרסה 3/סיבוכיות/סיבוכיות זמן/סיבוכיות לינארית
פעלות עם סיבוכיות לינארית
עריכה- פעולות אריתמטיות
- פעולות השוואה
- הצהרה משתנה
- פקודת השמה
- שימוש במתודה או בפונקציה (ראה דוגמה 5)
דוגמא 1
עריכהנתבונן על הדוגמה הבאה:
def findmax(lst):
curr_max = lst[0]
for i in lst:
if i > curr_max:
curr_max = i
return curr_max
- זמן הרצת ה- - מאחר שאנו עוברים על כל איבר ברשימה אשר אורכה מסומנת ב- ומשווים איבר, איבר ברשימה לאיבר אחר, זמן ההרצה הינו
- התנאי המותנה הוא - קבועה שחשיבותו אינו נכלל בזמן הסיבוכיות.
דוגמא 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:
במקרה הרע ביותר נכניס איבר למיקום האחרון ולכן זמן הריצה הוא
פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.