סיבוכיות זמן כמה צעדים?

O(1) ו-O(n)

O(1): מספר קבוע של צעדים, לא משנה כמה גדול n. למשל nums[0]. O(n): לולאה אחת על כל האיברים. פי 10 איברים, פי 10 צעדים.

O(n²)

לולאה בתוך לולאה, שתיהן עד n. על כל איבר עוברים שוב על כולם. פי 10 איברים, פי 100 צעדים. עם 1000 איברים זה כבר מיליון.

O(log n)

בכל צעד הבעיה נחצית. מ-1000 מגיעים ל-1 בערך ב-10 צעדים. כך עובד חיפוש בינארי, ולכן הוא כל כך מהיר.

שתי לולאות זו אחרי זו

לולאה ואחריה עוד לולאה זה n + n = 2n צעדים, כלומר O(n). רק לולאה בתוך לולאה נותנת O(n²).

for x in nums:
    print(x)
for x in nums:
    print(x * 2)

לולאה פנימית קבועה

אם הלולאה הפנימית רצה תמיד 3 פעמים, זה 3n, כלומר O(n). שואלים: האם גם היא גדלה עם n?

for x in nums:
    for k in range(3):
        print(x + k)

לולאה שמסתתרת

x in nums, nums.index(x), sum(nums) ו-max(nums) עוברים על כל הרשימה. בתוך לולאה הם הופכים אותה ל-O(n²).

for x in nums:
    if x * 2 in nums:
        print(x)

מודדים בשעון

זמן בשניות תלוי במחשב. סיבוכיות סופרת צעדים, ולכן היא נכונה בכל מחשב. מחשב מהיר פי 10 לא מציל O(n²) כש-n גדל פי 1000.

steps = 0
for x in nums:
    steps = steps + 1
print(steps)    # n