אַלע רעכט, אַזוי, קאַמפּיוטיישאַנאַל קאַמפּלעקסיטי. נאָר אַ ביסל פון אַ ווארענונג איידער מיר ונטערטוקנ זיך אין צו פאַר-- דעם וועט מיסטאָמע זיין צווישן די מערסט מאַט-שווער זאכן מיר רעדן וועגן אין קס50. אַלעווייַ עס וועט נישט זיין צו אָוווערוועלמינג און מיר וועט פּרובירן און פירן איר דורך די פּראָצעס, אָבער נאָר אַ ביסל פון אַ שיין ווארענונג. עס ס אַ קליין ביסל פון מאַט ינוואַלווד דאָ. אַלע רעכט, אַזוי אין סדר צו מאַכן נוצן פון אונדזער קאַמפּיוטיישאַנאַל רעסורסן אין דער עמעס וואָרלד-- עס ס טאַקע וויכטיק צו פֿאַרשטיין אַלגערידאַמז און ווי זיי פּראָצעס דאַטן. אויב מיר האָבן אַ טאַקע עפעקטיוו אַלגערידאַם, מיר קענען מינאַמייז די סומע פון ​​רעסורסן מיר האָבן פאַראַנען צו האַנדלען מיט אים. אויב מיר האָבן אַ אַלגערידאַם אַז איז געגאנגען צו נעמען אַ פּלאַץ פון אַרבעט צו פּראָצעס אַ טאַקע גרויס שטעלן פון דאַטן, עס ס געגאנגען צו דאַרפן מער און מער רעסורסן, וואָס איז געלט, באַראַן, אַלע וואָס מין פון שטאָפּן. 

אַזוי, ווייל קענען צו אַנאַלייז אַ אַלגערידאַם ניצן דעם געצייַג שטעלן, בייסיקלי, בעט די קוועסטיאָנ-- ווי טוט דעם אַלגערידאַם וואָג ווי מיר וואַרפן מער און מער דאַטן אין עס? אין קס50, די סומע פון ​​דאַטן מיר ניטאָ ארבעטן מיט איז שיין קליין. בכלל, אונדזער מגילה זענען געגאנגען צו לויפן אין אַ רגע אָדער לעסס-- מיסטאָמע אַ פּלאַץ ווייניקער דער הויפּט פרי אויף. 

אבער טראַכטן וועגן אַ פירמע אַז דילז מיט הונדערטער פון מיליאַנז פון קאַסטאַמערז. און זיי דאַרפֿן צו פּראָצעס אַז קונה דאַטע. ווי די נומער פון קאַסטאַמערז זיי האָבן געץ ביגער און ביגער, עס ס געגאנגען צו דאַרפן מער און מער רעסורסן. ווי פילע מער רעסורסן? נו, אַז דעפּענדס אויף ווי מיר אַנאַלייז די אַלגערידאַם, ניצן די מכשירים אין דעם מכשירים. ווען מיר רעדן וועגן די קאַמפּלעקסיטי פון אַ אַלגאָריטהמ-- וואָס מאל איר וועט הערן עס רעפעררעד צו ווי צייַט קאַמפּלעקסיטי אָדער פּלאַץ קאַמפּלעקסיטי אָבער מיר ניטאָ נאָר געגאנגען צו רופן קאָמפּלעקסיטי-- מיר ניטאָ בכלל גערעדט וועגן די ערגסטע-פאַל סצענאַר. געגעבן די אַבסאָלוט ערגסט הויפן פון דאַטע אַז מיר קען זייַן טראָוינג אין עס, ווי איז דעם אַלגערידאַם געגאנגען צו פּראָצעס אָדער האַנדלען מיט וואָס דאַטן? מיר בכלל רופן די ערגסטע-פאַל רונטימע פון ​​אַ אַלגערידאַם גרויס-אָ. אזוי אַ אַלגערידאַם זאל זיין האט געזאגט צו לויפן אין אָ פון N אָדער אָ פון N סקווערד. און מער וועגן וואָס די מיינען אין אַ רגע. 

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

און אין דעם קלאַס, מיר ניטאָ בכלל געגאנגען צו לאָזן די שטרענג אַנאַליסיס באַזונדער. עס זענען ססיענסעס און fields געטרייַ צו דעם מין פון שטאָפּן. ווען מיר רעדן וועגן ריזאַנינג דורך אַלגערידאַמז, וואָס מיר וועט טאָן שטיק-דורך-שטיק פֿאַר פילע אַלגערידאַמז מיר רעדן וועגן אין די סאָרט. מיר 'רע טאַקע נאָר גערעדט וועגן ריזאַנינג דורך עס מיט פּראָסט זינען, ניט מיט פאָרמולאַס, אָדער פּראָאָפס, אָדער עפּעס ווי אַז. אַזוי טאָן ניט זאָרג, מיר וועלן נישט זייַן אויסגעדרייט אין אַ גרויס מאַט קלאַס. 

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

איצט, מיר קענען מעסטן אַ אַלגאָריטהמ-- אין באַזונדער, ווען איך זאָגן מיר קענען מאָס אַ אַלגערידאַם, איך מיינען מיר קענען מעסטן ווי פילע רעסורסן עס נעמט זיך. צי די רעסורסן זענען, ווי פילע בייטן פון ראַמ-- אָדער מעגאבייט פון באַראַן עס ניצט. אָדער ווי פיל צייַט עס נעמט צו לויפן. און מיר קענען רופן דעם מאָס, אַרביטרעראַלי, ו פון ען. ווו N איז די נומער פון עלעמענטן אין דער דאַטן שטעלן. און ו פון N איז ווי פילע סאָמעטהינגס. ווי פילע וניץ פון רעסורסן טוט עס דאַרפן צו פּראָצעס אַז דאַטע. 

איצט, מיר אַקשלי טאָן ניט זאָרגן וועגן וואָס ו פון N איז פּונקט. אין פאַקט, מיר זייער ראַרעלי ווילל-- זיכער וועט קיינמאָל אין דעם קלאַסס-- איך ונטערטוקנ זיך אין קיין טאַקע טיף אַנאַליסיס פון וואָס ו פון N איז. מיר 'רע נאָר געגאנגען צו רעדן וועגן וואָס ו פון N איז בעערעך אָדער וואָס עס טענדז צו. און די טענדענץ פון אַ אַלגערידאַם איז דיקטייטיד דורך זייַן העכסטן סדר טערמין. און מיר קענען זען וואָס איך מיינען דורך אַז דורך גענומען אַ קוק אין אַ מער באַטאָנען בייַשפּיל. 

אזוי לאָזן ס זאָגן אַז מיר האָבן דרייַ פאַרשידענע אַלגערידאַמז. דער ערשטער פון וואָס נעמט N קובעד, עטלעכע וניץ פון רעסורסן צו פּראָצעס אַ דאַטן שטעלן פון גרייס ען. מיר האָבן אַ רגע אַלגערידאַם וואָס נעמט N קובעד פּלוס N סקווערד רעסורסן צו פּראָצעס אַ דאַטן שטעלן פון גרייס ען. און מיר האָבן אַ דריט אַלגערידאַם אַז ראַנז ינ-- אַז נעמט זיך N קובעד מינוס 8ן סקווערד פּלוס 20 N וניץ פון רעסורסן צו פּראָצעס אַ אַלגערידאַם מיט דאַטן שטעלן פון גרייס ען. 

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

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

איצט, די חילוק צווישן די אַלגערידאַמז אָנהייבן צו ווערן אַ ביסל ווייניקער קלאָר. און די פאַקט אַז עס זענען נידעריקער-סדר טערמס-- אָדער גאַנץ, טערמינען מיט נידעריקער עקספּאָנענצ-- אָנהייבן צו ווערן ירעלאַוואַנט. אויב אַ דאַטן שטעלן איז פון גרייס 1,000 און דער ערשטער אַלגערידאַם ראַנז אין אַ ביליאָן טריט. און די רגע אַלגערידאַם ראַנז אין אַ ביליאָן און אַ מיליאָן טריט. און די דריטע אַלגערידאַם ראַנז אין נאָר שעמעוודיק פון אַ ביליאָן טריט. עס ס שיין פיל אַ ביליאָן טריט. יענע נידעריקער-סדר ווערטער אָנהייבן צו ווערן טאַקע ירעלאַוואַנט. און פּונקט צו טאַקע האַמער היים די פּאָינט-- אויב די דאַטע ינפּוט איז פון גרייס אַ מילליאָנ-- אַלע דרייַ פון די שיין פיל נעמען איין קווינטילליאָנ-- אויב מיין מאַט איז קאָררעקט-- טריט צו פּראָצעס אַ דאַטע ינפּוט פון גרייס אַ מיליאָן. אַז ס אַ פּלאַץ פון טריט. און די פאַקט אַז איינער פון זיי זאל נעמען אַ פּאָר 100.000, אָדער אַ פּאָר 100 מיליאָן אַפֿילו ווייניקער ווען מיר ניטאָ גערעדט וועגן אַ נומער אַז ביג-- עס ס מין פון ירעלאַוואַנט. זיי אַלע טענד צו נעמען בעערעך N קובעד, און אַזוי מיר וואָלט אַקטשאַוואַלי אָפּשיקן צו אַלע פון ​​די אַלגערידאַמז ווי ווייל אויף די סדר פון N קובעד אָדער גרויס-אָ פון N קובעד. 

דאָ ס אַ רשימה פון עטלעכע פון ​​די מער פּראָסט קאַמפּיוטיישאַנאַל קאַמפּלעקסיטי קלאסן אַז מיר וועט טרעפן אין אַלגערידאַמז, בכלל. און אויך ספּעסיפיקאַללי אין קס50. דאס זענען אָרדערד פון בכלל fastest אין די שפּיץ, צו בכלל סלאָואַסט אין די דנאָ. אַזוי קעסיידערדיק צייַט אַלגערידאַמז טענד צו זיין די fastest, ראַגאַרדלאַס די גרייס פון די דאַטע ינפּוט איר פאָרן אין. זיי שטענדיק נעמען איין אָפּעראַציע אָדער איינער אַפּאַראַט פון רעסורסן צו האַנדלען מיט. עס זאל זיין 2, עס זאל זייַן 3, עס זאל זיין 4. אבער עס ס אַ קעסיידערדיק נומער. עס טוט נישט בייַטן. 

לאַגערידמיק צייַט אַלגערידאַמז זענען אַ ביסל בעסער. און אַ טאַקע גוט בייַשפּיל פון אַ לאַגערידמיק צייַט אַלגערידאַם איר ווע שורלי געזען דורך איצט איז די טירינג באַזונדער פון די טעלעפאָנירן בוך צו געפֿינען מייק סמיט אין די טעלעפאָנירן בוך. מיר שנייַדן די פּראָבלעם אין העלפט. און אַזוי ווי N געץ גרעסערע און גרעסער און לאַרגער-- אין פאַקט, יעדער מאָל איר טאָפּל ן, עס נאָר נעמט איינער מער שריט. אַזוי אַז ס אַ פּלאַץ בעסער ווי, זאָגן, לינעאַר צייַט. וואָס איז אויב איר טאָפּל ן, עס נעמט טאָפּל די נומער פון טריט. אויב איר דרייַיק ן, עס נעמט דרייַיק די נומער פון טריט. איין שריט פּער אַפּאַראַט. 

דעמאָלט דאס באַקומען אַ ביסל מאָרע-- ביסל ווייניקער גרויס פון דאָרט. איר האָבן לינעאַר רידמיק צייַט, מאל גערופֿן קלאָץ לינעאַר צייַט אָדער נאָר N קלאָץ ען. און מיר וועט אַ משל פון אַ אַלגערידאַם אַז ראַנז אין N קלאָץ N, וואָס איז נאָך בעסער ווי קוואַדראַטיק טימע-- N סקווערד. אָדער פּאַלינאָומיאַל צייַט, ען צוויי קיין נומער גרעסער ווי צוויי. אָדער עקספּאָונענשאַל צייַט, וואָס איז אַפֿילו וואָרסע-- C צו די ען. אַזוי עטלעכע קעסיידערדיק נומער האט צו די מאַכט פון די גרייס פון די ינפּוט. אַזוי אויב עס ס 1,000-- אויב די דאַטע ינפּוט איז פון גרייס 1,000, עס וואָלט נעמען C צו די 1000 מאַכט. עס ס אַ פּלאַץ ערגער ווי פּאַלינאָומיאַל צייַט. 

פאַקטאָריאַל צייַט איז אַפֿילו ערגער. און אין פאַקט, עס טאַקע טאָן עקסיסטירן Infinite צייַט אַלגערידאַמז, אַזאַ ווי, אַזוי-גערופֿן נאַריש סאָרט-- וועמענס אַרבעט איז צו ראַנדאַמלי שאַרן אַ מענגע און דעמאָלט טשעק צו זען צי עס ס אויסגעשטעלט. און אויב עס ס ניט, ראַנדאַמלי שאַרן די מענגע ווידער און טשעק צו זען צי עס ס אויסגעשטעלט. און ווי איר קענען מיסטאָמע ימאַגינע-- איר קענען ימאַדזשאַן אַ סיטואַציע ווו אין די ערגסטע-פאַל, וואָס וועט קיינמאָל אַקטשאַוואַלי אָנהייבן מיט די מענגע. אַז אַלגערידאַם וואָלט לויפן אויף אייביק. און אַזוי אַז וואָלט זיין אַ Infinite צייַט אַלגערידאַם. אַלעווייַ איר וועט ניט זיין שרייבן קיין פאַקטאָריאַל אָדער אַנלימאַטאַד צייַט אַלגערידאַמז אין קס50. 

אַזוי, לאָזן ס נעמען אַ ביסל מער באַטאָנען קוק אין עטלעכע סימפּלער קאַמפּיוטיישאַנאַל קאַמפּלעקסיטי קלאסן. אַזוי מיר האָבן אַ עקסאַמפּלע-- אָדער צוויי יגזאַמפּאַלז הערע-- פון קעסיידערדיק צייַט אַלגערידאַמז, וואָס שטענדיק נעמען אַ איין אָפּעראַציע אין די ערגסטע-פאַל. אַזוי דער ערשטער עקסאַמפּלע-- מיר האָבן אַ פֿונקציע גערופֿן 4 פֿאַר איר, וואָס נעמט אַ מענגע פון ​​גרייס 1,000. אבער דעמאָלט משמעות טוט ניט אַקטשאַוואַלי קוקן ביי יט-- טוט ניט טאַקע זאָרגן וואָס ס ין פון עס, פון וואָס מענגע. שטענדיק נאָר קערט פיר. אַזוי, אַז אַלגערידאַם, טראָץ דער פאַקט אַז עס נעמט 1,000 יסודות טוט ניט טאָן עפּעס מיט זיי. נאָר קערט פיר. עס ס שטענדיק אַ איין שריט. 

אין פאַקט, לייגן 2 נומס-- וואָס מיר ווע געזען פריער ווי וועלל-- נאָר פּראַסעסאַז צוויי ינטאַדזשערז. עס ס ניט אַ איין שריט. עס ס אַקטשאַוואַלי אַ פּאָר טריט. איר באַקומען אַ, איר באַקומען ב, איר שטעלן זיי צוזאַמען, און איר רעזולטאַט די רעזולטאטן. אַזוי עס ס 84 טריט. אבער עס ס שטענדיק קעסיידערדיק, ראַגאַרדלאַס פון אַ אָדער ב. איר האָבן צו באַקומען אַ, באַקומען ב, לייגן זיי צוזאַמען, פּראָדוקציע די רעזולטאַט. אַזוי אַז ס אַ קעסיידערדיק צייַט אַלגערידאַם. 

דאָ ס אַ בייַשפּיל פון אַ לינעאַר צייַט אַלגאָריטהמ-- אַ אַלגערידאַם אַז געצ-- וואָס נעמט איינער נאָך שריט, עפשער, ווי דיין ינפּוט וואקסט דורך 1. אַזוי, לאָזן ס זאָגן מיר ניטאָ קוקן פֿאַר די נומער 5 ין פון אַ מענגע. איר זאל האָבן אַ סיטואַציע ווו איר קענען געפֿינען עס פאַירלי פרי. אבער איר קען אויך האָבן אַ סיטואַציע ווו עס זאל זיין די לעצטע עלעמענט פון די מענגע. אין אַ מענגע פון ​​גרייס 5, אויב מיר ניטאָ קוקן פֿאַר די נומער 5. עס וואָלט נעמען 5 טריט. און אין פאַקט, ימאַדזשאַן אַז עס ס ניט 5 ערגעץ אין דעם מענגע. מיר נאָך אַקטשאַוואַלי האָבן צו קוקן אין יעדער איין עלעמענט פון די מענגע אין סדר צו באַשליסן צי אָדער ניט 5 איז עס. 

אַזוי אין די ערגסט-פאַל, וואָס איז אַז די עלעמענט איז לעצט אין די מענגע אָדער טוט נישט עקסיסטירן אין אַלע. מיר נאָך האָבן צו קוקן אין אַלע פון ​​די ען עלעמענטן. און אַזוי דעם אַלגערידאַם ראַנז אין לינעאַר צייַט. איר קענען באַשטעטיקן אַז דורך עקסטראַפּאָלאַטינג אַ ביסל דורך געזאגט, אויב מיר האבן אַ 6-עלעמענט מענגע און מיר זענען קוקן פֿאַר די נומער 5, עס זאל נעמען 6 טריט. אויב מיר האָבן אַ 7-עלעמענט מענגע און מיר ניטאָ קוקן פֿאַר די נומער 5. עס זאל נעמען 7 טריט. ווי מיר לייגן איינער מער עלעמענט צו אונדזער מענגע, עס נעמט איינער מער שריט. אַז ס אַ לינעאַר אַלגערידאַם אין די ערגסטע-פאַל. 

פּאָר שנעל שאלות פֿאַר איר. וואָס ס די רונטימע-- וואָס ס די ערגסטע-פאַל רונטימע פון דעם באַזונדער סניפּאַט פון קאָד? אַזוי איך האָבן אַ 4 שלייף דאָ אַז ראַנז פון דזש יקוואַלז 0, אַלע די וועג אַרויף צו עם. און וואָס איך בין געזען דאָ, איז אַז די גוף פון די שלייף ראַנז אין קעסיידערדיק צייַט. אזוי ניצן די טערמינאָלאָגיע אַז מיר ווע שוין גערעדט אַבאָוט-- וואָס וואָלט זיין די ערגסטע-פאַל רונטימע פון ​​דעם אַלגערידאַם? נעמען אַ רגע. די ינער טייל פון די שלייף ראַנז אין קעסיידערדיק צייַט. און די ויסווייניקסט טייל פון די שלייף איז געגאנגען צו לויפן עם מאל. אזוי וואָס ס די ערגסט-פאַל רונטימע דאָ? האט איר טרעפן גרויס-אָ פון עם? איר 'ד ווערן רעכט. 

ווי וועגן אן אנדער איינער? דאס מאָל מיר האָבן אַ שלייף ין פון אַ שלייף. מיר האָבן אַ ויסווייניקסט שלייף אַז ראַנז פון נול צו פּ. און מיר האָבן אַ ינער שלייף אַז ראַנז פון נול צו ז, און ין פון וואָס, איך שטאַט אַז די גוף די שלייף ראַנז אין קעסיידערדיק צייַט. אזוי וואָס ס די ערגסט-פאַל רונטימע פון דעם באַזונדער סניפּאַט פון קאָד? נו, ווידער, מיר האָבן אַ ויסווייניקסט שלייף אַז ראַנז פּ מאל. און יעדער טימע-- יטעראַטיאָן פון וואָס שלייף, אלא. מיר האָבן אַ ינער שלייף אַז אויך ראַנז פּ מאל. און דעמאָלט ין פון אַז, עס ס די קעסיידערדיק טימע-- קליין סניפּאַט דאָרט. 

אַזוי אויב מיר האָבן אַ ויסווייניקסט שלייף אַז ראַנז פּ מאל ין פון וואָס איז אַ ינער שלייף אַז ראַנז פּ טימעס-- וואָס איז די ערגסטע-פאַל רונטימע פון דעם סניפּאַט פון קאָד? האט איר טרעפן גרויס-אָ פון פּ סקווערד? 

איך בין דאַג לויד. דאס איז קס50.