Даг LLOYD: Значи во CS50 научивме за различни сортирање и пребарување алгоритми. А понекогаш тоа може да биде малку незгодно да се задржи пратите на она што алгоритам што прави. Ние сме навистина само обезмастено површината премногу, постојат многу други пребарување и алгоритми за сортирање. Така што во овој видео ајде само да потрае неколку минути да се обиде да го дестилираат секој алгоритам надолу за да нејзините основни елементи за да можете да се сеќавам на повеќето важни информации за нив и да бидат способни да ги артикулираат разлики, ако е потребно. 

Првиот е селекција вид. Основната идеја зад селекција вид се најде најмалиот несортиран елемент во низа и го трампа со Првиот несортиран елемент на таа низа. Кажавме дека најлошото се кандидира за време на која беше n квадрат. И ако сакате да се потсетиме зошто, да ги преземе Еден поглед на избор на вид на видео. Време најдобар случај бегство е исто така n квадрат. 

Меур вид, идејата зад кои едно е да се разменуваат со соседните парови. Значи тоа е клучот, кој ви помага запомните разликата тука. Селекција вид е, досега, најдете smallest-- меурот вид е разменуваат со соседните парови. Ние разменуваат со соседните парови на елементите, ако тие се надвор од употреба, кои ефикасно меурчиња поголеми елементи на правото, и во исто време, исто така, таа започнува да се движи помали елементи од лево. Време случај рок најлош случај на меур вид е N на квадрат. Време најдобар случај бегство на меур вид е n. Бидејќи во таква ситуација ние не actually-- ние не би можеле да треба да се направи било размена на сите. Ние само треба да се направи една поминат низ сите n елементи. 

Во вметнување вид, Основната идеја тука се менува. Тоа е клучниот збор за вметнување вид. Ние ќе треба да се чекор еднаш преку низа од лево кон десно. И што и да правиме, ние сме ќе се префрлат елементи веќе видовме се направи простор за помали, кои треба да се вклопи некаде назад во таа подредени дел. За да можеме да се изгради една низа сортирани елемент во исто време, од лево кон десно, и ние смена работите да се направи простор. Времето на најлош случај на бегство вметнување вид е N на квадрат. Време најдобар случај се кандидира е n. 

Логирате sort-- клучниот збор тука е поделена и се спојуваат. Тргнавме целиот низ, без разлика дали тоа е шест елементи, осум елементи, 10.000 elements-- ние го подели надолу за половина, на половина, за половина, додека имаме под низа од n еден елемент низи. А во собата на еден елемент n низи. Па почнавме со една 1000-елемент низа, а ние се дојде до точка каде што има 1.000 еден елемент низи. Тогаш почнуваме да се спојат овие суб низи повторно заедно во правилен ред. Па ние се две една елемент низи и создаде две-елемент низа. Земаме две со две низи елемент и да се создаде четири-елемент на низата и така натаму и така натаму се додека ние сме повторно го обновил еден n елемент низа. 

Времето на најлош случај на бегство спојат вид е n log n пати. Имаме n елементи, но овој процес рекомбинирачките зема логирате n чекори за да добие назад кон целосна низа. Најдобар случај кандидира време е исто така n најавите n бидејќи овој процес навистина не грижа дали низата беше подредени или да не се започне со. Процесот е ист, има нема начин да краток спој работите. Така n log n во најлош случај, n log n во најдобар случај. 

Ние разговаравме за двајца пребарување алгоритми. Така линеарно пребарување е за процесирањето. Ние се продолжи низ низа еднаш, од лево кон десно, во обид да се најде бројот кои ги барате. Најлош случај кандидира време е голема О на n. Тоа би можело да ни потрае процесирањето низ секој елемент да се најде на елементот што го бараме за, било на последното место, или воопшто не. Но, ние не може да се потврди дека до Ние гледаше во сè. m на најдобар случај, ние веднаш се најде. Време најдобар случај на бегство линеарно пребарување е омега на 1. 

И на крај, имаше бинарни пребарување, која бара избрани низа. Се сеќавам дека е многу важен предвид кога се работи со бинарни пребарување. Тоа е предуслов за користење it-- низата дека барате преку мора да се решат. Инаку, на клучен збор е раздели па владеј. Подели на низа во половина и елиминира половина на елементи секој пат како што напредувате низ. Затоа што на оваа поделба и освојување и поделба на работите на половина пристап, време најлош случај бегство на бинарни пребарување е најавите n, што е значително подобра од n линеарно пребарување е. Време најдобар случај се кандидира е уште еден. 

Ние може да го најдете веднаш прв пат, ние правиме поделба, но, повторно, се сеќавам дека иако бинарни пребарување е значително подобро од линеарно пребарување со самото тоа што наспроти најавите n n, можеби ќе треба да се оди преку работата на сортирањето вашиот низа Првиот, кој Може да се направи тоа помалку ефикасни во зависност од големината на процесирањето подредени. 

Јас сум Даг Лојд, ова е CS50.