סיבוכיות קוד
קפיצה לניווט
קפיצה לחיפוש
סיבוכיות קוד היא ערך המייצג מורכבות של תוכנת המחשב. היא נבדלת מסיבוכיות זמן וסיבוכיות מקום בכך שאינה מעריכה ביצוע אלגוריתם אבסטרקטי בערכי פונקציות של גודל הקלט, אלא קוד מסוים המממש אלגוריתם כלשהו. מימושים שונים של אלגוריתמים זהים יכולים להיות בסיבוכיות קוד שונה, וזה אף נדרש כאחד מהקריטריונים של שימושיות מדד סיבוכיות קוד[1].
מדדי סיבוכיות קוד
ישנם מספר מדדים שמשמשים להערכת סיבוכיות קוד, כשכל מדד תוקף את בעיית ההערכה מזווית אחרת. הסיבה היא שאין ממש הגדרה ברורה למושג מורכבות הקוד, ולכן עצם ההערכה של סיבוכיות הקוד, או מורכבותו, תלויה קודם כל במה נתפס כ"מורכב".
המדדים היותר נפוצים הם:
- שורות קוד - המדד הזה בודק את סיבוכיות הקוד מההיבט הפשוט של גודל הקוד. לעיתים, עצם בדיקת אורך הקוד נותנת מושג סביר לגבי מורכבותו. למשל, לפי תקני קוד המקובלים בתעשייה[2], נהוג שאורך שגרת קוד בודדת לא יעלה על כ-200 שורות קוד.
- סיבוכיות ציקלומטית (Cyclomatic Complexity) - זהו למעשה המדד הראשון לסיבוכיות קוד, שבו משתמשים החל מפרסומו ב-1976[3], ועד היום. למדד הזה קוראים, לפעמים, סיבוכיות מקקייב (McCabe's Complexity) או ערך הסיבוכיות הציקלומטית (Cyclomatic Complexity Number - CCN). הערך מייצג את מספר מסלולי הבקרה הנפרדים בקוד (code branching). בדרך כלל, יתכוונו לסיבוכיות ציקלומטית כשמדברים על סיבוכיות קוד באופן כללי. ישנו קשר ישיר בין ערך הסיבוכיות הציקלומטית של הקוד, לבין מספר תסריטי בדיקה הנפרדים הנדרשים לבדוק את הקוד, מה שמוסיף לערכו של המדד הזה, ומשתמשים בו על מנת לבדוק היתכנות בדיקה (testability) של הקוד. ככל שערכי הCCN גבוהים יותר, כך נדרשים יותר תסריטי בדיקה ייחודיים על מנת לבדוק את כל מסלולי הבקרה האפשריים של התוכנה הנבדקת. על בסיס וכהרחבה לסיבוכיות ציקלומטית, פותחה בישראל נוסחה לחישוב סיבוכיות סנכרון המעריכה את הסיבוכיות הנוספת של תוכנות מקביליות הנגרמת על ידי פקודות סנכרון בקוד.
- מדד קישוריות (Coupling Measure) - המדד הזה נותן ערך מספרי לקישורים הדדים בין מודולי תוכנה שונים. ככל שמודולים קשורים יותר אחד לשני (פונים אחד לשני ומשתמשים בנתונים אחד של השני) כך הערך הזה יהיה גבוה יותר. בתכנות מונחה עצמים, ערך גבוה של מדד הקישוריות מסמן ניתוח מערכת לוקה בחסר, שהביא להפרדה של מודולים שקשורים ברמה הלוגית.
הערות שוליים
- ^ Evaluating Software Complexity Measures, E.J.Weyuker, IEEE Transactions on Software Engineering, 14(9), 1988 IEEE
- ^ Joint Strike Fighter Air Vehicle C++ Coding Standards for the System Development and Demonstration Program." Document Number 2RDU00001 Rev C., December 2005. PDF
- ^ A Complexity Measure, T.McCabe, IEEE Transactions on Software Engineering, 2(4), 1976 IEEE
25134482סיבוכיות קוד