[Musiqi ifa] DAVID Malan: Yaxşı. Bütün sağ, geri salamlayıram. Beləliklə, bu, əvvəlində həftə 4 onların artıq. Və keçən həftə xatırlamaq lazımdır, biz qoymaq Bir az kənara kod və biz bir az daha danışmağa başladı kimi yüksək səviyyəli haqqında şeyi olan baxmayaraq, axtarış və çeşidlənməsi qədər sadə fikir var problemlərin sinif nümayəndəsi Siz xüsusilə həll başlayacaq Siz yekun düşünmədən başlamaq kimi layihələr və maraqlı çözümleri real-dünya problemləri ola bilər. İndi bubble sırala sadə biri idi Belə alqoritmlər və bu, Bu kiçik nömrələr edərək işləyib siyahısı və ya bir sıra növ ilə qədər üst bubble onların yol və böyük ədəd onların yol aşağı hərəkət ki, siyahı sonu. Və biz görüntüləmək bilər ki, xatırlamaq bubble sırala bir az bu kimi bir şey. Mənə davam və Start basın bildirin. Mən bubble sırala dərhal etdik. Və geri əgər ki taller mavi xətləri kiçik, böyük nömrələr təmsil mavi xətləri kimi, az sayda təmsil biz təkrar bu yolu getmək və yenə hər növbəti iki bar müqayisə qırmızı başqa, biz dəyişdirmək olacaq ən böyük və əgər kiçik onlar üçün həyata. Bu getmək və getmək və getmək edəcək ki, , və siz böyük görürsünüz elementləri onların yol verirlər sağ, və kiçik elementləri sol yol edilməsi. Amma biz hesablamaq başladı səmərəliliyinin ki, Bu alqoritm keyfiyyəti. Və biz bildirib ki, pis halda, bu alqoritm etdi təxminən neçə addımlar? Belə n kvadrat. Və n nə idi? Auditoriya: elementlərinin sayı. DAVID Malan: Belə n idi elementlərinin sayı. Və belə ki, biz tez-tez bu edəcəyik. Biz ölçüsü haqqında danışmaq istədiyiniz zaman bir problem və ya bir və ölçüsü giriş, və ya lazım vaxt məbləği çıxış istehsal, biz yalnız rəftar ümumiləşdirilmiş nə giriş n kimi. Belə ki, geri Həftə 0, sayı səhifələr telefon kitab n idi. Tələbələrin sayı otaqda N edilib. Belə ki, burada da biz aşağıdakı edirik ki, model. İndi n kvadrat xüsusən deyil sürətli, biz daha yaxşı etməyə çalışdım. Və belə ki, biz bir neçə baxdı digər alqoritmlər, onlardan seçim sort idi. Idi seçim sort Belə ki, bir az fərqli. Demək olar ki, sadə idi, mən demək cəsarət, Mən əvvəlində başlayan vasitəsi könüllü siyahısı və mən bir daha və təkrar ilə getdi kiçik həyata Yolma siyahısı bir zamanda element və ya ona verilməsi onun siyahının başında. Amma bu da bir dəfə biz düşünməyə başladılar riyaziyyat və daha vasitəsilə şəkil, neçə dəfə haqqında fikir Mən irəli və geri geri gedir və və irəli, biz pis halda dedi: seçim sort da nə idi? n kare. İndi real dünyada, o bilər həqiqətən cüzi daha sürətli ola bilər. Yenə Çünki, mən saxlamaq yox idi Mən sıralanır idi bir dəfə backtracking ki, kiçik elementləri. Amma biz çox böyük n haqqında düşünmək və əgər Siz növ riyaziyyat kimi əgər Mən n kvadrat ilə board etdi minus bir şey, başqa hər şey n kare, bir dəfə n başqa həqiqətən böyük olur, yox həqiqətən çox əhəmiyyətli. Belə ki, kompüter alimləri kimi, biz sort kiçik bir göz yummaq amillər və yalnız amilindən mərkəzində etmək olacaq bir ifadə ən böyük fərq var. Bəli, nəhayət, biz baxdı durub sort edir. Və bu ruhda oxşar idi, amma iteratively keçir və daha çox bir də kiçik element birini seçin zaman, mən əvəzinə əl etdi ki, mən bütün məşğul və mən qərar qəbul edilib sağ, burada məxsusdur. Sonra növbəti element üçün köçüb və qərara aldı ki, o və ya o burada idi. Və sonra mən və köçürülüb. Və mən, yol boyu üçün güc üçün bu uşaqlar keçmək onlar üçün otaq etmək. Belə ki, ruh bərpa cür idi seleksiya sort ki, biz durub sırala çağırıb. Belə ki, baş bu mövzular real dünyada. Bir neçə il əvvəl, zaman müəyyən bir senator prezident çalışan edilmişdir Eric Schmidt, zamanı CEO Google, həqiqətən imkanımız oldu Onun müsahibə. Və biz bu YouTube bölüşmək istədiyiniz fikir biz çevirmək bilər, burada sizin üçün kəsmək həcmi. [Video playback] -İndi, senator, siz Google buradayıq və mən prezidentliyə düşünmək istəyirəm iş müsahibə kimi. [Gülüş] -İndi almaq çətindir prezident kimi bir iş. Və vasitəsilə olacaq İndi rigors. Google bir iş üçün də çətindir. Biz sualınız və biz xahiş bizim namizədlər suallar. Və bu bir Larry Schwimmer edir. [Gülüş] -Siz uşaqlar I söylüyorum alıram mi? Sağ burada. Üçün ən səmərəli yolu nədir bir milyon iki-bit integers sort? [Gülüş] -Yaxşı, uh - -Ben üzr. Bəlkə biz olmalıdır - -Xeyr, heç, heç, heç,. -Bu deyil - OK. -Mən bubble sırala edəcəklərini düşünürük getmək üçün yanlış yol ola bilər. [Gülüş] [Təzahürat və alqışlarla] Ona izah edən, on-gəlir? OK. [END video playback] DAVID Malan: Belə ki, orada siz var. Belə ki, biz bu çalışan hesablamaq başladı dəfə, belə bir şey ilə, danışmaq olan asimptotik notation adlı yalnız dönüş bizim sort istinad kor bir o kiçik amillərin göz və yalnız çalışan zaman baxaraq, bu alqoritmlərin performans, n zamanla həqiqətən böyük olur kimi. Və belə ki, biz böyük O. və böyük O tətbiq düşündük ki, təmsil bir şey bir üst bound kimi. Və həqiqətən, Barry, biz düşürebilirsiniz mic bir az daha? Biz bu bir üst bound edir düşündüm. N kvadrat vasitələrinin Belə böyük O ki, Ən pis halda, belə bir şey seleksiya sort edəcək kvadrat addımlar n. Durub sort kimi və ya bir şey n kvadrat addımlar olacaq. İndi durub kimi bir şey sort, ən pis halda nə idi? Bir sıra nəzərə alaraq, nə pis var tapa bilər ki, mümkün ssenari özünüz ilə üzləşib? Bu doğru, tamamilə geri var? Tamamilə geri əgər Çünki, Əgər iş bir çox var. Çünki siz tamamilə geri istəyirsinizsə, Siz tapmaq olacaq Burada ən böyük element olsa orada aşağı məxsusdur. Belə ki, sizə, demək bütün doğru olacaq vaxt bu anı, siz burada məxsusdur belə ki, tək buraxın. Sonra, oh, həyata lənətləmək, mən var Bu qədər kiçik element hərəkət Siz sol. Sonra daha nə var və təkrar. Və mən geri və irəli getdi, əgər fəaliyyətinin hiss sort olacaq ki, alqoritm, çünki daim mən də aşağı hər kəs shuffling üçün otaq etmək array. Belə ki, ən pis halda var. Əksinə - və bu son dəfə cliffhanger idi - biz bildirib ki, durub sırala hansı bir omega idi? Ən yaxşı halda davam nedir durub növ vaxt? Belə ki, əslində n oldu. Yəni, biz tərk boş idi şurası son dəfə. Və N omega niyə çünki var? Yaxşı, ən yaxşı halda, nə var durub sırala təhvil olacaq? Tamamilə ayrılır ki, Bəli, bir siyahısı artıq, nə minimal çalışır. Bəs durub sırala haqqında səliqəli var burada başlayır və ona görə ki, qərar, oh, siz var bir, burada məxsusdur. Oh, nə qismət. Siz sayı iki istəyirik. Siz həmçinin burada məxsusdur. Daha yaxşı sayı üç, Burada məxsusdur. Bu sonuna olur kimi tezliklə siyahısı, hər durub sırala nin pseudocode biz şifahi vasitəsilə gəzmiş ki, son dəfə bunu. Amma seçim sort, əksinə, nə saxlanılır? Saxlanılan siyahısını keçir təkrar və yenidən. Əsas fikir yalnız idi Siz bütün yol baxdı sonra siyahısı sonuna, müəyyən ola bilər seçdiyiniz element olduğunu həqiqətən hazırda kiçik element. Bu fərqli əqli modellər sonunda Belə ki, çox real-dünya verir up bizim üçün fərqlər, habelə bu nəzəri asimptotik fərqlər. Belə ki, yalnız n böyük O, sonra, Recap üçün kare, bir neçə belə gördüm İndiyədək alqoritmləri. N Böyük O? Ki, ola bilər alqoritm nədir n böyük O olduğu deyilə? Ən pis halda, o, edir addımlar xətti nömrəsi. OK, xətti axtarış. Və pis halda, harada olduğunu element zaman aradığınız xətti axtarış tətbiq? OK, ən pis halda, hətta mövcud deyil. Və ya ikinci pis halda, bu, olan sonunda bütün yol, plus-ya mənfi bir addım fərq. Belə ki, günün sonunda, biz bu xətti var demək olar. N Böyük O xətti axtarış olardı, ən pis halda, çünki element hətta mövcud deyil və ya onun sonunda bütün yolu. Yaxşı, n daxil böyük Ç. Biz böyük ətraflı danışmaq etməyib Bu, ancaq əvvəl bu gördük. Nə qondarma loqarifmik çalışır zaman, pis halda? Bəli, belə ki, binar axtarış. Ən pis halda və ikili axtarış yerdə element ola bilər orta, və ya haradasa serialın içərisində. Amma yalnız bir dəfə tapmaq ildə yarısında siyahısı bölmək yarısı yarısında yarısında. Və sonra voiture, bu, var. Və ya yenidən, ən pis halda, hətta mövcud deyil. Amma orada deyil ki, bilmirəm Siz növ ki, ötən çatmaq qədər halving tərəfindən alt-Ən çox elementləri və halving və halving. 1 Big Ç. Beləliklə, biz 3 2 böyük O böyük O bilər. Yalnız sabit bir sayı istəyirik zaman, biz yalnız sadələşdirmək növ ki, 1 böyük O kimi. Hətta real, Sürsə baxmayaraq Bir 2 və ya hətta 100 addımlar, əgər addımlar sabit sayı, Biz yalnız 1 böyük Ey deyirlər. Ki, bir alqoritm nədir 1 böyük O? Auditoriya: uzunluğu tapmaq bir dəyişən. DAVID Malan: The tapmaq dəyişən uzunluğu? Auditoriya: Xeyr, uzunluğu artıq sıralaması varsa. DAVID Malan: Yaxşı. OK, belə ki, bir şey uzunluğu tapmaq əgər kimi ki, bir şey uzunluğu, bir sıra, bəzi dəyişən saxlanılır. Yalnız dəyişən oxuya bilərsiniz Çünki və ya dəyişən çap, və ya yalnız ümumiyyətlə dəyişən olmaq. Daimi vaxt tələb edir və voiture. Əksinə, danışıq geri edirəm. C ilk həftə geri düşünün, yalnız printf zəng və çap ekranda bir şey arguably edir daimi dəfə, o, yalnız edir, çünki göstərmək üçün CPU dövründən bir sıra Ekranda ki, mətn. Yoxsa gözləyin - edir? Necə başqa biz model ola bilər printf yerinə? Kimsə razı etmək istəyirəm ki, bəlkə həqiqətən daimi vaxt deyil? Printf çalışan nin hansı mənada vaxt, həqiqətən bir string çap ekranın bir şey ola daimi başqa. Auditoriya: [işitilemez]. DAVID Malan: Bəli. Belə ki, bizim perspektiv asılıdır. Biz, həqiqətən, üçün daxil düşünüyorsanız simli kimi printf və Ona görə də biz ki, ölçüsü ölçmək onun uzunluğu giriş - belə zəng edək eləcə də ki, uzunluğu n - arguably, printf özü n böyük o siz n addımlar olacaq, çünki o n hər çap çox güman simvol. Ən azı biz güman dərəcədə Bəlkə loop üçün istifadə ki, başlıq altında. Ancaq biz baxmaq olardı daha yaxşı anlamaq kodu. And olsun ki, bir dəfə uşaqlar başlamaq Siz, öz alqoritmlər lazımdır təhlil sözün yalnız bunu. Göz almasının Sort kodunuzu və hesab edirəm ki, haqqında - Bütün sağ, mən bu loop var burada və ya burada iç-içə loops var n şeyi n dəfə, nə olacaq ki, və səbəbi yol çeşidləyə bilərsiniz kodu ilə, hətta bu pseudocode və faktiki kodu. Belə ki, kvadrat N omega haqqında nə? Alqoritm nə idi ki, ən yaxşı halda, hələ də aldı n kvadrat addımlar? Bəli? Auditoriya: [işitilemez]. DAVID Malan: Bu seçim növ. Ki, problem həqiqətən azaldıb Çünki yenə bilmirəm ki, Mən qədər mövcud kiçik gördük Mən bütün darn elementləri yoxlanılır etdik. N, demək, belə Omega, biz yalnız bir ilə gəldi. Durub növ. Siyahısına sıralanır olur artıq, ən yaxşı halda, biz yalnız var onun vasitəsilə bir pass etmək, hansı emin nöqtədə. Və sonra deyilə bilər ki, əmin, xətti olmalıdır. 1 omega haqqında nə? Ən yaxşı halda bilər nə addımlar sabit bir sayı? Belə xətti axtarış, yalnız şanslı almaq əgər və siz aradığınız element , siyahının başında sağ Siz başlanğıc olduğunuz ki, əgər O siyahıda xətti traversal. Bu bir həqiqətdir şeylər sayı. Məsələn, hətta ikili axtarış 1 omega edir. Həqiqətən darn nə almaq Çünki əgər ortasında uğurlu və tam-dab Sizin array sayı aradığınız? Beləliklə, siz həmçinin, orada uğurlu əldə edə bilərsiniz. Bu, nəhayət, n log N omega. Belə n log n, biz, həqiqətən etmədi hələ danışmaq, ancaq - Auditoriya: sort Birleştirme? DAVID Malan: Merge növ. Bu, ötən vaxt cliffhanger oldu Biz təklif və biz göstərdi yerləşir vizual, alqoritmlər var. Və yalnız belə bir növ daxil əsaslı sürətli ki, alqoritmi Bu digər uşaqlar bir çox. Əslində, yalnız qısa birləşməsi ən pis, ən yaxşı halda n log n, halda n log n. Və bu təsadüf zaman omega və böyük O eyni şey olan? Biz, həqiqətən, nə ki, təsvir edə bilərsiniz O, baxmayaraq ki, teta adlı az az ümumi. Lakin bu, yalnız iki həddi deməkdir bu halda, eynidir. Belə növ birləşməsi, bu nə bizim üçün həqiqətən aşağı qaynatmaq? Yaxşı, motivasiya xatırlayıram. Mənə bir animasiya qədər çəkin edək biz sonuncu dəfə baxmadı. Bu, eyni fikir, lakin bir az daha böyük var. Və mən irəli getmək və qeyd etmək gidiyorum birinci - biz durub növ var üst sol, sonra seçim sort, bubble sırala digər növ bir neçə - shell və sürətli - danışdıq deyil ki, haqqında və yığın və sort daxil. Ən azı gözlerini diqqət cəhd Belə ki, sonra sol üç top və Mən tıkladığınızda növ daxil bu yaşıl arrow. Amma yalnız, onlara bütün run edək edəcəyik Siz müxtəliflik hissi vermək dünyada mövcud alqoritmlərin. Mən bu run imkan gidiyorum yalnız bir neçə saniyə üçün. Və sizin gözləri diqqət əgər - Bir seçin yalnız üçün alqoritm, bunu saniyə - siz görmək başlamaq lazımdır o həyata ki, model. Birləşməsi sort, bildiriş edilir. Yığın sort, sürətli sort, shell - biz üç təqdim belə görünür pis alqoritmləri keçən həftə. Amma ki, biz bu gün burada olduğunu yaxşı birləşməsi sort baxmaq, onlardan biri asan olanları, hətta baxmaq üçün yəqin ki, sizin fikrinizi əymək baxmayaraq Bir az. Burada biz görürük yalnız nə qədər Seçim Sıralama gücünü zaptetti. Amma flip tərəfdən, bu, həyata keçirmək həqiqətən asan. Və bəlkə P Set 3 ki, biri siz həyata keçirilməsi üçün seçdi alqoritmlər Standard Edition üçün. Mükəmməl düzgün, mükəmməl gözəl. Ancaq yenə də, n böyük olur kimi, əgər daha sürətli alqoritm həyata keçirmək üçün seçin sort birləşməsi kimi, bahis böyük və böyük giriş, kodu yalnız daha sürətli run gedir. Sizin veb daha yaxşı işləmək olacaq. Sizin istifadəçi xoşbəxt olacaq. Və belə ki, bu təsiri var əslində verilməsi bizə bir daha dərin düşündüm. Elə birləşməsi nə bir nəzər edək sort haqqında əslində. Bu sərin şey daxil ki, sort yalnız bu deyil. Bu adlı ne, təkrar edir pseudocode, pseudocode varlıq İngilis-kimi sintaksis. Və sadəlik edir maraqlı növü. Belə n elementlərinin yığımı - belə ki, yalnız deməkdir, burada bir sıra var. Bu n şeylər var. Yəni biz deyən etdiyiniz bütün var. N 2-dən az olarsa, qayıtmaq. Belə ki, yalnız mənasız halda var. N az 2, onda açıq-aydın var 1 və ya 0, bu halda şey artıq çeşidlənir və ya mövcud deyil, belə ki, yalnız geri. Heç bir əlaqəsi yoxdur. Belə ki, yoluq-yoluq etmək üçün sadə bir işi var. Başqa, biz üç addımlar var. Elementlərin sol yarısı, sort Sort elementləri hüququ yarısı, və sonra sıralanır yarıya indirir daxil. Burada maraqlı olduğunu Mən sağ, punting növü Ben? Dairəvi müəyyən növ var bu alqoritmi. Bu alqoritm nə mənada deyil definition dairəvi? Auditoriya: [işitilemez]. DAVID Malan: Bəli, mənim çeşidlənməsi alqoritmi, onun addımlar iki "sort var ki, begs ki, bir şey. "Və sual, yaxşı, nə istifadə gedirəm sol yarım düzmək üçün və sağ yarım? Və burada gözəllik ki, hətta yenidən, bu mind-əyilmə edir hissəsi potensial, siz eyni istifadə edə bilərsiniz sol yarım düzmək üçün alqoritmi. Amma bir dəqiqə gözləyin. Siz düzmək deyib etdiyiniz zaman sol yarım, iki nə addımlar növbəti olacaq? Biz sol yarısı düzmək lazımdır sol yarısı və sağ sol yarısının yarısı. Lanet olsun, necə bu iki sort yoxdur yarıya indirir və ya dörddə indi? Amma ki, OK. Biz burada bir çeşidlənməsi alqoritm var. Və siz narahat ola bilər, baxmayaraq ki, ilk bu sonsuz növü loop, bu heç olan bir dövrü var son gedir - bu gedir nə bir dəfə başa? Bir n az 2 olur. Hansı nəhayət, baş verəcək saxlamaq əgər halving görə Bu yarıya indirir halving ildə halving, şübhəsiz ki, nəticədə siz başa olacaq yalnız 1 və ya 0 elementləri ilə. Olan nöqtə, bu alqoritm hazırda Bitirdiğinizde deyir. Belə ki, bu real sehrli alqoritm olmaq görünür ki, son addım, birləşməsi. Yalnız iki birləşmə ki, sadə ideya əşyalar, nəticə etibarilə neler var Bizim bir sıra düzmək üçün imkan, edək, səkkiz elementləri deyirlər. Belə ki, mən daha səkkiz stress top var burada səkkiz kağız parçaları və bir Google Glass - I saxlamaq almaq. [Gülüş] DAVID Malan: biz səkkiz ala bilər könüllü və bir-görək biz əgər Belə ki, bu həyata oynayır. Wow, OK. Kompüter elm fun əldə edilir. Bütün hüquqlar. Belə ki, necə haqqında üç, var ən böyük əl. Geri dörd. Və necə ki, biz bunu edəcəyik Bu sırada üç? Ön və dörd. Belə ki, səkkiz up gəlib. [Gülüş] DAVID Malan: Mən, həqiqətən, Ben onu nə əmin olun. Bu stress top mu? Bu masa lampaları? Maddi? İnternet? OK. Belə up gəlib. Kim istərdim - qədər gələn saxlamaq. In nəzər salaq. Və bu yerdə sizə qoyur - Əgər yer bir istəyirik. UH-oh, bir dəqiqə gözləyin. 1, 2, 3, 4, 5, 6, 7 - yaxşı, oh. Bütün sağ, biz yaxşı istəyirik. Bütün sağ, belə hər kəs bir oturacaq var lakin Google Glass haqqında. Mənə növbə bu qədər edək. Sizin adınız nədir? Michelle: Michelle. DAVID Malan: Michelle? Bütün sağ, sizin kimi baxmaq almaq ki, turk, OK ki, əgər. Bəli, mən də, mən güman, yalnız bir an. Gözləmə Bütün hüquqlar. Biz ilə gəlmək üçün çalışırıq olduğunuz Google Glass üçün halda istifadə və biz bunu yalnız əyləncə olardı düşündüm bu xalq səhnədə olduqda. Biz dünyada qeyd edəcək onların perspektiv. Bütün hüquqlar. Heç yəqin ki, nə Google nəzərdə tutulub. Əgər ağla deyil əgər bütün hüququ, qalıcı növbəti yöndəmsiz dəqiqə bu, ki, gözəl olardı. Bütün sağ, biz burada bir sıra var elementləri, habelə düşən dizi, Bu insanlar kağız parçaları ' əlləri, hazırda Sıralanmamış edir. Michelle: Oh, belə ki, qəribə deyil. DAVID Malan: Bu olduqca çox təsadüfi deyil. Və yalnız bir anda, biz cəhd olacaq birlikdə sort daxil həyata keçirilməsi əsas fikir olduğu və görürük. Və birləşməsi növ ilə burada oyun deyil biz hələ güman deyil ki, bir şey. Biz, həqiqətən, bəzi lazımdır əlavə yer. Beləliklə, nə xüsusilə olacaq Bu barədə Maraqlıdır ki, bu uşaqlar bir az ətrafında hərəkət edir bit, çünki mən varsaymaktayım ki, yer əlavə array var onlara arxasında, deyirlər. Onların kafedrasının arxasında istəyirik, əgər orta sıra var. Onlar burada oturmuş istəyirsinizsə, var əsas array. Amma bu var ki, bir resurs deyil bubble ilə indiyədək kullanılarak geliştirilebiliyor deyil sort, seçim növ ilə, durub növ ilə. Keçən həftə Xatırladaq, hər kəs yalnız cür yer qarışdırılmış. Onlar heç bir əlavə yaddaş istifadə etməmişdir. Biz insanlar üçün otaq etdi ətrafında insanların hərəkət. Belə ki, bu da əsas fikir deyil. Bu ticarət-off ümumiyyətlə, var resursların informatika. Əgər bir şey sürətləndirmək istəyirsinizsə, müddət kimi, siz olacaq qiymət ödəməli olurlar. Və bu qiymətləri bir çox tez-tez yer, yaddaş məbləği və ya ağır istifadə etdiyiniz disk space. Və ya, səmimi, məbləği proqramçı vaxt. Ne kadar insan, sizi zaman, əslində bir daha həyata keçirmək mürəkkəb alqoritmi. Amma bu gün üçün, ticarət-off zaman və məkan deyil. Uşaqlar yalnız almaq bilər, belə ki, sizin Sizə olduğunu nömrələri görə bilərsiniz həqiqətən 4, 2, 6, 1, 3, 7, 8 uyğun. Əla. Beləliklə, mən orkestra üçün cəhd gidiyorum əşyalar, əgər uşaqlar bilərsiniz yalnız burada mənim qurğuşun edin. Buna görə ilk həyata keçirəcəyik edirəm olan pseudocode ilk addım n Əgər n elementləri daxil haqqında 2-dən az, sonra qayıdırlar. Aydındır ki, yox müraciət, biz keçin. Belə ki, elementləri sol yarısı Sıralama. Belə ki, mən diqqət gidiyorum deməkdir mənim Bu yalnız bir an diqqət Burada dörd uşaqlar. Bütün sağ, mən gələn nə etməliyəm? Auditoriya: sol yarısı Sort. DAVID Malan: Belə ki, indi mən düzmək üçün Bu uşaqlar sol yarısı. Yenə Çünki özünüz üçün güman məqsədi sol yarısı düzmək üçün edir. Necə ki etməliyəm? Yalnız belə, təlimatlara əməl edin yenə bunu edirik, baxmayaraq ki. Belə ki, sol yarım Sıralama. İndi mən bu iki uşaqlar çeşidlənməsi alıram. Nədir gəlir? Auditoriya: sol yarısı Sort. DAVID Malan: sol yarısı Sort. Belə ki, indi bu, burada bu oturacaq, ölçüsü 1 siyahısı. Və adı nə yenidən? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy burada. Və belə ki, o, artıq çeşidlənir çünki siyahısı ölçüsü 1 edir. İndi nə etməliyəm? O siyahıda, çünki OK, qayıtmaq 2-dən az olan ölçüsü 1. Daha sonra növbəti addım nədir? İndi cür var fikrinizi backtrack. Olan doğru yarım, sort - Sizin adınız nədir? LINDA: Linda. DAVID Malan: Linda. Və biz indi nə etməliyəm biz ölçüsü 1 bir siyahısını var? Auditoriya: qayıt. DAVID Malan: Qayğıkeş. Biz ilk qayıtmaq və indi üçüncü addım - və mən əgər növ ilə təsvir İndi, indi iki oturacaqlar qucaqlayan Bu iki elementlər daxil etmək üçün var. Belə ki, indi təəssüf ki, elementləri məqsədilə həyata. Amma o burada birləşdirilməsi prosesi var çekici almaq üçün başlayır. Uşaqlar yalnız durmaq bilər Belə ki, əgər bir an, mən, siz lazımdır gidiyorum an, sizin kafedrasının arxasında addım. Və əgər Linda, 2 çünki 4-dən kiçik, nə deyil ilk ətrafında gəlir? Orada qalın. Linda Belə ki, ilk ətrafında gəlir. İndi əslində yalnız bir sıra əgər biz yalnız real vaxt onun hərəkət edə bilər Kafedrada bu spot. Belə ki, bəzi sabit etdi ki, təsəvvür addımlar 1 nömrəsi. İndi - Biz sizə qoymaq lazımdır burada birinci yer. İndi siz ətrafında gəlmək bilər həmçinin, biz olacaq yeri iki ola bilər. Və bu kimi, bu hiss olsa belə, Bir müddət alaraq, artıq gözəl nə var ki, sol yarım sol yarısı indi çeşidlənir. Indi əgər Növbəti addım nə idi hekayə daha geri? Auditoriya: Sağ yarısı. DAVID Malan: sağ yarısı Sort. Belə ki, uşaqlar, eləcə də bu var. Siz durmaq bilər Belə ki, əgər yalnız bir an üçün? Və adı nədir? Jess: Jess. DAVID Malan: Jess. OK, belə ki, Jess indi sola sağ yarısının yarısı. Və o ölçüsü 1 bir siyahısı var. O, açıq-aydın sıralaması var. Və adı yenidən? Michelle: Michelle. DAVID Malan: Michelle açıq-aydın deyil ölçüsü 1 siyahısı. O, artıq sıralaması var. Belə ki, indi sehrli, baş ki, birləşmə prosesi. Belə ki, kim birinci gəlmək olacaq? Aydındır Michelle. Geri ətrafında gəlmək bilər əgər. Indi onun üçün mövcud yer Burada bu kafedra arxasında deyil. İndi siz də qayıda bilər, indi iki, aydın olmaq, var yarıya indirir, ölçüsü 2 hər - və yalnız anlatımı xatirinə, əgər boşluq bir az edə bilər - biri yarım burada sol burada sağ yarısı. Hekayə daha geri keçmək. Nə addım gələcək? Auditoriya: Birleştirme. DAVID Malan: Belə ki, indi biz daxil etmək üçün var. Belə OK, belə ki, indi, təşəkkürlə, biz yalnız dörd stul qədər azad. Beləliklə, biz çox yaddaş kimi iki dəfə istifadə olunan, lakin sonra biz flip-flopping arasında verə bilər iki seriallarda. Yəni sayı ilk gəlib? Belə ki, açıq-aydın, Michelle. Belə ki, ətrafında gəlib almaq burada oturacaq. Və sonra 2 saylı açıq-aydın deyil Növbəti, belə ki, buraya. Sayı 4, 6 saylı. Və yenə bir var olsa belə, cəlb gəzinti az bit, həqiqətən, bu, dərhal baş verə bilər - bir hərəkət OK, yaxşı oynadıq. [Gülüş] DAVID Malan: Və indi biz istəyirik olduqca yaxşı vəziyyətdə. Bütün olan sol yarısı input indi sıralanır edilmişdir. Bütün sağ, belə ki, bu uşaqlar idi mənim üstünlüyü - necə bütün qızlar başa etməyib sol və sağ bütün oğlanlar? OK, belə ki, uşaqlar artıq dönüb. Beləliklə, mən size yol deyil Bu addımlar. Biz yeniden bilər görəcəyik Eyni pseudocode. Siz irəlidə getmək və ayağa istəyirsinizsə və uşaqlar, mənə mic verim. Əgər kopya deyil bilərsiniz əgər baxın nə Biz yalnız burada etdi siyahısı digər sonu. Kim, ilk danışmaq lazımdır alqoritmi əsasında? Belə ki, əvvəl işle izah Hər hansı bir ayaq hərəkətləri edir. HOPARLÖR 1: Yaxşı, belə-ci ildən Mən də sol yarısı am sol yarım, mən qaytarın. Sağ? DAVID Malan: Yaxşı. Sonra: - HOPARLÖR 1 DAVID Malan: kim mic növbəti getmək? HOPARLÖR 1: Next nömrəsi. HOPARLÖR 2: Mən sağ yarım Ben Bu sol yarım sol yarım, mən qaytarın. DAVID Malan: Yaxşı. Siz geri. Belə ki, indi iki növbəti up nədir? HOPARLÖR 2: Biz kiçik olan görmək istəyirik. DAVID Malan: Eynilə elə. Biz daxil etmək istəyirik. Biz daxil etmək üçün istifadə etmək niyyətində olduğunuz yer Əgər onlar olmalarına baxmayaraq, daxil açıq-aydın artıq sorted, biz olacaq eyni alqoritm riayət edin. Belə ki, kim geri İlk gedir? 3 Beləliklə, sonra 7. İndi isə mic gedir Bu uşaqlar, OK? HOPARLÖR 3: Mən hüququ yarım Ben sol yarısı, və n-dən az deyil 1, mən yalnız qəbul etmək gidiyorum - DAVID Malan: Yaxşı. HOPARLÖR 4: Mən hüququ yarım Ben sağ sağ yarısı yarısı və Ben da bir adam, mən deyiləm geri gedir. Belə ki, indi biz birləşməsi. HOPARLÖR 3: Beləliklə, biz geri. DAVID Malan: Beləliklə, siz geri daxil. Belə ki, 5 ardından 8, ilk gedir. Ki, olan və indi auditoriya, indi geri üçün addım beynimizdə geri? Auditoriya: Birleştirme. DAVID Malan: Birləşdirən sol yarısı və sağ orijinal sol yarısının yarısı. Belə ki, indi - və yalnız bu aydın etmək kosmik bir az etmək sizin aranızda iki uşaqlar. Belə ki, indi iki siyahıları ki, sol və sağ. Belə ki, necə biz indi uşaqlar daxil daxil yoxdur Oturacaqların ön sırada yenə? 3 ilk gedir. Sonra 5, açıq-aydın. Sonra 7, indi 8. OK, indi biz? Auditoriya: etmədi. DAVID Malan: görülmüş işlər deyil, çünki Aydındır ki, qalan bir addım var. Ancaq yenə də, səbəbi mən bu kullanıyorum "fikrinizi geri" kimi jargon ki, həqiqətən, çünki bu neler. Biz bu addımlar bütün vasitəsilə olacaq lakin biz üçün duraklatarak növ istəyirik daxil anı, dalğıc dərin alqoritmi, bir an üçün duraklatarak, alqoritmi daxil dərin dalış, və indi bizim geri növ var ağıl və bu təbəqələrin bütün əvvəlki halına qaytar biz növ gözləməyə qoymaq etdiyiniz. Belə ki, indi biz ölçüsü 4 iki siyahıları var. Uşaqlar son bir dəfə ayağa bilər və burada yer bir az etmək Bu sol olduğunu aydın etmək orijinal, yarısı orijinal sağ yarısı. Kim birinci sayının ki, biz geri daxil çəkmək lazımdır? Əlbəttə Michelle. Belə ki, biz burada Michelle qoydu. Və kim 2 nömrəli var? 2 nömrəli geri eləcə də gəlir. Sayı 3? Əla. Sayı 4, nömrə 5, 6 saylı, 7 saylı və sayı 8. OK, belə ki, bir çox kimi hiss addımlar, əmin üçün. Amma indi biz təsdiq edə bilmirsinizsə Bakalým sort daxilən ki, bu əsaslı alqoritm, xüsusilə n, biz gördük ki, həqiqətən böyük olur Animasiyalar ilə deyil, əsaslı sürətli. Mən pis, bu alqoritm iddia ən yaxşı halda halda, hətta n dəfə log n böyük Ey edir. Yəni bu bəzi aspekti var n addımlar atır, lakin alqoritmi digər aspekti yerdə var ki iteration ki, loop ki, log n addımlar atır. Nə o bizim barmaq qoya bilər iki ədəd istinad olunur? Bəli, burada - mic Hara gedəcəklər? HOPARLÖR 1: daxil n olacaq iki bizi qopur - mahiyyətcə, iki bölünməsi. DAVID Malan: Eynilə elə. Biz hər hansı bir alqoritm görmək heç bir zaman uzaq, bu model olub , ayırıcı ayırıcı, ayırıcı. Və adətən azaldıla oldu ki, bir şey etmək loqarifmik, log baza 2. Amma bu, həqiqətən, bir şey ola bilər lakin baza 2 daxil edin. İndi n haqqında nə? Düşünürəm ki, biz növ siz bölünür görə bilərsiniz uşaqlar - Siz bölünür, siz bölünür siz bölünür, siz bölünür. Sonunda haradan gelir? Belə ki, birləşmə var. Bu barədə Çünki düşünürəm. Birlikdə səkkiz nəfər daxil zaman, onların yarısı dörd bir sıra var vasitəsi və digər yarısı digər var dörd dəsti, siz necə getmək yoxdur ki, birləşmə etdiyini izah? Yaxşı, uşaqlar bunu ədalətli daxilən. Mən əvəzinə bunu Amma əgər bir az daha metodiki, mən qeyd ola bilər mənim sol ilə ilk leftmost şəxs tərəfdən, leftmost adam da qeyd ki, sağ əli ilə yarım və yalnız sonradan vasitəsilə getdi ən kiçik element də işarə siyahısı, Hər dəfə mənim barmaq hərəkət və ərzində siyahısı boyunca lazımdır. Amma nə bu birləşmə haqqında əsas var proses Mən bu cüt müqayisə alıram edir elementlərinin. Sağ yarısı və soldan yarım, bir backtracking heç alıram. Belə ki, birləşməsi özü edir artıq addımlar n artıq. Və neçə dəfə var idi birləşmə ki, bunu? Yaxşı, n daha çox, yox, və biz yalnız son birləşməsi ilə gördüm. Və belə edir ki, bir şey, əgər , n addımlar n dəfə, və ya əksinə daxil Bu, bizə n dəfə log n vermək olacaq. Və niyə bu daha yaxşıdır? Yaxşı, biz artıq log bilirsinizsə n n daha yaxşıdır - sağ? Biz, ikili axtarış telefon kitab gördüm Məsələn, log n mütləq idi xətti daha yaxşı. Deməkdir n dəfə log n Belə ki, başqa n dəfədən çox mütləq yaxşı n, AKA n kvadrat. Və biz nəticədə hiss budur. Alqış Belə böyük dəyirmi, əgər biz bu uşaqlar üçün ola bilər. [Alqış] DAVID Malan: Və ayrılıq hədiyyələr - Siz nömrələri saxlaya bilər Əgər istəyirsinizsə. Və ayrılıq hədiyyə, adi kimi. Oh, və biz sizə göndərir ki, görüntülər, Michelle. Təşəkkür edirik. Bütün hüquqlar. Bir stress topu özünüzü kömək edir. Və mənə arada, qoparmaq imkan təklif etmək bizim dostumuz Rob Bowden Bu barədə bir qədər fərqli baxış, bu barədə düşünmək bilər-ci ildən bir qədər baş verən addımlar müxtəlif yol. Haqqında Rob nə üçün əslində, set-up bizə göstərmək üçün biz var güman edir ki, artıq ayırıcı qədər həyata səkkiz kiçik siyahıları böyük siyahısı, ölçüsü 1 hər. Belə ki, biz pseudocode dəyişən edirik az yalnız almaq və düzmək üçün işlərin birləşdirilməsi necə əsas fikir. Amma nə çalışan zaman etmək haqqında o var hələ eyni olacaq. Və yenə, burada set-up o var ki, ölçüsü 1 səkkiz siyahıları ilə başlayıb. Belə ki, o olduğu hissəsi buraxılmış sonra əslində log n, log n, log n görülən giriş və bölünməsi. [Video playback] Addım bir it-var. Dəfələrlə addım iki üçün siyahıları cüt birləşməsi. DAVID Malan: Hm. Yalnız audio gəlir mənim kompüter həyata. Nin yenidən cəhd edək. -Just özbaşına hansı seçin - indi biz dörd siyahıları var. Əvvəl əldə edin. DAVID Malan: biz də gedin. -Birləşdirən 108 və 15, biz son up ilə siyahıda 15, 108. Biz, 50 və 4 birləşmə 4, 50 ilə başa. Biz, 8 və 42 birləşdirilməsi 8, 42 ilə başa. Və biz, 23 və 16 birləşdirilməsi , 16, 23 olacaq. İndi bütün siyahıları ölçüsü 2 edir. Qeyd edək ki, hər dörd siyahıları çeşidlənir. Beləliklə, biz birləşmə başlaya bilərsiniz yenidən siyahıları cüt. Biz, 15 və 108 və 4 və 50 birləşdirilməsi ilk, sonra, sonra 15, 4 almaq 50, daha sonra 108. , 23 8, 42 və 16 birləşməsi, biz ilk almaq 8, daha sonra 16, sonra 23, sonra 42. Belə ki, indi biz ölçüsü yalnız iki siyahıları var 4, çeşidlənir hər biri. Belə ki, indi biz bu iki siyahıları birləşməsi. Birincisi, 4 almaq, sonra almaq 8, sonra biz sonra, 16, sonra 15 almaq Sonra sonra 23, 42, 50, 108. [END video playback] DAVID Malan: Yenə, bildiriş, o, heç vaxt müəyyən bir fincan bir çox dəfə toxunub onun hüdudlarından kənara irəlilədikdən sonra. O təkrar heç oldu. Belə ki, o, həmişə, yan hərəkət edir biz n aldığı və var. Niyə bir animasiya qoparmaq imkan Bayaq gördüm, amma bu dəfə birləşməsi sort yalnız diqqət. Mənə irəli getmək və zoom edək burada üzrə. Birinci Mənə bir təsadüfi giriş seçin edək, bu uca, siz bax çeşidləyə bilərsiniz biz verilən əvvəllər üçün etmişdir nə daxil sort həqiqətən edir. Siz və ya bu yarıya indirir almaq, belə ki, qeyd ki, bu rüb və ya bu eighths problem birdən-birə yaxşı forma almaq üçün başlayın. Və sonra nəhayət, siz görmək çox sonuna ki, bam, hər şey birlikdə birləşmə. Belə ki, bu yalnız üç müxtəlif eyni fikri qalır. Amma yalnız uçurum kimi əsas fikir, və ilk sinfində qalib biz elə bölmək qərara idi ki, böyük bir şey, daxil problem ruh eyni bir şey sort lakin kiçik və daha kiçik və daha kiçik və kiçik. Düşünürəm düzmək üçün indi başqa əyləncə yolu Bu barədə, hətta baxmayaraq ki, deyil eyni intuitiv verir anlaşma edir aşağıdakı animasiya. Beləliklə, bu birlikdə qoymaq bir video biri ki, müxtəlif bağlı üçün müxtəlif əməliyyatları ilə səsləri durub sırala birləşməsi sort üçün, digər bir neçə. Belə ki, bir anda, mən Play olmaq üçün gedirəm. Bu uzun haqqında bir dəqiqə var. Və hələ də görə bilərsiniz, hətta nümunələri, siz bu dəfə baş Bu alqoritmlər nə də eşitmək fərqli və həyata qədər müxtəlif nümunələri. Bu durub sortudur. [Melodiyalar PLAYING] DAVID Malan: Bu yenidən çalışır hər element əlavə etmək üçün o aid olduğu daxil. Bu bubble sortudur. [Melodiyalar PLAYING] DAVID Malan: Və hissi çeşidləyə bilərsiniz nisbətən az bunu necə işləmək hər addım. Bu bıkdırıcılıq kimi səslənir edir. [Melodiyalar PLAYING] DAVID Malan: Bu seçim sortudur, Biz istəyirik element seçin yerləşir daha keçir və təkrar və əvvəlində qoymuşdur. [Melodiyalar PLAYING] DAVID Malan: Bu birləşməsi sortudur, hansı həqiqətən hiss başlaya bilərsiniz. [Melodiyalar PLAYING] [Gülüş] DAVID Malan: gnome deyilən şey biz baxdı olmayan sort. [Melodiyalar PLAYING] DAVID Malan: Yəni, indi mənə bax bildirin Siz inşallah tərəfindən kimi çevirirsən Mən bir az sürüşmək bilər musiqi, Burada riyaziyyat bit. Belə ki, biz dördüncü yolu vardır bu nə deməkdir haqqında düşünmək sürətli fərqli ola funksiyaları biz əvvəl gördüm ki. Və sizdən kurs gələn edirsinizsə, riyaziyyat fon, siz həqiqətən artıq bəlkə bilirik ki, siz bu texnika bir müddət sillə bilər - yəni recursion, funksiyanı ki, birtəhər özünü çağırır. Və yenə ki, birləşmə sort Xatırladaq pseudocode mənada recursive idi ki, birləşmə sort nin addımlardan biri Sıralama zəng etmək üçün idi - ki, özü edir. Amma təşəkkürlə, çünki biz saxlanılır , sort zəng və ya sort daxil Xüsusilə, daha kiçik və daha kiçik və kiçik siyahısı, biz nəhayət dediyimiz olacaq nə üçün bottomed thanks bir baza halda, sabit kodlu halda ki, siyahısı kiçik olarsa, az 2 deyib bu halda, yalnız dərhal qayıtmaq. Ki, xüsusi halda yox idi varsa, alqoritm alt həyata, heç vaxt və həqiqətən bir nəzərə almaq olardı həqiqətən əbədi sonsuz loop. Amma biz indi qoymaq istədilər güman Bu bəzi nömrələri, yenə, n istifadə giriş və ölçüsü kimi. Və mən nə var, xahiş etmək istəyirdi cəlb ümumi vaxtını birləşməsi sort çalışan? Və ya ümumiyyətlə, nə var vaxtında dəyəri? Yaxşı ki ölçmək üçün olduqca asandır. N az 2 olarsa, vaxt cəlb n elementləri çeşidlənməsi ilə, N 2 olduğu 0 edir. Biz yalnız geri edir. Edilməsi üçün heç bir iş yoxdur. İndi arguably, bəlkə bu bir addım və ya iki məbləğ anlamaq üçün addımlar işləmək, lakin bu 0 kifayət qədər yaxın ki, Mən heç bir iş demək gidiyorum siyahısı, kiçik əgər tələb maraqsız olunacaq. Amma bu halda maraqlıdır. Bu recursive halda filialı oldu başqa bildirib ki, pseudocode, sort sol yarısı, sağ düzmək yarım, iki yarıya indirir daxil. İndi niyə bu ifadə edir ki, xərc təmsil? Yaxşı, n T yalnız deməkdir n elementləri düzmək üçün vaxt. Və sonra da sağ tərəfində orada işarə bərabər, n T bölünür 2 nə dəyəri istinad olunur? Sol yarım çeşidlənməsi. 2 bölünür n digər t ehtimalla üçün dəyəri istinad sağ yarım Sıralama. Və sonra plus n? Ki, birləşmə edilir. Çünki iki siyahıları, biri varsa ölçüsü 2-dən çox n və başqa ölçüsü n 2-dən artıq, siz mahiyyətcə toxunmaq yalnız Rob kimi bu elementlərin hər biri Fincan hər toxunub və yalnız biz hər qeyd kimi səhnədə könüllü. Belə n birləşməsi hesabına edir. İndi təəssüf ki, bu formula özü recursive edir. N əgər Belə ki, demək, sual 16, əgər səhnədə 16 nəfər var və ya video 16 fincan, neçə ümumi addımlar onlara düzmək üçün sürer birləşməsi növ ilə? Bu, həqiqətən, açıq-aydın bir cavab deyil İndi düzmək, çünki recursively bu formula cavab. Mənə təklif edək, çünki Lakin ki, OK biz aşağıdakı ki. 16 nəfər sort və ya cəlb vaxt 16 fincan təmsil olunacaq gedir ümumiyyətlə 16 T kimi. Amma o görə, bərabərdir bizim əvvəlki formula, 2 dəfə artıq vaxt bu sort edir 8 fincan plus 16. Və yenə, üstəgəl 16, birləşdirmə zamanı və 8 iki dəfə T edir sol yarısı və sağ yarım düzmək üçün vaxt. Ancaq yenə də, bu, kifayət deyil. Biz dərin dalış lazımdır. Bu, cavab deməkdir sual, 8 T nədir? Quyu 8 T yalnız 2 4 plus 8 dəfə T. Yaxşı, 4 T nədir? 4 T 2 plus 4 yalnız 2 dəfə T-dir. Yaxşı, 2 T nədir? 2 T 1 plus 2 yalnız 2 dəfə T-dir. Və yenə, biz əldə cür istəyirik Bu dövrü yapışdırılır. Amma bu barədə hit ki, baza halda deyilən. 1 T ne Çünki, biz iddia idi? 0. Belə ki, indi nəhayət, biz geri işləyə bilər. 1 T 0, mən indi bir geri bilərsiniz Bu oğlan xətti və mən 1 T 0 plug. Belə ki, o deməkdir ki, o, 2 dəfə sıfra bərabər başqa 0, plus 2 kimi tanınır. Və belə ki, bütün ifadə 2-dir. Mən onun cavab 2 T, almaq İndi əgər 2, orta xətt, T onu yerləşdirin 4, mənə 2 dəfə verir 2 plus 4, 8 belə. Mən sonra əvvəlki 8 plug edin xətti, mənə 2 dəfə 8, 16 verir. Və biz sonra ilə davam edərsə, 24 16 əlavə, nəhayət, biz almaq 64 dəyər. İndi özü və sort bilir ki, n notation üçün heç bir şey ki, böyük O, biz etdiyiniz Omega bəhs edilmişdir. Lakin bu 64 həqiqətən çıxır ki, 16 giriş ölçüsü, 16 baza 2 daxil edin. Bu, bir az yad əgər yalnız geri hesab edirəm ki, və geri gəlmək lazımdır siz nəhayət. Bu günlük baza 2 olarsa, bu, 2 kimi nə siz 16 verir qaldırdı? Oh, 4, belə ki, 16 dəfə 4 var. Və yenə bir böyük deyil, bu halda bir dumanlı yaddaş sort indi. Amma indi üçün, iman götürmək 16 günlük 16 64 edir. Və, həqiqətən, bu sadə ağlı başında olma ilə yoxlamaq, biz təsdiq etdik - lakin rəsmi sübuta - ki, birləşmə və çalışan zaman Sıralama həqiqətən n n daxil edin. Belə ki, pis deyil. Bu daha mütləq yaxşı Biz bu günə qədər görülən və sonra alqoritmlər biz kullanılarak geliştirilebiliyor etdik, çünki bu, bir var recursion adlandırılan bir texniki. Ki, daha, lakin daha maraqlı ayırıcı və fəth anlayışı. Yenə, həqiqətən həftə 0 stuff ki, İndi hətta bir təkrarlanan olunur daha çekici yol. İndi bir əyləncə az həyata, siz var əgər Bunu heç vaxt - və yəqin olmazdı, çünki normal sort nəfər bunu düşünmürəm. Amma google.com və əgər Əgər Mən bir şey öyrənmək istəyirəm recursion daxil edin. [Gülüş] [Daha çox gülüş] DAVID Malan: Bad zarafat yavaş-yavaş yayılır. [Gülüş] DAVID Malan: Just halda, bu, var. Mən bunu yanlış yazım vermədi, və zarafat var. Bütün hüquqlar. Siz yanında insanlara izah əgər kifayət qədər yalnız hələ tıklayan deyil. Lakin recursion, ümumiyyətlə, aiddir zəng funksiyası prosesinə özü və ya daha çox, ümumiyyətlə, bir-birindən ayıran ola bilər ki, bir şey problem eyni həlli ilə tədricən həll nümayəndəsi problemləri. Yaxşı, edək dəyişiklik Gears yalnız bir an. Biz müəyyən cliffhangers də başa istəyirəm belə müəyyən başlamaq edək mərhələ, bir neçə dəqiqə çox sadə fikir - iki element dəyişdirmə ki, sağ? Bütün bu alqoritmlərin biz oldum keçmiş neçə söhbət mühazirələr bəzi cəlb dəyişdirmə növ. Bu gün onların əldə görüntülenmeyecektir edilib öz kafedra həyata gəzir, amma kodu, biz ki, yalnız bir array bir element almaq və başqa daxil Plop bu. Biz bunu haqqında necə gedirik? Yaxşı, mənə davam və yazmaq imkan burada tez program. Mən irəli getmək və nə üçün gidiyorum Bu, aşağıdakı kimi. Gəlin bu zəng - Bu bir zəng etmək üçün nə istəyirsiniz? Əslində, yox. Mənə geri edək. Mən bunu istəmirəm hələ cliffhanger. Bu fun korlamaq olacaq. Əvəzinə bunu edək. Mən bir az yazmaq istəyirəm Güman proqram və indi bu əhatə recursion ideyası. I növ var qabaqda özümü var. Mən aşağıdakı gedirəm. Birincisi, sürətli, standart io.h daxildir cs50.h. habelə bir daxil Və sonra irəli getmək gidiyorum və int əsas etibarsız elan adi qaydada. Mən fayl misnamed sonra həyata, belə ki, mənə yalnız burada belə bir. c uzadılması əlavə etmək istərdim biz düzgün tərtib edə bilər. Bu funksiya başlayın. Və funksiyası Mən yazmaq istəyirəm Sadəcə, soruşur ki biridir sonra bir sıra istifadəçi və əlavə arasında bütün nömrələri sayı və, demək, 0. Belə ki, birinci mən irəli getmək gidiyorum və int n bəyan edir. Sonra bəzi kodu kopyalayın ki, biz bir müddət istifadə etdik. Şey doğru olsa. Mən bir anda ki, qayıda bilərsiniz. Mən nə etmək istəyirsiniz? Mən printf müsbət demək istəyirəm tam edin. Və sonra mən gidiyorum n int almaq olur deyirlər. Belə ki, yenə də, bəzi Demirbaş kodu biz əvvəl istifadə etdiyiniz. Və mən bunu gidiyorum n az 1 edir. Belə ki, bu təmin edəcək istifadəçi Mənə bir müsbət tam verir. İndi isə aşağıdakı gedirəm. Mən nömrələri bütün əlavə etmək istəyirəm n, və ya 0 və n 1 arasında və equivalently, ümumi məbləği almaq üçün. Belə ki, böyük sigma simvolu Siz geri bilər. Beləliklə, mən birinci çağırışının bunu gidiyorum sigma adlı funksiyası, n bu keçən, sonra mən gidiyorum printf demək, cavab hüququ vardır. Belə ki, qısa, mən almaq və istifadəçi Int. Mən bunu müsbət var təmin edir. Mən dəyişən deyilən cavab bəyan bu növü int və mağaza qaytarılması giriş kimi n keçən sigma dəyəri. Və sonra mən ki, cavab çap. Təəssüf ki, sigma səslənir, hətta ola bilər ki, bir şey kimi ki, math.h fayl, onun bəyannamə, bu, həqiqətən deyil. Belə ki, OK. Mən bu özümü həyata keçirə bilərlər. Mən adlı bir funksiyası həyata gidiyorum Siqma və bu almaq olacaq parametri - Gəlin yalnız m zəng, yalnız belə fərqli. Və sonra burada, mən demək gidiyorum m 1-dən az olduğu halda yaxşı, - bu, çox proqram maraqsız. Beləliklə, mən davam gedən və alıram dərhal 0 qaytarın. Bu, yalnız bütün əlavə etmək üçün mənada etmir 1 və m əgər arasında nömrələri özü 0 və ya mənfi. Və sonra irəli getmək gidiyorum və çox iteratively bunu. Mən köhnə məktəb bu cür etmək gidiyorum və mən irəli getmək gidiyorum və mən gidiyorum ki, 0 olmağa məbləğ bəyan edir. Sonra Mən gedirəm int loop üçün - və mənə bu, bizim uyğun edək distribution kodu, belə surəti evdə. int i qədər 1 olur i daha az və ya m bərabərdir. i plus plus. Və sonra daxili loop üçün bu - biz demək olar ki, orada etdiyiniz - cəmi məbləğin plus 1 olur. Və sonra məbləği geri gedirəm. Beləliklə, mən tez bunu olduqca admittedly. Ancaq yenə də, əsas funksiyası olduqca var biz var Məcəlləsinə əsasən, sadə İndiyədək yazılı. Müsbət almaq üçün ikili loop istifadə edir istifadəçi Int. Mən sonra yeni funksiya ki, int keçmək n, yenidən, bu zəng, sigma çağırıb. Və mən qaytarılması dəyər, cavab saxlamaq Hal-hazırda qara qutusu dəyişəndə, sigma kimi tanınan cavab çağırıb. Sonra o yazdırın. Indi hekayə davam etsəniz, sigma necə həyata keçirilir? Mən aşağıdakı kimi həyata keçirilməsi üçün təklif. Səhv yoxlanılması Birincisi, bir az istifadəçi deyil əmin etmək üçün Mənimlə messing və keçən bəzi mənfi və ya 0 dəyəri. Sonra adlı dəyişən elan məbləği və bu 0 seçin. İndi Mən bərabər hərəkət başlayacaq 1 Bütün yol və m o cümlədən, Mən bütün daxil etmək istəyirəm, çünki m vasitəsilə bir nömrələri, daxil. Və daxili loop üçün bu, mən yalnız bunu məbləği indi nə edir, üstəgəl i dəyəri. I Plus dəyəri. Bir kənara kimi, bu görmürsənmi olduğunuz halda əvvəl, bəzi sintaktik şəkər var bu xətt üçün. Üstəgəl i təşkil kimi, bu yeniden redaktə edəbilərsiniz yalnız özüm bir neçə tuş vuruşlarını saxlamaq və bir az soyuq baxmaq. Lakin bütün deyil. Bu funksional eyni şey var. Təəssüf ki, bu Məcəlləsinin hələ tərtib etmək niyyətində deyil. Mən necə sigma 0, etmək çalıştırıyorsanız Mən yelled almaq üçün gedir? Nə kimi deyil olacaq? Auditoriya: [işitilemez]. DAVID Malan: Bəli, mən bəyan etməyib üst, sağ? up funksiyası C, mehriban axmaq olduğunu yalnız ki, Bunu demək nə, və ki bunu etmək lazımdır. Burada Enter düyməsini basın, əgər belə, mən gedirəm sigma barədə xəbərdarlıq örtülü almaq Bəyannamə. Oh, heç bir problem. Mən üst qədər getmək bilər, və mən bütün sağ, demək, bir dəqiqə gözləyin. Sigma qaytarır ki, bir funksiyası var bir int və bunu gözləsin bir giriş, nöqtəli vergül kimi int. Yoxsa Mən bütün funksiyası qoymaq bilər əsas yuxarıda, amma ümumilikdə, mən had bu, çünki ona qarşı gəlir həmişə üst belə olan əsas üçün gözəl sağ dalış və bilə bilməz nə proqram ilk əsas oxuyaraq əməlindəndir. Belə ki, indi mənə ekranı silmək imkan verir. Yeniden yapmak sigma 0. Bütün kontrol görünür. Mənə sigma 0 run edək. Müsbət inter. Mən bunu sayı verərəm 3 sadə saxlamaq. Belə ki, mənə 3 verməlidir plus 2 plus 1, belə ki, 6. Daxil edin və həqiqətən Mən 6 almaq. Mən böyük bir şey edə bilərsiniz - 50, 12, 75. Bir toxunan kimi, Mən gedirəm həqiqətən böyük kimi gülməli bir şey sayı, Oh, həqiqətən işləyib ki, - eh, mən doğru hesab etmirəm. In nəzər salaq. Nin həqiqətən bu mess edək. Bu problem var. Nə olacaq? Kod pis deyil. Bu hələ xətti var. Vıyıltı baxmayaraq, yaxşı təsir edir. Nə olacaq? Mən bunu eşidəndə əgər əmin deyil. Belə çıxır - və bu bir kənara kimi. Bu etmək üçün əsas deyil recursion ideyası. Mən çalışıram, çünki çıxır , ən çox belə bir böyük sayı təmsil edir güman ki, təhrif edib müsbət deyil nömrəsi kimi C, ancaq mənfi nömrəsi. Biz bu barədə danışmışıq, lakin onu mənfi nömrələri var çıxır Bundan əlavə dünyada müsbət nömrələri. Və siz vasitələri mənfi sayı təmsil edir mahiyyətcə, bir istifadə olunur göstərmək üçün xüsusi bit mənfi üzərində müsbət. Qeyd edək ki, bir az daha kompleks var amma ki, əsas fikirdir. Belə ki, təəssüf ki, C bir qarışıqdır əgər həqiqətən mənasını həmin bit, oh, bu mənfi, mənim loop Burada, məsələn, həqiqətən, heç vaxt dayandırmaq gedir. Mən, həqiqətən, bir şey çap edilmişdir Belə ki, əgər təkrar, biz ki, bir çox görürük. Ancaq yenə də, bu baxımdan yanaşı edir. Bu, həqiqətən, yalnız bir növ deyil biz lazımdır ki, intellektual maraq nəhayət geri. Amma hələlik bu bir doğru həyata keçirilməsi biz güman əgər ki, istifadəçi ints təmin edəcək ki, ints ərzində uyğun. Amma ki, bu kodu, səmimi iddia çox daha çox sadəcə edilə bilər. Əl məqsəd bir sıra almaq Əgər kimi m və bütün əlavə İT və 1, və ya əksinə arasında nömrələr 1 və o, mən iddia Mən birləşməsi ki, bu fikir borc bilər ki, sort bir problem edirdi ki, var idi Bu ölçüsü və onun bölünməsi kiçik bir şey. Bəlkə yarım, lakin kiçik, lakin representatively eyni. Eyni fikir, lakin kiçik bir problem. Beləliklə, mən, həqiqətən, Ben - Mənə bu faylı bildirin fərqli buraxılış nömrəsi ilə. Biz bu versiyası zəng edəcəyik 1 əvəzinə 0. Və Mən, həqiqətən, can iddia bu cür bu reimplement mind-əyilmə yol. Mən tək bir hissəsi tərk etmək gedirəm. M azdırsa demək gidiyorum çox və ya 0 hətta bərabər - Mən yalnız bir az olmaq gidiyorum daha anal bu dəfə - mənim səhv yoxlanılması ilə Mən irəli getmək və 0 qayıtmaq üçün gedirəm. Bu əsassız deyil. Mən sadəcə qərar qəbul edirəm əgər istifadəçi Mənə bir mənfi verir, Ben 0 qaytarılması və onlar oxumaq olmalıdır sənədlərin daha yaxından. Else - Mən gedirəm nə görürsünüz. Else I m plus qayıtmaq üçün gedirəm - m sigma nədir? Yaxşı, m plus m minus 1 Sigma, plus m mənfi 2, üstəgəl m mənfi 3. Mən ki, bütün yazmaq istəmirəm. Niyə ayaqla zərbə yalnız deyil? Recursively bir qədər ilə özüm zəng kiçik problem, nöqtəli vergül, və bir gün zəng? Sağ? İndi burada da hiss və ya narahat ola bilər Bu Ben bir sonsuz loop ki, Mən həyata edirəm vasitəsi fahişəliyə cəlb edilməsi maddələri, zəng sigma tərəfindən sigma. Amma ki, mükəmməl OK mən bir xətləri olan əlavə qabaqda fikir? Auditoriya: [işitilemez]. DAVID Malan: 23 26, hansı Mənim əgər şərtdir. Haqqında gözəl nə Çünki burada toplama işlemi, mən saxlamaq çünki verilməsi sigma kiçik problemləri, kiçik problemləri, kiçik - bu deyil yarısı ölçüsü. Bu kiçik yalnız bir körpə addım amma ki, OK. Nəhayət, biz işləmək lazımdır, çünki aşağı 1 və ya 0 yolumuza. Və bir dəfə biz 0 hit, sigma deyil artıq özü zəng etmək üçün gedir. Bu dərhal 0 qayıtmaq olacaq. Belə ki, təsiri, külək siz sort bu halda qədər nəzərə, m plus əlavə edir m mənfi 1, üstəgəl m mənfi 2, üstəgəl m minus 3, üstəgəl nöqtə, nöqtə, nöqtə, m minus m, nəticədə siz 0 verilməsi və təsiri bütün əlavə etmək üçün sonda edir birlikdə bu şeylər. Beləliklə, biz, recursion ilə yoxdur problemi həll ki, əvvəl həll edə bilməmişik. Həqiqətən, versiyası, bu 0 və hər tarixi problem, caiz olmuşdur yalnız loops istifadə və ya isə loops və ya oxşar yaradır. Amma recursion, mən daresay, bizə verir haqqında düşünür farklı bir yol problemləri, biz edə bilərsiniz vasitəsi əgər problem, bir şey onu bölmək qədər bir şey qədər böyük kiçik, biz bunu həll edə bilər ki, iddia bəlkə bir az daha zərif baxımından dizayn daha az kodu ilə və bəlkə hətta ki, problemlərin həlli biz nəhayət rəftar kimi, daha ola sırf iteratively həll oldu. Mən ki Amma cliffhanger bizə tərk etmək istəyirəm bu idi. Mənə davam və açmaq edək bir fayl up - Əslində, getməmə və Bu real sürətli bunu. Mənə davam və təklif edək aşağıdakı. Bu gün code arasında bu faylı burada. Bu bir, noswap. Belə ki, bu bir axmaq az proqramı Mən iddia etmək qədər çırpılmış aşağıdakı. Əsas, bu ilk bir bəyan int x adlandırıldı və verir 1 dəyər. Sonra bir int y elan edir və bu dəyəri 2 atar. Sonra x və y nə çap edir. Sonra, nöqtə nöqtə nöqtə dəyişdirmə, deyir. Sonra bir funksiyası zəng iddia x keçən və svop adlı ki, inşallah ki, fikir olan y, x və y qayıdacaqlarını müxtəlif, qarşı. Sonra dəyişdirildikdə iddia! ünlem işareti ilə. Sonra x və y çap edir. Lakin bu çıxır ki, bu çox aşağı sadə nümayiş burada həqiqətən arabası deyil. Mən müvəqqəti elan alıram baxmayaraq dəyişən və müvəqqəti bir qoyaraq ki, sonra reassigning alıram b dəyəri - Mən var, çünki ki, ağlabatan hiss temp bir surəti saxlanılır. Sonra bərabər b güncelleyin temp-ci ildə nə oldu. Bir hərəkət shell oyun bu sort Bu istifadə edərək daxil daxil b və b orta-man temp hiss çağırıb mükəmməl məqbul. Mən bu çalıştırdığınızda Amma iddia kodu, İndi nə olacaq kimi - Mənə irəli getmək və burada yapışdırıb imkan verir. Mən bu noswap.c zəng edəcəyik. Adı təklif kimi, bu deyil düzgün proqram olacaq. Noswap olun. / No Swap. x 1, y, 2 dəyişdirmə, dəyişdirildikdə. x 1, y 2-dir. Bu, hətta kökündən yanlış Bu mükəmməl görünür baxmayaraq mənə ağlabatan. Və orada bir səbəb, lakin biz deyilik yalnız hələ səbəbi ortaya gedir. Mən istəyirdim ikinci cliffhanger indi sizi tərk etmək, bu kupon kodları növ elan. Mərhum gün ilə yenilik bu il qeyri-mənasız sayı təhrik etdi suallar, hansı idi bizim niyyətimiz. Bu kupon kodları niyyəti, qovuşdurmağımız siz problemin bir hissəsidir əgər Beləliklə, əlavə gün alınması, erkən müəyyən uşaqlar kömək etmək üçün həqiqətən özünüzü erkən, sort başlamaq Siz incentivizing tərəfindən. Bizə arasında yük yaymaq kömək edir ofis saat daha yaxşı ki, bu qazan-qazan növ var. Təəssüf ki, mən göstəriş edirəm Belə ki, tarix üçün çox aydın, olmamışdır Mən bu həftə sonu geri getdi və yenilənir etmək üçün daha böyük, bolder mətn spec Bu kimi güllə izah edir. Və yalnız, daha açıq demək Default, problem dəstləri Cümə axşamı bağlıdır günorta saatlarında proqramları təşkil edir. Siz hissəsi başa erkən başlamaq edin 12:00 Çərşənbə tərəfindən müəyyən edilmiş problem PM, bir kupon aid olan hissəsi kodu, fikri siz uzada bilər ki, üçün sizin son tarix P Cümə gününə qədər seçin. Bu bit P kiçik bir hissəsi off edir adətən nə nisbətən müəyyən böyük problem və siz almaq özünüz əlavə gün. Yenə də, bu barədə düşünürük siz alır problem set, siz olur ofis saat tez. Lakin kupon kodu problem hələ də siz onu təqdim etməyən belə, tələb olunur. Amma daha compellingly bu. (Mərhələ Whisper) və bu insanlar tərk erkən peşman mý var. Kimi balkon insanlar var. Üzrə insanlar əvvəlcədən üzr istəyirik olacaq səbəblərdən balkon yalnız bir anda sil. Beləliklə, biz bir üçün uğurlu Da CS50 keçmiş baş müəllim yoldaşları dropbox.com adlı bir şirkət. Onlar çox səxavətlə bir hədiyyəsində tapıldı Bu çox yer üçün bura kupon kodu, dən olan qədər adi 2 gigabaytlık. Ona görə də mən fikir nə biz bu barədə nə olardı final qeyd, bir yarışma bir az nə edir yalnız bir anda, biz ortaya çıxaracaq vasitəsi qalib edən kupon var Əgər onların to kodu veb-bu yazın və voiture, almaq Sizin üçün bütövlükdə çox Dropbox yer cihaz və şəxsi faylları. Və ilk kim iştirak etmək istəyirəm Bu rəsm? OK, indi ki, daha çox əyləncə edir. Bu 25 gigabyte qəbul edən şəxs kupon kodu - uzaq olan Mərhum daha çekici İndi, bəlkə də, gün - bir üst oturacağı olan biridir var olan altında oturacaq yastığı ki, kupon kodu. İndi altında ola bilər Sizin oturacaq yastığı. [Video playback] -Bir, iki, üç. [Qışqırmağa] -Siz avtomobil almaq! Siz avtomobil almaq! DAVID Malan: Biz görəcəksiniz Çərşənbə günü siz. -Siz avtomobil almaq! Siz avtomobil almaq! Siz avtomobil almaq! Siz avtomobil almaq! Siz avtomobil almaq! DAVID Malan: Balkon insanlar gəlib aşağı burada ön, figüran olduq yerləşir. -Hər bir avtomobil olur! Hər bir avtomobil olur! [END video playback] Dastançı: növbəti CS50 hazırda - HOPARLÖR 5: Gosh Gosh Gosh Gosh Aman Gosh Gosh Gosh Gosh Gosh Gosh - [UKELELE Plays]