מה זו סיבוכיות ולמה עושים מזה עניין ?

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

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

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

מקובל לחלק יעילות לשני חלקים: יעילות זיכרון ויעילות ריצה. 

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

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

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

לגבי יעילות של זמן, צריך להבין על מה מדובר.

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

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

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

למשל - אם על כל 10 נתונים, האלגוריתם רץ 10 פעמים - זה נחשב יעילות ליניארית: גידול של 1 בכמות הנתונים יגרום לגידול של 1 במספר הריצות. זה נחשב סביר, אבל לא מעולה.

אם על כל 10 נתונים, האלגוריתם ירוץ 100 פעם, זה נחשב יעילות ריבועית: די גרוע אבל שמיש.

אלגוריתם ממש גרוע ירוץ 1000 פעם על כל 10 נתונים. זו יעילות אקספוננציאלית.

אלגוריתם נחשב טוב אם הוא רץ פחות מליניארי, או הכי טוב ביחס של Log שזה אומר שהוא ירוץ פעם אחת על כל 10 נתונים. נשמע פסיכי, אבל זה אפשרי.

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

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

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

אז איך מודדים יעילות?

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

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

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

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

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

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

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

במידה ותרצו להבדיל את עצמכם מהשאר, אני ממליץ לכם ללמוד את התחום ולהתייחס לנושא ברצינות.
אחת הבעיות של מתכנתים בינוניים היא חוסר המודעות שלהם לפעולות שהקוד שלהם מבצע מאחורי הקלעים. בנוסף, שאלות על איכות של קוד נשאלות לא אחת בראיונות עבודה. מועמד שלא יודע לענות על שאלות כאלה, לרוב נדחה על הסף, בעיקר במשרות פיתוח רציניות.

לסקירה חביבה של הנושא ניתן לצפות בסרטון הבא: