[MUSIC PLAYING] DAVID J. MALAN: Bu CS50 edir. Bu həftə üç başlanğıc. Beləliklə, biz maraqlı bir çox var hər şeyi bu gün əhatə. Imkanları bir çox üçün səhnəyə könüllüsü. Və nəticədə, bu gün Biz kodu haqqında bütün. Amma bu, fikir haqqında və Bu alqoritmlər haqqında, və həqiqətən bəzi geri gətirilməsi Həftə sıfır öyrəndim dərslər, orada geri, biz Bu canavar təqdim etdi. Və borc ilham ki, başlamaq üçün daha mürəkkəb həll etmək algorithmically problemləri. Lakin ilk, elanlar bir neçə. Belə bir, siz qoşulmaq istəyirsinizsə, Nahar CS50 heyəti və sinif yoldaşları bu cümə, həm də burada və Cambridge, və New Haven, Əlbəttə nin müraciət edin bir URL bilər veb. Bu Çərşənbə edəcək mühazirə Sanders burada deyil. Bu, belə ki, yalnız online olacaq CS50 saytında tune, burada Cambridge olub və ya New Haven həmçinin. Və sonra problem iki set Əlinizdə artıq. Siz hələ getdi deyil varsa, mənə imkan verir sərt təklif təklif xüsusilə indi, kimi problem, əvvəlcədən müəyyən Siz, həqiqətən, indi əgər başlamaq istəyirəm həftə sonu və ya əvvəl bir az dabble Onlar ilk çıxmaq zaman Fridays, siz lazımdır, çünki onlar mütləq deyilik ki, tapmaq uzun və ya daha çətin başına əldə se. Mən, siz ki, tapa bilərsiniz edirəm Ümumiyyətlə, onlar təxminən edirlər eyni məbləği ətrafında. Lakin əlbəttə asılıdır tələbə və bu barədə zehniyyət asılıdır olan siz yanaşırıq. Amma daim, siz olacaq bir divar qarşı çalıştırmak üçün, və hit olacaq bəzi səhv və siz etdiyiniz yalnız etmək niyyətində deyil bir nöqtədə artıq almaq. Və bu etmək üçün natarazcasına qiymətli deyil üz addım növbəti gün geri gəlmək, ofis saat getmək, CS50 haqqında post müzakirə və ya kimi, həqiqətən engelleyicisi almaq üçün. Belə ki, nəzərə ki, saxlamaq. Mümkün erkən başlayaraq Siz edə bilərsiniz ən yaxşı şey deyil. Biz başladı Belə ki, burada Həftə sıfır üzərində class. Və biz könüllü əldə edə bilərsiniz Burada məni ÇGKS tapmaq üçün? OLDU. Artıq daimi. Qədər gəlib. Ki, iş gedir necə var danışarlar. Sənin adın nədir? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Qədər gəlib. Görüşmək Nice. ALAN ESTRADA: Cavab gözəl. DAVID J. Malan: Və burada idi Bizə həftə sıfır, əlbəttə ilə. ALAN ESTRADA: I idi. Mən idim. DAVID J. MALAN: Belə ki, getmək bilər irəli və Mike Smith bizim üçün tapmaq, Siz kimi sürətli kimi? Siz kimi sürətli kimi. Sözün problem qoparmaq yarısında sizə lazım kimi. ALAN ESTRADA: Um. DAVID J. MALAN: Sözün yarısında problem qoparmaq. ALAN ESTRADA: Oh. Mm. Çox yaxşı. DAVID J. MALAN: OK. Yaxşı. Təşəkkür edirəm. ALAN ESTRADA: Çox yaxşı. OLDU. DAVID J. MALAN: Və indi, Siz aşağı whittled etdik problemin yarısı ölçüsü. İndi biz bir rüb aşağı istəyirik. Siz diqqət edirsiniz biz saxlanılması edirik yan? [Gülür] ALAN ESTRADA: Bəli, mən Sizcə DAVID J. MALAN: Nə bölmə biz var? ALAN ESTRADA: Mufflers, belə. DAVID J. MALAN: OK. Amma Mike Smith gedir Mufflers sonra olmalıdır. Belə ki-- [Gülür] Oldu. ALAN ESTRADA: Harada biz axtarır? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: İndi biz cərrahi istəyirik. İndi, həkimlərin. , Indi ALAN ESTRADA: real ilə gedək Let's-. Real. DAVID J. MALAN: Real. OLDU. Siz real ehtiyac varsa. İndi Mike Smith yol var? ALAN ESTRADA: Bu yolla. DAVID J. MALAN: yol? ALAN ESTRADA: gözləyin. M is-- sağ? Biz with-- başladı DAVID J. MALAN: Bəli. Onlar tərk edirik. Sağ. ALAN ESTRADA: Bəli. DAVID J. MALAN: Belə ki, Mike burada da. ALAN ESTRADA: Nə? [Gülür] Pis nümunə, uşaqlar. Sorry. DAVID J. MALAN: Bu öyrətmək olacaq Siz kafedra həyata atılmaq üçün. ALAN ESTRADA: Oh. Oh. Səni anladım. Səni anladım. Oh. Oh. Bu OK is--, mən sizə var. Burada Smith? DAVID J. MALAN: Smith, təşəkkür edirəm. Beləliklə, mən Smith axtarır saxlamaq lazımdır? ALAN ESTRADA: Bəli, Oh. Yox, yox, yox. Ah, yox. Bu mina. DAVID J. MALAN: Oh, siz Smith var. OLDU. ALAN ESTRADA: Bəli, mən burada Smith var. Bağışlayın, uşaqlar. Mən Michael-- fikir biz Michael aradığınız. Sorry. DAVID J. MALAN: OK. Bütün hüquqlar, indi biz istəyirik Paccini and Sons daxil. ALAN ESTRADA: Paccini və oğulları. DAVID J. MALAN: Yalnız və mən bu barədə var. OLDU. Bizə Mike Smith tapmaq. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Biz zibil üçün R istəyirik. ALAN ESTRADA: Rubbish. Oh. Bu bir müddət gedir. [Gülür] DAVID J. MALAN: Shoes. Biz ayaqqabı istəyirik. ALAN ESTRADA: İndi biz gonna-- edirik DAVID J. MALAN: Nice. ALAN ESTRADA: Which-- [Gülür] Oh, bu böyükdür. [Gülür] DAVID J. MALAN: OK. ALAN ESTRADA: Oh, bu yaxşıdır. Mən gedirəm düşünmürəm Bundan sonra PSAT arkadaşları var. DAVID J. MALAN: Yaxşı. İdman. ALAN ESTRADA: İdman. Um, L, M, N, O, P. DAVID J. MALAN: OK. Belə ki, yarısında bu qoparmaq edək. Yaxşıdır. Bu, hər halda zəif başa Mike çünki Smith sarı pages olmayacaq. ALAN ESTRADA: Aw. DAVID J. MALAN: Xeyr, bu, OK. Amma kimi iddia edək O, bu səhifədə var. Belə ki, indi siz aşağı problem whittled etdik bir səhifə və biz Mike Smith tapılmadı. [Təzahürat] OK, təşəkkür edirəm. OLDU. Bu qeyri-adi idi. Amma hələ daha sürətli idi xətti axtarış daha orada biz başlamaq Kitabın əvvəlində, soldan sağa və biz yol hərəkət, nəticədə Mike Smith axtarır. Belə ki, əgər telefon kitab , bəlkə 1000 pages idi bəlkə qəbul olardı bizə 10 və ya belə səhifə gözyaşlarını tuta bilmədi. Amma leveraged ola bilər bir ehtimal toxunub ki, bütün əsnasında olan demək deyil əvvəlcədən telefon kitab nə idi ki? Auditoriya: sıralandı. DAVID J. MALAN: Bu sıralanır. Sağ? Bu, belə ki, əlifba sırası ilə sıralanır oldu bu adları və nömrələri bütün A-dən ayrılır Z-nin, və əlifba sırası ilə arasında. Amma bu gün, indi xahiş sual, yaxşı, necə Verizon və ya telefon etdi Şirkət ki, dövlət onu almaq? Bir şey var, çünki leverage ki, fərziyyə və buna görə də, bir bir problem həll alqoritm daha səmərəli. Amma biz, həqiqətən, Həftə sıfır istədi, yaxşı, dəyəri bunu nə qədər Verizon və ya başqa kimsə sorted üçün ki, telefon kitab almaq üçün necə? Sağ? Əgər Fərq etməz Mike Smith axtarır bu bir edir, əgər, super sürətli il ilk pages düzmək üçün. Sağ? Siz həmçinin yalnız elemek bilər bir randomizə telefon kitab vasitəsilə, Bu super olacaq, əgər bu sort üçün bahalı. Belə ki, biz bir könüllü ola bilər. Bir almaq burada axtarmaq bildirin Biz necə gündəmə gəlib might-- necə Biz bu çeşidlənməsi haqqında getmək bilər. Əgər Jordan həqiqətən bilər səhnədə burada bizə qoşulmaq. Yalnız bir an üçün gəlib. Sənin adın nədir? CAROLINE: Caroline. DAVID J. MALAN: Caroline qədər gəlib. Və qoşulub olacaq burada mənə və İordaniya tərəfindən. Caroline, təşəkkür edirəm. Oldu. Beləliklə, biz burada nə Caroline 26 mavi kitab FAS idarə üçün istifadə edir ki, Müəyyən final imtahanları. Bu tapmaq çətin qovuşur lakin biz əvvəlcədən nə etdik biz kiminsə adını qoymaq etdik ki, bu hər ön, lakin biz çox sadə saxlanılır etdik sonra tam adları həyata qoyulması. Beləliklə, biz adı ilə şəxs qoymaq olardı L, D, J, B, bütün yol A-dan Z vasitəsilə, lakin onlar təsadüfi qaydada edirik. Və ki, əgər Belə ki, söhbət sizin kimi problem vasitəsilə yol Bu, siz davam edə bilər yoxdur və A-dan Z., bizim üçün bu sort Auditoriya: OK, belə ki, L orta kimi. C başlayır. B. L. B əvvəl J, Q. DAVID J. MALAN: ki, tutun bir ikinci düşündüm. Başqa, çünki bu yalnız Siz mənə və İordaniyaya maraqlı. Biz orada getmək. Auditoriya: [işitilemez]. R. DAVID J. MALAN: OK. Nə edirsiniz? CAROLINE: M O. sonra gəlir DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Yaxşı. CAROLINE: E. DAVID J. MALAN: E, F. Bəli. CAROLINE: T, U, V. DAVID J. MALAN: V, T, U, V. Bu, belə Siz davam making-- etdiyiniz kimi görünür. Siz edirik kimi görünür Böyük bir qalaq burada, və orada böyük bir qalaq cür. Belə ki, əlifbası ilk yarısında, əlifbası ikinci yarısı. OLDU. Yaxşı. Kind iki problemi parçalanması. M, N, X. Bəli. CAROLINE: K. DAVID J. MALAN: OK. K. Belə ki cür seçilməsi edirik başqa sonra onlara bir, sol və ya sağ ya onu qoyaraq, və ya Z-nin mərtəbəsində gedir. OLDU. CAROLINE: Z mərtəbəsində olacaq. DAVID J. MALAN: OK. Y mərtəbəsində davam edir. İndi biz X. qoya bilər CAROLINE: G. DAVID J. MALAN: G sol gedir. S doğru gedir. Bütün sağ, sol bütün yol gedir. CAROLINE: A, B, C, D DAVID J. MALAN: İndi yaxşı. Biz bir var, B, C. W aşağı gedir. Bütün hüquqlar, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Yaxşı. CAROLINE: mərkəzində, mən gonna-- alıram DAVID J. MALAN: OK. Belə ki, indi biz cür olacaq bu müxtəlif hemoroid daxil. Belə ki, C ilə, sonra D, və E, və F, və G və H, və I. Nice. J, K. Və sonra, bu xovlu altüst, lakin OK. Sure. Biz bəzi küncləri kəsilmiş bilər. OLDU. Və sonra biz W, X, Y, Z. lazımdır CAROLINE: Bəli. DAVID J. MALAN: Əla. Belə ki, böyük bir təşəkkür Bu çeşidlənməsi üçün Caroline. [Təzahürat] Təşəkkür edirəm. Çox sağ olun. Belə ki, indi bir an nəzərdən keçirək necə Caroline bunu haqqında getdi, və məhz biz necə to-- bacardıq biz ki, həll edə bildik problem zaman biz yalnız idi təsadüfi giriş bütün dəstə verilir. Bəli, orada kimi görünür bir sistemin bir az idi? Right. Əvvəllər məktublar Belə ki, əlifbası ilə, o, idi sol qoyaraq, və əlifbası sonra məktublar, O, sağ verilməsi oldu. Və tezliklə o tapıldı bəzi proksimal məktublar, olanları ki, bir-birinə doğru növbəti getmək o üçün bu qoymaq olardı. Və belə ki, biz cür bu kiçik idi meydana gələn sorted vəsaitlərin hemoroid. Və belə ki, kifayət qədər kimi nə bizim ən insanlar olardı. Biz sort vasitəsilə elemek ki, və biz növ bir mexanizm var ediyorum. Amma bu yazmaq üçün çətin ola bilər aşağı bir düstur özlüyündə da. Bu daha üzvi bir az daha hiss etdim. Belə ki, görək, əgər biz bound indi bilərsiniz az giriş ilə problem. Əvəzində 26, edək çox az bir şey yalnız arxasında, yeddi, demək Bu qapılar, belə danışmaq. Yalnız yeddi ədəd var? İndi məqsəd əgər əl bir dəyər tapmaq üçün, görmək necə səmərəli imkan biz bunu haqqında getmək bilər. Və biz indi əgər nin görək bir ədəd tətbiq başlamaq, və ya bəzi düsturlar olan təsvir etmək Bizim telefon kitab səmərəliliyi alqoritm, bizim imtahan kitab alqoritm və ümumiyyətlə, məlumat tapmaq. Bu Belə ki, mənə irəli gedək və sensor ekran üzərində burada, bir web browser qablaşdırılmış məhz bu yeddi qapılar. Və biz bir başqa almaq bilər burada gəlib könüllü, Mən burada bu eyni qapılarını qoymaq etdik. Quick könüllü. Bu one-- demoları gedir daha sürətli və daha sürətli indi. Aşağı gəlir. Sənin adın nədir? TREVOR: Trevor. DAVID J. MALAN: Trevor? Bütün hüquqlar, Trevor, aşağı gəlir. Belə ki, Trevor burada könüllü edib oxşar problem, lakin ki, bir əhatə dairəsi dar ki, olacaq imkan İndi rəsmiləşdirmək üçün cəhd bu rəqəmlər çeşidlənməsi prosesi. Belə ki, Trevor, siz cavab gözəl. Belə ki, burada bir sıra belə edir yeddi qapı bir siyahısını danışmaq. Durmayın, bizə sayı 50 tapmaq. Və sonra fakt sonra, Siz onu aşkar necə bizə. Bütün sağ be-- lazımdır. Bəli, burada biridir? UH-oh. OLDU. Siz ki, bir tıklayan. Yaxşı. Və yaxşı. İndi ki, bir tıklayan. Və mənə mikrofon verək, ki, yalnız bir anda var. Durmayın basın Siz niyyətində növbəti qapı. Bəli, yaxşı. TREVOR: Mən qapını unclick edə bilərəmmi? DAVID J. MALAN: Xeyr, siz unclick bilməz. TREVOR: OK. Bu bir. DAVID J. MALAN: Harada getmək istəyirsiniz? Hansı? TREVOR: Ki, bir. DAVID J. MALAN: Xeyr TREVOR: OK. Bu bir. DAVID J. MALAN: Bəli. Ki, yaxşı idi. Oldu. Belə ki, alqoritm nə idi və ya Bu, Trevor bunu qaydası? TREVOR: Mən yalnız yolu ilə getdi qapı qədər bir 50 tapdı. DAVID J. MALAN: OK. Əla alqoritmi. Belə ki, gözəl var. Əslində, mən aşkar çünki nə bu iki qapı arxasında, nə biz ki, burada tapa bilərsiniz biz yalnız təsadüfi giriş var. Belə ki, kimi həqiqətən idi Siz əldə edə bilər kimi yaxşı. Və əslində, siz daha yaxşı oldu exhaustively bütün array axtarış, bu, həqiqətən olardı, çünki uğursuz Nömrəni hit əgər Son qapıda 50. Amma nə əvəzinə biz əgər bir ehtimal verdi. Sort bütün hərhalda ətrafında bu qapılar, ki, var ədəd bu dəfə sıralanır, lakin bu dəfə həqiqətən a, bu dəfə different-- Bu, həqiqətən, sizin üçün sıralanır. Əl İndi qol sayı 50 təşkil edir. TREVOR: OK. DAVID J. MALAN: nədir olacaq sizin alqoritm? TREVOR: bu Bəli, əgər sıralanır, ya gedir ən böyük əgər ən böyük be-- üçün, enən, ilk biri olacaq və ya əks halda, Bu son bir olacaq. Mən yalnız bu qapı kran və lazımdır sonra yalnız son qapını dokunun. DAVID J. MALAN: Əla. Oldu. Beləliklə, biz sayı 50 tapdı. Belə ki, tezliklə bilirdi kimi onlar sıralanır edilmişdir, biz Bu ehtimal leverage edə bildik. Belə ki, onlar kimi çox istəyirik telefon kitab misal. Kimi tezliklə, hətta kimi bu kimi kiçik problem, Sizin giriş pre-sıralanır, biz həqiqətən arguably dəyər tapmaq daha səmərəli. Mən sizə bu idi əgər demək etməyib kiçik böyük kiçik, ya böyük sıralanır və buna çox ağlabatan idi bir sonunda və ya digər başlamaq üçün həqiqətən ki, hədəf dəyər tapmaq üçün. Belə ki, həm də Trevor üçün təşəkkür edirəm. Mən gözəl işlər propose-- lazımdır. Biz həqiqətən bir az klip var , CS50 bizim sevimli anları arasında qovuşdurmağımız bəzən bu demoları olduqca planına uyğun olaraq getmək yoxdur. Həqiqətən indi, mən yanlış interface qədər çıxardı olan sensor istifadə etmək. Belə ki, mənim günahım var idi. Belə ki, bu edəcək kimi gələn il clip Mən öz ekran tıklayarak niyə üçün. Amma tez nəzər salaq Ötən il baş verən nə daha gündəmə gəldi Jay, ilə burada Trevor kimi, könüllü və bu qısa clip, siz görürsünüz Bu eyni demo kifayət qədər necə öyrəndim eyni dərsləri göstərir. [Video playback] Mən bunu istəyirəm -Bütün indi Mənim üçün tapmaq və bizim üçün, həqiqətən, sayı 50 bir zaman bir addım. -Bu Sayı 50? -Bu Sayı 50. Və nə aşkar edə bilərsiniz Bu qapılar hər arxasında sadəcə bir barmaq ilə toxunan. Lənət olsun. [Gülür] [END playback] DAVID J. MALAN: Belə ki, çox yaxşı keçdi. Həmin çeşidlənməmiş qapı idi. Və Jay, əlbəttə, çox tez bütün tapdı. Trevor çox daha yaxşı bir iş idi bir öğrenmeye hevesli an baxımından, bu il, danışmaq Artıq alaraq tapmaq üçün. Əlbəttə, biz verdi Jay ikinci şans, vasitəsi biz qapıları sıralanır biz Trevor üçün etdiyiniz kimi, və Trevor super bu dəfə idi. Amma Jay yarısı kimi tez bunu etdi. [Video playback] -Bu Məqsədi indi də edir Bizə sayı 50 tapmaq lakin algorithmically bunu, və bu barədə olacaq necə bizə. -OLDU. Siz tapmaq Əgər -Və, siz film saxlamaq. Siz tapa deyilsə, siz onu geri vermək. Man. -Oh! - [Işitilemez] OK. Beləliklə, mən başa yoxlamaq üçün gedirəm Oh there's-- əgər müəyyən etmək üçün ilk. [Alqış] [END playback] DAVID J. MALAN: OK. Belə aydın qapılarını çeşidlənməsi daha çox səmərəliliyi gətirib çıxarır. Belə ki, iki dəfə sürətli Mən demək nə. Və belə Jay xoşbəxt iki dəfə var. O, həmçinin bildirib ki, son uğurlu var il, Mən Blu-ray disklər sifariş həqiqətən vermək. Bu il kədərləndim, biz Trevor eyni yox idi. Amma daha yaxşı hələ bir neçə il geri idi. Və bəzi bu bilirik bilər O CS50 idi fellow, Sean, dəqiq ilə etiraz edildi Eyni problem, SD olsa da, tezliklə geri gün görəcəksiniz kimi. Və yalnız vermədi ki, tapa bilərsiniz O, Jay bir az uzun Trevor bir az artıq idi həqiqətən bu gözəl fürsət demək olar ki, hər kəs məşğul Sıxlıq bir la Qiymət təşviq hüququ Onu biz axtardığımız da sayı tapmaq üçün. Edək. tez göz atın. [Video playback] -OLDU. Belə ki, burada Task, Sean, belədir. Mən bu arxasında gizli Qapı sayı yeddi. Lakin bu qapı bəzi üz tucked eləcə də digər mənfi nömrələri var. Və məqsədi hesab edir ədəd bu top sıra yalnız bir sıra, və ya kimi kağız parçaları ardıcıllığı onların arxasında nömrələri ilə. Sizin məqsədi yalnız üst istifadə edərək, array Burada Mənə sayı yeddi tapa bilərsiniz. Və biz sonra tənqid gedir siz bunu haqqında getmək necə. -Oldu. Bizə sayı yeddi edin tap. Yox. Beş, 19, 13. [Gülür] Bu oyun sual deyil. Biri. [Gülür] Bu nöqtədə, sizin hesab çox deyil yaxşı, belə ki, siz də davam edə bilər. Üç. [Gülür] Davam et. Açığı, mən kömək lakin təəccüb bilməz nə hətta Belə ki, haqqında düşünür istəyirsinizsə [Gülür] Yalnız top satır, belə Üç sol var. Belə ki, mənə yeddi tapa bilərsiniz. [Gülür] 17. Seven. [Alqış] Oldu. [END playback] DAVID J. MALAN: Belə ki, biz bilər Bu gün boyu baxın. Və əlbəttə, bəzi Bu il demoları bəlkə indi növbəti sona çatacaq il video həmçinin. Belə ki, indi həqiqətən edək alqoritmlər diqqət Biz əgər burada bax İndi rəsmiləşdirmək başlamaq Biz data alınması haqqında getmək necə Bu dövlət sıralanır ki, belə ki, son nəticədə, biz, həqiqətən, bilərsiniz daha səmərəli axtarış. Və biz olacaq, baxmayaraq ki, kifayət qədər kiçik data dəstləri istifadə etmək, səkkiz ədəd biz kimi board burada var, nəticədə bu eyni fikir müraciət edə bilər 1000 giriş, bir milyon giriş, 4 milyard giriş, alqoritmlər, çünki əsaslı eyni olacaq. Və belə ki, bu, bizim son könüllü gün üçün fürsət, lakin bəlkə də ən cəlb biri, olan biz səkkiz könüllülər lazımdır gəlmək və vasitəsilə bizə gəzmək çeşidlənməsi prosesi nə tezliklə olacaq Bu musiqi ola burada dayanır. Mənə burada geri başlamaq edək. Belə ki, turquoise-- yaşıl bir o? Siz törətməkdə edirsiniz? Iki. Aşağı gəlir. OLDU. Üç. Dörd. Beş OK me-- edək. Sizin dost tərəfindən irəli edirik. Altı, yeddi, səkkiz. Qədər gəlib. Oldu. Çox sağ ol. Qədər gəlib. Qədər gəlib. Oldu. Beləliklə, biz burada bu nə daha yöndəmsiz olanları arasında, Bu çünki siz ki, yumor tələb edəcək zaman yalnız bir az mənə. Siz bir nömrəli olacaq. Sənin adın nədir? ANNAN: Annan. DAVID J. MALAN: Annan. David. Sənin adın nədir? JOSEPH: Joseph. DAVID J. MALAN: Joseph, Siz sayı iki. SERENA: Serena, sayı üç. Stefan, sayı dörd. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, sayı beş. [Işitilemez] DAVID J. MALAN: [işitilemez]. David sayı altı. MATT: Matt. DAVID J. MALAN: Matt sayı yeddi. Və? WAVERLY: Waverly. DAVID J. MALAN: Waverly sayı səkkiz. Oldu. Əgər whoops could--. Siz əgər, kimi orada ilk problem, səkkiz musiqi stendləri var Burada tamaşaçı qarşısında duran. Siz nömrələri qoymaq bilər Bu musiqi, belə bir şəkildə dayanır onlar ilə sıralamaq ki lövhədə eyni nömrələri. Belə ki, özünüzü ilə kimi baxmaq Bu musiqi nömrələri qoyulması burada dayanır. Əla günə qədər. Əla. OLDU. Belə ki, indi biz xahiş olacaq bir neçə müxtəlif yollarla sual. Necə ki, biz çeşidlənməsi haqqında getmək olar Burada bu millət up? Biz bir neçə yanaşma idi, çünki əvvəllər, biz vasitəsi idi cür iki müxtəlif buketler edilməsi. Və sonra biz ümumiyyətlə idi birlikdə şeyi durub. Kimi tezliklə biz iki ədəd gördüm ki, birlikdə məxsus biz onlara birlikdə qoymaq. Birlikdə məxsusdur iki məktubu. Amma əgər görək biz Bu rəsmiləşdirilməsi bilməz, biz nəticədə var ki, Siz bəzi yalançı indeksi, olan bu problemləri həll edə bilər. Belə ki, indi mən arıyorum Burada bu nömrələri. Mən səhvlər bütün dəstə görmək. Nəhayət, mən bir istəyirəm sol və sağ səkkiz. Və mən baxıram Bu iki, dörd və iki. Və problem təbii ki, nə var? Bəli. Belə ki. İki açıq-aydın əvvəl gəlir dörd, belə ki, nə bilirik? Mənə ilk bir görməmiş yanaşma edək, çox kimi problem siz əgər Siz geri əgər one-- müəyyən Problem Set One Standard Edition, Mən yalnız yerli problem həll ki, mənə qarşısında sağ burada mənə rəhbərlik harada görmək. OLDU. Belə ki, iki və dörd, mənə gedək irəli və yalnız iki dəyişdirmək. Fiziki hərəkət edə bilər Özünüzü və kağız, Mən kazanılmış görünür Daha yaxşı vəziyyətdə siyahısı. İndi, onlar yaxşı deyilik. Mən hərəkət gedirəm dörd və altı, yaxşı görünür. Bir problem. Altı və səkkiz, OK. Səkkiz və bir başqa problem. Səkkiz biri haqqında doğru nə çünki? One səkkiz əvvəl gəlir və biz nə etməliyik? Nin bu iki dəyişdirmək edək. Bir və səkkiz. Və indi mən davam gedirəm. Mən irəli axtarır saxlamaq üçün gedirəm. Və nə görmək edək. Səkkiz və üç, Əlbəttə ki, qaydada həyata. Mübadilə edək. Əlbəttə səkkiz yeddi. Qaydada həyata. Mübadilə edək. Səkkiz və beş, əlbəttə, imkan mübadilə. Oldu. Siyahı çeşidlənir. bəli? OK, açıq-aydın deyil. Amma bu doğru bir az daha yaxşıdır? Baş bildiriş çünki. Hər dəfə biz mübadilə, həyata kiçik sayı cür ki, yol percolated, və böyük bir sayı Bu şəkildə percolated, və ya biz lazımdır üçün bubbled deyərək başlamaq sol və ya sağ bubbled. İndi, çünki kifayət qədər deyil yaxşı bir sıra bilər bir spot köçürülüb irəli, və ya pis, bir sıra ola bilər Daha bir ləkə köçürülüb. Belə ki, nə bu cür bilirik bu günə qədər olduqca yaxşı işləyib. Mənə yalnız bir daha cəhd edək. Iki və dörd, onlar OK istəyirik. Dörd və altı, onlar OK istəyirik. Six və bir qaydada həyata. Belə ki, siz iki dəyişdirmək imkan verir. İndi problem Qeyd yaxşı yenə bir az almaq üçün başlayır. Six və üç qaydada həyata. Nin iki dəyişdirmək edək. Altı və yeddi, yaxşı deyilik. Seven və beş, əlbəttə, qaydada həyata. Məqsədilə yeddi və səkkiz. Və indi mən lazımdır daha bu bir neçə dəfə. Və əslində, özünüz üçün hesab edirəm ki, bəlkə neçə dəfə maksimum Mən geri və irəli getmək üçün ola bilər? Biz geri gəlmək lazımdır. Belə ki, iki və dörd hələ OK var. Dörd və bir Xeyr. Belə ki, svop imkan verir. Və yenə, vizual qeyd bir bubbling növüdür bu olmalıdır sol, üçün. Dörd və üç svop. Dörd və altı. Six və beş svop. Altı və yeddi. Yeddi, səkkiz yaxşı. Yaxşı. Biz daha yaxşı əldə edirik. Belə ki, görək. İndi biz iki və bir var. Əlbəttə ki, dəyişdirmək. Iki və üç, üç və dörd, dörd və beş, altı və yeddi, yeddi və səkkiz. Yaxşı. Və nə bilirik? Mən orada bir dəyişiklik Çünki Mənə bir ağlı başında olma çek edək. Mənə bütün yol getmək edək əvvəlinə geri. OLDU. One, yup two--, görmək? Bir şey yanlış idi. Üç, dörd, beş, altı, yeddi, səkkiz. Və bu son pass var mənim indi rahat Bu çeşidlənir iddia edən? OLDU. Görmə, ki, tamamilə doğrudur. Lakin funksional, nə də yalnız baş idi imkan verir ki, ötən pass bu siyahı həqiqətən olduğunu təsdiq etmək sıralanır? Mən nə və ya bu son pass etmədi? Auditoriya: heç bir dəyişiklik var idi. DAVID J. MALAN: Sorry? Auditoriya: heç bir dəyişiklik. DAVID J. MALAN: heç bir dəyişiklik var idi. Belə ki, mənə axmaq olardı yenidən eyni alqoritm nə Mən heç bir etməyib əgər ilk dəfə dəyişir. Dövlət dəyişməyib. Şübhəsiz ki, mən etmək niyyətində deyiləm Hər hansı bir ikinci dəfə dəyişir. Belə ki, indi təhlükəsiz demək siyahısı çeşidlənir. And olsun ki, bu indi bir şey ki, biz ümumiyyətlə lazımdır zəng bubble sort, vasitəsi pairwise, Siz yenə səhvləri düzəltmək və yenidən və yenidən, və geri və irəli gedən saxlamaq, və geri və irəli, sizin qədər belə svopları, edən nöqtədə Mən, evet, əmin ola bilərsiniz səhvlər bütün təyinat tamamladı. Nin yenidən qurmaq və bir yanaşma cəhd edək. Sizlərin geri getmək bilər üçün siz bir an əvvəl idi bu kimi baxdı. İndi bir yanaşma götürək daha imtahan kitab kimi kiçik, vasitəsi biz daim idi əlifbası məktub seçilməsi biz növ istəyirdi ki növbəti ilə məşğul. Bəlkə bir yüksək məktub idi, A, və ya aşağı məktub Z. kimi Belə ki, hər kəs geri bu qaydada var. İndi mənə bunu bildirin. Mən Mən bilirəm görmək edək Burada səkkiz ədəd. Mən irəli getmək üçün gedirəm və yalnız qəsdən seçin kiçik elementləri. Sağ? Bu da asan görünür. Niyə kiçik tapmıram bu məxsusdur harada element, qoyun sonra növbəti kiçik element almaq qoymaq Bu məxsusdur və yalnız təkrar edir. , Daxilən Çünki çox işləməlidir. Belə ki, dörd ki, olduqca az sayda var. Mən bu harada yadda gedirəm. Bir dəqiqə gözlə. İki kiçik. Mənə indi harada yadda edək ki, iki və dörd unutmayın. Biz sonra ilə məşğul olacaq. Six, mən maraqlı deyiləm. Səkkiz, mən maraqlı deyiləm. One mənim yeni kiçik sayı. Mən bir harada yadda gedirəm. Üç, maraqlı deyil. Seven, maraqlı deyil. Beş, maraqlı deyil. Off düşən olmadan belə mərhələ bu il, Mən sayı işğalçı gedirəm one-- və adı yenə nə idi? ANNAN: Annan. DAVID J. MALAN: Annan. Və mənə qoşula bilər əgər siyahının başında, aid harada sizi edək. Unfortunately-- adı nədir? STEFAN: Stefan. DAVID J. MALAN: Stefan yol var. Stefan bu həll əvvəl Belə ki, problem, biz nə etməliyik? Biz Stefan ilə nə etməliyəm? Auditoriya: [işitilemez]. DAVID J. MALAN: OK. Belə ki, biz bunu edə bilər. Biz növ Stefan və bilər onun Dörd, və yalnız bir dəyişən qoyun və bu keçirilməsi zaman bəzi məbləği, bununla da bir nömrəli otaq edilməsi. Və pis deyil. Niyə yoxdur, təklif edə bilər biz yalnız burada Stefan qoymaq? Niyə bu bir pozan bilər fikir başladığımız Keçən həftə son dəfə söhbət? Evet? Auditoriya: [işitilemez]. DAVID J. MALAN: bunun üçün heç bir index var. Bir kimi, həqiqətən, bu düşünüyorsanız array, bu mənfi kimi deyil, belə ki, heç yaddaş həqiqətən var Burada bu həqiqətən bir sıra varsa, kimi biz mühazirə ötən həftə elan etdi. Beləliklə, biz bu lazım deyil. Biz dəyişən onu saxlamaq bilər. Yoxsa nə? Mən başqası gəlir eşitdim. Biz Stefan ilə başqa nə edə bilər? Niyə biz yalnız onu köçürmək deyil və bir nömrəli olduğu onu qoydu. Siz orada getmək istəyirəm Belə ki, əgər. Həqiqətən, bu bir olduqca yaxşı həlli. İndi, bir tərəfdən, mən cür var pis problemi etdi. Dörd uzaq indi bu olmalıdır harada. Bu yarım doğru olmalıdır. Amma nə bilirik? Pis luck ola bilərdi. Bəlkə sayı səkkiz burada idi. Belə ki, bəlkə biz lucky kazanılmış, və sonunda səkkiz yaxın basdı. Günün sonunda Belə ki, bu cür bütün orta edir. Biz dörd qayğı ehtiyac yoxdur. İndi qayğı bütün kiçik element seçilməsi. Və indi mən nə gedirəm bir nömrəli unuda nə daimi, mən bilirəm, çünki arxamda siyahısı indi çeşidlənir. Belə ki, mənim siyahısı əvvəllər ölçüsü səkkiz idi. İndi, bu, ölçüsü yeddi var. Belə ki, mənim problem olur xətti olsa da, kiçik. Belə ki, indi mən seçmək gedirəm Cari kiçik element, iki. Altı, səkkiz, dörd, üç, yeddi, beş. Ki, kiçik element idi. Belə ki, nə mən with-- gedirəm adı yenidən nə idi? JOSEPH: Joseph. DAVID J. MALAN: Joseph? Biz yer Yusifi tərk etmək olacaq. İndi iddia gedirəm Bu uşaqlar yaxşı are-- ki, Mən bilirəm ki, bu iki artıq sıralanır. İndi diqqət edək siyahısı qalan. Six cari kiçik deyil. Səkkiz böyükdür. Dörd hazırda kiçik deyil. Üç hazırda kiçik deyil. Və indi, mən üç seçmək üçün gedirəm olan adınız yenidən nə is--? SERENA: Serena. DAVID J. MALAN: Serena, siz ola bilər, əgər nömrənizi və svop with-- qamarlamaq KALSANG: Kalsang. DAVID J. MALAN: Kalsang. Geri gəlin, və biz istəyirik bu iki dəyişdirmək üçün gedir. İndi, autopilot bu qoymaq bildirin. Mən getmək və uşaqlar onu tərk gedirəm növbəti kiçik elementləri seçin. Dun, dun, dun, dun. Number dörd, siz nə etməliyəm? Əla. İndi mən başqa keçid etmək üçün gedirəm. Dun, dun, dun, dun. Mən beş Növbəti kiçik görmək. İndi bir keçid almaq gedirəm. Dun, dun, dun, dun. Six kiçik deyil. Yaxşı. Seven kiçik deyil. Heç bir dəyişiklik. Səkkiz kiçik deyil. Done. Belə ki, nə biz yalnız iteratively tərəfindən etdik digər sonra bir element seçilməsi biz istəyirik bir şey həyata ki, seçim sort kimi rəsmiləşdirmək üçün gedir. Və hətta bəlkə var izah etmək sadə, sözün bütün siz ki, yalnız saxlamaq etmək istəyirəm siyahısını geri və irəli gedir seçilməsi növbəti kiçik element, Bitirdiğinizde qədər. Belə ki, bəlkə də, daha asan var daxilən, son daha. Son bir bir cəhd edək. Sizlərin özünüzü yenidən bilər Aşağıdakı vəzifələrin daxil bir final dəfə, görək, əgər biz bilməz indi başqa bir yanaşma rəsmiləşdirilməsi. Əslində, ki kimsə orada təklif etmək istəyirəm biz bunu necə haqqında başqa getmək bilər? Buzzwords və ya arıtlamaq tossing Without artıq məlumdur cavab, yalnız daxilən, biz nə edə bilər? Auditoriya: [işitilemez]. DAVID J. MALAN: Bəli. Belə ki, orada bəzi böyük intuisiya var. Yaxşı şeylər bu günə qədər baş görünür biz bölmək kompüter və bölünməsi problemi fəth Bu yarım yarım və yarısında. Və belə ki, həqiqətən, biz bunu başlamaq bilər. Və əslində, ki, olmaq, biz olacaq olacaq hələ bizim ən yaxşı çözümleri biri oldu. Amma uzun əvvəl geri gəlsin. Əslində, biz nə olacaq bir az sonra bu həftə ki. Bu həll etmək üçün, biz başqa nə edə bilər? Belə ki, burada hər kəs edir zahirən təsadüfi sifariş. Siz nə bilirik? Əksinə geri və irəli getmək çox, geri və irəli, geri və irəli Hər dəfə bu kimi hiss Mən gəzinti bir çox edirəm. Niyə sadəcə başlamaq deyil siyahının başında, və yalnız bu məxsusdur dörd qoymaq? Mənə an üçün fərz edək ki, mənim siyahısı yalnız bu ilk element var. Dörd vaxt bu anda çeşidlənir, əgər mən qayğı bütün hər şey burada? Bu növ trivially doğru, doğru? Bir sıra ehtiva siyahısı, və kimi ki, sayı dörd açıq-aydın çeşidlənir. Mənə yalnız müəyyən edək Bu siyahı çeşidlənir. Amma indi bu siyahıda qalan var. Belə ki, indi mən iki qarşılaşa. Harada açıq-aydın iki deyil dörd ilə bağlı aid? Dörd əvvəl. Mən burada nə edə bilər? Sizin adınız yenidən nədir? JOSEPH: Joseph. DAVID J. MALAN: Joseph, Siz geri addım bilər Sizin sıra yalnız bir an üçün. Və Stefan indi nə etməliyəm? Burada artıq Stefan keçmək edək. İndi Yusif bura gəlib bildirin. İndi mənə iddia edək Burada hər şey çeşidlənir. Belə ki, oxşar nəticə, lakin əsaslı müxtəlif yanaşma. Mən hətta orada nə baxdı yoxdur. Mən yalnız elementləri alaraq saxlamaq Onlar mənə təqdim etdiyiniz kimi, və onlara ilə məşğul. Belə ki, indi mən sayı altı görürük. Harada sayı altı məxsusdur? Biz iki, dörd, altı var. Məhz o, indi olduğu. Belə ki, indi ki, tək buraxsınlar, və siyahısı bu hissəsi olduğunu iddia İndi çeşidlənir. Belə ki, bu əsaslı hiss ki, müxtəlif mən yalnız deyiləm Burada siyahısı vasitəsilə hərəkət xətti, və mən heç vaxt geri misli edirəm. Bəli. Oldu. Belə ki, səkkiz, burada aid edirsiniz? Burada. Mükəmməldir. Belə ki, indi, bir. UH-oh. Bu kimi bu hiss bahalı olacaq. İndi əvvəlki alqoritm, Mən yalnız insanların dəyişdirildikdə. Belə ki, mən ona bütün yol qoymaq bilər başlanğıcı, lakin sonra Yusifi köçürülüb. Amma indi, Yusif hərəkət əgər nə yanlış olacaq? İndi sort I var undone-- var irəli və sonra bir addım bir addım geri, indi Joseph qaydada həyata olardı. Belə ki, bunu edək. Siz bir nömrəli almaq bilər və yalnız bir an üçün geri addım. Necə ki, biz put-- bilər nə adı yenidən idi? ANNAN: Annan. DAVID J. MALAN: yerdə Annan? Nə ilə bağlı nə etmək lazımdır iki, dörd, altı və səkkiz? Onlar bütün keçmək lazımdır. Səkkiz Belə ki keçmək istəyirəm , sonra altı, sonra dörd, sonra iki. Və sonra Annan, əgər istədiyiniz yaxşı, bura gəlib istəyirəm. Amma burada, biz yalnız var belə bir əvəzlər ödədi alqoritm fərqli bir nöqtədə. Seçimi ilə son dəfə isə sort və hətta bubble sort, Mən geri gedirəm və irəli, geri və irəli, əlbəttə ki, up əlavə olunur vaxt müdrik və sanki stepwise. Durub sort, ilk bu kimi nəzər görünür super asan, ki, mən yalnız deyiləm yavaş, artan tərəqqi, amma geri və irəli, bu fikrində deyiləm. Amma kimsə həqiqətən əgər üçün, bildiriş həyata Mən yalnız nə idi bütün işləri. Mən siyahısı yarım hərəkət idi yalnız bir nömrəli üçün otaq etmək. Belə ki, eyni məbləği iş indiyədək onu iş yalnız bir növ, hiss edir. Davam edək. Belə ki, indi hər kəs bilirik ki, bir və səkkiz arasında sıralanır. Burada sayı üç var. Siz almaq istəyirəm əgər sayı üç, geri bir addım. Və nə uşaqlar nə etmək lazımdır? Yep. Belə ki, başqa bir, iki, üç addımlar var. Yalnız başa zaman üç dənə Mənə üç indi uyğun ki. Nəhayət, yeddi. Nin irəli getmək və edək Bir addım geri almaq. Bu yalnız bizim başa gedir bir dəfə vahid, lakin OK. İndi, beş gedir bir az daha bahalı ola bilər. Siz geri addım istəyirsinizsə. Biz səkkiz hərəkət etmək lazımdır və yeddi və altı. Və sonra hər kəs indi çeşidlənir. Belə ki, burada bizim könüllü böyük əməyi. Çox sağ ol. [Alqış] Bütün təşəkkür edirik. Bütün təşəkkür edirik. Belə ki, indi yalnız necə edək ki, bütün bahalı idi. Bəlkə nəzərdən keçirək bu sadə bubble sort. Mən yalnız çünki sadə demək Siz sadəcə görməmiş həll edə bilər burada pairwise problemi həll. Pairwise problem Fix burada, təkrar və yenə bir çox təkrar sizin kimi dəfə həqiqətən lazımdır. Belə ki, çıxır ki, bir bubble növ ilə, yaxşı, neçə addımlar Mən etmək var ki, alqoritm ilk pass? Mən, bu bir see-- imkan take-- bilər iki, üç, dörd, beş, altı, yeddi. Və burada səkkiz elementləri var. Belə ki, n minus 1 addımlar kimi siyahının başında almaq siyahısı sonuna. Amma seçim növ ilə, mən ki, xatırlayıram təkrar elementləri seçilməsi və daha kiçik var Mən yerdə qoyulması alıram lakin sonra mən deyiləm daha arxamda axtarır. Mən bir az daha aydın hesab edirəm sonra ilk dəfə ki, mən bilər bütün n mənfi 1 addımlar var kiçik element tapmaq üçün. Sonra mən yer onları qoymaq və mən əvvəllər burada idi kim köçürmək. Lakin mən yoxdur Bu element axtarır saxlamaq, Mən bilirəm, çünki bu Artıq kiçik. Belə ki, indi mən yalnız yeddi baxmaq olar elementləri, sonra altı elementləri, sonra beş elementləri, dörd elementləri. Və belə riyazi, n, əgər elementləri və ya nömrələri sayı biz ilə başladı ki, siz təsəvvür edə bilərsiniz Bu n minus 1 kimi eyni olduğunu, plus n minus 2 addımlar, plus n minus 3 addımlar, plus n minus 4 addımlar, bütün yol aşağı yalnız bir addım. Mən keçən şəxs deyiləm. Və bir çox Xatırladaq ki, əgər kitab və ya riyaziyyat kitab stats həmin düsturlar var geri Hardcover və ya onların ön, bu seriyası çıxır ki, daha çox sadəcə ifadə edilə bilər n dəfə n kimi minus 2-dən 1. Ki, əgər bu gözəl Fikrinizi önündə. Amma bu həqiqətən doğrudur. Ki, yazılı bir sadə yoludur. Və sonra hesab edirəm ki, əgər geri grade məktəbə, Yalnız vurulması başlamaq zaman şeyi, əlbəttə, bu, yalnız n kvadrat minus n 2 bölünür. I etdiyiniz bütün genişləndirmək deyil orada ifadələr. Və belə ki, bu yeniden imkan fərqli bir az. Ki, n 2 minus n / 2 bölünür kvadrat. Belə ki, yenə, mən yalnız cür tətbiq edirəm bəzi hesab var qaydaları. Amma indi görürsünüz ki, ən böyük müddətli Bu ifadə, belə ki, danışmaq, n kvadrat edir. Belə ki, bəli, bu n kvadrat var 2, minus n / 2 bölünür. Amma ümumiyyətlə n, əgər böyük dəyəri olacaq, Hesab edirəm ki, n kvadrat iddia gidiyorum dominant amil olacaq. Bu, sadəcə olacaq böyük töhfə n / 2-dən çox addımlar sayı. Belə ki, bu nə deməkdir? Hətta bir sadə misal cəhd edək riyaziyyat bir az böyük olur baxmayaraq. Belə ki, biz 1 milyon nəfər idi güman mərhələ, və ya 1 milyon şeyi biz düzmək istəyirəm ki. Bir milyon plug edək məhz formula daxil Bu ümumi nə qədər çox addımlar görmək demək istifadə edərək, bir milyon elementləri düzmək üçün, seçim sort. Beləliklə, biz əvvəlki kimi eyni formula var ediyorum. Mən almaq, belə ki, bir milyon plug istədiyiniz bir milyon, 2 bölünür kvadrat minus bir milyon 2 bölünür. Mən əvvəlcədən ki, riyaziyyat nə varsa Burada biz 500 milyard minus 500,000 hansı , 499.999.500.000 bizə verir olan olduqca darn böyük. Əslində, indi müqayisə etsək 499 milyard 999 milyon, Orijinal dəyəri qarşı 500,000, 500 milyard, belə lənətləmək yaxın. Sağ? n 2 verir bölünür kvadrat us-- daha doğrusu, N 2 bölünür kvadrat Bizə 500 milyard verdi. Bu olduqca darn yaxın 499.999.500.000 üçün, off 500,000 çıxarılaraq demək deyil ki, və ya ümumiyyətlə, off subtracting n həqiqətən, bir böyük kvadrat. Bu edir n kvadrat ədəd həqiqətən sürətli bitir. İndi, bu, yalnız vacibdir insofar biz kimi, kompüter alimləri, ümumiyyətlə qədər qayğı niyyətində deyil bu düsturlar nüanslar haqqında və dəqiq nə dəqiq cavab var. Biz yalnız ki, nə qayğı? Günün sonunda, bu formula kvadrat n sifarişi edir. Bəli, biz orada 2 ayırıcı edirik. Bəli, biz off n minus 2 subtracting edirik. Lakin günün sonunda, müddətli ki, həqiqətən bizi incidir və bizə xərcləri addımlar bir çox kvadrat anlayışdır. Və nə bir kompüter alim ümumiyyətlə nə gedir o bütün ignore edir kiçik sifariş şərtləri, və yalnız bir baxmaq dəyəri ən töhfəsini verir. Bu, çünki biz, gözəl İndi daha çox ümumiliyinə danışmaq alqoritmlər haqqında və onları müqayisə edə bilərsiniz. Mən ki, fakt Bu O istifadə qəsdən edir. Mən qaydada deyəndə mən xüsusi edirəm bir şey toxunaraq böyük O. Və böyük O çağırıb bir notation edir ki, bir kompüter alim təsvir etmək üçün istifadə yuxarı bir şey borcludur. Bir alqoritm ki, əgər belə n kvadrat böyük O deyil, Mən təklif yalnız bir an əvvəl o deməkdir ki ki, onun çalışan baxımından vaxt və ya onun səmərəliliyi, Bu qaydada edir n kvadrat addımlar. Bəlkə az, bəlkə daha çox. Amma bu n sifarişi kvadrat var. Və üst bound var. Bu olmaq niyyətində deyil daha ağrılı. Bu n Cubed olacaq, ya 2 deyil n, və ya daha böyük bir şey. Bu bound yuxarı deyil nə ki, dəyəri. Belə ki, edək ki, verilmiş Yalnız bir neçə nümunəni nəzərdən keçirək. Və bu, yalnız məhdud siyahısı çox ümumi çalışan dəfə üçün nəzərdə alqoritmlər üçün biz bəzi şeyləri illüstrativ artıq görünür. Məsələn, işi belə seçim sort, mən burada nə iddia edirəm seleksiya sort var çalışan time n qaydası kvadrat edir. Ən pis halda, mən gedirəm burada təsadüfi ədəd bir bütün dəstə. Və biz riyazi gördüm, Mən gəzinti saxlamaq əgər siyahısını vasitəsilə siyahısı, kiçik növbəti seçilməsi təkrar element I əgər həqiqətən addımlar bütün yazmaq Mən formulaically təklif kimi mən alıram əvvəl, kvadrat n sifarişi var Mən alıram addımlar. Və bu bubble çıxır sort və durub sort ən pis halda kimi yavaş. Məsələn, hesab, durub sort, biz ilə məşğul son alqoritm, ki, bizi element baxmaq idi Bu aid olduğu və sonra daxil. Və sonra biz növbəti element baxdı, Bu aid olduğu və daxil. Belə ki, mümkün olan ən yaxşı ssenari hesab edir. Mən könüllü sıralamaq idi düşünək sanki bu kimi səkkiz vasitəsilə bir, artıq sıralanır. Durub sort neçə addımlar səkkiz nəfər düzmək üçün etmək niyyətindədir, Onlar səhnədə gəlmək əgər bu kimi axtarır? Səkkiz nəfər artıq sıralanır. Mən durub növ istifadə edin. Alqoritmlərin ki, ötən. Yaxşı, real sürətli reenact bildirin. Mən burada başlamaq əgər Belə ki, mən bir bax. Harada bir məxsusdur? Bu burada məxsusdur. Mən iki oldu. Harada iki məxsusdur? Burada. Mən üç görürük. Üç məxsusdur? Burada. Mən dörd görmək. Burada. Beş, altı, yeddi, səkkiz. Özümü təkrar üçün heç bir səbəb yoxdur. Belə ki, nə qədər çox addımlar ki, n baxımından? Bu n sifarişi var addımlar, sağ? n minus 1. Amma xətti sıra etdi addımlar, və indi bitirdim. Belə ki, baxmayaraq ki, ən yaxşı halda var. Nə pis halda haqqında? Nə səkkiz, orada idi və yeddi, orada idi və bir və iki, belə ki, burada idi siyahısı həqiqətən ləğv edilmişdir ki? Yaxşı, nə həqiqətən olur bu sayı əgər? Və biz yalnız nümunələri bir neçə edəcəyik. Nə sayı səkkiz, həqiqətən, əgər burada və saysız whoops. Belə ki, nə əgər həqiqətən, sayı səkkiz, burada bütün yol və mən durub növ istifadə edirəm? OLDU. Mən bu yerdə var bu anda iddia edirlər. Amma indi, seven-- olduğu yeddi getmək edir? Əlbəttə ki, burada üzərində gedir. Mən bir yer üzərində səkkiz hərəkət var. İndi altı, harada getmək edir? Bəli, bütün hüququ. İndi mən artıq səkkiz hərəkət var bir yer və yer üzərində yeddi, və sonra mən altı aşağı Plop. Belə ki, ilk dəfə, o dəyəri şeyi düzeltmek üçün mənə bir addım, o şeyi düzeltmek üçün mənə iki addımlar başa gəlir. Bu neçə addımlar düzeltmek üçün etmək niyyətindədir doğru yerdə beş qoymaq üçün hər şeyi? Üç. İndi mən var bir iki, üç hərəkət. Neçə addımlar etmək niyyətindədir doğru yerdə dörd qoymaq? 4 plus 5, plus 6, plus 7. Və belə bu riyazi eyni deyil biz seçim sort üçün təsvir nə. Biz bu seriyası var yalnız artan oldu. 1 plus 2 plus 3 plus 4, və ya əksinə, 7 plus 6 plus 5 Plus 4 gün üçün əlavə n sifarişi üzrə məqsədlər kare. Belə ki, mənə də ki müəyyən edək bubble sort n kvadrat də var. Çünki bubble sırala, hər dəfə, siyahı ilə getmək Mən təxminən neçə addımlar alaraq alıram? Hər dəfə mən sözün oradan oraya getmək? Təxminən n addımlar. Amma neçə dəfə mən bilər siyahı ilə getmək lazımdır? Bəli, təxminən n vaxt. Bəlkə n mənfi 1, amma təxminən n dəfə. Yaxşı, niyə ki? Yaxşı, bubble növ ilə, əgər Biz bubble sırala ilə başlamaq ən pis mümkün siyahısı ilə yenidən tamamilə vəziyyət, geri, nə baş verəcək? Mən siyahısı ilə getmək və sayı bir orada bütün yol məxsusdur. Amma bubble növ ilə, nə qədər bir deyil siyahısını mənim ilk pass hərəkət? Neçə ləkələr o almaq deyil düzgün yerə yaxın? Yalnız bir. Belə ki, bu vasitəsilə, əgər cür səbəbi, Bu alqoritm vasitəsilə hər zaman, Davudun alaraq təxminən n addımlar. Amma nə qədər keçir siyahısına vasitəsilə bubble bir etmək niyyətindədir bu məxsusdur sol? O, kimi hərəkət etmək var n boşluq bu yol. Belə ki, yalnız siyahısı çeşidlənməsi etmək, Mən geri və irəli n dəfə gəzmək lazımdır. Və hər dəfə mən deyiləm n elementləri baxaraq. Belə ki, n şeyi n dəfə n qaydası kvadrat. İndi biz bəzi görəcəksiniz şort ki CS50 növbəti problem daxil edilir Bu da başqa bir yanaşma müəyyən lakin indi üçün, yalnız hesab edək bəzi digər çalışan dəfə, xüsusilə çeşidlənməsi olanları əgər vaxt bir az endirmək üçün. Biz artıq gördüm bir alqoritm var ki, n addımlar üçün qalır? Xətti sıra almaq lazımdır nə Biz indiyə qədər gördüm ki addımlar? Bu nədir? telefon kataloqu axtarış. ilk alqoritm. Sağ? Biz xətti olduğunuz Mike Smith üçün axtarış? Həqiqətən. Həftə sıfır, mən açılmış zaman bir-bir səhifə dönüş, və mən hətta bu cür olduğunu bildirib xətti hissi alqoritm, və biz şəkil idi düz qırmızı xətt ilə board və düz sarı line, o həqiqətən idi n böyük O olan alqoritmləri. Bir telefon Mike Smith tapmaq üçün ən pis halda n pages, kitab, Məni n addımlar bilər. Iştirak alaraq haqqında nə? Bir, iki, üç, dörd, beş, altı. Bu çalışan zaman nədir iştirak görülməsi üçün alqoritm? Çünki nəzəri n böyük O, I otaqda hər kəs qeyd etmək lazımdır. İndi bir kənara kimi, nə Həftə sıfır digər optimallaşdırılması? Iki, dörd, altı, səkkiz, 10, 12. A kompüter alim olardı həyata bir dəqiqə gözləyin, ki əmri var n iki addımlar bölünür. Sağ? Mən bir anda iki nəfər edirəm, çünki. Amma biz ignore olacaq o aşağı sifariş şərtləri, və biz yalnız olacaq 2 bölmək tullamaq, və yalnız demək n böyük O də ki, alqoritmi üçün. Bu barədə nə? Biz bu bəzi üzərində keçmək lazımdır, lakin nə n log olan bir alqoritm idi? Ki, təxminən n addımlar daxil aldı? bölmək və fəth. Məhz. Telefon kitab misal kimi həftə sıfır və əvvəllər bu gün, biz problemi bölünür təkrar və yenidən. Biz həftə board çəkdi bir əyri yaşıl xətt kimi sıfır, və biz bu gün olduğunu söylədi bir logarithmic alqoritmi. Həqiqətən, sayı addımlar onu uçurum çıxış və fəth edir, və ya ikili axtarış kimi biz başlamaq lazımdır telefon kitab kimi, zəng, Giriş və addımlar üçün edir. Və bu qəribə bir az. Bir addım nə, və ya daha çox xüsusi addımlar daimi sayı? Bəlkə, bəlkə üç var, iki deyil, lakin bir kompüter alim yalnız 1 böyük O kimi asanlaşdırır, addımlar bəzi daimi nömrəsi. Siz bunu edə bilər ki, bir şey nədir addımlar sabit bir sayı edir? Alqış çalışan zaman nədir? Constant vaxt. Sağ? Kimi, çalışan zaman nə yalnız birini tutur şey bunu əməliyyat kimi F Hello World çap. Ki, daimi vaxt olduğu ifadə edilə bilər print F az künc halda halda, nə vaxt çalışan bilər çap F həqiqətən ola bilərmi? Və niyə? Bu halda n ölçü nədir? Auditoriya: [işitilemez]. DAVID J. MALAN: Exactly. simvolların sayı biz çap etmək istəyirəm. Belə ki, çox kontekstində həssas var. Bu gün biz bir çox diqqət etdik məktublar və board nömrələri. Lakin bu da ola bilər faktiki simli simvol. Başqa var həyata Belə ki, çevrilir haqqında qayğı başlayacaq tədbir ki, əks edir big O, belə danışmaq. Ki, omega notation var. Big O, nə deməkdir, halbuki yuxarı çalışan zaman bağlı? Maksimum, nə qədər vaxt bir şey ola bilər? Omega-- sorry bu gələn saxlayır gündəmə ki, qarşı deyil, Bu aşağı bound var vasitəsi vaxt bir şey məbləği bilər. Belə ki. məsələn, nə bir alqoritm var ki, həmişə n kvadrat addımlar atır? Yaxşı, alqoritmlərin biz gördük Bu gün, əslində, həm də ki, ola bilər. Seçim sort. Seçim sort olduqca axmaq var. Hətta, alqoritm sorry əgər array artıq çeşidlənir əgər, seçim sort gedir siyahısını gəzinti saxlamaq Bu kiçik var əmin etmək element təkrar və yenidən. Və insanlar olsa da tamaşaçı, bir dəqiqə gözləyin ki, bilirik, Əgər siz artıq keçdi kiçik element, kompüter görünür qədər bilmir siyahısını bütün yol. Eynilə, aşağı ki, bağlı də nəzərə alınmalıdır bilər xətti vaxt ola bilər. Bu almaq nə qədər vaxt yaxşı sort n elementləri bubble sırala kimi bir şey istifadə halda? Sizin siyahısı artıq çeşidlənir düşünək. Biz bubble sırala qalır bildirib n qaydası addımlar kvadrat. Lakin artıq nə sıralanır əgər? Nə sonra həyata əgər array vasitəsilə bir pass ki, bir svopları etdik? Siz keçir daha davam etmək üçün lazımdır? Yox. Belə ki, aşağı bubble növ bağlı xətti olduğu ifadə edilə bilər. N Omega. Və biz baxmaq olar eləcə də bu başqaları. Belə ki, tez nəzər salaq Burada yalnız bir vizual at bu özlərini ayırmaq necə. Mən bu daxil burada enmək gedirəm C50 saytında mövcuddur səhifə lakin bu iş almaq üçün bir ağrı olacaq, Bu adlı bir texnologiya istifadə edir-ci ildən Bir Java kiçik, bu gün əsasən dəstəklənmir, ən azı Chrome və müəyyən başqaları tərəfindən. Və mənə irəli getmək və bu sürətləndirmək imkan və neler izah edir. Bu bubble nümayiş edir sort, ilk alqoritm biz baxdı. Və bu ki, bir vizual hər var bu bar bir sıra edir. böyük bar, sayı daha böyük. kiçik bar, sayı kiçik. Və hətta, vizual bilərsiniz nə Bu baxmayaraq, super sürətli gedir qırmızı bar mənim kimi ki, geri gəzinti və irəli problemləri təyinat. Siz böyük elementləri olduğunu görə bilərsiniz Həqiqətən sağ qədər burda olunur, və kiçik elementləri sol qədər burda olunur. Və burada, biz əgər həqiqətən, çox yaxından baxmaq, Biz, həqiqətən, saymaq olar müqayisə və svopları sayı ki, aparılır. Lakin əvəzinə, bu baxaq İkinci alqoritm biz əvvəllər baxdı bizim könüllü seçim sort. Görmə, bu bir çox fərqli təsiri. Amma bu, yenə, çox asan deyil biz kiçik növbəti seçilməsi saxlamaq element və biz bir az uğurlu var. Ki, əsaslı sürətli hiss etdim. Amma biz təkrar bu qaçdı əgər və yenidən giriş çox, biz həqiqətən ki, görmək olardı hələ n böyük O kvadrat. Tək son bir imkan Burada durub sort, olan üçüncü alqoritm idi Biz və geri baxdı bu bir ilə məşğul ki, elementlər onları qarşılaşmalar kimi, lakin sonra bəlkə növbədə şeyə otaq etmək onların mənsub elementləri daxil. Və bu çox verilməsi başa Yekun nəticə. İndi o bütün üç olduqca sürətli hiss etdim. Həqiqətən, Mən onlara qaçdı olduqca yaxşı klip. Lakin əsaslı, onlar bütün istəyirik olduqca dəhşətli, vicdanlı olmalıdır. Bu alqoritmlərin bütün indiyə qədər n böyük O ki run kvadrat bir qədər almaq vaxt sonunda çalıştırmak üçün. Həqiqətən, biz görürük və nəhayət bu hiss Mən bu üçüncü və son demo qoparmaq bilər. Bu başqa ki, vizual olacaq sol, bubble növ göstərmək üçün, ortada seçim sort, və bir şey, biri kimi bizim tərəfdən, əvvəllər təklif artırır sağ sort daxil. A bölmək və fəth sağ strategiyası. Və biz etdiyiniz nə, əslində, var Çərşənbə günü baxmaq üçün gedir. Amma paralel bu vaxt imkan verir. Bu təxminən eyni sayı elementləri, eyni zamanda çalışan. Seçilməsi vs bubble sırala Birləşmə sort vs sort. İndi onlar bütün yayınlıyorsanız eyni zamanda nəzəri. CPU at çalışan Eyni sürətli, lakin bu necə darıxdırıcı hiss edə bilərsiniz çox tez olmaq üçün gedir, və necə sürətli zaman biz həftə bir az yeritmək Zero alqoritmlər bilərsiniz Biz hər şeyi sürətləndirmək. İndi müqayisə edək son bir formada bu. Mən irəli getmək üçün gedirəm CS50 veb üçün Biz bu gün bu son link harada internet kimsə xahiş bir video birlikdə qoymaq ki, Nə müxtəlif çeşidlənməsi tutan alqoritmlər kimi səs. Bu durub sort edir. [Səs siqnalı] Qovuşdurmağımız bir tezlik tətbiq edirik bar bar hündürlüyü əsasında. Bu bubble sort edir. [Warped səs siqnalı] Gələn is-- növbəti qədər gələn Növbəti is-- seçim sort, burada yenə biz seçilməsi edirik növbəti kiçik element, və biz bu artan bilərsiniz Soldan sağa. Bizim qalibi indiyədək bu gün, sort daxil. Bu şeyi ayırıcı necə edək [Işitilemez] yarısında dörddə daxil. Biz var Gnome sort, danışdıq və vizual yaradır və bir az audally müxtəlif forma və sound. Geri və irəli gedən, şeyi təmizlənməsi. Həmçinin heapsort kontrol bu oğlan saytında. Və bu. Biz sizə növbəti dəfə görəcəksiniz. [Whooshing AND MUSIC]