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

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

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

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

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

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

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

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

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

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

אם ערכת הנתונים שלנו היא בגודל 10, ש הוא גדול יותר, אך לא בהכרח ענק, אנחנו יכולים לראות שיש למעשה קצת הבדל. האלגוריתם השלישי הופך יעיל יותר. זה בעצם על 40% - או 60% יעילים יותר. זה לוקח 40% את כמות הזמן. זה יכול run-- זה יכול לקחת 400 יחידות של משאבים לעבד סט נתונים של גודל 10. בעוד הראשון אלגוריתם, לעומת זאת, לוקח 1,000 יחידות של משאבים לעבד סט נתונים של גודל 10. אבל תראה מה קורה כ המספרים שלנו להגיע אפילו גדולים יותר. 

עכשיו, ההבדל בין אלגוריתמים אלה מתחיל להיות קצת פחות נראית לעין. והעובדה שיש נמוך-מנת terms-- או לייתר דיוק, מונחים עם exponents-- הנמוך מתחיל להיות לא רלוונטי. אם ערכת נתונים היא בגודל 1,000 והאלגוריתם הראשון פועל במליארד שלבים. והאלגוריתם השני פועל ב מיליארדים ומיליון צעדים. והאלגוריתם השלישי פועל בפשוט ביישן של מיליארדים צעדים. זה די הרבה מיליארדים צעדים. אלה תנאים התחתון כדי להתחיל כדי להפוך באמת לא רלוונטי. ורק כדי באמת פטיש בית point-- אם נתוני הקלט הוא בגודל million-- כל שלושת אלה פחות או יותר לקחת quintillion-- אחד אם המתמטיקה שלי היא צעדי correct-- לעבד קלט נתונים גודל מיליון. זה הרבה שלבים. והעובדה שאחד מהם עשויה לקחת כמה 100,000, או לזוג 100 מיליון אפילו פחות כאשר על מספר אנחנו מדברים שbig-- זה סוג של לא רלוונטי. כולם נוטים לקחת כ קוביות n, וכך היינו למעשה מתייחס לכל אלגוריתמים אלה כמו להיות על סדר n קוביות או גדול-O של קוביות n. 

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

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

אז דברים מקבלים קצת more-- קצת פחות גדול משם. יש לך זמן קצוב ליניארי, לפעמים נקרא זמן ליניארי יומן או פשוט להיכנס n n. ואנחנו דוגמא של אלגוריתם ש ריצות בn n יומן, שהוא עדיין טוב יותר מ n time-- ריבועית בריבוע. או זמן פולינום, n שני כל מספר גדול משני. או זמן מעריכי, ש הוא אפילו C לworse-- n. אז כמה מספר קבוע העלה ל כוחו של גודל הקלט. אז אם יש 1,000-- אם נתוני קלט הוא בגודל 1,000, זה ייקח C לכח -1,000. זה הרבה יותר גרוע מאשר זמן פולינום. 

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

אז, בואו ניקח קצת יותר מבט בטון בכמה פשוט כיתות מורכבות חישובית. אז יש לנו example-- או שתי דוגמאות כאן-- אלגוריתמים זמן קבועים, שתמיד לוקחים פעולה אחת במקרה הגרוע ביותר. אז example-- הראשון יש לנו פונקציה נקרא 4 בשבילך, ש לוקח מערך של גודל 1,000. אבל אז, ככל הנראה, לא ממש נראה בלא ממש אכפת מה it-- בתוכו, של מערך זה. תמיד רק חוזר ארבעה. אז, אלגוריתם ש, למרות שזה לוקח 1,000 אלמנטים לא לעשות שום דבר איתם. רק חוזר ארבעה. זה תמיד צעד אחד. 

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

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

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

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

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

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

אני דאג לויד. זה CS50.