Big O מוסבר למתכנתים

מה Big O מודד?

Big O מתמקד בקצב הצמיחה ולא במספר מדויק של מילישניות. קבועים חשובים במערכות אמיתיות, אך האיבר הדומיננטי מספק השוואה ראשונית ברורה לקלט גדול.

זהו מחלקות נפוצות

גישה ישירה היא לרוב O(1), חיפוש בינארי הוא O(log n), מעבר מלא הוא O(n), ושתי לולאות מקוננות הן לעיתים O(n²).

• O(1): קבוע
• O(log n): לוגריתמי
• O(n): ליניארי
• O(n log n) ו־O(n²)

נתחו קוד שלב אחר שלב

הגדירו את גודל הקלט, ספרו פעולות שגדלות איתו, חברו עבודה עוקבת והכפילו עבודה מקוננת. ברקורסיה כללו את מספר הקריאות ואת העבודה בכל קריאה.

זכרו סיבוכיות מקום

פתרון מהיר יותר עשוי להשתמש בקבוצה, מפה, תור או מחסנית רקורסיה. ציינו גם זמן וגם זיכרון עזר כדי להבהיר את הפשרה.