מבוא למורכבות הזמן של האלגוריתמים

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

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

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

מורכבות זמן

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

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

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

1. חיפוש לינארי.

2. חיפוש בינארי.

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

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

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

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

באופן כללי, חיפוש לינארי ייקח n מספר פעולות במקרה הגרוע ביותר שלו (כאשר n הוא גודל המערך).

בואו נבחן את אלגוריתם החיפוש הבינארי למקרה זה.

ניתן להבין בקלות חיפוש בינארי על ידי דוגמה זו:

מקור: Learneroo

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

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

מספר פעולות = יומן (10) = 4 (בערך)

לבסיס 2

אנו יכולים להכליל תוצאה זו עבור חיפוש בינארי כ:

עבור מערך בגודל n , מספר הפעולות המבוצע על ידי החיפוש הבינארי הוא: log (n)

סימון ביג או

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

מקור: טכטוד

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

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

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

מורכבות הזמן או סימני ה- Big O עבור כמה אלגוריתמים פופולריים מפורטים להלן:

1. חיפוש בינארי: O (log n)
2. חיפוש לינארי: O (n)
3. מיון מהיר: O (n * log n)
4. מיון בחירה: O (n * n)
5. איש מכירות נוסע: O (n!)

סיכום

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

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

לדוגמא, אם יש לנו 4 מיליארד אלמנטים לחיפוש, אז במקרה הגרוע ביותר, חיפוש לינארי ייקח 4 מיליארד פעולות כדי להשלים את משימתה. חיפוש בינארי ישלים משימה זו ב -32 פעולות בלבד. זה הבדל גדול. עכשיו נניח שאם פעולה אחת אורכת 1 אלפיות שנשלמה להשלמה, החיפוש הבינארי ייקח רק 32 אלפיות ואילו החיפוש הליניארי ייקח 4 מיליארד אלפיות שניים (כלומר כ- 46 יום). זה הבדל משמעותי.

זו הסיבה שלימוד מורכבות הזמן הופך להיות חשוב כשמדובר בכמות כה גדולה של נתונים.

אֶמְצָעִי

אלגוריתמים גישושים - מאת Aditya Y Bhargava

מבוא לסימון Big O ולמורכבות זמן- מאת CS Dojo