מה זה Big O ולמה מתכנתים מדברים על זה¶
בשלב מסוים בלמידה שלכם, מישהו יגיד "כן אבל מה הסיבוכיות של זה?" ואתם תרגישו שנכנסתם לשיחה בשפה זרה. Big O נשמע כמו סימון מתמטי שנועד להפחיד, אבל האמת היא שהרעיון שמאחוריו פשוט להפליא, וברגע שתבינו אותו, לא תוכלו להפסיק לחשוב במונחים שלו.
מה הבעיה ש-Big O בא לפתור¶
תדמיינו שאתם כותבים שתי דרכים שונות לפתור אותה בעיה, ואתם רוצים לדעת איזו מהן "יותר טובה". אתם יכולים למדוד זמן ריצה בשעון, אבל זה תלוי מדי בדברים לא רלוונטיים - כמה חזק המחשב שרץ עליו, כמה תוכניות אחרות פתוחות ברקע, איזו שפת תכנות השתמשתם. Big O בא לענות על שאלה יותר יסודית: איך זמן הריצה של האלגוריתם גדל כשכמות המידע גדלה, בלי קשר לחומרה או לשפה.
זה לא מודד זמן בשניות. זה מודד קצב צמיחה.
הדוגמה שתגרום לכם להבין את זה לתמיד¶
תדמיינו שיש לכם ספר טלפונים עם אלף שמות, ואתם מחפשים שם ספציפי.
שיטה אחת: לעבור עמוד-עמוד, שם-שם, מההתחלה עד שמוצאים. אם השם שאתם מחפשים נמצא בסוף, תעברו על כל האלף שמות. אם יהיו לכם מיליון שמות, תעברו על כל המיליון. ככל שהרשימה גדלה, זמן החיפוש גדל באותו יחס בדיוק. זה נקרא O(n) - זמן ליניארי.
שיטה שנייה: לנצל שהספר ממוין לפי א"ב. פותחים באמצע, בודקים אם השם שמחפשים לפניו או אחריו באלף בית, וזורקים חצי מהספר. חוזרים על זה עם החצי שנשאר. עם כל צעד אתם חוצים בחצי את מה שנשאר לבדוק. גם אם הספר יגדל פי אלף, מספר הצעדים יגדל בקושי - זה נקרא O(log n) - זמן לוגריתמי, וזה בדיוק הרעיון מאחורי חיפוש בינארי.
זה כל ההבדל בין קוד שמרגיש "איטי" לקוד שמרגיש "מהיר" כשהנתונים גדלים.
כמה סימונים שכדאי להכיר, בלי בהלה¶
- O(1) - זמן קבוע. הפעולה לוקחת אותו זמן בדיוק בלי קשר לכמות המידע. לדוגמה, לשלוף ערך ממילון לפי מפתח.
- O(log n) - לוגריתמי. גדל לאט מאוד. חיפוש בינארי, חיפוש בעץ מאוזן.
- O(n) - ליניארי. עוברים על כל איבר פעם אחת. לדוגמה, לחפש איבר ברשימה לא ממוינת.
- O(n log n) - קצת יותר מליניארי. רוב אלגוריתמי המיון היעילים, כמו מיון מיזוג, נמצאים כאן.
- O(n²) - ריבועי. בדרך כלל לולאה בתוך לולאה על אותם נתונים. מיון בועות, למשל. גדל מהר מאוד וכואב על נתונים גדולים.
אתם לא צריכים לשנן את כל הרשימה בעל פה. אתם צריכים להבין את הכיוון הכללי - ככל שאתם נעים ימינה ברשימה הזו, הביצועים מחמירים דרמטית ככל שכמות המידע גדלה.
למה מתכנתים בכלל טורחים עם זה¶
כי ההבדל בין O(n) ל-O(n²) לא נראה בהתחלה על נתונים קטנים, אבל הופך לקטסטרופלי על נתונים גדולים. קוד שרץ על 100 איברים תוך פחות משנייה בשתי הגישות, יכול לרוץ על מיליון איברים תוך שנייה בגישה אחת, ותוך שעות שלמות בגישה השנייה. חברות כמו גוגל ופייסבוק לא שואלות על סיבוכיות בראיונות עבודה בגלל טקס פולחני - הן שואלות כי בקנה מידה שלהן, ההבדל הזה שווה שרתים, כסף וזמן טעינה אמיתי למשתמשים.
איך לומדים את זה בלי לפחד¶
תפסיקו לנסות "לחשב" Big O במדויק בהתחלה. תתאמנו רק לזהות לולאות: לולאה אחת שעוברת על הנתונים היא בדרך כלל O(n). לולאה בתוך לולאה על אותם נתונים היא בדרך כלל O(n²). זו כבר אינטואיציה שתיקח אתכם רחוק. עם הזמן וכמה תרגילים, זה נהיה טבעי ממש כמו לזהות תחביר.
בקורס התכנות הבסיסי שלנו אנחנו בונים את האינטואיציה הזו דרך תרגילים אמיתיים, לא דרך נוסחאות יבשות.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
Big O הוא פשוט דרך לתאר איך זמן הריצה של הקוד שלכם גדל כשכמות המידע גדלה, בלי תלות בחומרה. זה לא מתמטיקה מפחידה, זו רק שפה משותפת שמאפשרת למתכנתים להשוות פתרונות בצורה הוגנת. ברגע שתתחילו לחשוב במונחים האלה, תראו הזדמנויות לשיפור קוד שפשוט לא ראיתם קודם.
יש לכם שאלה על סיבוכיות של תרגיל שאתם עובדים עליו? קפצו לדיסקורד שלנו.