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

דוגמא 1

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

def findmax(lst):
    sum = 0

    for i in lst:
        if i < 10:
            for j in range(len(lst)):
                sum+ = j

    return sum

במקרה זה, הלולאה הראשונה והתנאי במקרה הרעה ביותר ירוצו $n$ פעמים, כאורך הרשימה.

באופן דומה במקרה השני, הלולאה השנייה, תרוץ $n$ פעמים בהכרח ולכן סה"כ התכנית תרוץ $o(n*n)=o(n^{2})$.

דוגמה 2

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

דוגמה עם while  

דוגמה 3

מיון בחירה רץ $o(n^{2})$.

def selection_sort(lst)
for i in range(len(lst)):
    min_index = i
    for j in range(i, len(lst)):
        if lst[min_index]>lst[j]:
            min_index=j
    lst[i], lst[min_index] = lst[min_index], lst[i]