הרצאה 9 - סיבוכיות זמן ומקום (Time & Space Complexity)

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

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

באופן כללי, אלגוריתמים צורכים שני משאבים עיקריים:

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

נפתח דרך שיטתית להשוות בין צריכת המשאבים הללו בין אלגוריתמים שונים.

Big-O Notation

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

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

int find_in_array(int* arr, int n);

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

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

נקודה 3 בעייתית מבחינתנו. אנחנו לא רוצים להשוות בין כל מחשב לכל מחשב אחר - לכן הניתוח שלנו יתמקד באותם אינוריאנטים שלא משתנים ממחשב למחשב. בנקודות 1-2 נוכל להשתמש בצורה חכמה יותר.

חסם עליון

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות \( f(n), g(n) \). נסמן כי \( f(n) = O(g(n)) \) אם קיים \(c>0\) ו-\( N \) שלם כך שלכל \(n>N\) מתקיים \( c \cdot g(n) \ge f(n) \).

אינטואיטיבית, ההדרה אומרצ

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות $f(n), g(n)$. נסמן כי $O(g(n)) = f(n)$ אם קיים $0<c$ ו-$N$ שלם כך שלכל $N<n$ מתקיים $g(n) \cdot c \ge f(n)$.

אינטואטיבית, ההגדרה אומרת שהחל ״ממקום מסוים״, $g(n)$ תמיד גדולה מ-$f(n)$. בלשון הדיבור, אומרים ש-“$f(n)$ היא O (האות O) של $g(n)$״.

לדוגמא, עבור:

אפשר להראות כי:

כאשר החלפנו את האיברים $\log n$ ו-$1$. לכן מתקיים $O(n^2)=f(n)$.

חסם תחתון

קיימת הגדרה סימטרית לכיוון ההפוך, עם סימון אחר:

הגדרה: יהיו שתי פונקציות חיוביות ומונוטוניות לא יורדות $f(n), g(n)$. נסמן כי $\Omega (g(n)) = f(n)$ אם קיים $0<c$ ו-$N$ שלם כך שלכל $N<n$ מתקיים $g(n) \cdot c \le f(n)$.

וכעת ניתן לשלב את שתי ההגדרות להגדרה שתעניין אותנו:

הגדרה: אם מתקיים $O(g(n)) = f(n)$ ו-$\Omega (g(n)) = f(n)$, אז נאמר ש-$g(n)$ היא חסם אסימפטוטי של $f(n)$ ונסמן $\Theta(g(n)) = f(n)$.

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

דוגמאות:

1. עבור פולינום כללי:

ניתן לחסום את $f(n)$ משני הכיוונים ע״י פולינומים $^kn$, ולכן $\Theta(n^k)=f(n)$. למעשה השמטנו את כל האיברים שאינם החזק ביותר. כמו כן, נשים לב שהשמטנו את הקבוע הכפלי של $^kn$ - אין צורך בו, מכיוון שההגדרה מדברת על כך שקיים קבוע כללי.

2. עבור:

ניתן לכתוב:

גם כאן, זיהינו כי מתקיים $\sqrt n < n$ באופן כללי, ולכן גם $\sqrt n < n \log n$. כלומר, $n \log n $ הוא הגורם השולט על הפונקציה ולכן ניתן להשמיט את $\sqrt n$.

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

הגדרה: נתונה פונקציה $f(n)$ המתארת את זמן הריצה או צריכת הזכרון של אלגוריתם מסוים. סיבוכיות הזמן או המקום בהתאמה של האלגוריתם היא החסם האסימפטוטי של הפונקציה: $\Theta (f(n))$.

דוגמא: נניח שקיימת פונקציה שזמן הריצה שלה מתואר ע״י הפונקציה הבאה:

כאשר $_ik$ הם קבועים הקשורים למחשב הספציפי בו האלגוריתם רץ. סיבוכיות הזמן של האלגוריתם הוא, כפי שראינו עבור פולינום כללי, $\Theta (n^2)$. נשים לב לכמה יתרונות עיקריים בגישת הגדרה זו:

1. אנחנו מסתכלים על האיבר הדומיננטי כאשר הקלט גדול - כאשר $\infty \rightarrow n$ האיברים שאינם $^2n$ פחות רלוונטים, וזה מאפשר לנו להתעסק בעיקר ולהשוות בין אלגוריתמים עם התנהגות אסימפטוטית דומה.
2. אנחנו מבטלים את התלות במחשב הספציפי עליו האלגוריתם רץ, ומתעסקים בניתוח כללי של האלגוריתם עצמו.
3. יש לנו כעת דרך שיטתית להשוות בין אלגוריתמים שונים ולהחליט מי מהן עדיף לנו.

תלות הסיבוכיות בקלט

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

• המטרה נמצאת באינדקס 0 - במקרה זה, נמצא את המטרה בפעולה אחת והסיבוכיות היא לכאורה $\Theta(1)$. זהו גם המקרה הטוב ביותר האפשרי עבור הקלט.
• המטרה נמצאת באינדקס n - 1 - במקרה זה, נמצא את המטרה ב-n פעולות והסיבוכיות היא לכאורה $\Theta(n)$. זהו גם המקרה הגרוע ביותר האפשרי עבור הקלט.

מה נכון?

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

דוגמאות

חיפוש בינארי

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

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

Bubble Sort

במיון בועות יש להסתכל על המקרה הגרוע ביותר. נסתכל למשל על מערך ממוין הפוך:

באיטרציה הראשונה של מיון בועות, ה-5 יבעבע כלפי מעלה עד למצב הבא:

ובאיטרציה הבאה 4 יצטרך לבעבע שוב עד למעלה, אבל מכיוון שאנחנו יודעים שהאיבר הגדול ביותר כבר נמצא באינדקס n - 1, נצטרך לבעבע רק עד ל-n - 2:

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

זוהי סדרה חשבונית עם הפרש $1=d$ ו-$n$ איברים, שסכומה:

כלומר, סיבוכיות הזמן היא $\Theta(n^2)$. בהמשך נראה שזוהי סיבוכיות זמן לא מוצלחת מאוד עבור אלגוריתם מיון, ושניתן לעשות זאת בסיבוכיות טובה יותר.

מיזוג

להזכירכם, הנה הקוד לביצע מיזוג מערכים ממוינים:

void merge(int* arr1, int n, int* arr2, int m, int* arr3) {
    for(int i1 = 0, i2 = 0, i3 = 0; i1 < len1 && i2 < len2; i3++) {
        if(arr1[i1] < arr2[i2]) {
            arr3[i3] = arr1[i1++];
        } else {
            arr3[i3] = arr2[i2++];
        }
    }
    // Copy leftover elements from either array
    while(i1 < len1) {
        arr3[i3++] = arr1[i1++];
    }
    while(i2 < len2) {
        arr3[i3++] = arr1[i2++];
    }
}

נסמן ב-n את אורך המערך הראשון וב-m את אורך המערך השני. בכל איטרציה של המיון אנחנו מקדמים או את i1 או את i2 - גם לאחר מכן, בהעתקת שארית המערכים, אנחנו בכל איטרציה מקדמים אינדקס למערך הרלוונטי. כמו כן, בכל איטרציה אנו מבצעים מספר קבוע של פעולות, שאינו תלוי בגודל הקלט. כלומר, מספר הפעולות פרופורציונלי (שווה עד כדי קבוע כפלי) לסכום אורכי המערכים, n + m. לכן, נגיד כי סיבוכיות הזמן של מיזוג מערכים ממוינים היא לינארית בסכום אורכי המערכים, או:

הקצנו לטובת הפונקציה גודל קבוע שאינו תלוי בקלט (מספר משתנים בודדים), ולכן סיבוכיות המקום של המיזוג היא $\Theta(1)$.

הערה: פונקציה לינארית היא פולינום ממעלה ראשונה, מהצורה $b+an=f(n)$.

מיון מיזוג

מצאנו את סיבוכיות הזמן של מיזוג, ולכן יהיה פשוט יותר למצוא את סיבוכיות הזמן של מיון באמצעות מיזוג (Merge Sort). במיון מיזוג מתחילים במיזוג של מערכים באורך 1, לאחר מכן 2, 4 עד למיון של כל המערך (כאשר נניח לפשטות שהמערכים באורך חזקה של 2, $^k2=n$). לכן, כפי שראינו, מספר האיטרציות של מיזוג שיתבצעו הוא $\log_2n$. כמו כן, ראינו כי כל מיזוג מכיל $m+n$ איטרציות כאשר $m,n$ הם אורכי המערכים הממוזגים. כמו כן, בכל איטרציה יש למיין מספר יורד של מערכים - בהתחלה $^{k-1}2$, ואז $^{k-2}2$ וכך הלאה.

כלומר, בשלב ב-$h$ של המיון, ישנם $^{k-h}2$ מערכים למיין, שאורך כל אחד מהם $^{h}2$. לכן מספר הפעולות בכל שלב היא:

וישנם $\Theta(n)=\log_2n$ שלבים למיון, כך שסה״כ סיבוכיות הזמן של מיון מיזוג היא:

הוכחה - מציאת חסם אסימפטוטי

ננסח את הטענה הקודמת בצורה מדויקת יותר:

טענה: תהי $f(n)$ פונקציה

תרגילים

תרגיל 1

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

int f(int n) {
    int a = 1;
    while(a < n) {
        a *= 2;
    }
    for(int i = 0; i < 10000000; i++) {
        printf("a + i = %d", a + i);
    }
    return a;
}

כרגיל, אנחנו מעוניינים למצוא את סיבוכיות הזמן כתלות בגודל הקלט n ולכן ניתן להשמיט כל מספר קבוע של פעולות. אף על פי ש-10000000 הוא מספר שנראה גדול, הוא עדיין קבוע, ולכן כל הלולאה השנייה מתבצעת ב-$\Theta(1)$. הלולאה הראשונה לעומתה מתבצעת כל עוד a < n, כאשר a מוכפל ב-2 בכל איטרציה. דרך נוחה להבין כמה איטרציות לולאה מתבצעת היא לחשוב מה קורה באיטרציה ה-k עבור מספר טבעי כלשהו. באיטרציה ה-k מתקיים $^k2=a$, ולכן האיטרציה האחרונה תתקיים כאשר:

כלומר, יתקיימו לכל היותר $\log_2n$ איטרציות של הלולאה, לסה״כ סיבוכיות זמן של $\Theta(\log n)$. סיבוכיות המקום היא $\Theta(1)$ מכיוון שמוקצה מספר קבוע של משתנים שאינו תלוי בקלט.

תרגיל 2

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n. הניחו שסיבוכיות הזמן של malloc היא $\Theta(1)$.

void f(int n) {
    int* arr = malloc(n * sizeof(int));
    int** ptrs = malloc(n * sizeof(int*));
    for(int i = 0; i < n; i++) {
        ptrs[i] = malloc(n * sizeof(int));
        for(int j = 0; j < n; j++) {
            arr[i] = j;
            arr[j] = i;
        }
    }
    free(arr);
    for(int i = 0; i < n; i++) {
        free(ptrs[i]);
    }
    free(ptrs);
}

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

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

שאלה 3

חשבו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void f(int* a, int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n && a[i] < a[j]; j++);
    }
}

הפונקציה אינה משתמשת בזכרון דינמי (או רקורסיה, עליה נלמד בהרצאה הבאה) ולכן סיבוכיות המקום שלה היא $\Theta(1)$. מבחינת סיבוכיות המקום, הפונקציה מכילה שתי לולאות מקוננות. החיצונית רצה n איטרציות ללא תלות בפנימית. עם זאת, מספר האיטרציות של הלולאה הפנימית תלוי בקלט! כיצד נדע? להזכירכם, אנחנו תמיד מסתכלים בסיבוכיות על המקרה הגרוע ביותר - הקלט עבורו סיבוכיות הזמן הכי גרועה שיכולה להיות. ניתן לייצר מערך קלט a עבורו התנאי a[i] < a[j] לכל i, j , כך שלכל אחת מ-n האיטרציות החיצוניות יהיו n איטרציות פנימיות. לכן סיבוכיות הזמן היא:

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

שאלה 4

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void f(int n) {
    for(int i = 2; i < n; i *= i);
}

מבחינת סיבוכיות מקום, מוקצה מספר קבוע של משתנים ולכן היא $\Theta(1)$. סיבוכיות הזמן מעט יותר מורכבת. ננסה לחשב - מהו ערכו של i באיטרציה ה-k? נכתוב כמה מהערכים הראשונים:

אם נכתוב את הערכים הראשונים כחזקות של 2, קצת יותר קל לראות את הסדרה:

בכל איטרציה מתקיים מספר קבוע של פעולות, כאשר מספר האיטרציות $k$ מקיים:

שאלה 5

מצאו את סיבוכיות הזמן והמקום של הפונקציה הבאה כתלות ב-n:

void g(int k) {
    for(int l = 0, m = 0; l < n || m < n * n; l++, m++);
}
void f(int n) {
    for(int i = 0; i <= n; i += 10) {
        g(i);
        g(n - i);
    }
}