>> HOPARLÖR: Bu CS50 Tüm hakkıdır.
Bu haftanın üç sonu ve eğer Eğer zaten avantaj almamış
öğle olacağını biliyorum nerede zamanki gibi bu Cuma
Eğer iyi konuşma keyfini Fire and Ice ve gıda
CS50 en bazı Personel ve sınıf arkadaşları.
Burada bu URL'ye gidin.
>> Şimdi çağırmak, ya olabilir yakında tanımak olabilir,
Burada bu şeyler, hangi sonunda dışarı verilir
Birçok sınıflar için dönem.
Sözde sınav mavi kitaplar, hangi Eğer sınavlara cevaplarınızı yazın.
Şimdi ben burada var 26 gibi Bunların her biri mavi kitaplar,
Z. aracılığıyla bir isim, A yazılır Ve aslında isimler basit, A yönündedir
Z. aracılığıyla Ve biri el bugün gol
ne devam olacak biz hangi Pazartesi günü başladı
çok kod bakarak, ama gerçekten fikirler ve problem çözme bakarak.
Hedeflerinden biri ve Bu dersin vaatleri
Daha fazla düşünmek için size öğretmek için dikkatle, daha metodik,
ve daha verimli sorunları çözmek için.
Ve gerçekten de, gerçekten bunu yapabilirsiniz Hatta bir kod satırı dokunmadan.
Yani filler bir çift var yukarı bugün burada, turuncu ve mavi,
biz bir gönüllü alabilir, belki geriye normalden daha gelen.
Nasıl orada hakkında, aşağı gel.
hedefi için olacak yardım artı burada, bu sınavı yönetmek.
Adınız ne?
>> İZLEYİCİ: Mary Beth.
HOPARLÖR: Mary Beth, yukarı gel.
Senin için burada mikrofonu alayım.
Tanıştığımıza memnun oldum.
>> İZLEYİCİ: Nice to meet you.
HOPARLÖR: Pekala, ben var Burada mavi kitaplar A'dan Z'ye yoluyla,
ve ben iddia gidiyorum Ben, öğrencilerden biri var
ve onlar biraz rasgele geliyorlar üç saatlik sınav bloğunun sonunda,
bu yüzden bazı biten konum Bu gibi yarı-rasgele düzen.
Şimdi sadece bir an iş gidiyor Bu onlar olsun ne kadar aslında şey olmak
sonunda döndü sınıf, büyük olasılıkla.
İşiniz şimdi oldukça, olacak sadece, bizim için bu mavi kitapları sıralamak için
A, Z ile
>> İZLEYİCİ: Ah, bu sonsuza kadar alacak.
>> HOPARLÖR: Ve biz izleyecek Bunu gibi, herhangi bir baskı.
HEDEF KİTLE: Hayır, herhangi bir baskı ya da bir şey.
>> HOPARLÖR: Ve eğlence için, en bir zamanlayıcı koyalım.
>> İZLEYİCİ: Çok eğlenceli, çok eğlenceli.
>> HOPARLÖR: Senin için mikrofon tutabilir.
Pekala, biz sadece bizim hızını iki katına ettik.
Bu arada Yani, benim ne poz verelim Mary Beth için soru olacak
O ne yapıyor olduğunu, nasıl olduğunu o bu çözümü hakkında gidiyor?
Ve aslında, sahip olmayabilir Hiç bir şey düşündüm
Eğer pick kadar basit Böyle 26 kitap kadar,
Doğal var olan Onlara sipariş.
Süreci nedir Bu aslında kullanmak?
Oldukça rastgele sadece Gördüğünüz ilk bir toplama
ve onun yerine koyarak?
Ilk etrafında ellerini hareket etmeyin Bir sonra B arıyor arıyor?
Eğer bir göz atın musunuz yan yana bir çift
ve sadece bir dakika bekleyin, bu demek doğru değil, ve sonra sipariş takas?
Biz Pazartesi günü zaten gördüm yolları bir dizi var ki
hangi biz bu yapmak ve Nitekim biz burada sonuna yakın olarak,
Ben belki not alacağını Neyin Mary Beth yapıyor.
Biz öyle görünüyor birkaç yığınları var, bir üç küçük olanları, bir büyük.
>> İZLEYİCİ: Ben bunları sipariş ediyorum Ben iki harf bulduğunuzda
Ben biliyorum, bir dizide birlikte olduklarını, I do not böylece onları bir araya koymak
tutma konusunda endişelenmenize gerek kitap bir bütün dizisinin iz.
Bu, bir ilk, ah, sadece var Ben burada bu yığını var.
Neredeyse gibi Yani,: SPEAKER Bir puzzle parçaları olduğunu
doğru şekli var birbirleri ile maç.
HEDEF KİTLE: Oldukça fazla, evet.
HOPARLÖR: Tamam, mükemmel.
Ve şimdi bu her kazık muhtemelen sıralanır?
>> İZLEYİCİ: Evet.
Z. All aracılığıyla Pekala, A: >> HOPARLÖR Doğru, tebrikler, bunu yaptım.
Sen seçim var.
Mavi?
Pekala, bunun için teşekkür ederim.
Yani Mary Beth teklif vermedi ne onun yaklaşımı oldu,
ama başka bir yaklaşım nedir nasıl Bunları sıralama hakkında gidebilir?
Ne yapardın?
yenmek için kayıt olurdu bir dakika ve 50 saniye ya da öylesine,
artı ben unuttum olanları saymak.
Ne yapardın?
Evet?
HEDEF KİTLE: yığını alın.
Baştan başlatır.
Senin kağıtları kontrol edin.
Ve üst bir yüksek ise daha belki, onlar vardır
alt biridir yüksek, daha sonra onları geçmek.
>> HOPARLÖR: Tamam, bu yüzden başlayan üst ve alt kısmında,
ve sonra yolunuzu çalışma içe böyle, onları takas?
Benzer Tamam, bu yüzden biraz kabarcık tür ruhu içinde,
ancak aşırı seçerek değil komşu çiftleri.
Ama kısa var olduğunu Farklı şekillerde mutlaka bir demet
Biz bunu, ve olabilir açıkçası, ben tür size düşünüyorum
Sağ, bir kaç yaklaşımları kabul?
Dört sıralı kazık tür yapılmış ve Sonra birlikte etkili onları birleşti.
Ve başka, daresay, var tamamen tekniği.
Sen, büyük bir yığın olarak ele vermedi Eğer, dört dörtlü içine sorunu bölünmüş
olacak, ve sonra bir şekilde eğer Sonunda onları birleşti.
>> Yani sonuçta, düşünelim, Biz bunu nasıl başka.
Biz kavramı resmiyet kabarcık sıralama son kez,
ve kabarcık sıralama hatırlama olan bir Biz görüntülenmiştir algoritma
buraya sınıf arkadaşlarının sekiz, görünüşte rastgele ilk sıralanır.
Ve biz o takdirde, çiftler halinde karar İki element, düzenin dışında
sadece onları takas.
Bu yüzden, dört ve iki tanesi Açıkçası bozuk,
böylece bu iki sınıf arkadaşları pozisyonları açık.
Ve sonra, dört ve altı tekrarlanan Daha sonra altı ve sekiz, her tekrarında,
sağa hareket.
>> Peki, kaç eşli sekiz kişiyi verilen yürüyüş sırasında karşılaştırmalar ben yaptım
Böyle bir tekrarında sağa sola?
Kaç karşılaştırmalar?
Yedi, değil mi?
Sekiz varsa Çünkü İnsanlar ancak çift var
Onları ve hareketli tutmak bir, sağa hop
Eğer sekiz olması için gidiyoruz değil karşılaştırmalar karşılaştırın olamaz çünkü
kendisine karşı bir eleman, ya da olur Sadece anlamsız, bu yüzden yedi var.
Ya da daha genel olarak, eğer Biz n insanlar var, biz
n eksi 1 karşılaştırmalar yapmak kabarcık sıralama ile.
>> Peki ne kadar iyi şimdi düşünelim veya Kötü kabarcık sıralama aslında, ve deneyin
ile kendimizi kelime vermek Böyle eleştiri algoritmaları hangi,
ve yakında kendi.
Ile ilk geçişte Yani kabarcık sıralama, ilk kez
Ben genelinde sağa sola yürüdü sahne, beni n eksi 1 karşılaştırmalar aldı.
Ve bu olacak benim ölçü birimi, değil mi?
Ben tür konuşma ve gezinme oldu, biraz biraz yavaş, hızlı,
böylece saniye benim sayısını sayma özellikle söylüyorum değil,
ancak sayısını sayma Ben Pazartesi günü yaptığı işlemler,
İki kişiyi karşılaştırarak, hissediyor bir ölçü birimi gibi güzel.
>> Yani n eksi 1, ilk defa adımlar, ama sonra sonra ne oldu?
Tek seferde bir ters nedir Aksi takdirde sıralanmamış liste boyunca?
Eğer eleman hakkında bana söyleyebilir neler Oradaki tüm yol kimdi?
Evet?
Bu doğru, büyük unsur oldu?
Sayı sekiz, hatta she olsa burada başladı, her zaman
karşı onu karşılaştırıldığında Bir komşu, o tuttu
sağa kadar köpüren Listenin tarafta.
Ve gerçekten de, bu nerede algoritması adını alır.
>> Şimdi bu mantığa göre, kaç karşılaştırmalar Ben ikinci kez yapmak gerekir
Soldan sağa o pas yapmak?
n eksi 2, değil mi?
I eğer sadece benim zaman israf olacaktır birine karşı sekiz karşılaştırarak devam
Başka biz zaten biliyoruz çünkü o doğru yerde idi.
Yani bir bir parçasıdır optimizasyon, sonraki geçiş böylece
artı eksi n iki adım olacak, burada, n, insan sayısıdır.
Şimdi tür bile, tahmin edebilirsiniz Eğer bir bilgisayar bilimcisi değilseniz,
bu nasıl biter.
Bu algoritma sonunda, muhtemelen Eğer sadece bir karşılaştırma sol var.
Sen tür düzeltmek zorunda durumda iki listenin başında
ve bir düzenin dışında ve bir ve iki olmalıdır
bu nedenle bu dibe artı 1 Final karşılaştırılması.
>> Şimdi nokta, nokta, bu kadar dalgaların nokta tür suludur detay bazı eller,
ama sadece gitmek önde ve basitleştirmek edelim.
Yüksek gelen hatırlayacak olursak Sizin okul, açıkçası, bir sürü
vardı matematik kitapları Biraz hile levha
Ön kapak veya Seni gösterdi arka kapak
ne gibi serisi toplamları Bu sonuçta kadar ekledi.
Genel durumda, bir varsa n gibi değişken ve aslında bu bir,
Eğer baktı eğer senin eski okul matematik kitabı,
Eğer bu aslında görürdünüz Burada bu toplamı kadar ekler
n kere n eksi 1, tüm bölü 2.
Yani şimdi bana sadece şart izin Bu yüzden inanç bir sıçrama üzerine, doğrudur
bu toplar ne kadar, ve biz olabilir
Daha genel bir durumda olduğunu kanıtlamaktadır.
Ama şimdi gelin bunu genişletmek edelim.
Yani bu çarpın izin böylece var n kare, eksi n, tüm 2'ye bölünür.
Yani, gerçekten n kare var eksi n üzerinde 2, 2 bölü,
böylece tüm güzel ve ilginç.
Ama ne biz olur plug-in değeri?
Ben sekiz yoktu varsayalım İnsanlar, ancak bir milyon söylüyorlar.
Ve bir milyon sırf bu, oldukça büyük bir sayı var
en bu in fiş ve ne görelim.
Ben bu formüle bir milyon fiş Yani eğer Ben, bir milyon kare almak için gidiyorum
2 bölü eksi bir milyon, 2 bölü.
Şimdi ne olacak ki eşit olacak?
Yani 500 milyar, eksi 500.000.
Ve aslında yaparsam Bu matematik dışarı, o aracı
bir milyon sıralama kabarcık tür insanlar
Bana 499.999.500.000 sürebilir sonunda adımlar veya karşılaştırmalar,
biz sadece extrapolating ediyoruz.
>> Bu oldukça yavaş hissediyor, ama açıkçası belirli bir girişi ölçüm
Bu gibi tüm söylüyorum değildir.
Ama gerçekten de n olarak öneririz yok Daha büyük ve daha büyük, bu algoritma alır
tür hissediyor kötü ve kötü, ya da gerçekten
Bunun acısını hissetmeye başlar üstel, bu n, kare
hangi oldukça hızlı ekler.
Ve bu ayrıntı değil Aslında, insanlar üzerinde kayıp
birkaç yıl önce belli bir senatör kim kampanya, bir görüşme için oturdu
Google'ın Eric ile Schmidt, zaman CEO'su,
ve bir soru ile meydan çok bugün keşfetmek gibisin.
Bir göz atalım.
>> [VİDEO OYNATMA]
>> -Senatör, Sen buradasın Google'da, ve ben gibi
cumhurbaşkanlığı düşünmek Bir iş görüşmesi olarak.
Şimdi, almak zor Başkan olarak bir iş,
ve şimdi zorluklarına yoluyla gidiyoruz.
Bu Google'da bir iş için de zor.
Biz sorularınız varsa, ve biz Bizim adayların soru sormak,
ve bu bir Larry Schwimmer değil.
Ne-- siz ben düşünüyorum Şaka, işte burada.
En etkili yolu nedir Bir milyon 32-bit tamsayı sıralamak?
>> -Well--
>> -Özür Dilerim, belki--
>> -Hayır, Hayır, hayır.
Ben kabarcık sıralama düşünüyorum gitmek için yanlış bir yol olacaktır.
>> Haydi, kim ona bunu söyledim?
Ben bilgisayar görmedim Arka plan bilim.
>> -We've Orada bizim casusları var.
>> -Tamam, En farklı soralım Görüşme bir soru.
>> [SON VİDEO OYNATMA]
>> HOPARLÖR: Yani bahsediyoruz ama özel sayılar,
tüm bu yararlı olacak değil.
Bu bir hayat dersi bu balonu değil sıralama, bir milyon girişleri verilen,
gibi birçok milyar 500 gibi adımlar olabilir.
Gerçekten genelleme olamaz Çok etkili bir şekilde gelen
ve iyi tasarım kararları programları yazarken.
Yani nasıl olsa odaklanmak izin Bu sonuç kolaylaştırmak olabilir.
>> Yani burada sarı vurgulanmış ettik n sonucu, 2 bölü
yani bir milyon kare 2 ile ayrılır ve daha sonra
Ben vurgulanır kadarıyla nihai cevap oldu
Biz kapalı çıkarılır kez n bölü 2.
Ve ben şimdi yapmaya gidiyorum iddia olduğunu Eğer kapalı çıkarma durumunda kimin umurunda halt
2 üzerinde biraz eski n birinci Bu formülün parçası çok daha büyük?
Diğer hakim terimi, burada n, 2 bölü
gibi, açık bir şekilde, çok daha büyük olduğunu n, bir milyon gibi büyük olur
Bu gerçekten büyük bir fark var 500.000.000.000 arasındaki gün sonu
ve 499999500000?
Tam olarak değil.
Ve böylece ne için gidiyoruz Bilgisayar bilim adamları gibi yapmak
Bu alt mertebeden terimleri görmezden ve Bu ve gerçekten böyle bir şey almak
Sadece onu basitleştirmek önemli olacak terim.
büyük, bizim veri setleri, büyük olsun Bizim veritabanları, daha fazla web sayfaları olsun
biz daha fazla aramak zorunda arkadaşlar Facebook'ta var.
N büyüdükçe >> biz gerçekten konum en büyük umurumda olacak
ve bu tür herhangi bir analizde süreli Bizim algoritmaları performans.
Ve ben ne biliyorum, söylemek için gidiyorum, kabarcık sıralama büyük O sırasına üzerinde,
n sırasına kare.
Tam n değil Gördüğümüz gibi kare,
ama kimin umurunda gerçekten bu küçük terimler hakkında,
ve açıkçası, kim gerçekten Biz 2 ile bölmek umurunda?
Bu sadece bir sabit faktör var.
Ve 250 karşı 500 milyar olduğunu milyar anlaşma gerçekten büyük?
Ben sadece bir yıl beklemek, kelimenin tam anlamıyla benim laptop izin
donanımda iki kat daha hızlı olsun ve farkı bu tür
Sadece zamanla doğal gider.
>> Yaklaşık nedir bakım ifadesi, bölüm
değişir gidiyor ifade Bizim girişi büyük ve büyüdükçe.
Ve gerçekten de, gerçek dünyada, giderek neler var
bizim sorunlara giriş ve algoritmalar büyüyor.
Yani büyük O gösterimi olacak, asimptotik gösterimi, biz sadece
Bilgisayar bilim adamları tanımlamak için kullanın performans, ya da çalışma süresi,
bir algoritma.
Biz algoritmaları karşılaştırabilirsiniz Böylece Yazılı farklı bilgisayarlarda
farklı kişiler tarafından kullanılarak Bazı temelde benzer metrik
karşılaştırmaların sayısı gibi sen Belki swap sayısını yapma, ya da
Eğer yapıyoruz.
>> Ne biz gitmiyoruz sayısı zaman miktarıdır
Bu saat geçer tipik haliyle duvar üzerinde.
Ne endişe etmeyeceğiz yaklaşık ne kadar bellek
En bugün kullanıyorsanız Bu olsa, en az
Biz ölçmek olabilir başka bir kaynak.
Biz bizim analizler temel denemek için gidiyoruz sadece temel operasyonlar, olanlar,
açıkçası, en görsel görebilirsiniz.
N büyük O gibi bir şey So kare, ben n Ç kare iddia
bir üst sözde ile bağlı olduğu kabarcık tür çalışma süresi.
Diğer bir deyişle, eğer var olduğunu iddia etmek istedim
kaç bu üst sınırı bir algoritma sürebilir adımları,
o n büyük O'da olacak Bu durumda kare, bir üst sınır.
>> Yerine değiştirirsem ne Hikaye değil, kabarcık sıralama hakkında olmak
ancak bu üst sınır hakkında.
Bir algoritma düşünebilir biz zaten baktım ki
Kendilerinin üst sınır, maksimum zaman ya da operasyonların ölçmek,
sınırlı olduğu söylenebilir istiyorum n ile, doğrusal bir fonksiyonu,
değil kavisli olan bir kuadratik bir?
Bir algoritma nedir ki Her zaman daha fazla alır
n, adım, ya da bu gibi daha 2n adımlar veya 3n adımları?
Evet?
>> İZLEYİCİ: Bulma Bir listedeki en büyük sayı?
>> HOPARLÖR: Mükemmel bulma Bir listedeki büyük sayıda.
Ben bir liste verilmiş yaşıyorum Örneğin insanlar,
kim her biri bir numara tutuyor maksimum sayı nedir
adımlar beni almalı, makul akıllı bir kişi,
Bu listede en büyük kişiyi bulmak için?
n, değil mi?
En kötü durumda, nerede Çünkü En büyük değeri olabilir?
Doğru, sonunda tüm yol.
En kötü durumda Yani Üst bağlı, ben belki
tüm yol gitmek zorunda Burada ve benzeri olmak,
oh, burada sayı sekiz var, ya bu değer ne olursa olsun.
Şimdi sadece aptalca olurdu Ben, doğru devam etti olur?
Daha fazla ve daha fazla eleman arıyorsunuz Bunlardan son orada olup olmadığını?
Yani kesinlikle n bir üst sınırdır.
Ben almak gerekmez daha fazla adım.
>> Bunun yerine eğer ben önerdi ne Bu dünyada algoritmaları vardır
olan bir çalışan zaman var Günlük n büyük O tarafından sınırlanan, n log?
Nerede daha önce gördük?
Evet?
>> İZLEYİCİ: Telefon rehberi probleminde?
HOPARLÖR: Telefon rehberi problemi gibi.
Nasıl ölçüsü neydi kadar zaman ya da kaç gözyaşı onu
Benim gibi birini bulmak aldı Telefon defterinde Mike Smith?
Biz günlük n olduğunu iddia ve Hatta yabancı ya da eğer o var
ne küçük bir puslu logaritma veya üs oldu,
sadece günlük n hatırlıyorum genel olarak işleme değinmektedir,
Bu durumda, bölme tekrar ve tekrar yarısında şey,
ve tekrar ve tekrar, böyle öyle Bunu giderek küçük olur.
>> Peki emin atıfta n log, Telefon rehberi örnek,
teoride ikili arama, ne zaman biz , gemide sanal kapılar vardı
veya Sean iken bir şey arıyor.
O ikili arama kullanmış olsaydık, n log ne kadar üst sınır olacak
geçen süre.
Ama koştu o algoritmalar n ne anahtar detay kabul log?
Liste, sağ sıralanır olduğunu?
Sizin algoritması ise yanlış senin girdi, sıralanır
ve henüz kullanıyorsanız İkili arama gibi bir şey
Eğer atlamak olabilir çünkü Sağ öğe üzerinde
Farkında olmadan gerçekten var.
>> Şimdi bu bir büyük O ne demek olabilir?
Bu algoritma anlamına gelmez , ve tek bir adım alır
o sadece bir sürer demektir adımlannın sabit sayısı.
Belki öyle, belki değil, 1 var 10, belki de 1,000 var,
ancak bağımsızdır sorunun büyüklüğü.
Ne kadar büyük n, sabit zaman algoritması
hep adım aynı sayıda alır.
Peki bir algoritma olabilir biz yaklaşık ya da sadece konuştuk
sezgisel o size geliyor hep sözde sabit zamanda çalışır?
Evet?
>> İZLEYİCİ: iki sayı ekleyin.
HOPARLÖR: İki numara ekle 2 artı 2 yapılır, 4 eşittir.
Yani işe yarayabilir, başka ne?
Nasıl daha gerçek dünya hakkında, evet?
>> İZLEYİCİ: Bulma Bir listedeki ilk şey.
HOPARLÖR: İlk bulma Bir listede eleman, emin olun.
Biz aslında durduk Zaten diziler hakkında,
at almak nasıl Bir dizideki ilk elemanı,
ne kadar uzun Dizi C kodu nedir?
Sadece dirsek gibi kullanmak sıfır gösterim, bam, sen oradasın.
Ve bir kenara olarak gerçekten diziler, Destek şey genellikle bilinen
Rasgele erişim olarak rastgele erişimli Bellek, kelimenin tam anlamıyla can çünkü
herhangi bir yerde atlamak.
Biz sadece bu daha da yapabilirsiniz biz hafta sıfır geri sarma
biz Scratch yaptım.
Ne için aldınız ne kadar zaman Scratch blok yürütmek söylemek?
Sadece zaman sabiti, değil mi?
Bir şey söylemek söyle şey, önemli değil
Büyük çizikler dünya nasıl, her zaman var zaman aynı miktarda alacak
sadece bir şey söylemek için.
>> Bu sabit zaman Yani, ama kapak tarafı nedir?
Bu üst olsaydı sınırları, ne isterseniz
alt sınır tanımlamak için Bizim algoritmaların çalışma süresi?
Neredeyse en iyi durumda potansiyel, eğer sen,
bu terimler en iyi şekilde geçerli olabilir ama davalar, en kötü durumda, ortalama vakalar daha fazla
Genellikle, ama sadece odak sağlar alt sınırları daha genel.
Ne var bir algoritma var bir düşük değerli n adımlarının bağlı
veya 2n adımlar, yoksa 3n adımları?
N, bazı adımlar faktörü Bu onun alt sınır var.
Evet?
>> İZLEYİCİ: Kabarcık sıralama?
>> HOPARLÖR: Kabarcık sıralama alır Eğer minimal n adımları, neden?
Neden?
Neden bu başlangıç ​​sana gelmek gerekir sezgisel, öyle olsa bile sadece
Henüz?
Evet?
>> İZLEYİCİ: [duyulamaz].
KONUŞMACI: Kesinlikle.
Mümkün olan en iyi senaryoda kabarcık sıralama, ve algoritmalar bir sürü,
Sana sekiz kişi el, eğer kim zaten sıralanır,
bu aptalca olurdu Sizin için, algoritma,
ileri ve geri gitmek için defadan fazla, değil mi?
En kısa sürede senin kadar Çünkü bir kez listede yürümek,
Eğer, fark oh gerektiğini, ben yapılan hiçbir swapları, bu liste, çıkış sıralanır.
Ama sen n adımlar atmaya gidiyor.
>> Ve tersine, ne başka var Bu konuda düşünme yolu?
Kabarcık sıralama bir omega olduğunu, yani n, konuşmak,
Eğer bakarsanız, çünkü daha az n elemanları, ne
temel sorun vardır?
O sıralanır eğer sağ bilmiyorum.
Biz sekiz kudreti bakış insanlarda İnsanlar ve, gibi oh, o sıralanır var olmak
beni n adımlar sürmedi, ama yaptım.
Gözlerin bile nazik sana rağmen bir, vizyon büyük bir alan var
sekiz elemanları baktı, Eğer, sekiz kişi baktı
Bu etkili bir sekiz adım var.
Ve ben bütün yürümek sadece Liste, evet sıralanır, fark yok.
Ben durdurmak Eğer yarım tüm düşünme Doğru, bu oldukça şimdiye kadar sıralanır var,
o sıralanır değil oran nedir?
Bu doğru olacak değil algoritmaları.
Daha hızlı, ama yanlış olabilir.
>> Şimdi biz bir yol olan var bir alt sınır açıklayan,
ve sürekli zaman hakkında ne?
Bir düşük olan bir algoritmadır biri kendi çalışma zamanında bağlı?
1 adım 2 adım, 10 adım, ama sabit n bağımsız olarak,
girdi boyutu?
Evet, arka.
>> İZLEYİCİ: Printf?
HOPARLÖR: Bu nedir?
HEDEF KİTLE: Printf?
KONUŞMACI: Printf.
Emin, tamam.
Bu yüzden adımlar sabit sayıda alır.
Ve ben şimdi şimdi-- gerekir Biz C kodu hakkında konuşuyor
ve Scratch, bir şey diyelim ki gibi, printf ile,
dikkatli olsun başlamalıdır.
Printf sürer Çünkü giriş, bir dize var,
ve dizeleri teknik uzunluğu var.
Şimdi almak istiyorsanız size, sakıncası yoksa,
teknik o printf iddia olabilir değişken uzunluk girişi sürer,
ve kesinlikle daha fazla sürebilir Zaman, bu uzun bir dize yazdırmak için
Bu uzun daha.
>> Yani biz sadece ne düşünün sıralama ve örnekler arıyor?
Telefonda Mike Smith hakkında neler Kitap, ya da daha genel olarak ikili arama?
En iyi durumda, ne olur acaba?
Ben, bam, telefon defterini açmak ve Mike Smith'in numara var.
Ben hemen onu arayabilirsin.
>> Belki iki adım, bir adım aldı ancak adımlar sabit sayıda
Ben şanslı var ise.
Ve açıkçası, biz gördüm Pazartesi günü sınıf arkadaşı
Arka arkaya iki kez oldukça şanslı olsun.
Ve bu gerçekten sabit oldu bir alt sınırları içinde zaman
Söz konusu algoritma bulmak için Bu kapalı arkasındaki numara 50
kapılar.
>> Şimdi, bir kenara, keşfetmek gibi hem büyük O, üst sınır olduğunu
ve omega, düşük, bağlı , aynı birdir
Aynı formül olduğunu parantez, siz de yapabilirsiniz
sadece fantezi olmak demek, bir şey teta
n veya başka bir değer teta evi.
Bu sadece zaman büyük anlamı Ç ve omega aynıdır.
Şimdi seçim sıralama hakkında ne?
Şimdi bu yeni kelimeleri kullanmak edelim.
Seçim tür, ne kalmıştık Yine yapıyor, ve tekrar ve tekrar?
Ben üzerinden ileri ve geri gidiyordu Liste, kimin arıyor?
küçük sayı.
>> Peki kaç adım, nasıl Birçok karşılaştırmalar I did
anlamaya için yapmak zorunda olan Listede en küçük elemanı oldu?
n eksi 1, değil mi?
Ben sadece ben biri ile başlamak Çünkü eğer Verilen ve ben ona karşılaştırarak başlar,
Onu ya da onu, onu sonra Onu, onu ya da onu, ben ya
Sadece elemanları eşleştirebilirsiniz Birlikte n eksi 1 kez.
Yani seçim sıralama benzer alır n eksi 1, ilk defa adımlar.
O beni sürer >> kaç adım İkinci küçük elemanı bulmak?
n eksi 2, ben olduğum için aptal olmak Ben aynı insanlar bakarak devam edersem
Yine ben zaten onu seçtiyseniz ya da onu ve onların yerine koyun.
Üçüncü adım, n, eksi 3, n eksi 4.
Biz bu desen gördüm önce ve gerçekten
Seçim sıralama benzer sınır bir üst vardır
n biz toplamı kadar yaparsanız kare.
Alt sınır, seçim sıralama nedir?
Minimal, ne kadar zaman gerekir seçimi Biz Pazartesi günü tanımlandığı gibi sıralamak almak?
İki seçenek önerilmesi.
Belki daha önce olduğu gibi, n var.
Belki bunun gibi, kare n var Üst sınır olarak şimdi.
>> İZLEYİCİ: n kare.
HOPARLÖR: kare n.
Neden?
>> İZLEYİCİ: Eğer Çünkü [duyulamaz] tanımlamak için.
>> HOPARLÖR: Kesinlikle.
Ben seçim sıralama tanımlanan en azından oldukça naif oldu, devam,
küçük eleman bulmak.
Küçük eleman bulmak, tekrar gitmek.
Hiçbir tür yok Orada ki optimizasyonu
Bana sonra iptal izin olabilir Sadece n ya da öylesine adımlar.
Bu yüzden, gerçekten seçim sıralama, n omega kare.
>> Ben aldı ekleme tür, ne Ben verildi, ve sonra onu plopped kim
ya da onu doğru yerde?
Sonra, ikinci kişiye ilerledi doğru yerde ona plopped.
Sonra gelecek kişi, plopped Onu ya da onu doğru yerde.
Bu çok olduğunu fark lineer, tabiri caizse.
Ben değilim, düz bir çizgi değilim ileri ve geri gitmiyor,
Ben asla gerçekten geriye bakarak, ama ettik Onu taktığınızda ne oluyor
başında içine onu ya Liste biz Pazartesi günü yaptığımız gibi?
Ne oluyor?
Evet?
HEDEF KİTLE: [duyulamaz].
HOPARLÖR: Evet, bu Doğru, yakalamak oldu?
Sen hatırlayacağınız senin sınıf arkadaşları, onlar eğer
herhangi bir hareket ile yapıyor kendi ayakları, bu bir operasyon oldu.
Yani eğer orada üç kişi burada olduğumuzu ve Yeni bir kişi, orada yol üzerinde aitti
Bu gibi uzun sahnede, emin, o ya da o sadece sonuna kadar gidebiliriz.
Ama biz düşünmeye eğer Bilgisayar ve bellek dizi
Bu insanlar gidiyor üzerinde shuffle zorunda
o kişi için yer açmak için.
Böylece bu durumda n eksi 1 sürümeleri, n, eksi 2 sürümeleri n
eksi 3 sürümeleri sadece tür olduğunu değil önümde, arkamda oluyor
daha önce olduğu gibi, bir anlamda.
Şimdi bir kenara olarak, ve gibi online görmüş olabilir
hakkında çevresinde alay başlarsanız sıralar, pek çok farklı olanları var
Bunların dışında orada bazı diğerlerinden daha iyi.
Gerçekten de, Saçma sıralama biridir Bu bakmak için eğlenceli tür.
Saçma sıralama bir dizi alır sayılar ya da bir deste demek,
rastgele onları karıştırır, ve kontroller onlar sıralanır eğer.
Değilse Ve, yine öyle.
Değilse, yine öyle.
İnanılmaz aptal.
>> Ve gerçekten, sen okursanız Wikipedia makalesi gibi,
onun takma aptal tür.
Sonunda çalışacaktır, umarım yeterli zaman verildiğinde,
ama zaman bu miktarı oldukça zaman alabilir.
Ben, diyelim eğer hız şeyler Yani Daha önce Mary Beth'in Örneğin kadar,
Birkaç daha fazla eleman sağlayarak, ama iki işlemci.
İki kişi, eğer Beni katılmadan sakıncası olur değil.
Nasıl yaklaşık 1 buraya, ve en orada kimse go-- izin?
Oradaki kimse?
TAMAM MI.
Siyah Sen gömlek, evet, aşağı gel.
Pekala, senin adın ne?
>> İZLEYİCİ: Peter.
>> HOPARLÖR: Bu nedir?
>> İZLEYİCİ: Peter.
HOPARLÖR: Peter David, nice to meet you.
Pekala, biz burada Peter var eğer buraya masaya gelmek istiyorum.
Ve senin adın ne?
>> İZLEYİCİ: Elena.
KONUŞMACI: Elena.
Tamam, seninle tanışmak güzel.
Elena Peter buluşuyor.
Peter, Elena.
Ve Andrew gerekir burada da yukarı, lütfen.
Ve meydan gidiyor bir deste sıralamak olmak.
Ve yabancı ise, güverte Kartların gerekir sonuçta
gibi küçük bir şey sıralanabilir Bu biz sonra, kulüpleri yapacağız nerede
maça, ardından kupa ve Bir biri olarak ace gelen elmas,
Kral kadar tüm yol.
>> Kartları Sana vereceğim miktar 52 olacak.
Biz benzer gidiyoruz Sadece bir an zaman sizi.
Biz Andrew atmak için gidiyoruz Burada ekranda,
Bunu gibi öylesine izlemek için.
Ve böylece bu tüm bu , daha görünür
Bu Ben Amazon üzerinde var kartlar.
Yani rastgele zaten sıralanır ve sizi zaman zaman gidiyoruz.
Ve biz gidiyoruz gerçek bu sefer tutmak
bu yüzden size baskı denemek için gidiyoruz aksi halde, bu sıkıcı olsun çünkü
hızlı.
Eğer 52 sıralamak devam olsaydı Şimdi birlikte bazı yollarla unsurlar.
>> Ve yine, bu seyretmek gibi adamlar sonunda neler yapmak
bariz bir üretecek Sonuç, gerçekten düşünmek
nasıl her yapıyorsun, bunu nasıl açıklayabilir.
Yine, bunlar için Tüm işlemler, algoritmalar
Bir insan olarak kabul ediyoruz ki.
Ama muhtemelen uzun yaşadım sezgi, sizden çok önce bile
Bir alma konusunda düşünce bilgisayar bilimi sınıfı size
sezgi vardı olabilir hangi böyle sorunları çözmek için.
Ama bir kez Tanımadığınız desenler ve başlar
ile adımları resmileştirmek için Eğer bu sorunları çözüyoruz,
Eğer çok çözebilir bulacaksınız daha ilginç ve çok daha karmaşık
Hızlı sorunlar.
Yani seyirci birisi, ne algoritmanın en az bir element
Burada kullanıyor olduğunuzu?
>> İZLEYİCİ: [Duyulmaz]
HOPARLÖR: Bu nedir?
HEDEF KİTLE: takım olarak.
HOPARLÖR: takım olarak.
Böylece ilk onlar kümelendiği elmas hep birlikte
o, bütün görünüyor Birlikte görünüyor kalpleri,
ve benzeri, saygı olmadan kartlarındaki numaraları için.
Ve şimdi onlar Örneğin, görünür, sayısına göre dizerek için.
Çok iyi.
>> Pekala, ne oluyor Daha sonra burada son adım olacak?
Dört sıralı suit, bir kez ne dört yığınları yapmam gerekiyor
birini elde etmek için oldukça basit, güverte sıralanır?
Yani biz onları tekrar birleştirmek gerekir.
>> Yani ilginç bir fikir var ki Yine, daresay, hatta çok sezgisel
Eğer tokatladı asla olabilir eğer Bunun üzerine etiket bu tür.
Bölme Bu temel kavramı Sorun değil yarısı bu süre içinde,
ama en az dört parçaya.
Hemen hemen Çözme temelde aynı sorunlar
birbirinden ayrı olarak, ve sonra sonuçları birleştirme.
Ve mükemmel, bitti.
Pekala, büyük bir yuvarlak alkış, eğer biz yapabilirdik.
>> [Alkış]
>> HOPARLÖR: Ben ne olacak hiç bir fikrim yok Bu yapmak, ama burada gitmek.
Çok teşekkür ederim.
Yani, iki dakika görelim ve sekiz saniye,
Eğer arkadaşlarınıza meydan istiyorsanız.
Ne o gidiyor Bu uzak almak bir olmak
daha genel olarak kaldıraç olabilir?
Peki, geri düşünüyorum sayıların bu dizi,
ve bazı geri şimdi düşünüyorum biz geçmişte yazdık pseudocode,
ve bunun için yalancı kod oldu Telefon rehberi problem çözme.
Bu sayede pseudocode I Bir daha metodik bir şekilde numaralandırılmış
Ben bir çok sezgisel nasıl yaptığını anlatan Telefonu bölünmesi insan algoritması
yarısında kitap, tekrar, tekrar, tekrar Ben bulana kadar Mike Smith gibi biri,
O telefon defterinde gerçekten eğer.
>> Ama ben tür ben ararım ne kullanılır Burada bir çok tekrarlayıcı bir yaklaşım,
Özellikle haber hat 8 ve satır 11.
Bunlar iteratif kanıtıdır yaklaşım, bir döngü yaklaşımı,
tam olarak çünkü Onlar neden davranış.
Bu satırlar, hem gitmek demek çizgi, üç, ve mümkün tür
o düşünüyorum senin Bir döngü olarak zihnin gözü.
Bu adıma kadar geri gitmek için söylüyor Üç ve tekrar, tekrar ve tekrar,
ve yine.
>> Ama ne bir anahtar fikir kaldıraç eğer Burada biz son kez yaptım,
ve çizgi 8 basitleştirmek ve hat 11 ve komşularının
Sadece bu, sarı gibi.
Bu temelde kısaltarak değil çok pseudocode,
ancak temelde değişiyor Benim algoritma doğası.
Ne şimdi söylüyorum Aşama 7, adım 10'da,
Mike aramak için aynı şekilde,
ama sadece sol yarım veya sağ yarısı.
>> Yani başka bir deyişle, eğer I, Aşama l'deki başlangıç
, orta açık telefon kitap almak telefon rehberi, isimleri bakmak,
Smith arasında ise, adı en Mike, başka çağrı
Smith daha önce kitapta ise, yedi adım Kitabın sol yarısında Mike arayın.
Ama bu tür gibi hissediyor Doğru, asılı beni terk ediyor?
Sarı olarak, bir talimat, ama ben nasıl
sol Mike aramak Telefon rehberinden yarısı?
Ben bir Nerede var algoritması I
Mike Smith gibi birisi için arama yapabilirsiniz?
Peki, bu bize yüzüne bakıyor.
Ben tam anlamıyla aynı kullanabilirsiniz Program etkin bir üstüne kadar gidiyor
Tekrar ve tekrar çalışma aynı kod satırları.
>> Peki bu bile hissetmeniz gerekir ama döngüsel bir tanım biraz gibi
nerede birileri var yanıtlayan ediyoruz sadece sıralama sorarak sorusu
Yine aynı soru, gibi neden, neden, neden?
biz zor kodlanmış ettik çünkü gerçeklik özel çizgiler bir çift, adım 4,
Bir, eğer, ve adım 12 olduğu hangi etkin bir dalıdır
Biz bu eğreti önlemler var çünkü, Bu algoritma sona eğer biz
Mike bulmak, ya da biz yapmazsan.
Ama şimdi adım 7 ve 10, biz var ne bir özyinelemeli bir algoritma arayacağım.
Ve yineleme gerçekten güçlü bir fikir Bu, ilk bakışta bükme küçük bir zihin var
aşağıdaki gibi şimdi uygulayabilirsiniz.
>> Birleştirme sıralama son sıralama olacak resmen en azından sınıfta bakmak.
Ve bu temelde farklı kesinlikle bu son üç, ve gelen
Son dört Biz Saçma sıralama eklerseniz.
İşte birleştirme sıralama için pseudocode var.
N elemanlarının girişi, yani verildiğinde n büyüklüğünde bir dizi, n, en az 2 olması durumunda
dönmek.
Peki neden bunu var aklı ilk kontrol edin?
Seni el eğer ima neler var uzunluğu n bir dizi 2 azdır?
Zaten doğru, tabii ki, sıralanır oluyor?
Liste ya Çünkü trivially olan bir eleman,
o çünkü kriteri Orada tek şey.
Ya da, demek boyutu sıfır var sıralamak için hiçbir şey doğası gereği, böylece var
o sıralanır.
Orada yanlış sadece bir şey yok.
Yani bizim sözde temel durum var.
>> Bu ruhu benzer Biz Mike ile ne kadar.
Mike telefon defterinde ise, onu aramak.
Orada değilse, vazgeçmek.
Bu sözde temel durum var, emin olmak için Günün sonunda bu algoritma
Bazı durumlarda duracaktır.
>> Ama burada inanç sıçrama, başka, şimdi var elemanların sol yarısı sıralamak
sonra hakkını sıralamak elementlerin yarım,
ve sonra sıralanmış yarıları birleştirme.
Hissediyor Ve burada var gibi biz copping ediyoruz.
Ben sıralamak istedim ettik n elemanları, ve ben
sıralayarak, tamam, bunu yapmak söyleyerek Sol ve sağ sıralama.
Ama ben bir tane söylüyorum Başka bir şey, ve bu
öyle görünüyor ki anahtar tema Bugüne kadar sezgi olarak,
birleştirme bu üçüncü adımı var.
Hangi bile olsa , ruhu o kadar aptal görünüyor
gibi sadece şeyler birleştirme Birlikte, öyle görünüyor
doğru önemli bir adım olduğunu İki sorunların takılması ki
devre sonunda ayrıldı.
>> Yani olacak eğer, hadi yapalım, sıralama birleştirme bir daha gösteri ile mizah beni,
sadece bu yüzden bazı var numaraları ile çalışmak.
Ben sekiz stres alışverişinde Can Sekiz kişilik topları?
Pekala, nasıl dört sen, üç size hakkında Bu bölümde, beş, altı, ve diyelim içinde
7, 8, yukarı geliyor.
Tamam, evet, tamam.
Eksi 8, oraya gidiyoruz, artı 1.
Mükemmel.
Pekala yukarı gel, haydi hızla size numaralarını vermek.
İki numara, numara üç, dört numara, sayı beş, altı, yedi, sekiz.
Ben doğru bu kez sekiz yaptım.
>> Tamam, bu yüzden eğer yapabilirsen devam, ve orijinal düzende sıralamak izin
Dün vardı baktım ki Bu gibi sakıncası olmaz eğer.
Ve masanın önünde yapalım.
Pekala, sıralama birleştirme.
Gidiyor budur ilginç tür almak için,
Kendimi veriyor gibi görünüyor, çünkü çok az bilgi bugün.
>> Peki sıralama şeyden önce birleştirme n elemanlarının girişi,
ve bu, tabii ki az iki Sekiz, ben yapmak için biraz daha fazla iş var.
Şimdi zihinsel bir sınıf olarak Başka dalında şimdi,
hangi üç adım anlamına gelir.
Öncelikle, ben sıralamak zorunda elemanların sol yarısı.
Peki nasıl bunu hakkında gidiyorsun?
Eh, ben tür gidiyorum zihinsel burada liste bölmek,
Eğer zorunda değilsiniz fiziksel hareket ve ben
sadece odaklanmak olacak Burada elemanların sol yarısı.
Yani sıralama hakkında nasıl gidiyor Şimdi boyutta dört bir liste?
Benim algoritması nedir?
Önce kontrol hayır, ikiden n az, Böylece tekrar başka bir bloğa devam.
Sıralama elemanların yarı yaptı.
>> Peki şimdi tekrar, zihinsel, ve bu nerede
Eğer bir sürü tahakkuk zorunda zihinsel tarih, eğer sen.
Şimdi sol sıralama ediyorum Sol yarısı yarısı.
Pekala, şimdi benim aynı birleştirme çağrı sıralama algoritması, daha az iki N edilir?
Hayır, iki, bu yüzden sıralamak zorunda sol yarım ve sağ yarım.
Yani burada biz sol yarısını sıralamak, gidin.
Neden sadece yok bir adım ileri götürmek.
Adınız ne?
>> İZLEYİCİ: Darren.
>> HOPARLÖR: Dan.
Dan öne çekildi.
>> İZLEYİCİ: Darren.
HOPARLÖR: Darren, bitti.
Eğer Darren veya Dan dedin?
>> İZLEYİCİ: Darren.
>> HOPARLÖR: Darren.
Tamam, Darren çekildi ileri ve şimdi sıralanır.
Ve bu neredeyse bir olduğunu anlamsız iddia, değil mi?
Gerçekten ulaşmak için görünmüyor şey, ama en devam edelim.
Şimdi bana hakkını sıralamak izin elementlerin yarım.
Adınız ne?
>> İZLEYİCİ: Luke.
>> HOPARLÖR: Luke.
Hadi, ileri adım.
Bitti, ben Luke sıralamış.
Sol yarısı şimdi sıralanır ve Doğru yarısı şimdi, sıralanır
ama yine, burada önemli bir adım var.
Ne sonraki yapmam gerekiyor?
Sıralanır yarıları Birleştirme.
Şimdi sadece zorunda gidiyoruz ileri geri bu şekilde herkes,
Ben tür ihtiyacım var çünkü Bazı çizik alanı.
Neredeyse bu gibi adamlar masanın üzerinde,
ve ben bazı oda ihtiyacım onları hareket etmek.
Yani birleştirmek için gidiyorum bakarak siz
Sol ve sağ yarısında yarıda.
Ve tabii ki, ilk kim geliyor, Sol yarım veya sağ yarısı?
Yani sağ yarısı, yani bitti Luke geçelim Burada Darren orijinal konumuna getirin.
Ve şimdi sol yarısını birleştirmek için, Darren orada hareket edecek.
>> Yani hemen hemen gibi hissediyor Bir kabarcık sıralama etkisi,
ama benim temel algoritma, Bu sefer çok farklı.
Şeyler nereden Ama şimdi var Biraz can sıkıcı senin yüzünden
zihinsel sarmak zorunda Ben nerede kalmıştık.
Ben sadece Sıralı yarıyı birleşti ettik, hangi Benim algoritması nerede olduğumu demek?
Ben sağ, sağ yarısını sıralamak zorunda?
>> Kelimenin tam anlamıyla, geri alırsanız video, sen olacak
Bu var olduğunu görmek Luke ve Darren noktası
Sol sıralayarak Sol yarısı yarısı.
Sonra o birleşti Sıralanan yarısı, hangi
Bir sonraki adım, sıralama demektir Sol yarısı sağ yarısı.
Pekala, diyelim daha hızlı yapmak.
Pekala, altı, ben iddia gidiyorum Şimdi ileri gel, sıralanır.
Adınız ne?
>> İZLEYİCİ: Adriano.
>> HOPARLÖR: Adriano.
Adriano şimdi sıralanır.
Ve senin adın ne?
>> İZLEYİCİ: Alex.
>> HOPARLÖR: Alex şimdi sıralanır.
Sol yarım, sağ yarısı, Son adım nedir?
Birleştirme.
Oldukça önemsiz, ben değilim altı birleştirmek olacak,
geri adım atmak, Sekiz, bir adım geri almak.
Ve şimdi bu fark yararlı bir paket, ne
Şimdi sol yarısı doğrudur Liste, bağımsız biz başladı nasıl?
Bu sıralanır.
>> Şimdi sıralanır değil şeylerin büyük düzeni,
ancak bağımsız sıralanır diğer yarısı.
Ben tutarsan Şimdi ne adım I am on Hikaye nasıl başladı sarma?
Şimdi sağ yarısı sıralamak zorunda.
Yani şimdi biz dönerken konum Hikayenin başlangıcı,
ve en daha hızlı yapalım.
Yani sıralamak için gidiyorum Bütün listesinin sağ yarısı.
Bir sonraki adım nedir?
Sağ yarısında sol yarısını sıralayın.
Sol yarısını sırala Sağ yarısında sol yarısı.
Ve senin adın ne?
>> İZLEYİCİ: Ömer.
>> HOPARLÖR: Ömer, ileri adım, bitti.
Sol yarım sıralanır.
Ve senin adın ne?
>> İZLEYİCİ: Chris.
>> HOPARLÖR: Chris, bir adım atmak ileri, şimdi sıralanır.
Şimdi önemli bir adım nedir?
Birleştirme.
Yani bir yerde birleştirmek için gidiyor Burada, geri adım atması eğer,
ve üç gidiyor birleştirme, bir adım geri almak.
Yani sol yarısı Sağ yarım, şimdi sıralanır.
Açıkçası, bu algoritma biz gibi hissediyor daha önce yol daha fazla zaman harcıyorsun,
gerçek zamanlı olarak bunu ama eğer, biz olacak paketler olacak görmek.
Şimdi burada ben sağ, ben Sağ yarısında yarısı,
Beni go ahead ve sol yarısını sıralamak verelim.
İleri Adım, senin adın ne?
HEDEF KİTLE: Ramsey.
HOPARLÖR: Ramsey şimdi sıralanır.
Adınız ne?
>> İZLEYİCİ: Marina.
>> HOPARLÖR: Marina şimdi sıralanır iyi, ileri bir adım götürsem.
Burada önemli bir adım şimdi ben, birleştirme edilir benim iki listelerden koparmak için gidiyoruz,
sol ve sağ.
Beş, ilk gelip gidiyor ve yedi yanındaki gelip gidiyor.
Ve yine, bu kasıtlı olduğunu.
onlar alıyorsun gerçeği ileri ve geri adım
temsil etmek içindir ki biz değil kolayca yerine bu algoritmayı yapmak
kabarcık sıralama, seçme ve sıralama gibi, ve yerleştirme sıralama nerede biz sadece
insanları takas tuttu.
Ben tam anlamıyla bir tür ihtiyaç karalama kağıdı olan
Bu millet koymak Ben birleştirilmesi yaparken,
ve sonra tekrar yerine koyabilirsiniz.
Ben bir kullanıyorum çünkü bu anahtar yeni kaynak, uzay, sadece zaman.
>> Tamam, bu inanılmaz.
Sol yarısı doğru yarısı, sıralanır Sıralanan, şimdi anahtar birleştirme aşaması.
Nasıl bu birleştirme gidiyorum?
Eğer takip edeceğiz Yani benim Sol el ve sağ el,
Ben sol elimi işaret gidiyorum Sol yarısında, benim sağ
Sağ yarısında, ve şimdi var içinde birleştirmek için adım adım karar.
Kim Açıkçası önce gelir?
Bir numara.
Yani buraya gel, Burada bizim karalama defteri var.
Yani şimdi bir tane, ve haber sayı Sağ elimle ne yapacağım,
Benim sağ bir hareket gidiyorum numara üç nokta üzerinde adım,
ve şimdi yapmak zorunda Aynı karar.
Ve aslında hakkını standı Luke burada eğer yapabilirsen ön,
Bu bizim karalama defteri çünkü.
Peki kim geliyor?
Biz iki numaralı ile Luke var veya Chris numarası üç ile.
Açıkçası Luke, sayı İki, bu yüzden buraya gelmek.
>> Ama benim sol şimdi gidiyor Darren işaret etmek artırılır,
ve burada anahtar ile take away var birleştirme, ben bunu yapmaya devam edeceğim,
Açıkçası, eğer tür mantığını izleyin.
Ama ellerim asla geriye gidecek,
ki ben sadece hiç taşınıyorum demektir Benim birleştirme işlemi sol,
ve bu anahtarı olacak Sadece bir an bizim analizi.
>> Peki şimdi hızla bu kadar bitirelim.
Yani üç yanında gelir, Daha sonra dört yanında gelir,
ve şimdi beş altı, sonra, sonraki gelir Yedi, ve sonra nihayet sekiz ve.
Yavaş algoritması gibi hissediyor Henüz, ama aslında biz eğer
Aynı tür de çalıştırın Saat hızı, böylece
ile aynı, konuşmak daha önce olduğu gibi saati geçiyor.
Neden?
Peki, bir atalım sonuçta bak.
>> Geri buraya dönelim, bana izin görsel bir gösteri yukarı çekin
biz sadece ne yaptığını.
Bunun üzerine, burada yakınlaştırma Burada sayfa, Firefox söylüyorum
Biz sıraya istiyorum Bu kutuya kadar, diyelim
, kabarcık sıralama söylemek hangi biz artık iyi tanıdık
Başka bir seçim sıralama, Oldukça basit bir,
ve şimdi bugünün birleştirme sıralama, hangi Bizim iklim biten olacaktır.
çok daha uzun sürdü bu yüzden nedeni Burada insanlar ve ben sözlü olduğunu
Açıkçası, ben her adımı açıklayan ediyorum.
Ama sadece bu, çok yürütmek durumunda gibi yaptığımız kabarcık sıralama ve seçme
sıralama değil sadece görsel, izle sadece ne kadar daha verimli
Bu kaldıraç bölünme ve fetih
bu, bir veri seti için kullanılan zaman bile boyutu sekiz, ama hatta çok,
çok daha büyük.
Ben tarafından, sıralama yan birleştirme vermek bu algoritmaları ile yan.
Bu acı almak için gidiyor hızlı ve bitiş
Özellikle iklim değil onlar sadece sıralanır sonuna kadar.
Fakat anahtar olduğunu take away sıralama ne kadar hızlı birleştirme bakmak
Eğer ben olduğumu düşünüyorum sürece, oldu sadece tür seninle karıştırmasını.
Bu son bir kez yaparsanız, Şimdi bu yeniden izin, geri dönelim
ve, kabarcık sıralama seçin ve sadece tekmeler için,
en ekleme seçmenize izin sıralama, sadece iyi ölçmek için.
Ve bu sefer yine diyelim birleştirme tür seçin ve atalım
aslında yan bu yan çalıştırın.
>> Ve bir şans eseri, aslında değildir.
Ne ben etkili yaptık Ben ettik olduğunu yine yarısında benim girişi bölünmüş
ve tekrar ve tekrar.
Ve yapabilirsiniz, sadece çok kez var yarıya içine girdi bölmek, sol
ve sağ.
Ne görmeye devam formülü Bu yarıda bölünme açıklar
Tekrar ve tekrar, ve tekrar ve tekrar?
>> İZLEYİCİ: n açın.
>> HOPARLÖR: n açın.
Ama sonra bir diğer önemli adım var, Bu algoritma günlük n adımlar değildir.
Sadece log n olsaydı adımlar, Aynı sorun olurdu
Biz olamaz nerede daha önce olduğu gibi Her şeyin en sıralanır.
Sen minimal n elemanlı bakmak zorunda Emin olmak için n elemanlar sıralanır,
aksi takdirde bir inanç sıçrama.
>> Yani minimal oturum n adımlar, ama oluyor Bu anahtar birleştirme adımı ne olacak
Ben birleşti benim sol yarım ve sağ Yarım ve sahnede yürüdü?
Bu birleştirme kaç adım?
Bu n var, ama ben sadece etmedi son bir kez birleştirme.
Her üzerindeki bu yuvalanmış çağrıları her günü bu yuvalanmış birleştirmelerinin, ben hala sıralanır.
Daha sonra bu iki bu iki adam, birleşti çocuklar, daha sonra bu iki adam ve benzeri.
>> Bu yüzden tekrar birleştirme, ve yine yoktu.
Kaç kere?
Yani her zaman bölünmüş Liste yarısında, bir birleştirme yaptım.
Bir birleştirme yapmak, yarısı listeyi bölün.
Listeyi bölünmesi Yani eğer Günlük n kere yapılabilir,
ve birleştirme sonuçta n alır adımlar, şimdi ne üst olabilir
çalışan üzerinde bağlı Bizim algoritmanın zaman?
n log.
>> Ve gerçekten de, bu ne var Burada elde ettik.
Yani görsel zaman görmek hissediyorum Bu üç şey yan yana çalıştırmak
n n karşı karesi n günlük n karşı kare.
Göreceğiz temelde Hangi, Bugün ancak gelecekte sadece,
çok, çok daha hızlıdır.
Bu adamlar için alkış yuvarlak, Ben stres topları ile onları ödüllendirecek.
En Bugün burada erteleme edelim, ve biz Pazartesi günü göreceksiniz.