סיבוכיות זמן בסיסית לחזרה

מהי סיבוכיות ליניארית?

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

מהי סיבוכיות ריבועית?

סיבוכיות ריבועית מתארת אלגוריתמים שפועלים בזמן $\displaystyle O(n^2)$, לדוגמה, מיון בבחירה.

האם סיבוכיות מעריכית היא טובה?

לא, סיבוכיות מעריכית, כמו $\displaystyle O(2^n)$, היא מאוד כבדה ומובילה לביצועים גרועים.

שווה או לא: $\displaystyle O(n) = O(n^2)$?

לא. $\displaystyle O(n)$ טוב יותר מ-$\displaystyle O(n^2)$.

שלב את המושגים: סיבוכיות ליניארית ___ סיבוכיות ריבועית.

טובה יותר. ליניארית יעילה יותר מריבועית.

מה הקשר בין גודל הקלט לסיבוכיות?

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

מהי סיבוכיות קבועה?

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

נכון או לא: $\displaystyle O(n^3)$ זה יותר טוב מ-$\displaystyle O(n^2)$?

לא נכון. $\displaystyle O(n^3)$ גרוע יותר מ-$\displaystyle O(n^2)$.

מהי דוגמה לאלגוריתם ליניארי?

חיפוש בקו, שבו נבדק כל איבר ברצף.

מהי סיבוכיות מעריכית?

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

מהי השפעת סיבוכיות על ביצועי התוכנה?

סיבוכיות גבוהה יכולה להוביל לזמן ריצה ארוך ולא יעיל.

מתי נשתמש באלגוריתם ריבועי?

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

מה זה $\displaystyle O(n imes m)$?

סיבוכיות המתארת אלגוריתמים שמבצעים חישובים על שני גדלי קלט, $\displaystyle n$ ו-$\displaystyle m$.

נכון או לא: כל אלגוריתם ליניארי הוא גם ריבועי?

לא נכון. ליניארי הוא יעיל יותר.

מהי התנהגות סיבוכיות באלגוריתמים מדויקים?

סיבוכיות מדויקת בדרך כלל היא גבוהה יותר.

תן דוגמה לאלגוריתם מעריכי.

חיפוש פתרונות לכל הקומבינציות, כמו במשחקי לוח.