HOPARLÖR: Bütün sağ, bu CS50 edir. Bu həftə üç sonu, və əgər siz artıq istifadə deyil nahar olacaq bilirik ki, harada həmişə olduğu kimi bu Cümə yaxşı söhbət edə bilərsiniz Yanğın və Ice və ərzaq CS50 nin bəzi işçiləri və sinif yoldaşları. Burada bu URL rəhbərlik. 

İndi geri, və ya edə bilər tezliklə ilə tanış ola bilər, Burada bunlar, hansı sonunda verilir çox siniflər üçün dövr. Qondarma imtahan mavi kitab olan imtahan üçün cavab yazın. İndi mən burada var 26 belə Onların hər biri haqqında mavi kitab, Z. vasitəsilə bir ad, A yazılıb And həqiqətən adları sadə, A ki Z. vasitəsilə Və bir əl bu gün də qol nə davam olacaq biz deyil, bazar ertəsi günü başlayan qədər kodu baxaraq, lakin həqiqətən fikir və problem həll axtarır. Məqsədlərindən biri və Bu kurs vədlər daha sizə öyrətmək üçün diqqətlə, daha ardıcıl, və daha səmərəli problemləri həll etmək. Biz, həqiqətən, həqiqətən edə bilərsiniz Hətta kodu xətti toxunmadan. Mən filler bir neçə var up bu gün burada, narıncı və mavi, biz bir könüllü əldə edə bilər, bəlkə uzaq geri adi dən çox. Necə orada haqqında, aşağı gəlir. Olan məqsəd olacaq kömək plus burada bu imtahan idarə. Sizin adınız nədir? 

Auditoriya: Mary Beth. HOPARLÖR: Mary Beth qədər gəlib. Mənə sizin üçün burada mikrofon almaq edək. Görüşmək Nice. 

Auditoriya: Nice görüşmək. HOPARLÖR: Bütün sağ, mən var burada mavi kitab Z, və mən ki, iddia gedirəm Mən şagirdlərdən biri var və onlar bir qədər təsadüfi gələn edirik üç saat imtahan blokunun sonunda, onlar bəzi sona edirik bu kimi yarı təsadüfi sifariş. İndi yalnız bir anda iş gedir Bu onlar almaq nə əslində be-- üçün sonunda çevirdi sinif, çox güman ki,. Sizin iş indi olduqca olacaq sadəcə, bizim üçün bu mavi kitab sort A-dan Z. vasitəsilə 

Auditoriya: Oh, bu əbədi almaq olacaq. 

HOPARLÖR: Biz izləyəcək Bunu kimi, heç bir təzyiq. Auditoriya: Xeyr, heç bir təzyiq və ya bir şey. 

HOPARLÖR: Və əyləncə üçün, üzrə timer qoymaq bildirin. 

Auditoriya: Belə fun, çox fun. 

HOPARLÖR: Mən sizin üçün mikrofon aça bilər. Bütün hüquqlar, biz yalnız bizim sürəti iki dəfə etdik. Bu vaxt, belə ki, mənə nə yaradır ili Mary Beth üçün sual olacaq o nə edir ki, necə o, bu həll gedir? Və əslində, siz ola bilər Heç bir şey haqqında fikir Seçdiyiniz zaman belə sadə bu kimi 26 kitab up, təbii olan var onlara sifariş. Prosesi nədir ki, siz həqiqətən istifadə? Kifayət qədər təsadüfi yalnız gördüğünüz ilk bir toplama və onun yerinə qoyaraq? Ilk ətrafında əllərinizi hərəkət edirsiniz A sonra B axtarır axtarır? Bir nəzər etməyin tərəfindən onlara yan cüt və yalnız bir dəqiqə gözləyin, bu demək doğru deyil, və sonra sifariş dəyişdirmək? Biz bazar ertəsi artıq gördüm bir sıra yollar var ki, biz bunu edə bilərsiniz həqiqətən biz burada sonuna yaxın, Mən bəlkə qeyd edəcək nə Mary Beth edir. Biz görünür bir neçə payaların var, bir üç kiçik, bir böyük. 

Auditoriya: Mən onları sifariş edirəm Mən iki məktublar tapmaq zaman bilirəm ardıcıllıqla birlikdə ki, Mən ki, mən onlara birlikdə qoymaq saxlanılması barədə narahat var kitab bütün sıra track. Bu, ilk deyil, oh, yalnız var Mən burada bu yığını var. Demək olar ki, kimi Belə ki,: HOPARLÖR bir puzzle ədəd ki doğru forma var bir-biri ilə uyğun. Auditoriya: Pretty çox, evet. HOPARLÖR: OK, əla. Və indi bu hər hemoroid ehtimalla çeşidlənir? 

Auditoriya: Bəli. 

Z. Bütün vasitəsilə bütün sağ, A: HOPARLÖR sağ, təbrik, siz bunu. Siz seçimi var. Blue? Bütün sağ, üçün təşəkkür edirik. Belə ki, Mary Beth təklif etdi nə onun yanaşma idi, lakin başqa bir yanaşma nə necə Bu şeyi çeşidlənməsi haqqında getmək bilər? Nə edərdin? Döymək üçün rekord olardı bir dəqiqə və 50 və ya belə saniyə, üstəgəl mən unuttum olanları saymaq. Nə edərdin? Bəli? Auditoriya: yığını edin. Əvvəldən başlamaq. Sizin sənədləri yoxlamaq. Və üst bir ali əgər daha, bəlkə, onlar var alt biridir ali, sonra onlara keçid. 

HOPARLÖR: OK, belə ki, başlanğıc üst və alt, və sonra yol iş daxili kimi, onlara dəyişdirmə? Oxşar OK, belə ki, bir az bubble sırala ruhu, lakin ifrata seçilməsi deyil bitişik cüt. Amma bu qısa var ki müxtəlif yollarla, şübhəsiz ki, bir dəstə biz bunu bilər və səmimi, mən növ, siz hesab sağ, bir neçə yanaşmalar qəbul? Siz dörd sorted hemoroid növ hazırlanmış və sonra səmərəli birlikdə onlara birləşdi. Və başqa, daresay var cəmi texnika. Siz böyük bir qalaq kimi müalicə etməyib Əgər dörd quads daxil problem bölünür Siz, sonra birtəhər əgər sonunda onlara birləşdi. 

Belə ki, son nəticədə, hesab edək, Bunu necə başqa. Biz anlayışı rəsmiləşdirilir bubble sırala son dəfə, və bubble sırala geri idi biz görüntülenmeyecektir ki, alqoritm up burada sinif yoldaşları səkkiz ilə, zahirən təsadüfi ilk sıralanır. Və biz sonra əgər pairwise qərar iki elementləri, üçün həyata sadəcə onları dəyişdirmək. Belə ki, dörd və iki açıq-aydın üçün həyata, həmin iki sinif yoldaşları mövqeləri işə. Və sonra biz, dörd və altı ilə təkrar sonra altı və səkkiz, hər iteration, sağ hərəkət. 

Belə ki, necə bir çox pairwise səkkiz nəfər verilir gəzinti isə müqayisə etdim belə bir iteration sağ? Neçə müqayisələr? Seven, sağ? Səkkiz var, çünki insanlar ancaq cüt onlara və siz hərəkət saxlamaq bir, sağdakı hop Siz səkkiz fikrində deyilik müqayisə müqayisə edə bilməz, çünki özü qarşı element, və ya o ki, yalnız mənasız, belə ki, yeddi var. Və ya ümumiyyətlə, əgər biz n insanlar var, biz n minus 1 müqayisə bubble sırala ilə. 

Belə ki, necə yaxşı, indi hesab edək və ya pis bubble sırala həqiqətən, və cəhd ilə özümüz söz vermək bu kimi tənqid alqoritmlər olan, və tezliklə öz. Vasitəsilə ilk pass belə bubble sort, ilk dəfə Mən rast soldan sağa getdi mərhələ, məni n minus 1 müqayisə etdi. Və olacaq mənim ölçü vahidi, sağ? I növ söhbət və strolling edilib, qədər qədər yavaş, sürətli, belə saniyə mənim sayının hesablanması xüsusilə söyləyirəm deyil, lakin sayının hesablanması Bazar ertəsi günü idi ki, əməliyyatlar, iki nəfər müqayisə, hiss ölçü gözəl vahid kimi. 

Belə ki, n minus 1 ilk dəfə addımlar, lakin sonra ondan sonra nə oldu? Bir pass biri ayaq nədir başqa çeşidlənməmiş siyahısı vasitəsilə? Siz element haqqında mənə nə deyə bilərsiniz orada bütün yol kim idi? Bəli? Bu doğru, ən böyük element idi? Sayı səkkiz, hətta o olsa Burada açılmış hər dəfə qarşı öz müqayisədə bir qonşu, o saxlanılır sağ qədər burda siyahısı tərəfdən. And olsun ki, harada alqoritm adını alır. 

İndi məntiq, nə qədər müqayisə Mən ikinci dəfə etmək lazımdır Soldan sağa edirəm ki, keçid etmək? n minus 2, sağ? I, əgər yalnız mənim vaxt israf olunacaq kimsə qarşı səkkiz müqayisə saxlamaq başqa, biz artıq bilirik, çünki o doğru yerdə idi. Belə ki, bir bir az var optimallaşdırma, növbəti pass belə plus n minus iki addım olacaq, n insanların sayı. İndi cür hətta extrapolate bilər bir kompüter alim değilseniz, Bu necə bitir. Bu alqoritm sonunda, ehtimalla Yalnız bir müqayisə tərk var. Siz cür düzeltmek üçün var halda iki siyahı başlayan və bir qaydada həyata və bir və iki olmalıdır bu həyata bottoms plus 1 final müqayisə. 

İndi nöqtə, nöqtə, dalğaları dot cür var juicier detalların bəzi əlləri, lakin yalnız irəli getmək və sadələşdirmək bildirin. Yüksək geri əgər sizin məktəb, səmimi, bir çox ki idi math kitablar bir az istifadə etmək hesabatı ön örtüyü və ya on sizə göstərdi ki, geri əhatə nə kimi seriyası summations Bu nəticədə qədər əlavə. Ümumi halda, əgər sizin bir n kimi dəyişən, və həqiqətən bu, Siz baxdı əgər sizin köhnə məktəb riyaziyyat kitab, Bu, həqiqətən, görmək olardı burada bu məbləğin qədər əlavə n dəfə n minus 1 bütün 2 bölünür. Belə ki, indi mənə yalnız müəyyən edək Bu, belə iman bir sıçrayış haqqında doğru, bu yekunlaşdırır nə qədər və biz bilər daha ümumi halda olduğunu sübut edir. Amma indi bu genişləndirməyə imkan. Belə ki, bu, çoxaltmaq edək, belə ki n kvadrat, minus n, bütün 2 bölünür. Ki, həqiqətən n kvadrat minus n 2, 2 bölünür, belə ki, bütün gözəl və maraqlı. Amma nə biz olur İndi plug-in bir dəyər? Mən səkkiz yox idi düşünək insanlar, lakin bir milyon deyirlər. Və bir milyon yalnız çünki Bu, olduqca böyük sıra ki plug və nə görmək edək. Mən ki, formula bir milyon plug əgər Belə ki, Mən bir milyon kvadrat almaq üçün gidiyorum 2 bölünür, minus bir milyon, 2 bölünür. İndi nə ki, bərabər olacaq? Belə ki, 500 milyard minus 500,000. Mən, həqiqətən, əgər ki, riyaziyyat həyata ki, vasitələri ki, bir milyon çeşidlənməsi bubble sırala insanlar Mənə 499.999.500.000 bilər sonunda addımlar və ya müqayisə, biz yalnız apardığımızda edirik. 

Bu olduqca yavaş hiss, lakin səmimi müəyyən bir giriş ölçü bu kimi bütün izah deyil. Amma həqiqətən o n kimi ki, yoxdur böyük və daha böyük, bu alqoritm olur cür hiss pis və pis, və ya, həqiqətən ki, ağrı hiss başlamaq exponentiation ki, n, kvadrat olduqca sürətli up edir. Və bu detal deyil əslində, insanların itirilmiş bir neçə il bundan əvvəl müəyyən senator olan təşviqat, müsahibə üçün oturdu Google Eric ilə Schmidt, zaman CEO, və bir sual ilə etiraz edildi çox biz bu gün kəşfiyyat etdiyiniz kimi. Bir nəzər salaq. 

[Video playback] 

-Senator, Siz burada olduğunuz Google, və mən istəyirəm prezidentliyə hesab Bir iş müsahibə kimi. İndi almaq çətindir prezident kimi bir iş, və indi rigors ilə olacaq. Bu Google bir iş almaq üçün də çətindir. Biz suallar var və biz bizim namizədlərin sual, bu bir Larry Şvimmer edir. What-- Sizlərin edirəm Zarafat deyil, burada var. Ən səmərəli yoldur nədir bir milyon 32-bit integers sort? 

-Well-- 

Sorry -Ben, maybe-- 

Heç, heç, No. Mən bubble növ hesab getmək üçün səhv yol olardı. 

Hadi haqqında, ona verib? Mən kompüter görmədim Sizin fon elm. 

-We've Orada bizim casusları var. 

-Ok, Fərqli bir soruşaq müsahibə sual. 

[END Video playback] 

HOPARLÖR: Belə ki, haqqında söhbət baxmayaraq xüsusi nömrələri, bütün faydalı olacaq deyil. Bu həyat dərsi ki, bubble deyil sort, bir milyon giriş verilir, kimi bir çox milyard 500 addımlar bilər. Siz, həqiqətən, ümumiləşdirmək bilməz çox səmərəli ki və yaxşı dizayn qərarlar qəbul etmək proqramları yazarkən. Belə ki, necə olsa diqqət edək biz bu nəticəni sadələşdirmək bilər. 

Mən burada sarı qeyd etdik n nəticə 2 bölünür kvadrat belə bir milyon kvadrat 2 bölünür, sonra Mən qeyd etdik nə son cavab idi biz off çıxılacaq dəfə N 2 bölünür. Mən indi etmək gedirəm iddia edir Siz off çıxmaq əgər kim heck qayğıları 2-dən bir az köhnə n ilk Bu formula hissəsi qədər böyükdür? Bu digər hökm sürür müddətli, n 2 bölünür kvadrat , aydın, çox böyükdür n, bir milyon kimi böyük olur ki, həqiqətən böyük bir fərq var 500 milyard arasında gün sonu və 499.999.500.000? Deyil, həqiqətən. Və nə biz olacaq kompüter alimləri kimi bunu O aşağı order şərtləri ignore və Bu, həqiqətən kimi bir şey almaq yalnız onu sadələşdirmək Fərq gedir ki müddəti. Böyük bizim data dəstləri, böyük almaq Bizim verilənlər bazası, daha çox web pages almaq biz daha çox axtarış dostlar Facebook var. 

N böyük olur ki, biz, həqiqətən istəyirik Ən böyük qayğı gedir bu cür təhlili müddətli bizim alqoritmlər performans. Və mən bilmək, demək gedirəm, bubble sırala böyük O əmri deyil, n qaydada kvadrat. Bu dəqiq n deyil biz gördük kimi kvadrat, lakin həqiqətən qayğı bu kiçik şərtləri haqqında, və səmimi, həqiqətən biz 2 bölmək əgər umurunda? Bu yalnız daimi amil var. 250 qarşı 500 milyard milyard müqavilə həqiqətən böyük? Mən yalnız bir il gözləmək bilər, sanki mənim laptop imkan , hardware iki dəfə kimi sürətli almaq və fərq sort yalnız zamanla təbii üz gedir. 

Biz nə qayğı deyil ifadəsi, hissəsi fərqli olacaq ki, ifadə bizim giriş böyük və daha böyük olur kimi. Və həqiqətən, real dünyada, ki, getdikcə daha neler var bizim problemləri giriş və alqoritmlər böyük alır. Belə ki, böyük O notation olacaq, asimptotik notation, biz yalnız kompüter alimləri təsvir etmək kimi istifadə performans, və ya çalışan zaman, bir alqoritm. Biz alqoritmlər müqayisə edə bilərsiniz, belə ki, yazılı müxtəlif kompüter müxtəlif insanlar tərəfindən, istifadə edərək, Bəzi əsaslı oxşar metrik müqayisə sayı etdiyiniz kimi bəlkə svopları sayı edilməsi, və ya Siz edirik. 

Biz nə etmək fikrində deyilik count vaxt məbləği ki, saat keçir adətən divar. Biz nə narahat fikrində deyilik haqqında nə qədər yaddaş Siz bu gün istifadə etdiyiniz ki, baxmayaraq ki, ən azı biz ölçmək bilər ki, bir resurs. Biz təhlillər əsaslandırmaq üçün cəhd olacaq yalnız əsas əməliyyatlar üzrə, olanları, səmimi, ən çox vizual bilərsiniz ki,. N böyük O kimi bir şey ilə belə kvadrat, mən n kvadrat Ey iddia bir üst qondarma borcludur bubble növ çalışan zaman. Başqa sözlə, əgər var olduğunu iddia etmək istədi necə çox bu üst limit bir alqoritm bilər addımlar, Bu n böyük O olacaq bu halda kvadrat, bir üst bound. 

Mən əvəzinə dəyişdirmək əgər hekayə deyil, bubble sırala haqqında olmaq lakin bu üst bound haqqında. Bir alqoritm hesab edə bilər biz artıq baxdı etdik ki, kimin üst bound, maksimum zaman və ya əməliyyatların ölçmək, həmsərhəddir üçün olacağını bildirib n, bir linear function, deyil əyri ki, bir kvadrat bir? Bir alqoritm nədir ki həmişə çox edir n addımlar, və ya kimi çox 2n addımlar, və ya 3n addımlar? Bəli? 

Auditoriya: tapmaq siyahısı ən böyük sayı? 

HOPARLÖR: Perfect tapmaq siyahısı ən böyük sayı. Mən bir siyahısı verilir alıram əgər Məsələn adam, kim hər bir sıra keçirir maksimum sayı nə addımlar məni almaq lazımdır, bir məntiqi ağıllı adam, ki, siyahıda ən böyük şəxs tapmaq üçün? n, sağ? Ən pis halda, harada Çünki ən böyük dəyəri ola bilər? Sağ, sonunda bütün yolu. Ən pis halda belə yuxarı bağlı, mən bilər bütün yol getmək üçün var burada və kimi, oh, burada sayı səkkiz var, və ya ki, dəyəri nə. İndi yalnız axmaq olardı Mən doğru gedir saxlanılır əgər? Daha elementləri axtarır onların son orada olur? Beləliklə, şübhəsiz ki, n bir üst bound edir. Mən etmək lazım deyil daha addımlar. 

Belə ki, əvəzinə, mən təklif nə bu dünyada alqoritmlər var ki, ki, bir çalışan vaxt log n böyük O ilə həmsərhəddir, n daxil? Harada biz əvvəl bu gördük? Bəli? 

Auditoriya: telefon kitab problem? HOPARLÖR: telefon kitab problemi kimi. Necə tədbir nə idi çox vaxt və ya nə qədər göz yaşları onu mənim kimi kimsə tapmaq aldı Telefon kitab Mike Smith? Biz log n iddia və hətta tanımadığı və ya bu var nə bir az dumanlı logarithm və ya eksponent idi, yalnız log n xatırlayıram ümumiyyətlə prosesinə aiddir, bu halda, bölünməsi yenidən və yenidən yarısında bir şey, və yenidən və yenidən, bunun ki, bunu kimi getdikcə kiçik olur. 

N əmin istinad belə daxil, telefon kitab misal üçün, nəzəri ikili axtarış, biz , şurası virtual qapı idi və ya Sean idi bir şey üçün axtarış. O ikili axtarış istifadə edin, n log nə qədər bağlı yuxarı olacaq edir ki, zaman. Amma qaçdı ki, o alqoritmlər n nə əsas detal ehtimal log? Siyahısı, sağ sıralanır ki? Sizin alqoritm əgər səhv Sizin giriş, sıralanır deyil və hələ istifadə etdiyiniz ikili axtarış kimi bir şey Siz jump bilər, çünki sağ element üzərində fərqində olmadan həqiqətən var. 

İndi bu, böyük O nə demək bilər? Bu alqoritm demək deyil ki, bir və yalnız bir addım edir Bu yalnız bir edir deməkdir addımlar daimi nömrəsi. Bəlkə bu, bəlkə var, 1 var 10, bəlkə 1000 var, lakin müstəqil var problemin ölçüsü. Necə böyük olursa olsun n, daimi vaxt alqoritm həmişə addımlar eyni sayda edir. Belə ki, nə bir alqoritm ola bilər biz və ya yalnız söhbət etdik daxilən ki, sizə gəlir həmişə sözdə daimi vaxt çalışır? Bəli? 

Auditoriya: iki ədəd əlavə edin. HOPARLÖR: iki ədəd əlavə et 2 plus 2 aparılır, 4 bərabərdir. Belə ki, iş bilər, nə? Necə daha real dünya haqqında, yeah? 

Auditoriya: tapmaq bir siyahıda ilk şey. HOPARLÖR: ilk tapmaq siyahısı element, əmin olun. Biz, həqiqətən, söhbət etdik artıq Diziler haqqında, Bu siz almaq nə bir sıra ilk element, necə olursa olsun uzun array C kodu edir? Siz yalnız bracket kimi istifadə sıfır notation, bam, orada istəyirik. Və bir kənara kimi həqiqətən serialların, dəstək şey, ümumiyyətlə, məlum təsadüfi giriş kimi, təsadüfi giriş yaddaş, sözün bilərsiniz, çünki hər hansı bir yerə tullanmaq. Biz sadəcə bu daha çox edə bilərsiniz biz həftə sıfır geri bilər biz Not etdi. Bu almaq idi nə qədər vaxt Not blok icra demək? Just daimi vaxt, sağ? Bir şey demək bir şey etməz böyük çizilmelere dünya necə həmişə var eyni miqdarda almaq üçün gedir sadəcə bir şey demək. 

Belə ki, daimi vaxt, lakin flip tərəfində nə var? Ki, yuxarı idi həddi, biz nə istəyirsinizsə aşağı həddi təsvir etmək üçün Bizim alqoritmləri çalışan zaman? Demək olar ki, bir yaxşı halda potensial, Siz, Bu şərtlər yaxşı tətbiq bilər, baxmayaraq hallarda, ən pis halda, orta hallarda daha ümumiyyətlə, lakin yalnız diqqət edək aşağı həddi daha çox, ümumiyyətlə. Nə var ki, bir alqoritm var aşağı, n addımlar bağlı və ya 2n addımlar, və ya 3n addımlar? N addımlar bir amil, ki, onun aşağı bound var. Bəli? 

Auditoriya: Bubble sort? 

HOPARLÖR: Bubble sort edir minimal n addımlar, niyə? Niyə ki? Niyə ki start sizə gəlib etməlidir daxilən, bu, belə deyil, yalnız hələ? Bəli? 

Auditoriya: [işitilemez]. HOPARLÖR: Exactly. Mümkün olan ən yaxşı ssenari bubble sırala və alqoritmlərin bir çox, Mən sizə səkkiz nəfər əl əgər kim artıq sıralanır, Bu ağılsız olardı sizin üçün alqoritm, geri və irəli getmək üçün bir daha, sağ? Tezliklə sizin kimi çünki bir siyahısına vasitəsilə gəzmək, Siz həyata oh ki, mən edilən bir svopları, bu siyahı, çıxış çeşidlənir. Amma siz n addımlar olacaq. 

Və əksinə, nə başqa bir bu barədə düşüncə yolu? Bubble sort bir omega, belə n, danışmaq, baxsanız, çünki az n elementləri, nə əsas məsələ var? O sıralanır əgər sağ, bilmirəm. Biz səkkiz güc nəzər insanlar insanlar və kimi oh, o sıralanır ola ki, mənə n addımlar atmadı, ancaq etdi. Sizin gözləri, hətta belə sizə baxmayaraq ki, görmə böyük bir sahə var Siz səkkiz elementləri baxdı, Siz səkkiz nəfər baxdı səmərəli səkkiz addımlar var. Mən bütün vasitəsilə gəzmək yalnız siyahısı bəli, sıralanır, həyata yoxdur. Mən dayandırmaq ortasında bütün düşünür sağ, bu, olduqca günə qədər sıralanır, Bu sıralanır deyil bahis nə var? Doğru olacaq deyil alqoritmləri. Sürətli, amma yanlış ola bilər. 

Belə ki, indi biz yol var aşağı həddi izah, və daimi vaxt haqqında nə? Nə aşağı var ki, bir alqoritm var bir onun çalışan zaman bağlı? 1 addım, 2 addımlar, 10 addımlar, lakin , daimi n müstəqil, giriş ölçüsü? Bəli, geri. 

Auditoriya: Printf? HOPARLÖR: Nə olub? Auditoriya: Printf? HOPARLÖR: Printf. Əmin, OK. Belə ki, addımlar sabit nömrəsini edir. Və mən indi now-- lazımdır biz C indeksi haqqında söhbət edirik və Scratch şey demək kimi, printf ilə, biz ehtiyatlı almaq üçün başlamaq lazımdır. Printf almaq çünki giriş, bir simli var, və strings texniki uzunluğu var. Biz indi almaq istəyirsinizsə Belə ki, sizə, siz ağla deyil əgər, texniki biz printf iddia edə bilər Dəyişən uzunluğu daxil etmək deyil, və şübhəsiz ki, daha çox bilər time, bu uzun bir simli çap Bu uzun daha. 

Beləliklə, biz yalnız nə varsa çeşidlənməsi və nümunələr axtarış? Telefon Mike Smith haqqında nə kitab, və ya ikili axtarış? Ən yaxşı halda, nə baş verə bilər? Mən bam, telefon kitab açmaq və Mike Smith sayı var. Mən dərhal ona zəng edə bilərsiniz. 

Bəlkə iki addımlar bir addım aldı, lakin addımlar bir sabit sayı Mən xoşbəxt var, əgər. Və səmimi, biz gördüm Bazar ertəsi sinif yoldaşı Bir sıra iki dəfə olduqca uğurlu olsun. Və həqiqətən daimi idi aşağı həddi dəfə Söz mövzusu alqoritm tapmaq üçün həmin bağlıdır arxasında 50 qapılar. 

İndi bir kənara, siz tapmaq kimi , həm də böyük O, üst bound ki və omega, aşağı, bağlı ki, eyni biridir eyni formula edir parantez, siz də edə bilərsiniz yalnız xülya olmaq, demək ki, bir şey teta edir n və ya digər dəyər teta edir. Bu yalnız zaman böyük deməkdir O və omega eynidir. İndi seçim sort haqqında nə? Bu yeni söz istifadə edək. Seçim sort, nə biz idi yenə bunu və yenidən və yenidən? Mən vasitəsilə geri və irəli gedir siyahısı, kimə axtarır? Ən kiçik sayı. 

Belə ki, necə bir çox addımlar necə çox müqayisələr I etdi anlamaq üçün etmək olan siyahıda ən kiçik element idi? n minus 1, sağ? Mən yalnız mən deyiləm biri ilə başlamaq əgər, çünki verilmiş və mən onu müqayisə başlamaq, ona və ya onun ondan sonra onun, ona və ya onun, I və ya yalnız elementləri qoşmaq bilər birlikdə n minus 1 dəfə. Belə ki, seçim sort eyni edir n minus 1 ilk dəfə addımlar. 

Bu məni görür nə qədər çox addımlar ikinci kiçik element tapmaq? n minus 2, Ben çünki lal Mən eyni insanların axtarır saxlamaq əgər daha mən artıq onu seçdiyiniz əgər və ya onun və onların yer onları qoymaq. Və üçüncü addım, n mənfi 3, sonra n minus 4. Biz bu model gördüm əvvəl və həqiqətən seçim sort eyni bound yuxarı var n biz toplama up əgər kvadrat. Onun aşağı bound, seçim sort nədir? Minimal, nə qədər vaxt lazımdır seçim Biz bazar ertəsi müəyyən kimi sort, almaq? Iki variantları təklif. Bəlkə əvvəlki kimi, n var. Bəlkə bu kimi, kvadrat n oldu üst bound kimi indi. 

Auditoriya: n kvadrat. HOPARLÖR: kvadrat n. Niyə? 

Auditoriya: siz var [Işitilemez] müəyyən etmək. 

HOPARLÖR: Exactly. Mən seçim sort müəyyən ən azı Bu olduqca sadəlövh idi, davam, kiçik element tapa bilərsiniz. Kiçik element tapmaq, yenidən gedin. Kiçik element tapmaq, yenidən gedin. Heç cür var var ki, optimallaşdırma Mənə sonra abort imkan bilər yalnız n və ya belə addımlar. Belə ki, həqiqətən, seçim sort, n omega kvadrat. 

Mən aldı daxil sort haqqında nə Mən verildi, sonra mən onu plopped edən və ya onun doğru yerdə? Sonra, ikinci şəxsə davam Doğru yerdə ona plopped. Sonra növbəti şəxs, plopped ona və ya onun doğru yerdə. Bu çox olduğunu qeyd xətti, belə danışmaq. Mən deyiləm, bir düz xətt deyiləm geri və irəli gedən deyil, Mən, həqiqətən, geri axtarır sonra, lakin Mən ona daxil olduqda nə baş başlanğıcına onun və ya siyahısı, biz bazar ertəsi olduğu kimi? Nə olub? Bəli? Auditoriya: [işitilemez]. HOPARLÖR: Bəli, sağ, tutmaq idi? Siz geri bilər sinif yoldaşları, əgər onlar hər hansı bir hərəkət ilə qəbul edilmişdir ayaqları, bir əməliyyat idi. Belə ki, əgər üç nəfər burada idi və yeni şəxs, yol üzərində məxsus bu kimi uzun bir səhnədə, əmin, o və ya o, yalnız çox sonuna getmək bilər. Amma biz düşünərək edirsinizsə kompüter və yaddaş bir sıra, bu insanlar gedir üzərində shuffle üçün ki, şəxs üçün otaq etmək. Və belə ki, n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings yalnız növ mənə qarşısında, arxamda baş əvvəlki kimi, bir mənada. İndi bir kənara kimi, və Siz online görmüşəm bilər Siz ətrafında poking başlamaq əgər növ, bir çox müxtəlif olanları var Onların orada bəzi daha yaxşı. Həqiqətən, bogosort biridir ki, axtarmaq üçün əyləncə növü var. Bogosort bir sıra edir nömrələri və ya kartlar göyərtə demək, təsadüfi onlara shuffles və çek onlar sıralanır edirsinizsə. Və əgər, daha yoxdur. Və əgər, daha yoxdur. Əgər, daha yoxdur. Olduqca axmaq. 

Və həqiqətən, oxumaq əgər Wikipedia article kimi, onun ləqəbi axmaq sortudur. Bu nəticədə işləyəcək, ümid edirəm ki, kifayət qədər vaxt verilir, lakin zaman məbləğ olduqca bir müddət bilər. Mən edək bilər sürəti hər şeyi əvvəllər Mary Beth Məsələn up, bir neçə elementləri olan, lakin daha iki prosessorları. Iki nəfər, əgər mənə qoşulan ağla olardı. Necə haqqında 1 buraya, və orada heç bir bir go-- edək? Orada heç bir? OK. Qara ilə shirt, bəli, aşağı gəlir. Bütün hüquqlar, sizin adınız nədir? 

Auditoriya: Peter. 

HOPARLÖR: Nə olub? 

Auditoriya: Peter. HOPARLÖR: Peter, David, siz cavab gözəl. Bütün hüquqlar, biz burada Peter var əgər burada masa üzərində gəlmək istəyirəm. Və sizin adınız nədir? 

Auditoriya: Elena. HOPARLÖR: Elena. OK, siz cavab gözəl. Elena Peter cavab verir. Peter, Elena. Və biz Andrew lazımdır Burada eləcə də, xahiş edirik. Və problem gedir kartlar göyərtə düzmək üçün olmalıdır. Və tanımadığı əgər, göyərtə kartlar olmalıdır nəticədə kimi bir az bir şey sıralanır bu biz sonra klub nə lazımdır Bu matça, sonra ürəklərini və bir kimi ACE dən brilyant, padşahının bütün yol. 

Bu kartlar Mən sizə vermək gedirəm miqdarı 52 olacaq. Biz eyni olacaq yalnız bir anda dəfə sizə. Biz Andrew atmaq olacaq burada ekranda, Bunu kimi, izləmək. Və bütün bu ki, bütün daha çox görünür Bu Amazon var kartlar var. Belə ki, onlar təsadüfi artıq sıralanır, və biz sizə zaman olacaq. Və biz olacaq , real bu dəfə saxlamaq belə ki, biz sizə təzyiq etmək üçün cəhd olacaq başqa, bu yorucu olacaq, çünki tez. Siz 52 düzmək üçün davam edə bilər, əgər İndi birlikdə bəzi vasitələrlə elementləri. 

Və yenə, biz bu saat uşaqlar sonunda nə, nə açıq-aydın istehsal gedir nəticə, haqqında, həqiqətən, hesab necə bir bunu edirik, necə təsvir edə bilər. Yenə bu, çünki bütün proseslər, alqoritmlər bir insan kimi verilən biz almaq ki,. Amma yəqin ki, uzun yaşadım intuisiya, Sizinlə əvvəl hətta bir görülməsi haqqında fikir informatika sinif siz intuisiya ilə var ola bilər bu kimi problemləri həll etmək. Amma bir dəfə tanımaq nümunələri və başlamaq olan addımlar rəsmiləşdirilməsi Bu problemləri həll edirik, Siz çox həll edə bilər ki, tapa bilərsiniz daha maraqlı və daha çox kompleks tez problemləri. Belə ki, tamaşaçı kimsə, nə alqoritm ən azı bir element Onlar burada istifadə etdiyiniz? 

Auditoriya: [işitilemez] HOPARLÖR: Nə olub? Auditoriya: kostyum By. HOPARLÖR: kostyum By. Belə ki, ilk, onlar qruplaşmasını olunur almazdan bütün birlikdə ki, hamısı görünür birlikdə görünür ürəkləri, və s, hörmət olmadan kartları nömrələri. İndi onlar, misal üçün, görünür, sayı, onların çeşidlənməsi üçün. Çox yaxşı. 

Bütün hüquqlar, belə neler sonra burada son addım olacaq? Dörd sıralanır kostyum, var nə biz dörd hemoroid üçün nə etmək lazımdır birini əldə etmək üçün sadəcə, göyərtə sıralanır? Belə ki, biz onları yenidən daxil etmək lazımdır. 

Belə ki, bir maraqlı fikir var ki, yenə daresay, hətta çox asan deyil Siz yumruq heç vaxt bilər, əgər bu etiket bu cür. Ayırıcı Bu fundamental anlayışı Bu problem yarım bu dəfə, lakin ən azı dörd ədəd. Olduqca çox həlli əsaslı eyni problemlər birinə təcrid, və sonra nəticələri birləşmə. Və əla, görülən. Bütün sağ, böyük bir dəyirmi alqış, biz bilər. 

[Alqış] 

HOPARLÖR: Mən nə lazımdır heç bir fikrim yoxdur Bu ilə, lakin burada getmək. Çox təşəkkür edirik. Belə ki, iki dəqiqə görək və səkkiz saniyə, sizin dost etiraz istəyirsinizsə. Sonra nə gedir Bu uzaq almaq ola biz ümumiyyətlə leverage ki? Yaxşı, geri edirəm nömrələri bu array, və bəzi indi geri edirəm biz keçmişdə yazdıq pseudocode, və bunun üçün pseudocode idi telefon kitab problemi həll. Vasitəsi pseudocode I daha metodik şəkildə sıralana Mən çox intuitiv necə izah telefon ayırıcı insan alqoritm yarısında kitab, təkrar, təkrar, təkrar Mən tapmaq qədər Mike Smith kimi kimsə, O telefon kitab həqiqətən əgər. 

Amma cür I zəng edəcəyik istifadə Burada çox iterativ yanaşma, xəbəri line 8 və line 11. Bu bir iterativ sübut edir yanaşma, bir loop yanaşma, dəqiq, çünki Onlar bişirmək davranış. O xətləri də getmək demək line üç və siz cür ki, hesab sizin bir loop kimi fikrinizi göz. Bu addım geri getmək üçün belirten edir üç və təkrar yenidən və yenidən, və yenidən. 

Amma biz əsas fikir nə leverage əgər Burada biz son dəfə idi ki, və xətti 8 sadələşdirmək və line 11 və qonşularının yalnız bu, sarı kimi. Bu əsaslı qısaldılması deyil çox pseudocode, amma o dəyişir Mənim alqoritm təbiəti. Mən indi deyirəm addım 7, addım 10, Mike axtarmaq üçün eyni şəkildə, lakin yalnız sol yarım və ya sağ yarısı. 

Belə ki, başqa sözlə, əgər Mən addım bir başlamaq , orta açıq telefon kitab almaq telefon kitab, adları baxmaq, Smith arasında əgər adı üzrə, Mike, başqa zəng Smith əvvəl kitab olduğu halda, yeddi addım Kitabın sol yarısında Mike üçün axtarış. Amma bu cür kimi hiss sağ, asma məni tərk edir? Sarı, bir deyil təlimat, lakin mən necə sol Mike üçün axtarış telefon kitab yarısı? Mən harada var alqoritm ilə I Mike Smith kimi kimsə üçün axtarış edə bilərsiniz? Bəli, bu qarşısında bizi sizin ixtiyarınızdadır var. Mən sözün eyni istifadə edə bilərsiniz Proqram səmərəli üst qədər davam yenidən və yenidən çalışan kod eyni satır. 

Belə ki, bu hiss etməlidir baxmayaraq dövri müəyyən bir az kimi siz kimsə cavab edirik yalnız sort xahiş sual yenə eyni sual, niyə, niyə, niyə? Biz ağır kodlu etdik, çünki reallıqdır xüsusi xətləri bir neçə addım 4, bir, əgər, və addım 12 olan , səmərəli başqa qoludur biz bu stopgap tədbirlər var, çünki, Bu alqoritm ləğv əgər biz Mike tapmaq, və ya biz deyil. Amma indi addım 7 və 10, biz biz bir recursive alqoritmi zəng edəcəyik. Və recursion həqiqətən güclü fikir ki, ilk əyilmə bir az ağıl aşağıdakı kimi indi müraciət edə bilər. 

Son sort olacaq sort birləşməsi biz formal azı sinif baxmaq. Və əsaslı fərqli əlbəttə bu son üç və Son dörd biz bogosort daxil edin. Burada birləşmə sort üçün pseudocode var. N elementləri daxil, belə ki, verilmiş ölçüsü n bir sıra, n az 2 Əgər qayıtmaq. Belə ki, niyə mən ki var ağlı başında olma ilk yoxlamaq? Mən sizə əl əgər dolayısı nə var onun uzunluğu n bir sıra 2-dən azdır? Artıq doğru, açıq-aydın, sorted? Siyahısı və ya var, çünki trivially olan bir element, çünki sıralanır orada yalnız bir şey. Yoxsa, bu deməkdir ölçüsü sıfır var düzmək üçün heç bir şey təbiət belə var Bu çeşidlənir. Yanlış var heç bir şey yoxdur. Belə ki, bizim sözdə əsas işi var. 

Ki, ruhunda oxşar biz Mike ilə nə. Mike telefon kitab varsa, ona zəng. Orada deyilsə, imtina. Bu qondarma əsas işi var, əmin Günün sonunda bu alqoritm müəyyən hallarda dayandırmaq edəcək. 

Amma burada iman sıçrayış başqa, indi , elementləri sol yarım sort sonra sağ sort elementlərin yarım, və sonra sıralanır yarıya indirir daxil. Bu hiss və burada kimi biz copping edirik. Mən düzmək üçün sizə xahiş etdik n elementləri və mən çeşidlənməsi ilə, OK, bunu söyləyərək sol və sağ çeşidlənməsi. Amma bir də deyirəm digər şey, və bu Göründüyü əsas mövzusudur indiyədək intuisiya da, birləşmə bu üçüncü addım var. Hansı hətta baxmayaraq , belə ruh lal görünür kimi şeyi birləşməsi birlikdə, görünür Bu doğru mühüm addım olacaq iki problemləri reassembly ki yarısında nəticədə ayrıldı. 

Belə ki, lazımdır, əgər bunu edək, sort daxil bir daha nümayiş yumor mənə, yalnız, belə ki, biz bəzi nömrələri ilə işləmək üçün. Mən səkkiz stress mübadiləsi edə bilərsiniz səkkiz insanlar üçün top? Bütün hüquqlar, necə dörd, üç sizə haqqında Bu bölmədə, beş, altı, və edək in 7, 8, qədər gəlir yoxdur. OK Bəli, OK. Minus 8, orada biz gedin, plus 1. Əla. Bütün hüquqlar qədər gəlib, edək tez nömrələri verir. Sayı iki, sayı üç, sayı dörd, sayı beş, altı, yeddi, səkkiz. Mən düzgün bu dəfə səkkiz idi. 

OK, belə ki, ola bilər, əgər, davam və nin orijinal qaydada düzmək imkan Biz dünən idi ki, baxdı bu kimi, ağla deyil əgər. Və masa qarşısında bunu edək. Bütün hüquqlar, belə növ birləşməsi. O gedir harada bu maraqlı cür almaq üçün, Mən özümü verilməsi üçün görünür, çünki çox az məlumat bu gün. 

Belə ki, sort ilk növbədə birləşməsi n elementləri yığımı, və bu, açıq-aydın az olmayan iki səkkiz, mən bunu bir çox iş var. Belə ki, indi ruhi bir sinif kimi başqa filialının indi, üç addımlar deməkdir. Birincisi, mən düzmək lazımdır elementləri sol yarısı. Belə ki, necə bunu barədə getmək yoxdur? Bəli, mən növ gedirəm əqli burada siyahısını bölmək, Siz yoxdur fiziki hərəkət, və mən Bu yalnız diqqət gedir Burada elementləri sol yarısı. Mən çeşidlənməsi haqqında necə getmək yoxdur İndi ölçüsü dörd siyahısı? Mənim alqoritm nədir? Birinci mən yoxlamaq heç bir iki daha n az, mən yenə də başqa blokunun davam etdirilir. Sort elementləri yarım buraxdı. 

Belə ki, indi yenidən, əqli, və bu harada Siz bir çox reallaşdırma var ruhi tarixi, Siz. İndi sol çeşidlənməsi alıram sol yarısı yarısı. Bütün hüquqlar, belə ki, indi mən eyni birləşməsi zəng alqoritm çeşidlənməsi, az iki n olunur? Xeyr, bu, iki, mən düzmək lazımdır sol yarısı və sağ yarım. Belə ki, burada biz sol yarım sort, gedin. Niyə yalnız deyil irəli bir addım. Sizin adınız nədir? 

Auditoriya: Darren. 

HOPARLÖR: Dan. Dan irəli addım olmuşdur. 

Auditoriya: Darren. HOPARLÖR: Darren, görülən. Siz Darren və ya Dan demək mi? 

Auditoriya: Darren. 

HOPARLÖR: Darren. OK, Darren sürətləndirdi irəli və o, indi çeşidlənir. Və bu demək olar ki, bir deyil mənasız iddia, sağ? Mən, həqiqətən, əldə etmək görünmüyor bir şey, amma davam edək. İndi mənə hüququ sort imkan elementləri yarısı. Sizin adınız nədir? 

Auditoriya: Luke. 

HOPARLÖR: Luke. Hadi, irəli addım. Done, mən Luka sıralaması. Sol yarısı artıq çeşidlənir və sağ yarısı indi çeşidlənir amma yenə burada bir mühüm addım var. Mən növbəti nə etmək lazımdır? Sıralanır yarıya indirir daxil. İndi biz yalnız olacaq geri və irəli, bu şəkildə hər kəs, I növ lazımdır, çünki bəzi danışıq sahəsi. Demək olar ki, bu kimi uşaqlar bir masa var, və mən bir otaq lazımdır onları ətrafında hərəkət etmək. Mən daxil etmək üçün gedirəm baxaraq uşaqlar sol yarısı və sağ yarım. Və təbii ki, birinci gələn, sol yarım və ya sağ yarım? Belə ki, sağ yarım, belə ki, artıq Luka hərəkət edək burada Darren orijinal mövqe. İndi onların sol yarım birləşməsi, Darren orada hərəkət etmək olacaq. 

Belə demək olar ki, kimi hiss bir bubble sırala təsiri, lakin mənim fundamental alqoritm, bu dəfə çox fərqli. Hər şeyi bir almaq, lakin indi az annoying çünki əqli geri var Mən harada off tərk etdi. Mən yalnız sıralanır yarıya indirir birləşdi etdik, Mən mənim alqoritm harada Ben deməkdir? Mən sağ, sağ yarım sort var? 

Sözün, geri əgər video, will Biz bu var ki, görə Luka və Darren nöqtəsi sol çeşidlənməsi sol yarısı yarısı. Sonra biz həmin birləşdi sorted yarıya indirir olan Növbəti addım sort deməkdir sol yarısı sağ yarım. Bütün hüquqlar, belə edək daha tez bunu. Bütün sağ, altı, mən iddia gedirəm İndi irəli gəlib, sıralanır. Sizin adınız nədir? 

Auditoriya: Adriano. 

HOPARLÖR: Adriano. Adriano indi çeşidlənir. Və sizin adınız nədir? 

Auditoriya: Alex. 

HOPARLÖR: Alex artıq çeşidlənir. Sol yarısı, sağ yarım, son addım nədir? Birleştirme. Olduqca mənasız, mən deyiləm altı daxil olacaq, geri addım, səkkiz, bir addım geri almaq. Və indi bu fərq faydalı paket, nə İndi sol yarım haqqında doğru deyil siyahısı, asılı olmayaraq biz başladı necə? Bu çeşidlənir. 

İndi sıralanır deyil şeyi böyük sxem, lakin müstəqil çeşidlənir digər yarısı. Mən saxlamaq əgər İndi nə addım I am hekayə necə başladı rewinding? İndi mən sağ yarım sort var. Belə ki, indi biz yol geri istəyirik hekayə başından, və daha sürətlə bunu edək. Mən düzmək üçün gedirəm bütün siyahısı sağ yarım. Növbəti addım nədir? Sağ yarısında sol yarım sort. Bu sol yarım sort sağ yarısında sol yarısı. Və sizin adınız nədir? 

Auditoriya: Omar. 

HOPARLÖR: Omar, görülən irəli addım. Sol yarısı çeşidlənir. Və sizin adınız nədir? 

Auditoriya: Chris. 

HOPARLÖR: Chris, bir addım irəli, indi sıralanır. Indi əsas addım nədir? Birleştirme. Belə ki, bir yerdə daxil etmək üçün gedir burada bir addım geri bilər, əgər, və üç gedir birləşməsi, geri addım atmır. Belə ki, sol yarım sağ yarım, indi çeşidlənir. Açığı, bu alqoritm biz kimi hiss daha yol daha çox vaxt israf edilir, biz real vaxt bunu əgər, biz will takeaways olacaq nə görmək. İndi burada mən sağ, am sağ yarısı yarısı, Mənə irəli getmək və sol yarım sort imkan verir. Addım irəli, sizin adınız nədir? Auditoriya: Ramsey. HOPARLÖR: Ramsey artıq çeşidlənir. Sizin adınız nədir? 

Auditoriya: Marina. 

HOPARLÖR: Marina indi çeşidlənir yaxşı, irəli bir addım əgər. Burada əsas addım indi mən, daxil edilir mənim iki siyahıları dərmək üçün gedir, sol və sağ. Beş, ilk gələcək və yeddi gəlib gedir. Və yenə bu qəsdən edir. Onlar qəbul etdiyiniz ki irəli və geri addımlar təmsil deməkdir ki, biz bilməz kimi asanlıqla yerdə bu alqoritm nə bubble növ və seçim sort kimi, və durub sort biz yalnız insanların dəyişdirmə saxlanılır. Mən sözün bir növ lazımdır danışıq kağız olan bu millət qoymaq üçün Mən birləşdirilməsinə nə isə, və sonra mən yer onları geri bilər. Mən istifadə edirəm, çünki əsas var yeni resurs, kosmik, yalnız vaxt. 

OK, bu gözəl deyil. Sol yarısı sağ yarım edir, çeşidlənir sorted, indi əsas birləşmə addım. Mən bu daxil etmək üçün gedirəm? Təqib lazımdır, əgər belə mənim sol və sağ, Mən sol qeyd gedirəm sol yarım mənim sağ sağ yarım, indi mən var birləşməsi kimə addım-addım qərar. Kim təbii ki, birinci gəlir? Sayı bir. Belə ki, burada gəlib, burada danışıq pad var. Belə ki, indi bir və bildiriş sayı Mən sağ əli ilə nə edəcəyik, Mən sağ bir hərəkət etmək üçün gedirəm sayı üç point üzərində addım, və indi etmək lazımdır Eyni qərar. Və həqiqətən doğru dayanmaq Luka burada ola bilər əgər ön, bu, bizim danışıq pad edir. Belə olan sonrakı gəlir? Biz iki nömrəli ilə Luka var və ya Chris sayı üç ilə. Aydındır ki Luke sayı iki, belə ki, buraya. 

Amma mənim sol indi gedir Darren qeyd etmək artırılacağını, və burada əsas ilə üz var birləşmə, mən bunu saxlamaq üçün gedirəm, Aydındır ki, əgər cür məntiqi edin. Amma mənim əlləri heç vaxt geri getmək üçün gedir, Mən yalnız heç hərəkət edirəm deməkdir Mənim birləşmə prosesi ilə sol, və əsas olacaq yalnız bir anda bizim təhlili. 

Belə ki, indi sürətlə bu qədər bitirək. Belə ki, üç gələn gəlir, sonra dörd gələn gəlir, və indi beş-altı, sonra, növbəti gəlir yeddi, və sonra nəhayət səkkiz və. Yavaş alqoritmi kimi hiss Hələ yox, amma həqiqətən biz əgər eyni növ çalıştırın saat sürət, belə Eyni ilə, danışmaq əvvəlki kimi saat ticking. Niyə? Yaxşı, bir edək sonunda nəticəsində oldu. 

Mənə imkan, burada artıq geri gedək vizual nümayiş qoparmaq biz yalnız nə. Bu, burada yakınlaştırma Burada səhifə, Firefox izah biz növbə etmək istəyirəm ki, Bu qutusuna qədər, edək , bubble növ demək olan biz indi də tanış edirik başqa olan seçim sort, kifayət qədər sadə bir, və indi, bu gün birləşmə sort olan Bizim iqlim sona olacaq. Bu çox uzun, belə aldı səbəbi burada insanlar və mənə şifahi deyil, təbii ki, mən hər bir addım izah edirəm. Amma sadəcə bu, çox icra əgər kimi biz bubble sırala və seçim sort yalnız əyani, watch yalnız nə qədər daha səmərəli bu yararlanarak bölmə və fəth ki, bir data set tətbiq edilə bilər hətta ölçüsü səkkiz, hətta çox, çox böyük. Mən sizə görə sırala yan daxil vermək Bu digər alqoritmləri ilə yan. Bu ağrılı almaq üçün gedir tez və sona , xüsusilə iqlim deyil onlar yalnız sıralanır son. Amma əsas ki götürmek sort nə qədər sürətli birləşməsi baxmaq Mən olduğumu düşünürəm halda idi yalnız cür sizinlə messing. Bu bir final vaxt varsa, Bu yeniden imkan, dönək və bubble növ seçin və yalnız kicks üçün, nin durub seçin bildirin sort, yalnız yaxşı tədbir üçün. Və bu zaman yenə edək birləşməsi növ seçin və imkan həqiqətən tərəfindən bu yan run. 

Və bu, əslində, bir fluke deyil. Mən səmərəli etdik Mən var edir , yenə yarım mənim giriş bölünür və yenidən və yenidən. Və yalnız belə bir çox dəfə var yarıya indirir daxil giriş bölmək sol, və sağ. Biz görürük saxlamaq ki, formula var yarısında bölgüsünü təsvir yenidən və yenidən və yenidən və yenidən? 

Auditoriya: N olun. 

HOPARLÖR: N olun. Amma sonra başqa bir mühüm addım var, Bu alqoritm daxil n addımlar deyil. Yalnız log n olsaydı addımlar, biz eyni problem olacaq biz ola bilməz əvvəl əmin hər şey sıralanır. Siz minimal n elementləri baxmaq var əmin olmaq üçün n elementləri sıralanır, başqa iman bir sıçrayış var. 

Belə ki, minimal log n addımlar, həm Bu əsas birləşmə addım nə Mən birləşdi mənim sol yarısı və sağ yarısı və mərhələ üzrə gəzmiş? Daxil etmək üçün nə qədər addımlar? Bu n var, amma yalnız olmadı son dəfə daxil. Hər o iç içə zənglər hər On o iç içə əlaqələnir, mən hələ sıralanır. Mən bu iki bu iki uşaqlar birləşdi uşaqlar, sonra bu iki uşaqlar və s. 

Mən yenidən və yenidən birləşmə idi. Neçə dəfə? Belə ki, hər dəfə mən bölünmüş siyahısı yarısında, mən bir birləşməsi idi. Bir birləşmə etmək, yarısında siyahısı bölün. Siyahısını ayırıcı əgər Belə ki, log n dəfə edilə bilər, və birləşmə nəticədə n edir addımlar, nə indi üst ola bilər çalışan haqqında bağlı Bizim alqoritm vaxt? n log n. 

Və həqiqətən, nə ki biz burada əldə etdik. Belə ki, vizual görmək ki, hiss bu üç şeyi yan-yana run n n qarşı kvadrat n log n qarşı kvadrat. Biz görəcəksiniz əsaslı olan, bu gün, həm də gələcəkdə yalnız, çox, çox daha sürətli edir. Bu uşaqlar üçün alqış dəyirmi, Mən stress top ilə mükafatlandıracağıq. Bu gün burada təxirə bildirin, və Biz bazar ertəsi görəcəksiniz.