שונות

מורכבות זמן: מדוע אלגוריתמים מסוימים פועלים במשך מיליארדי שנים

מורכבות זמן: מדוע אלגוריתמים מסוימים פועלים במשך מיליארדי שנים

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

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

מהי מורכבות זמן?

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

במאמר הראשון בסדרה זו תיארתי ישר קדימה אלגוריתם סיכום. כדי לחשב את סְכוּם שֶׁל כל המספרים בין המספרים עמ ' ו ש, הכרזתי על משתנה אחר, ר, והגדר אותו ל אֶפֶס. לאחר מכן הוספתי עמ ' ל רואז הוספתי p + 1 ל ר, לאחר מכן p + 2, וכן הלאה עד שלבסוף הוספתי ש עצמה ל ר, בשלב זה עצרתי והחזרתי את התוצאה, ר, שהחזיק את סְכוּם.

כמה פעולות זה ידרוש, מבלי לדעת מה יהיה גודל הקלט האולטימטיבי, תוך שימוש רק במשתנים המופשטים עמ ' ו ש? מה שאנחנו באמת עושים זה להפעיל א לוּלָאָה איפה שכל איטרציה עולה עמ ' על ידי בדיוק 1 ומוסיף אותו ר. כך למעשה נראה האלגוריתם שלנו כשהוא מוצג בצורה יותר רשמית:

1. תן ר = 0
2. בזמן עמ ' הוא <= ל ש
3. ר=עמ '+ר
4. עמ ' = עמ '+1
5. לחזור ר

כשמונחים ככה במה שאנחנו מכנים פסאודוקוד, הרבה יותר קל לראות כמה פעולות זה ייקח. רד את המדרגות מספר אחר מספר וספר את הפעולות. הראשונה היא הוראה, אז זו פעולה אחת. השורה השנייה, לעומת זאת, שונה. לולאות כאלו חוזרות עד שהתנאי מתקיים, במקרה זה, פעם אחת עמ ' גדול מ ש. אנו יודעים אז שאנו כוללים ש ו עמ ' בתוך ה סְכוּם, כך מספר איטרציות דרך זה לוּלָאָה שווה ל q - (p - 1), שהוא ה גודל קלט לאלגוריתם שלנו.

אבל זה רק מספר הפעמים שאנחנו חוזרים דרך הלולאה, אנחנו צריכים גם לספור את הפעולות בתוכו, וזה המקום שאנחנו מוסיפים עמ ' ו ר ו לְהַקְצוֹת התוצאה ל ר ואז אנו מוסיפים עמ ' ו 1 ואז הקצה את התוצאה ל עמ ' אז אנחנו מופיעים שתי פעולות לכל איטרציה, ויש q - (p - 1)איטרציות. כל מה שאנחנו צריכים לעשות עכשיו זה להכפיל 2 פעולות ו q - (p - 1)איטרציות להשיג פעולות 2 * (q - (p - 1)) במשך כל הלולאה. הוסף את הפעולות ב -1 וב -5, מה שנותן לנו ספירה סופית של 2 * (q - (p - 1)) + 2 פעולות לאלגוריתם זה.

זוהי פונקציה לינארית מכיוון שאין מעריצים, ולכן ה- קצב גדילה כי אלגוריתם הסיכום שלנו הוא קשור ישירות ל ה קֶלֶט גודל, אותו אנו מכנים מורכבות זמן ליניארית. ככלל, מה שמונח הסדר הגבוה ביותר בנוסחה המגדירה את מורכבות הזמן שלנו הוא המאפיין את צמיחתו לאורך זמן, לכן אנו לוקחים את המונח הגבוה ביותר ונגרוט את השאר ונשאיר את q - (p - 1), אותו אנו שִׂיחָה נ למען הפשטות.

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

ידענו כבר הרבה מאוד זמן שה- סְכוּם שֶׁל את כלהמספרים מ 1 ו ש ניתן על ידי הנוסחה (q * (q + 1)) / 2. אנו יודעים גם כירכוש קומוטטיבי של תוספת אומר לנו שהתוצאה של (p-1 * (p)) / 2 נעדר מ (q * (q + 1)) / 2 פשוט מזנק את החלק של הסכום שכולל הכל 1 ל עמ '-1, עוזב את סְכוּם מהמספרים מ עמ ' ל ש מאחור, וזה בדיוק מה שאנחנו רוצים.

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

1. p = (p-1 * (p)) / 2
2. ש
= (q * (q + 1)) / 2
3. לַחֲזוֹר ( ש -עמ ' )

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

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

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

מהי Big O Notation?

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

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

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

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

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

* עַל): מורכבות זמן ליניארית- זה היה אלגוריתם הסיכום שלנו מההתחלה.

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

* עַל2): מורכבות זמן ריבועית- זה בדרך כלל נמצא בכל פעם שיש לך לולאות מקוננות. באלגוריתם הראשון שלנו, אם היה לנו לולאה שנייה בתוך הראשון, הפונקציה הייתה מפתחת מורכבות זמן ריבועית.

* עַלג, ג> 1): מורכבות זמן פולינומית- מורכבות זמן פולינומית הוא חשוב מאוד כי זה פחות או יותר מייצג את הגבול העליון על מה א מחשב קלאסי יכול לפתור תוך זמן מעשי.

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

* עַל!): מורכבות זמן פקטוריאלית- אלה אלגוריתמים שיכולים כנראה לרוץ עד למוות החום של היקום אם הם יקבלו גודל קלט גדול למדי של כמה אלפים. בכל פעם שיש לך משהו כמו "כמה דרכים שונות אתה יכול לארגן את הרצף הזה", יש לך בעיית תמורה ואומץ את הדרך לתשובה דורש ליצור n! ערכים שונים, הניתנים על ידי התוצאה של: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. אלה האלגוריתמים הפועלים כמעט במקביל ל ציר y בתרשים לעיל.

מדוע איננו יכולים רק להמציא אלגוריתמים טובים יותר

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

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

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

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

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

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


צפו בסרטון: Should I Give Up Computer Science If I Find It Hard? (דֵצֶמבֶּר 2021).