מבוא למדעי המחשב - סיבוכיות מקום

        5
       / \
      1   7
     /   / \
    6   2   9
         /
        4

• נתונה לכם תוכנית אשר קוראת מהמשתמש את המחרוזת $s$ (אורך ותוכן), קוראת לפונקציה ומדפיסה את הערך החוזר ואת המחרוזת החדשה.
• ניתן להניח שהקלט תקין ($s$ מחרוזת חוקית המכילה רק אותיות קטנות).

• סיבוכיות זמן: $\Theta (n)$ כאשר $n$ הוא אורך המחרוזת $s$.
• סיבוכיות מקום: $\Theta (1)$.

• נתונה לכם תוכנית אשר קוראת מהמשתמש את אורך המערך, ולאחר מכן את תוכנו.
• ניתן להניח שהקלט תקין, בפרט $arr$ מכיל רק מספרים חיוביים ו-$1<n$.

• סיבוכיות זמן: $\Theta (n)$.
• סיבוכיות מקום: $\Theta (1)$.

• נתונה לכם תוכנית אשר קוראת מהמשתמש את אורך המערך, ולאחר מכן את תוכנו ואת התווים $c$ ו-$x$.
• ניתן להניח שהקלט תקין, בפרט $\text{arr}$ לא מכיל את אותו איבר פעמיים, $c$ הוא אחת מהאפשרויות לעיל ו-$\text{arr}$ מסודר בהתאם אליו.

• סיבוכיות זמן עבור הפונקציה compare: $\Theta (1)$.
• סיבוכיות זמן כוללת: $O(\log (n))$.
• סיבוכיות מקום נוסף: $O(1)$.

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

• נתונה לכם תוכנית אשר קוראת מהמשתמש את המחרוזות $s_1$ ו-$s_2$ (אורך ותוכן), קוראת לפונקציה ומדפיסה את המחרוזת החדשה (ומשחררת אותה).
• ניתן להניח ש- $s_1$ ו- $s_2$ מחרוזות חוקיות שמכילות רק ספרות.
• המחרוזות לא יכילו אפסים מובילים (אבל הן יכולות להיות "0").
• לא ניתן להניח שהמספרים המתקבלים יכולים להיות מיוצגים כ- $\text{int}$ ואפילו לא כ- $\text{long long}$.

• סיבוכיות זמן: $O(n)$ כאשר $n$ הוא אורך המחרוזת הארוכה יותר.
• סיבוכיות מקום: $O(n)$.

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