הבנת סיבוכיות זמן ריצה: מדריך למתחילים

O(1) - סיבוכיות קבועה:

האופציה הכי מהירה והכי טובה היא גישה ישירה לתא במערך. לא משנה כמה גדול הקלט שלנו יהיה, הזמן לביצוע הפונקציה ישאר קבוע. במקרה שלנו, התוכנה תרוץ רק פעם אחת, ואם ניקח לדוגמה מערך של חמישה איברים ונרצה לגשת לאיבר השלישי, נוכל לבצע את זה במהירות של O(1). כלומר, גישה לכל תא במערך, לא משנה מה הגודל שלו, תהיה בזמן קבוע - O(1), וזה נכון לכל שפת תכנות!

O(log n) - סיבוכיות לוגריתמית:

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

תחשבו על משחק בו אתם מנסים לנחש מספר בין 1 ל-1,000, ואני אומר לכם בכל פעם אם המספר שאתם חשבתם עליו גדול יותר או קטן יותר מהמספר שבחרתי. אתם מתחילים על ידי שאלה אם זה המספר 500 (חצי מ-1,000). אם אני אומר "גדול יותר", אתם מבינים שהמספר שאני חושב עליו הוא בין 501 ל-1,000. בשלב הבא, אתם מציינים מספר באמצע הטווח החדש, כלומר 750. וכך הלאה, בכל פעם אתם מחצים את הטווח, עד שאתם מגיעים למספר שבחרתי.

הנה החישוב: המספר המרבי של הניחושים במשחק זה הוא log₂(1,000). למעשה, זה פחות מ-10 ניחושים! כלומר, גם אם אני בחרתי מספר בין 1 ל-1,000, תוכלו לנחש אותו בפחות מ-10 ניחושים בשיטה הזו. די מגניב לא? ובכדי להבין את המושג "לוגריתם", כדאי לדעת שהוא הפונקציה ההפוכה לחזקה. כלומר, אם אנחנו אומרים ש-log₂(1,000) הוא X, זה אומר ש-2 בחזקת X הוא 1,000, במילים פשוטות אפשר לאמר ש-log מרדד את המספר

O(n) - סיבוכיות ליניארית:

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

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

O(n * a):

כאשר יש לנו שני מערכים, הראשון באורך n והשני באורך a, ואנו רוצים לבצע פעולה בין כל איבר לאיבר, הפעולה תתבצע בסך הכול n * a פעמים, שבמקרה שלנו בקוד למטה הוא 8 פעמים.

O(n^2) - סיבוכיות בריבוע:

הכוונה היא שזמן הריצה של הפונקציה גדל באופן ריבועי בהתאם לגודל הקלט, לדוגמה מערך של חמישה איברים ירוץ 25 פעמים ( 25 = 2^5). בואו נראה דוגמה:

O(2^n) - סיבוכיות אקספוננציאלית:

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

אם יש לכם מנורה אחת, האפשרויות הן 2^1 = 2. כאשר תוסיפו מנורה נוספת, האפשרויות גדלות ל-4=2^2. כאשר תוסיפו מנורה שלישית, האפשרויות גדלות ל-8 = 3^2, וכך הלאה. באופן כללי, עבור 5 מנורות, יהיו לכם 2^n אפשרויות.

O(n!) - סיבוכיות פקטוריאלית:

אחת התופעות הנפוצות שבהם נתקלים בסיבוכיות זו היא בחישוב כל הצירופים האפשריים של רשימה. לדוגמה, דמיינו שאתם מזמינים חברים לבית שלכם למסיבת יומולדת, ואתם רוצים להתמקם בצידם בכל דרך אפשרית לצילום תמונה. אם יש לכם 3 חברים, יש לכם !3 (3 עצרת) אופנים שונים להתמקם:

• חבר 1, חבר 2, חבר 3
• חבר 1, חבר 3, חבר 2
• חבר 2, חבר 1, חבר 3
• חבר 2, חבר 3, חבר 1
• חבר 3, חבר 1, חבר 2
• חבר 3, חבר 2, חבר 1
• ==> 1 * 2 * 3 = 6.

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