תכנות וניתוח נתונים בשפת פייתון

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

מבוא לסיבוכיות אלגוריתמים

כאשר אנו כותבים תוכנה, קיימות לרוב מספר דרכים לפתור בעיה נתונה. השאלה היא איזו דרך היא הטובה ביותר? "טובה ביותר" בהקשר של מדעי המחשב מתייחסת לרוב ליעילות - כמה משאבים (זמן וזיכרון) האלגוריתם צורך. ניתוח סיבוכיות מאפשר לנו להעריך את ביצועי האלגוריתם באופן אבסטרקטי, בלתי תלוי בחומרת המחשב או בשפת התכנות.

סיבוכיות זמן (Time Complexity): מדד לכמות הזמן שהאלגוריתם צורך כפונקציה של גודל הקלט (n). אנו מתעניינים לרוב במספר הפעולות הבסיסיות שהאלגוריתם מבצע.

סיבוכיות מקום (Space Complexity): מדד לכמות הזיכרון שהאלגוריתם צורך כפונקציה של גודל הקלט (n). זה כולל זיכרון לאחסון הקלט עצמו וזיכרון עזר נוסף שהאלגוריתם דורש.

סימון Big O (Big O Notation): כלי מתמטי לתיאור קצב הגידול של פונקציה, ובפרט, לתיאור חסם עליון (worst-case scenario) לסיבוכיות זמן ומקום של אלגוריתם. הוא מתעלם מקבועים ומאיברים מסדר נמוך, ומתמקד בהתנהגות האסימפטוטית של האלגוריתם ככל שגודל הקלט (n) שואף לאינסוף.

ניתוח סיבוכיות זמן ומקום (Big O)

הבנת קטגוריות ה-Big O השונות היא קריטית להערכת יעילות אלגוריתמים. אנו מתמקדים בדרך כלל במקרה הגרוע ביותר (worst-case), מכיוון שהוא נותן לנו חסם עליון מובטח לביצועים.

O(1) - סיבוכיות קבועה

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

O(log n) - סיבוכיות לוגריתמית

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

O(n) - סיבוכיות לינארית

זמן הריצה גדל באופן פרופורציונלי לגודל הקלט. לדוגמה: סריקה של כל האיברים במערך כדי למצוא ערך מסוים (חיפוש לינארי).

O(n log n) - סיבוכיות לינארית-לוגריתמית

נחשבת ליעילה עבור אלגוריתמי מיון רבים. לדוגמה: מיון מיזוג (Merge Sort) ומיון מהיר (Quick Sort).

O(n²) - סיבוכיות ריבועית

זמן הריצה גדל באופן ריבועי עם גודל הקלט. לרוב מתרחש בלולאות מקוננות. לדוגמה: מיון בועות (Bubble Sort), מיון בחירה (Selection Sort).

O(2ⁿ) - סיבוכיות אקספוננציאלית

זמן הריצה גדל באופן אקספוננציאלי עם גודל הקלט. אלגוריתמים כאלה אינם מעשיים עבור קלטים גדולים. לדוגמה: פתרון בעיות ברוט-פורס (brute-force) מסוימות.

ניתוח Big O בפועל: קריטי להבין כיצד לגזור את סיבוכיות Big O מקטע קוד נתון. זכרו להתמקד בלולאות, קריאות רקורסיביות, ופעולות על מבני נתונים. התעלמו מקבועים ואיברים מסדר נמוך. לדוגמה, קוד עם לולאה אחת על n איברים הוא O(n), וקוד עם שתי לולאות מקוננות על n איברים הוא O(n²). טעות נפוצה היא לכלול קבועים או להתבלבל בין מקרה ממוצע למקרה גרוע ביותר. בבחינות, לרוב תתבקשו לנתח קוד ולציין את הסיבוכיות שלו, או להשוות בין אלגוריתמים שונים.

אלגוריתמי חיפוש בסיסיים

אלגוריתמי חיפוש משמשים למציאת איבר מסוים בתוך אוסף נתונים.

חיפוש לינארי (Linear Search)

הסבר: עובר על כל איברי הרשימה בזה אחר זה עד למציאת האיבר המבוקש או עד סוף הרשימה. דרישות: אין דרישות מיוחדות (הרשימה לא חייבת להיות ממוינת). סיבוכיות זמן: O(n) במקרה הגרוע ביותר (האיבר בסוף או לא קיים). סיבוכיות מקום: O(1).

חיפוש בינארי (Binary Search)

הסבר: עובד על רשימה ממוינת. מחלק את הרשימה לשניים שוב ושוב, ומצמצם את טווח החיפוש בחצי בכל שלב. דרישות: הרשימה חייבת להיות ממוינת. סיבוכיות זמן: O(log n) במקרה הגרוע ביותר. סיבוכיות מקום: O(1) (איטרטיבי).

אלגוריתמי מיון בסיסיים

אלגוריתמי מיון מסדרים אוסף נתונים בסדר מסוים (לרוב עולה או יורד).

מיון בועות (Bubble Sort)

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

מיון בחירה (Selection Sort)

הסבר: מוצא בכל שלב את האיבר המינימלי (או המקסימלי) מהחלק הלא ממוין של הרשימה ומחליף אותו עם האיבר הראשון בחלק הלא ממוין. סיבוכיות זמן: O(n²) בכל המקרים (טוב, ממוצע, גרוע). סיבוכיות מקום: O(1).

מיון הכנסה (Insertion Sort)

הסבר: בונה את הרשימה הממוינת איבר אחר איבר. בכל שלב, לוקח איבר מהחלק הלא ממוין ומכניס אותו למקומו הנכון בחלק הממוין. סיבוכיות זמן: O(n²) במקרה הגרוע והממוצע. O(n) במקרה הטוב ביותר (כשהרשימה כבר ממוינת). סיבוכיות מקום: O(1).

שאלות לדיון

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

נקודות לתשובת מודל

לשאלה: "הסבירו מדוע סימון Big O מתעלם מקבועים ומאיברים מסדר נמוך. תנו דוגמה שתמחיש את הנקודה."

התמקדות בהתנהגות אסימפטוטית: Big O נועד לתאר את קצב הגידול של זמן הריצה (או הזיכרון) ככל שגודל הקלט (n) שואף לאינסוף. עבור קלטים גדולים מאוד, האיבר בעל הקצב הגבוה ביותר הוא הדומיננטי והוא זה שקובע את הביצועים.
חוסר רלוונטיות של קבועים: קבועים (כמו 5n או 100n) משפיעים על זמן הריצה בפועל, אך אינם משנים את קצב הגידול. 5n עדיין גדל לינארית, בדיוק כמו 100n. בטווח הארוך, ההבדל ביניהם זניח לעומת ההבדל בין n ל-n².
חוסר רלוונטיות של איברים מסדר נמוך: איברים כמו n או log n בביטוי כמו n² + n + log n הופכים זניחים לחלוטין כאשר n גדול מאוד. n² יגדל הרבה יותר מהר מ-n או log n, ולכן הוא האיבר הקובע את קצב הגידול הכולל.
דוגמה: נניח שיש לנו שני אלגוריתמים:
- אלגוריתם א': 100n פעולות. סיבוכיות O(n).
- אלגוריתם ב': n² פעולות. סיבוכיות O(n²).
עבור n=10, אלגוריתם א' מבצע 1000 פעולות, ואלגוריתם ב' מבצע 100 פעולות. אלגוריתם ב' מהיר יותר. אבל עבור n=1000, אלגוריתם א' מבצע 100,000 פעולות, ואלגוריתם ב' מבצע 1,000,000 פעולות. אלגוריתם א' מהיר בהרבה. ככל ש-n גדל, ההשפעה של n² גוברת באופן דרמטי על ההשפעה של 100n, והקבוע 100 הופך ללא רלוונטי בהשוואה לקצב הגידול הריבועי. Big O מתמקד בתמונה הגדולה הזו.

מצאתם טעות או שחסר משהו?