>> [MÜZİK OYUN]
>> DAVID J. MALAN: Bu CS50 olduğunu.
Ve bu haftanın üç başlangıcıdır.
Bu yüzden heyecanlı bir sürü var işler bugün kapsayacak.
Fırsat bir sürü için sahneye gönüllü.
Ve sonuçta, bugün değil kodu hakkında tüm.
Ama bu fikirleri hakkında ve bu algoritmalar hakkında,
ve aslında bazı geri getiren Haftanın sıfır öğrenilen dersler,
burada hatırlama, biz bu ucubeyi tanıttı.
Ve borçlanma ilham bundan başlatmak için
her zamankinden daha karmaşık çözmek için algoritmik problemleri.
Ama önce, duyurular bir çift.
Yani bir, katılmak isterseniz Öğle yemeğinde CS50 personeli ve sınıf arkadaşları
Bu Cuma hem burada ve Cambridge, New Haven,
Tabii en adresini ziyaret edebilirsiniz Bir URL bulunabilir sitesi.
Bu Çarşamba olacak Anlatım Sanders burada olmayacak.
O yüzden sadece online olacak CS50 web sitesinde melodi,
Burada Cambridge olsun veya New Haven de.
>> Ve o zaman sorun iki set senin elinde zaten.
Henüz daldı yoksa, bana izin sert ifadeli öneri sunmak
Özellikle şimdi, olduğu gibi, bu Sorun, avans setleri
Eğer gerçekten, şimdi değilse başlamak istiyorsun hafta sonu veya önce üzerinde biraz serpmek
ilk dışarı çıktığınızda Cuma, sen olacak çünkü
onlar mutlaka değiliz bulmak uzun veya daha zorlu başına elde
se.
Ben de, o bulacaksınız düşünüyorum Genel, onlar kabaca almak eğilimindedir
zaman aynı miktarda etrafında.
Ama kesinlikle bağlıdır öğrenci ve üzerinde
anlayışla bağlıdır hangi ile yaklaşım.
Ama her zaman, sen gidiyorsun Bazı duvara karşı çalıştırmak için,
ve vurmak için gidiyoruz Bazı böcek, ve sen sadece
muktedir olacak değil bir noktada bitti olsun.
Ve bu muktedir derece değerli uzaklaşın ertesi gün geri gelmek için,
Mesai saatleri gidin CS50 post tartışın veya benzeri aslında engellenmemiş olsun.
Yani akılda tutmak.
Mümkün olduğunca erken başlayan Yapabileceğiniz en iyi şey.
Başladığımız yere Yani burada haftada sıfır üzerinde sınıf.
Ve biz bir gönüllü alabilirim Burada bana mikrofon bulmanıza yardımcı olmak için?
TAMAM.
Zaten Ayakta.
Yukarı gel.
O işe gidiyor nasıl sanırım.
Adın ne?
ALAN ESTRADA: Alan Estrada.
DAVID J. MALAN: Alan Estrada.
Yukarı gel.
Tanıştığımıza memnun oldum.
ALAN ESTRADA: Nice to meet you.
DAVID J. MALAN: Ve burada olduğunu Bize hafta sıfır, elbette sahip.
ALAN ESTRADA: Ben.
Ben ... idim.
>> DAVID J. MALAN: Yani gidebiliriz önde ve Mike Smith bulmak bizim için,
olabildiğince hızlı olarak?
Mümkün olduğunca hızlı.
Kelimenin tam anlamıyla sorunu yırtılma yarısında size ihtiyacınız olan.
>> ALAN ESTRADA: Um.
DAVID J. MALAN: Kelimenin tam anlamıyla yarısında sorunu yırtılma.
>> ALAN ESTRADA: Oh.
Mm.
Çok güzel.
>> DAVID J. MALAN: Tamam.
İyi.
Teşekkür ederim.
ALAN ESTRADA: Çok iyi.
TAMAM.
>> DAVID J. MALAN: Ve şimdi, Bunu whittled ettik
Sorunun yarısı boyutuna.
Şimdi, biz dörtte aşağı konum.
Eğer dikkat ediyorsunuz biz tutuyor hangi tarafta?
>> [Gülüyor]
>> ALAN ESTRADA: Evet, bence--
>> DAVID J. MALAN: Ne bölümünde biz mi?
ALAN ESTRADA: susturucular, yani.
>> DAVID J. MALAN: Tamam.
Ama Mike Smith gidiyor susturucuları sonra olmak.
Yani--
>> [Gülüyor]
>> Pekala.
ALAN ESTRADA: Nereye bakıyorsun?
DAVID J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. MALAN: Şimdi, cerrahi konum.
Şimdi doktorlar.
Şimdi--
>> ALAN ESTRADA: en gerçek ile gidelim Let's-.
Gerçek.
>> DAVID J. MALAN: Gerçek.
TAMAM.
Eğer Real, gerekiyorsa.
Şimdi, Mike Smith hangi tarafta?
>> ALAN ESTRADA: Bu şekilde.
>> DAVID J. MALAN: yol?
ALAN ESTRADA: Bekleyin.
M o-- değil mi?
Biz Şarkı söylemeyi kes başladı
>> DAVID J. MALAN: Evet.
Onlar kalacaksın.
Haklısın.
>> ALAN ESTRADA: Evet.
>> DAVID J. MALAN: Yani Ahmet'in burada.
ALAN ESTRADA: ne olacak?
>> [Gülüyor]
>> Kötü örnek, çocuklar.
Özür dilerim.
DAVID J. MALAN: Bu öğretecek Eğer sandalyeden sıçrama.
>> ALAN ESTRADA: Oh.
Ah.
Anladım.
Ah.
Bu Tamam bu--, seni aldım.
Burada Smith?
>> DAVID J. MALAN: Smith, teşekkür ederim.
Yani Smith ararken devam edeceğiz?
>> ALAN ESTRADA: Oh, evet.
Hayır hayır Hayır.
Oh hayır.
Bu benim.
>> DAVID J. MALAN: Oh, Smith var.
TAMAM.
>> ALAN ESTRADA: Evet, Burada Smith var.
Üzgünüm beyler.
Ben Michael-- düşündüm biz Michael aradılar.
Özür dilerim.
>> DAVID J. MALAN: Tamam.
Pekala, şimdi sen paccini and Sons içine.
>> ALAN ESTRADA: paccini ve oğulları.
DAVID J. MALAN: Sadece sen ve ben bu konuda vardır.
TAMAM.
Bize Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. MALAN: Smith.
Biz Çöp R konum.
ALAN ESTRADA: Berbat.
Ah.
Bu biraz zaman alacak.
>> [Gülüyor]
DAVID J. MALAN: Ayakkabı.
Biz ayakkabı konum.
>> ALAN ESTRADA: Şimdi zaman-- ediyoruz
>> DAVID J. MALAN: Nice.
ALAN ESTRADA: hususların
[Gülüyor]
Ah, bu harika.
[Gülüyor]
>> DAVID J. MALAN: Tamam.
>> ALAN ESTRADA: Oh, bu iyi.
Ben gidiyorum sanmıyorum Bundan sonra PSAT arkadaşları sahiptir.
DAVID J. MALAN: İyi.
Sporting.
ALAN ESTRADA: Sporting.
Aa, L, M, N, O, P
DAVID J. MALAN: Tamam.
Yani yarısında bu gözyaşı verelim.
Tamam.
Bu, zaten kötü biter Mike çünkü Smith sarı sayfalarda olmayacaktır.
>> ALAN ESTRADA: Aw.
>> DAVID J. MALAN: Hayır, sorun değil.
Ama böyle farz edelim O bu sayfada var.
Yani şimdi, aşağı sorunu whittled ettik bir sayfaya ve Mike Smith bulundu.
>> [Tezahürat]
Tamam teşekkür ederim.
TAMAM.
Bu olağanüstü oldu.
Ama yine de daha hızlıydı doğrusal arama daha,
burada biz başlar Kitabın başında,
soldan sağa ve biz yolumuza hareket Sonunda Mike Smith arıyor.
Ve böylece, eğer telefon rehberi belki 1000 sayfaları vardı
belki almış olurdu Bize 10 ya da öylesine sayfa gözyaşları.
>> Ama kaldıraçlı olabilir Bir varsayım dokundu
Bütün bunlar sırasında, hangi söylemektir peşin telefon rehberi neydi o?
HEDEF KİTLE: Sıralama.
DAVID J. MALAN: Bu sıralanmış oluyor.
Sağ?
O yüzden alfabetik olarak sıralanmış Bu isimleri ve numaraları tüm
A adlı ila sıralanır Z'nin, alfabetik arasında.
Ama bugün, şimdi sormak soru, iyi,
nasıl Verizon ya da telefon yaptım şirket bu duruma olsun?
>> Bu bir şey çünkü kaldıraç Bu varsayım ve bu nedenle,
Bir bir sorunu çözmek algoritması daha verimli.
Ama biz asla gerçekten haftada sıfır sordu, iyi,
Maliyet yaptım ne kadar Verizon veya bir başkası
sıralı sırayla bu telefon rehberini almak için?
>> Sağ?
Bu ise önemli değil Mike Smith bakıyor
Seni bir sürerse, süper hızlı yıl başlangıçta sayfaları sıralamak için.
Sağ?
Siz de sadece elemek olabilir randomize telefon defteri üzerinde,
süper olacak eğer sıralamak için pahalı.
Yani eğer biz başka gönüllü olabilir.
En bir alacak olarak buraya bakalım Biz nasıl up-- hadi Bir-- nasıl
bu sıralama hakkında gidebilir.
>> Ve eğer Ürdün aslında olabilir Sahnede bizi buraya katılın.
Sadece bir an için gel.
Adın ne?
CAROLINE: Caroline.
DAVID J. MALAN: Caroline, yukarı gel.
Ve katıldı olacak Burada benimle ve Ürdün tarafından.
Caroline, teşekkür ederim.
Pekala.
Yani biz burada için ne Caroline 26 mavi kitaplar olduğunu
FAS yönetmek için kullandığı Bazı final sınavları.
Bunlar, bulmak zor alıyorsanız ama biz önceden yaptık
biz birilerinin ismini koyduk olduğunu Bunların her birinin ön yüzünde,
ama biz basit sakladım daha sonra tam isimlerini koyarak.
Bu yüzden adı ile kişiyi vereceğini L, D, J, B, tüm yol Adan Zye,
ama onlar rasgele sırada sensin.
Ve sen-cekti eğer öyleyse, sizin yanınızdaki konuşuyor senin gibi sorunu ile yol
o, sen devam edebilir yoktur ve A'dan Z'ye, bizim için bu sıralama
>> HEDEF KİTLE: Tamam, bu yüzden L orta gibidir.
C başlıyor.
B. L. B öncesinde J, Q.
>> DAVID J. MALAN: Tut bir saniye düşündü.
Çünkü aksi takdirde, bu sadece Senin, benim, Ürdün ve ilginç.
Oraya gidiyoruz.
HEDEF KİTLE: [duyulamaz].
R.
DAVID J. MALAN: Tamam.
Napıyon?
>> CAROLINE: M O. sonra gelir
>> DAVID J. MALAN: Tamam.
>> CAROLINE: O.
DAVID J. MALAN: Ey, iyi.
>> CAROLINE E.
>> DAVID J. MALAN: E, F Evet.
>> CAROLINE: T, U, V.
>> DAVID J. MALAN: V, T, U, V o yüzden Eğer devam making-- konum gibi görünüyor.
Eğer yapıyoruz gibi görünüyor Büyük bir kazık buraya,
ve orada büyük bir yığın tür.
Yani alfabenin ilk yarısı, alfabesinin ikinci yarısı.
TAMAM.
İyi.
Tür ikisinde sorunu bölme.
M, N, X. evet.
CAROLINE: K.
DAVID J. MALAN: Tamam.
K. Yani bir tür seçerek ediyoruz birbiri ardına onları bir,
Sol veya sağ ya koyarak, ya da Z adlı katta oluyor.
TAMAM.
>> CAROLINE: Z kat oluyor.
>> DAVID J. MALAN: Tamam.
Y katta oluyor.
Şimdi X'i koyabilirsiniz
>> CAROLINE: G.
DAVID J. MALAN: G sol gidiyor.
S doğru gidiyor.
Pekala, bir sola tüm yol gidiyor.
>> CAROLINE: A, B, C, D
>> DAVID J. MALAN: Şimdi, iyi.
Biz bir var, B, C W aşağı orada olacak.
Pekala, T.
>> CAROLINE: H, I, J
DAVID J. MALAN: H, I, J iyi.
CAROLINE: merkezinde, ben zaman-- ediyorum
DAVID J. MALAN: Tamam.
Yani şimdi, biz tür gidiyoruz Bu çeşitli yığınları birleştirmek.
Yani A ile C arasındaki, o zaman ben D görüyorum ve E ve F, G ve H ve I güzel.
J, K Ve sonra, bu kazık baş aşağı, ama bu sorun değil.
Elbette.
Biz bazı köşeleri kesebilir.
TAMAM.
Sonra W, X, Y, Z mi
>> CAROLINE: Evet.
>> DAVID J. MALAN: Mükemmel.
Yani büyük bir teşekkür Bu sıralama için Caroline.
>> [Tezahürat]
>> Teşekkür ederim.
Çok teşekkür ederim.
Yani şimdi bir an için düşünelim nasıl Caroline yapıyor hakkında gitti,
ve tam olarak ne biz nasıl ki-- başardık biz
Bunu çözmek için başardık Sorun ne zaman biz sadece
rasgele girdilerin bir sürü verilen.
>> Peki, orada benziyor Orada bir sistemin biraz?
Sağ.
Önceki harf Yani alfabesinde, o
oldu sola koyarak ve alfabede daha sonra harfler,
O sağ içine koyarak.
Ve en kısa sürede o buldum Bazı yakın mektuplar, olanları
Bu, birbirine hemen yanında gitmek O sırada o koymak istiyorsunuz.
Ve böylece biz tür bu küçük vardı meydana gelen sıralı girdilerin yığınları.
>> Ve böylece oldukça ne demek Çoğumuz insanlar yapardı.
Biz tür bunun aracılığıyla elemek istiyorum ve biz tür bir mekanizma olurdu.
Ama yazmak zor olabilir aşağı bir formül haddi zatında.
Bundan daha organik biraz daha hissettim.
Yani görelim eğer bağlı şimdi can Daha az girişler sorun.
>> Yerine 26, haydi daha az şeyler yapmak
hemen arkasında, yedi, ile söylemek Bu kapılar, tabiri caizse.
Sadece yedi sayı var mı?
Ve şimdi hedef olarak ise El bir değeri bulmak için,
Bakalım ne kadar etkin izin Biz bunu hakkında gidebilirsiniz.
Ve şimdi eğer görelim Bazı sayılar uygulamak başlar,
ya da bazı formüller hangi tanımlamak için Bizim telefon rehberinden etkinliği
algoritma, bizim sınav kitap algoritması ve daha genel olarak, bilgi bulma.
>> Bu Yani, beni ileriye gidelim ve dokunmatik ekranda buraya,
sahip bir web tarayıcısı koymak Tam bu yedi kapı.
Ve biz bir başka alabilir Buraya gelmek için gönüllü,
Buraya bu aynı kapıları koyduk.
Hızlı gönüllü.
>> Bu Şehre demolar gidiyor daha hızlı ve daha hızlı şimdi.
Aşağı gel.
Adın ne?
TREVOR: Trevor.
>> DAVID J. MALAN: Trevor?
Pekala, Trevor, aşağı gel.
Yani Trevor burada gönüllü oldu benzer bir sorun, ama var bir tane
kapsamında dar ve bu gidiyor izin Şimdi resmileştirmek için denemek için
Bu numaraları sıralama işlemi.
>> Yani Trevor, tanıştığımıza memnun oldum.
Yani burada bir dizi çok olduğu yedi kapı listesini konuşuyoruz.
Devam edin ve bize sayı 50 bulabilirsiniz.
Ve sonra aslında sonra, Bunu nasıl bulduğunu bize bildirin.
Tamam göre-- etmelidir.
Evet, burada bir mı?
Ah ah.
TAMAM.
Bunu bir tıkladım.
İyi.
>> Ve iyi.
Şimdi o bir tıkladım.
Ve sana mikrofonu vereyim, böylece sadece bir an içinde var.
Devam edin ve tıklayın Eğer düşündüğünüz next door.
Evet iyi.
TREVOR: Ben bir kapı unclick miyim?
DAVID J. MALAN: Hayır, unclick olamaz.
TREVOR: Tamam.
Bu.
DAVID J. MALAN: Nereye gitmek istiyorsun?
Hangisi?
>> TREVOR: Bu bir.
>> DAVID J. MALAN: Hayır
>> TREVOR: Tamam.
Bu.
>> DAVID J. MALAN: Evet.
Bu iyi oldu.
Pekala.
Yani algoritması neydi ya Bu, Trevor yapmak için prosedür nedir?
>> TREVOR: Ben sadece gitti Kapılar kadar bir 50 bulduk.
DAVID J. MALAN: Tamam.
Mükemmel algoritma.
Yani sorun yok.
Aslında, eğer ben açığa Çünkü ne Bu diğer iki kapılar ardında ne
biz burada bulabilirsiniz biz sadece rastgele girişi var.
Yani bu kadar aslında sen-ebil almak kadar iyi.
Ve aslında, daha iyi anladım etraflıca bütün dizi arıyor,
Gerçekten olurdu çünkü şanssız Numarayı isabet olsaydı
Son kapıda 50.
Ama ne onun yerine biz eğer Sana bir varsayım verdi.
Sıralama tüm I varsayalım etrafında bu kapılar,
böylece var sayılar bu kez kriteri
ama bu sefer aslında a, bu kez different--
aslında sizin için sıralanır oluyor.
Eldeki Ve şimdi gol sayı 50 vurmaktır.
>> TREVOR: Tamam.
>> DAVID J. MALAN: neler var olacak sizin algoritması?
>> TREVOR: bu kadar Eh, eğer sıralanmış, o Ya gidiyor
En büyük eğer en büyüğü şey olmak, azalan, o ilk olacak
ya da tam tersi ise, bu sonuncusu olacaktır.
Yani sadece bu kapıyı dokunun ve edeceğiz sonra sadece son kapıyı dokunun.
DAVID J. MALAN: Mükemmel.
Pekala.
Bu yüzden sayı 50 bulundu.
Yani en kısa sürede bildiği gibi Onlar dizildi, biz
Bu varsayımı kaldıraç başardık.
Bu yüzden böyle çok fazla konum Telefon rehberi örneği.
En kısa sürede size, hatta birlikte olduğu gibi Bu gibi küçük bir sorun,
senin girişler önceden sıralanmış, biz Aslında tartışmalı değeri bulmak
daha verimli.
>> Ve seni o olsaydı söylemedi , küçük büyük, küçük ya da büyük kriteri
ve bu yüzden çok makul bir ucunda ya da başlatmak için
Aslında hedef değeri bulmak için.
Yani hem Trevor teşekkür ederiz.
Ve ben güzel yapılır propose-- edeceğiz.
Biz, aslında, küçük bir klip var , CS50 bizim favori anları arasında yer alıyor
böylece bazen bu demolar Oldukça plana göre gitmez.
Ve gerçekten de şu anda, ben Yanlış bir arayüz çekti
hangi ile dokunmatik ekranı kullanmak için.
Yani bu benim hatam oldu.
>> Yani bunun için yapacak olarak gelecek yılki klibi
Ben kendi ekranında tıklayarak oldu neden.
Ama hızlı bir göz atalım Geçen yıl ne de
çok gündeme geldi Jay, ile Burada Trevor gibi, gönüllü
ve bu kısa klipte, görürsünüz Bu aynı demo oldukça vermedi nasıl
öğrenilen aynı dersleri ortaya koymaktadır.
[VİDEO OYNATMA]
Ben yapmak istediğiniz -Tek artık Benim için bulmak ve bizim için,
Gerçekten, sayı 50 adım adım.
>> Sayılarının 50?
>> -The Sayı 50.
Ve sen ne ortaya çıkarabilir Bu kapıların ardında her
sadece bir parmak ile dokunarak.
Kahretsin.
>> [Gülüyor]
>> [SON OYNATMA]
DAVID J. MALAN: Bu yüzden çok iyi gitti.
Bu sıralanmamış kapı vardı.
Ve Jay, tabii ki, Çok hızlı bir şekilde buldum.
Trevor çok daha iyi bir iş yaptı Öğretilebilir an açısından,
bu nedenle bu yıl, konuşmak için uzun sürüyor bulmak için.
Tabii ki, o zaman biz verdi Jay ikinci şans,
bu sayede biz kapıları kriteri Biz Trevor için yaptığı gibi,
ve Trevor süper iyi bu sefer yaptı.
Ama Jay yarısı kadar çabuk yaptım.
[VİDEO OYNATMA]
-The Amaç da artık etmektir bize numara 50 bulabilirsiniz
ama algoritmik bunu, ve Bu konuda gidiyoruz nasıl bize bildirin.
>> -TAMAM.
>> Eğer bulursanız -Ve, filmi tutmak.
Eğer bulamazsanız, onu geri ver.
>> Adamım.
>> Oh!
>> - [Inaudible] Tamam.
Yani uçlarını kontrol edeceğim Oh orada- olmadığını belirlemek için, ilk.
>> [Alkış]
>> [SON OYNATMA]
DAVID J. MALAN: Tamam.
Yani açıkça kapıları sıralama daha verimli yol açar.
Ve böylece, iki kat daha hızlı Orada ne demek olduğunu.
Ve böylece Jay şanslı iki kere aldım.
Ve o da son olarak şanslı var yıl, bazı Blu-ray diskler sipariş
aslında dışarı vermek.
Bu yıl üzgünüm, biz Trevor aynı yoktu.
Ama daha iyisi bir kaç yıl önce oldu.
Ve bazılarınız biliyor olabilir, bu O CS50 oldu adam, Sean,
Kesin olan meydan Aynı sorun, SD de olsa,
Yakında, geri gün göreceğimiz gibi.
Ve sadece vermedi bulacaksınız O, Jay biraz daha uzun sürebilir
Trevor biraz daha uzun, öyleydi aslında bu harika bir fırsat
neredeyse herkes meşgul kalabalık la Fiyat teşvik Sağ
Onu biz arayan numarayı bulmak için.
Haydi. bir göz atın.
>> [VİDEO OYNATMA]
>> -TAMAM.
Yani burada görev Sean, şudur.
Ben bunların arkasında gizli Kapılar sayı yedi.
Fakat bu kapıların bazıları sıkışmış hem de diğer negatif sayılar vardır.
Ve hedef düşünmektir sayıların bu üst satırın
sadece bir dizi, ya da sadece kağıt parçaları dizisi
Arkalarında numaraları ile.
Ve amacınız sadece üst kullanılarak, bir Dizi burada, bana numarayı yedi bulabilirsiniz.
Ve biz o eleştirmek için gidiyoruz Bunu yaparken nasıl.
-Pekala.
Bize numarayı yedi, lütfen bul.
Hayır.
Beş, 19, 13.
>> [Gülüyor]
>> Bu hileli bir soru değil.
Bir.
>> [Gülüyor]
Bu noktada, puanınızı çok değil İyi, siz de devam olabilir.
Üç.
>> [Gülüyor]
>> Devam et.
Açıkçası, ben yardım edemem ama merak ediyorum ne bile yani-- düşünüyorsanız
>> [Gülüyor]
Sadece üst satır, böylece Üç sol var.
Bu yüzden bana yedi bulabilirsiniz.
>> [Gülüyor]
17.
Yedi.
>> [Alkış]
>> Pekala.
>> [SON OYNATMA]
>> DAVID J. MALAN: Yani biz-ebil Bu gün uzun izleyebilirsiniz.
Ve tabii ki, bazı Bu yılki demolar belki
Şimdi önümüzdeki içinde sona erecek yılın Video de.
Bu yüzden şimdi aslında atalım algoritmalar odaklanmak
biz değil eğer burada, ve görmek Şimdi resmileştirmek başlar
bizim veri alma hakkında nasıl gidebiliriz Bu duruma o sıralanmış var ki
yani sonuçta, biz aslında can daha verimli bir şekilde arayın.
Ve biz gidiyoruz bile oldukça küçük veri setleri kullanmak,
Sekiz sayı gibi biz Gemide burada var,
sonuçta bu aynı fikirleri uygulayabilirsiniz 1000 girişlere, bir milyon girişleri,
4 milyar giriş, algoritmalar, çünkü temelde aynı olacak.
>> Ve böylece bu bizim son bir Gönüllüler bugün için fırsat,
ama belki de en tutulan biri, hangi biz sekiz gönüllülere ihtiyacımız var
gelip bize yürümeyi sıralama işlemi, kısa sürede olacak
Bu müziği olmak burada duruyor.
Beni buraya başlayalım.
>> Yani turquoise-- yeşil bir değil mi?
Eğer ediyorsunuz demektir?
İki.
Aşağı gel.
TAMAM.
Üç.
Dört.
Beş Tamam bana-- edelim.
Sen arkadaş tarafından aday ediliyoruz.
Altı, yedi, sekiz.
Yukarı gel.
Pekala.
Çok teşekkür ederim.
Yukarı gel.
>> Pekala.
Yani biz burada-- ve bu ne var daha garip olanlar arasında yer alıyor,
Bu beri sana o mizah gerektirir zaman sadece biraz benim için.
Sen bir numara olacaktır.
Adın ne?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
David.
Adın ne?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, Eğer iki numaralı bulunmaktadır.
>> SERENA: Serena, üç numara.
Stefan sayı dört.
Cynthia: Cynthia.
DAVID J. MALAN: Cynthia, beş numara.
[Duyulamaz]
DAVID J. MALAN: [duyulamaz].
David sayı altı.
MAT: Matt.
DAVID J. MALAN: Matt sayı yedi.
Ve?
>> WAVERLY: Waverly.
>> DAVID J. MALAN: Waverly, sekiz numara.
Pekala.
Eğer hoppala Yapabileceğim.
Hepinizin ise, olduğu gibi senin Orada ilk sorun,
Sekiz Müzik standları vardır Burada seyirci karşı karşıya.
Eğer üzerinde numara koymak olsaydı Bu müzik şekilde duran
onlar hizaya olduğunu gemide aynı numaralar.
Yani kendinizi tarafından böyle görünmesi Bu müziği numaralarınızı koyarak
Burada duruyor.
Mükemmel kadar.
>> Mükemmel.
TAMAM.
Yani şimdi biz sormak için gidiyoruz Bir kaç farklı şekilde soru.
Nasıl sıralama hakkında gidebilirsiniz Burada bu millet kadar?
Biz birkaç yaklaşım vardı çünkü Daha önce, biz bu sayede vardı
tür iki farklı kova yapma.
Ve sonra biz genellikle vardı Birlikte bir şeyler ekleme.
En kısa sürede biz iki sayı gördüğümüz gibi bu arada ait
Biz bunları bir araya koymak.
Birbirine ait iki mektup.
>> Ama eğer görelim biz Bu resmileştirmek edemez,
sonuçta sahip olacak şekilde olacak bazı sözde kod,
hangi ile bu sorunları çözebilir.
Yani şimdi, ben bakıyorum Burada bu rakamlara.
Ve ben hatalar bir sürü görürsünüz.
Sonuçta, ben bir tane istiyorum sol ve sağ tarafta sekiz.
>> Ve bu yüzden bakıyorum Bu iki, dört ve iki.
Ve sorun Açıkçası, ne?
Evet.
So
İki besbelli önce gelir Dört, yani ne biliyor musun?
Beni ilk açgözlü bir yaklaşım ele alalım, çok benzer bir sorun eğer sen
Eğer gelen çağırmak durumunda Şehre set Sorun Set One Standard Edition,
Nerede Ben sadece yerel sorunu çözmek bana hemen önünde burada
beni nereye götürecek ve bakın.
>> TAMAM.
Yani iki ve dört, gitmeme izin önde ve sadece size iki takas.
Fiziksel hareket edebilirsiniz Kendinizi ve kağıt,
Ben aldık görünüyor Daha iyi bir durumda listelenmektedir.
>> Şimdi, onlar iyi.
Ben, hareket için gidiyorum dört ve altı iyi görünüyor.
Problem değil.
Altı ve sekiz Tamam.
Sekiz ve bir başka sorun.
Sekiz ve biri hakkında doğru ne için mi?
Bir, sekiz önce gelir ve böylece biz ne yapmalıyız?
Şimdi bu ikisini takas edelim.
Bir ve sekiz.
Ve şimdi, ben devam edeceğim.
Ben ileriye bakmaya devam edeceğim.
Ve en ne olacağını görelim.
Sekiz üç, ve Tabii ki, sıra dışı.
En takas edelim.
Elbette sekiz ve yedi.
Bozuk.
En takas edelim.
Sekiz'in ve beş tabii ki, hadi takas.
Pekala.
Liste sıralanır.
evet?
>> Tamam, tabii ki değil.
Ama bu doğru, biraz daha iyidir?
Ne haber Ne Çünkü.
Her zaman biz bir takas, gerçekleştirilen küçük bir sayı tür bu şekilde percolated,
ve daha büyük bir sayı Bu şekilde süzülmüş, ya da biz olacak
için kabarmış söyleyerek başlamak sola veya sağa kabarmış.
>> Şimdi, bunun nedeni, yeterli değil en iyi bir sayı olabilir
tek nokta taşındık ileri, ya da en kötüsü,
Bir numara olabilir ayrıca bir nokta taşındı.
Peki ne, bu tür biliyorum şimdiye kadar oldukça iyi çalıştı.
Bana sadece tekrar deneyelim.
İki ve dört onlar iyiyiz.
Dört ve altı, onlar iyiyiz.
Altı ve bir, sıra dışı.
Yani seni iki takas edelim.
Ve şimdi, sorun en dikkat iyi yine biraz almaya başlıyor.
Altı ve üç sıra dışı.
Seni iki takas edelim.
Altı yedi, sen iyisin.
Yedi beş, tabii ki, sıra dışı.
Sırayla yedi ve sekiz.
Ve şimdi, ben gerekebilir Daha fazla bu birkaç kez yapın.
Ve aslında, kendisi için düşünmeye belki kaç kez maksimum
Ben ileri geri yürümek zorunda kalabilirsiniz?
>> Biz geri geleceğiz.
Yani iki ve dört hala Tamam.
Dört ve bir, hayır.
Yani, en swap edelim.
Ve yine, görsel fark tek köpüren tür
Olması gereken solunda.
Dört ve üç takas.
Dört ve altı.
Altı ve beş takas.
Altı yedi.
Yedi sekiz iyidir.
>> İyi.
Biz daha iyi alıyoruz.
Yani görelim.
Şimdi, biz iki ve bir tane var.
Tabii ki, takas.
İki ve üç, üç ve dört, dört ve Beş, altı ve yedi, yedi ve sekiz.
İyi.
Ve biliyor musun?
Ben orada bir değişiklik yapılmadı Çünkü Bana bir sağlamlık denetimi yapalım.
Beni tüm yol gidelim başa geri.
TAMAM.
Bir, yup iki--, gördün mü?
Bir şeyler yanlış oldu.
Üç, dört, beş, altı, yedi, sekiz.
Ve bu son geçişte vardır benim şimdi ile rahat
o sıralanır iddia eden?
TAMAM.
Görme, kesinlikle doğrudur.
Ama işlevsel, ne Ayrıca sadece oldu
size izin verdiği son geçişte Bu liste aslında olduğunu teyit etmek
kriteri?
>> Ne yapmak ya bu son geçiş yapmadım?
HEDEF KİTLE: hiçbir değişiklik yoktu.
DAVID J. MALAN: Üzgünüm?
HEDEF KİTLE: değişiklik yok.
DAVID J. MALAN: herhangi bir değişiklik olmamıştır.
Bu yüzden benim aptal olacağını Yine aynı algoritmayı yapmak
Ben herhangi yapmadım eğer İlk defa değiştirir.
Ve devlet değişmedi.
Şüphesiz, ben yapmak için gitmiyorum her ikinci kez değiştirir.
Ve böylece, artık güvenli demek, liste sıralanır.
>> Ve gerçekten de, bu şimdi bir şey biz genellikle olacak
çağrı kabarcık sıralama, bu sayede ikili, Eğer tekrar hataları düzeltmek için
ve tekrar ve tekrar ve size ileri ve geri gidiyor tutmak,
ve ileri geri, senin kadar Böyle swapları, yapmak hangi noktada
Eğer ben, evet, emin olabilirsiniz hatalar tüm sabitleme tamamladı.
En sıfırlamak ve başka bir yaklaşım deneyelim.
Siz geri gidebiliriz Eğer sırası, bir an önce vardı
hangi bu gibi görünüyordu.
Şimdi bir yaklaşım a atalım Daha fazla sınav kitap gibi küçük,
bu sayede sürekli vardı Alfabenin harfini seçtikten
biz tür istedim Bir sonraki başa.
Belki yüksek bir mektup oldu, A, veya düşük mektup Z. gibi
>> Yani herkes geri bu sırada bulunuyor.
Ve şimdi bunu yapmama izin ver.
Diyelim ki ben biliyorum görelim Burada sekiz sayı.
Ben devam edeceğim ve Sadece kasten seçin
küçük elemanları.
Sağ?
Bu da sezgisel görünüyor.
Neden küçük bulmuyorum ait olduğu yere elemanın, koyun
sonraki en küçük elemanı olsun, koymak o aittir ve sadece tekrar nerede.
>> Sezgisel Çünkü Bu çok çalışması gerekir.
Yani dört, bu oldukça küçük bir sayı bu.
Ben bu nerede hatırlamak için gidiyorum.
Bir dakika bekle.
İki küçük.
Şimdi beni nerede anımsayalım iki ve yaklaşık dört unutun.
Biz daha sonra ilgilenirim.
Altı, ben ilgilenmiyorum.
Sekiz, ben ilgilenmiyorum.
Biri benim yeni küçük sayıdır.
Yani biri nerede olduğunu hatırlamak için gidiyorum.
Üç, ilgilenmiyorum.
Yedi, ilgilenmiyorum.
Beş, ilgilenmiyorum.
>> Düşmeden Yani sahne bu yıl,
Ben numarayı alayım Şehre ve senin adın neydi?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
Ve bana katılmak eğer Listenin başında,
nereye ait olduğunu seni koyalım.
Unfortunately-- adın ne?
>> STEFAN: Stefan.
>> DAVID J. MALAN: Stefan şekilde olduğunu.
Stefan, bu çözer önce Yani Sorun, ne yapmalıyız?
Biz Stefan ile ne yapacağız?
>> HEDEF KİTLE: [duyulamaz].
DAVID J. MALAN: Tamam.
Yani biz bunu yapabilir.
Biz tür Stefan ve sürebilir onun Dört ve sadece bir değişkene koymak
ve için ona tutun zaman bir miktar,
böylece bir numara için oda yapma.
Ve bu da kötü değil.
Ben neden bunu, hatırlatıyoruz Biz sadece burada Stefan koydu?
Neden bu bir ihlal edebilir fikirlerin başladık
Geçen hafta, son kez bahsediyoruz?
Evet?
>> HEDEF KİTLE: [duyulamaz].
>> DAVID J. MALAN: onun için hiçbir indeks var.
Bir şekilde, gerçekten, bu düşünürsek Dizi, bu olumsuz gibi olduğunu,
yani bellek aslında var Burada bu gerçekten bir dizi ise,
gibi biz derste geçen hafta ilan etti.
Yani biz bunu yapmamalıyız.
Biz bir değişkende saklamak olabilir.
>> Yoksa biliyor musun?
Ben başkası öneririz duydum.
Biz Stefan ile başka ne yapabilirdi?
Neden biz sadece onu tahliye yok ve bir numara nerede üzerine koydular.
Oraya gitmek istiyorum Yani eğer.
Ve gerçekten de, bu bir Oldukça iyi bir çözüm.
Şimdi, bir yandan, biraz ettik en kötü sorunu yaptı.
Dört uzağa şimdi olması gereken yerden.
Bu yarıda doğru olmalıdır.
>> Ama ne biliyor musun?
Bu kötü şans olabilirdi.
Belki sayı sekiz buradaydı.
Ve böylece, belki biz-cekti Şanslı aldık,
ve sonuna kadar sekiz yakın itti.
Günün sonunda Yani, bu tür tüm ortalamalar dışarı.
Biz yaklaşık dört bakım gerekmez.
Şu an umurumda hepsi En küçük eleman seçme.
>> Ve şimdi, ben ne gidiyorum bir numara unutun yapmak
kalıcı, biliyorum çünkü Arkamda listesi şimdi sıralanır.
Yani benim liste önceden boyut sekiz yaşındaydı.
Şimdi, bu büyüklük yedi bulunuyor.
Yani benim sorunum oluyor doğrusal olsa daha küçük.
Yani şimdi, ben seçmek için gidiyorum Geçerli en küçük elemanı, iki.
Altı, sekiz, dört, üç, yedi, beş.
O küçük elemanı oldu.
Peki Bense yapmaya gidiyorum Adın neydi?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph?
Biz bir yerde Yusuf'u terk edeceksin.
Şimdi, ben iddia gidiyorum Bu adamlar iyi mudur ki
Biliyorum ki bu iki Zaten sıralanır.
Şimdi odaklanmak edelim Listenin geri kalanı.
Altı akım küçüğüdür.
Sekiz büyük.
Dört artık geçerli küçüğüdür.
Üç şimdi geçerli küçüğüdür.
Ve şimdi, ben, üç seçmek için gidiyorum kim adınız tekrar ne bu--?
SERENA: Serena.
DAVID J. MALAN: Serena, sen-ebil eğer Numaranızı ve takas Şarkı söylemeyi kes kapmak
Kalsang: kalsang.
DAVID J. MALAN: kalsang.
Geri gel, ve biz konum Bu ikisini takas olacak.
Ve şimdi, otomatik pilotta bu etsinler.
Ben gidip adamlara bırakmak için gidiyorum Bir sonraki en küçük öğeleri seçin.
Dun, dun, dun, dun.
Dört numara, ne yapmalıyım?
Mükemmel.
Şimdi, ben başka bir geçiş yapmak için gidiyorum.
Dun, dun, dun, dun.
Beş sonraki küçük olduğunu görüyoruz.
Şimdi, ben başka bir geçiş almak gidiyorum.
Dun, dun, dun, dun.
Altı küçüğüdür.
İyi.
Yedi küçüğüdür.
Değişiklik yok.
Sekiz küçüğüdür.
Bitti.
>> Peki biz sadece iteratif tarafından yaptık birbiri ardına eleman seçme
Biz konum şey uygulamak olduğunu Seçim tür olarak resmileştirmek için gidiyor.
Ve hatta belki de var: açıklamak için daha basit,
kelimenin tam anlamıyla hepinizi ki Sadece tutmak yapmak istiyorum
liste üzerinden ileri ve geri gidiyor seçilmesi, küçük bir sonraki elemanı,
bitirdiniz kadar.
>> Bu yüzden belki de daha basit bulunuyor sezgisel, geçen daha.
En son deneyelim.
Siz kendinizi sıfırlamak olsaydı Aşağıdaki pozisyonlara
son bir kez görelim eğer biz değil Şimdi bir başka yaklaşım resmileştirmek.
Aslında, olur birisi Orada önermek istiyorum
Biz bunu hakkında nasıl başka gidebilir?
Buzzwords veya sıralama dışarı atarak olmadan Zaten bilinen cevapların,
sadece sezgisel, ne yapabilirdi?
>> HEDEF KİTLE: [duyulamaz].
DAVID J. MALAN: Evet.
Yani orada bazı büyük sezgi var.
İyi şeyler bugüne kadar ne gibi görünüyor Biz bölmek bilgisayar bilimi
ve bölme sorununu ele o yarı yarıya ve yarım.
Ve böylece gerçekten biz Bunu yapmak için başlayabilir.
Ve aslında, bu, olması biz edeceğiz gidiyor Henüz, bizim en iyi çözümlerden birini görüyorum.
Ama uzun zaman önce geri buna gelelim.
Aslında, biz yapacağız Bir süre sonra bu hafta söyledi.
Bunu çözmek için başka ne yapabilir?
Yani burada herkes içinde rastgele düzen.
Biliyor musun?
Aksine ileri ve geri gitmek yerine, ileri ve geri, ileri ve geri
Her zaman, bu gibi hissediyor Ben yürüyen bir sürü yapıyorum.
Neden sadece başlamak değil Listenin başında,
ve sadece ait dört koydu?
Bu yüzden bana şu an için varsayalım o Benim liste sadece bu ilk unsurdur.
Dört zamanında şu anda sıralanır, eğer umurumda tüm herşey burda mı?
Bu tür trivially doğrudur, değil mi?
Tek sayı içeren listede, ve benzeri bu sayı, dört Açıkçası sıralanır.
>> Bu yüzden bana şart izin bu liste sıralanır.
Ama şimdi bu listenin geri kalanını var.
Yani şimdi, ben iki karşılaşıyoruz.
Nerede Açıkçası iki yapar Dört göre aittir?
Dört önce.
Yani burada ne yapabilirim?
Yeniden, isminiz nedir?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, Eğer geri adım eğer
senin numarası ile sadece bir an için.
Ve Stefan burada şimdi ne yapmalıyım?
Şuraya Stefan vardiya edelim.
Ve şimdi, Yusuf buraya gelsin.
Ve şimdi, bana iddia izin Burada her şey sıralanır.
Yani, benzer bir sonuç, ama temelde farklı bir yaklaşım.
Ben bile aşağı orada ne bakmadım.
Ben sadece elemanlar alarak devam onlar bana teslim konum olarak,
ve onlarla anlaşma.
>> Yani şimdi, ben altı numarayı görüyorum.
Nerede altıncı aittir?
Biz iki, dört, altı var.
Tam o şimdi nerede.
Yani şimdi en yalnız bırakalım ve Listenin bu kısmı iddia
Şimdi sıralanır.
Ve böylece, bu temelde hissediyor Bu farklı ben sadece
Burada listede üzerinden hareket doğrusal ve asla geri katlama ediyorum.
Evet.
Pekala.
Yani sekiz, nereye ait?
Tam burada.
Mükemmel.
Yani şimdi, bir.
Ah ah.
Bu gibi hissediyor bu pahalı olacak.
Şimdi, daha önceki algoritimde olduğu, Ben sadece insanları takas.
Yani ben onu tüm yol koymak olabilir başlangıcı, ama sonra Joseph taşındı.
Ama şimdi, Joseph taşırsanız Ne yanlış olacak?
>> Şimdi, ben tür Birkaç gün önce undone-- ettik ileri ve daha sonra bir adım atmış
bir adım geri, çünkü şimdi Yusuf bozuk olacaktır.
Yani bu yapalım.
Eğer bir numara sürebilir ve sadece bir an için geri adım.
Nasıl put-- ne Adını bir daha?
>> ANNAN: Annan.
>> DAVID J. MALAN: yerine Annan?
Ne saygı ile gerçekleşmesi gerekiyor İki, dört, altı ve sekiz?
Hepsi kaydırmaya gerek.
Sekiz Yani eğer vardiya istiyorum Önce, sonra altı, daha sonra dört, daha sonra iki.
Ve sonra Annan, eğer ediyorum İyi, buraya gelmek istiyor.
Ama burada, biz sadece ettik tür bir bedel ödedi
algoritması farklı bir noktada.
Seçimi ile son kez Oysa sıralama ve hatta kabarcık sıralama,
Ben geri yürüyorum ve ileri, geri ve ileri,
kesinlikle hangi yukarı ekliyor Zaman bilge ve tam anlamıyla kademeli.
>> Yerleştirme sıralama, ilk başta bu gibi bakışta görünüyor
süper akıllı, ki ben sadece Yavaş, artan ilerleme,
ama ben ileri geri bu gitmiyorum.
Ama birisi gerçekten ise Sipariş, haber dışında
Ben sadece yapmak zorunda çalışmalarının tüm.
Ben listenin yarısını taşımak zorunda Sadece bir numara yer açmak için.
Yani aynı miktarda bulunuyor çalışma bugüne kadar bu
işin sadece farklı bir tür, hissediyor.
>> Devam edelim.
Yani şimdi herkesin biliyoruz bir ve sekiz arasında sıralanır.
Burada, sayı üç var.
Eğer almak isterseniz Üç numaralı, geriye bir tane adım.
Peki siz yapmak gerekiyor?
Evet.
Böylece başka bir, iki, üç adım var.
Sadece maliyet zaman üç ünite Bana üç şimdi sığabilecek şekilde.
Son olarak, yedi.
>> En go ahead ve atalım Bir adım geri alıyorum.
Bu sadece bize mal olacak Bir zamanlar birimi, ama bu sorun değil.
Ve şimdi, beş üyenin gidiyor Biraz daha pahalı olabilir.
Eğer geri adım istiyorsanız.
Biz, sekiz taşımak gerekir yedi ve altı.
Ve sonra herkes artık sıralanır.
Yani burada bizim gönüllülere büyük bir el.
Çok teşekkür ederim.
>> [Alkış]
>> Hepinize teşekkür ederim.
Hepinize teşekkür ederim.
Yani şimdi sadece nasıl görelim bunların hepsi pahalıya mal oldu.
En belki düşünelim Bu en basit kabarcık sıralama.
Ve ben, çünkü basit söylemek Sadece tarafından iştahla bunu çözebilir
Burada ikili sorunu çözmek.
İkili sorunu çözmek Burada, tekrar ve tekrar
ve yine, çok sayıda tekrar senin gibi kat aslında gerekir.
>> Bu yüzden çıkıyor Bir kabarcık sıralama ile, iyi,
kaç adım Ben almak gerekiyor Bu algoritma ilk geçiş?
Ben, en tane see-- izin take-- olabilir iki, üç, dört, beş, altı, yedi.
Ve burada sekiz elemanları var.
Yani n eksi 1 adımların gibi Listenin başından almak
Listenin sonuna.
>> Ama seçim sıralama ile, ben hatırlamak Tekrar öğelerinin seçilmesinden
ve yine o, en küçük bulunuyor Ben, bir yerde koyuyorum
ama sonra değilim Yine arkamda seyir.
Bu yüzden biraz daha net olduğunu düşünüyorum sonra ilk defa, ben belki
Tüm n eksi 1 adımları almak zorunda En küçük eleman bulmak için.
Sonra yere koyun ve ben Daha önce burada kim tahliye.
>> Ama sonra gerek yok Bu elemanın bakarak tutmak,
Biliyorum çünkü bu Zaten küçük.
Yani şimdi, ben sadece yedi bakabilirsiniz elementler, ardından altı elemanları,
daha sonra beş element, dört unsur.
Ve böylece matematiksel n ise elemanları veya sayıların sayısı
biz başladı, hayal edebileceğiniz Bu n eksi 1 ile aynı olduğu,
artı n eksi 2 adım artı n eksi 3 adım
artı n eksi 4 adım, tüm yol aşağı sadece bir adım.
Ve benim son kişi olduğumu.
>> Ve bir sürü olduğunu hatırlayacak olursak kitaplarını ya da matematik kitaplarını istatistik
üzerinde bu formüllere sahiptir Geri ciltli veya onların önünde,
Bu serinin çıkıyor daha basit ifade edilebilir
n kere n olarak eksi 2 üzerinde 1.
Bu değil Ve eğer gayet Aklını ön planda.
Ama bu gerçekten doğrudur.
İşte o yazı sadece basit bir yolu var.
Ve sonra düşünüyorsanız geri dereceli okula,
Sadece çarparak başladığınızda İşlerin, elbette bu,
Sadece n karesi eksi n 2'ye bölünür.
Yaptığım tüm genişletmek olduğunu Orada ifadeler.
Ve o yüzden bu yeniden izin biraz daha farklı.
Bu n, 2 eksi n / 2 bölü var.
>> Yani yine, ben sadece tür uygulayarak kulüpler Bazı aritmetik orada yönetir.
Ama şimdi dikkat edin büyük terim Bu ifadede, tabiri caizse,
n karesi olmasıdır.
Yani evet, n kare var 2 eksi n / 2 ile ayrıldı.
>> Ancak, genel olarak, n ise, Büyük bir değer olacak,
O n karesi iddia gidiyorum baskın faktör olacak.
Sadece olacak Daha büyük bir katkıda
n / 2 den adım sayısı kadar.
Yani bu ne demek istiyorsunuz?
Hatta, en basit bir örnek deneyelim matematik biraz büyük olur gerçi.
>> Bu yüzden, 1 milyon kişi vardı varsayalım evre, ya da 1 milyon şeylere
Biz sıralamak istiyorum.
En bir milyon fiş edelim tam olarak bu formüle
bu toplam alır kaç adım görmek için diyelim kullanılarak milyon unsurları sıralamak,
Seçim sıralama.
>> Bu yüzden daha önce olduğu gibi aynı formülü olurdu.
Ben olsun ki ben, bir milyon fiş ediyorum Bir milyon 2 bölü
eksi bir milyon 2'ye bölünür.
Ben önceden bu matematik yaparsanız Burada biz 500 milyar var
Eksi 500,000, burada , 499999500000 bize verir
hangi oldukça lanetlemek büyük.
>> Aslında, şimdi karşılaştırırsanız 499 milyar 999 milyon
Bizim özgün değer karşı 500.000, 500 milyar, o kadar lanet yakındır.
Sağ? n, 2 verir bölü us-- doğrusu, burada n, 2 bölü
Bize 500 milyar verdi.
Bu oldukça lanetlemek yakın 499,999,500,000 için
kapalı 500.000 çıkarılarak demek olan ya da daha genel olarak, kapalı çıkarılarak
n değil, gerçekten büyük bir anlaşma karesi.
Bu hale n karesi sayılar gerçekten çok hızlı büyür.
>> Şimdi, bu sadece önemli ölçüde biz olarak, bilgisayar bilim adamları olarak,
genellikle çok umurumda gidiş değildir Bu formüllerin nüansları hakkında
ve tam olarak ne Kesin cevaplar.
Biz sadece, sen biliyor musun bakım?
Günün sonunda, bu formül karesi n sırasına olduğunu.
>> Evet, biz orada 2'ye bölünüp ediyoruz.
Evet, biz kapalı n eksi 2 çıkarılarak ediyoruz.
Ama günün sonunda, dönem Bu gerçekten bizi incitiyor ve bizi maliyeti
adımları çok o kare bir terimdir.
Ve böylece ne bir bilgisayar bilimcisi Genellikle yapacak
bunların hepsi görmezden olduğunu Daha küçük mertebeden terimler,
ve sadece bir bakmak maliyet en katkıda bulunur.
>> Ve bu, çünkü biz, güzel, Şimdi çok daha fazla genellik konuşmak
algoritmalar hakkında ve bunları karşılaştırabilirsiniz.
Ben olduğumu ve aslında Bu O kullanarak kasıtlı olduğunu.
Ben sipariş üzerine derken , ben özellikle ben
şey atıfta Büyük O. Ve büyük Ey denilen
bir gösterim olduğu bir bilgisayar bilim adamı tanımlamak için kullandığı
Bir üst şeye bağlı.
>> Eğer bir algoritma olduğunu söylemek Yani eğer n karesi büyük O ise,
Ben önerildiği gibi sadece an önce bu aracı
onun çalışan açısından zaman ya da verimliliği,
Arızalı alır n adımları karesi.
Belki daha az, belki daha fazla.
Ama n emri karesi üzerinde bulunuyor.
Ve bu üst sınır var.
Bu olacak değil Bundan daha acı.
Bu n kuşbaşı olacak, ya da 2 değil n veya çok daha büyük bir şey.
Bu sınır bir üst olduğunu ne olursa olsun o maliyetidir.
Yani, haydi verilen Sadece birkaç örnek düşünün.
Ve bu sadece bir sonlu listesi çok yaygın çalışan süreleri
olması gerekiyordu algoritmalar için biz ettik bazı şeyleri tasvir
Zaten görüldü.
>> Örneğin, dava içinde So Seçim sıralama, ben burada ne yapıyorum iddia
bu seçim sırala koşu olduğunu Zaman n sırası kareli üzerindedir.
En kötü durumda, ben gidiyorum Burada rasgele sayılar bir sürü.
Ve biz matematiksel gördüğümüz gibi, Ben yürümeye devam eğer
Liste boyunca yoluyla Liste, en küçük bir sonraki seçme
Tekrar ve tekrar eleman, ben ise Aslında tüm adımları yazmak
Ben formulaically önerildiği gibi ben alıyorum önce, bu kare n emriyle var
Ben alıyorum adımlar.
>> Ve o balonu çıkıyor sıralama ve yerleştirme sıralama
En kötü durumda gibi yavaştır.
Örneğin, düşünün, ekleme sıralama, Biz ele en son algoritma,
hangi bize elemanın bakmak vardı ait olduğu yere ve sonra takın.
Ve sonra bir sonraki elemanın baktı, ait olduğu yere ve onu takılı.
>> Yani mümkün olan en iyi senaryoyu düşünün.
Ben gönüllüler sıraya vardı varsayalım kelimenin tam anlamıyla böyle, sekize kadar biri
Zaten sıralanır.
Ekleme sıralama kaç adım sekiz kişi sıralamak için sürecekse,
onlar sahnede gelirseniz Bu gibi bakıyor?
>> Sekiz kişi zaten sıralanır.
Ve ben ekleme sıralama kullanmak.
Algoritmalar Bu son.
Peki, gerçek hızlıca reenact edelim.
Ben buradan başlayın eğer Yani, bir bakın.
Nerede biri aittir?
Tam burada aittir.
Ben iki görüyorum.
Nerede iki aittir?
Tam burada.
Ben üç görüyorum.
Nerede üç aittir?
Tam burada.
>> Ben dört görüyorum.
Tam burada.
Beş, altı, yedi, sekiz.
Kendimi tekrarlamak için bir neden yok.
Ve böylece, kaç adım n'nin açısından mı?
Bu n sırasına bulunuyor adımlar, değil mi? n eksi 1.
Ama doğrusal sayı aldı adımlar ve şimdi ben bittim.
Yani olsa da, en iyi durumda değil.
Ne kötü durumda ne olacak?
Ne sekiz, oraya vardı yedi, oraya vardı
ve bir ve iki yüzden, buraya edildi Liste gerçekten tersine olduğunu?
>> Peki, gerçekten olur Bu sayı ne olur?
Ve biz örneklerden sadece bir çift yapacağız.
Ne sayı sekiz, gerçekten, eğer burada ve number-- hoppala.
Peki, eğer gerçekten, sayı Sekiz, buraya tüm yol
ve ben ekleme sıralama kullanıyorum?
>> TAMAM.
Ben yerinde var şu anda iddia.
Ama şimdi, yedi-- nereye yedi nereye gidiyor?
Tabii ki, burada gider.
Yani tek bir yerde sekiz taşımak zorunda.
Şimdi altı, nereye gidiyor?
Peki, tamam.
Şimdi, ben üzerinden sekiz taşımak zorunda Bir yerde, bir yerde yedi
ve sonra altı aşağı plop.
>> Böylece ilk kez, maliyet şeyleri düzeltmek için bana bir adım,
o şeyleri düzeltmek için bana iki adım mal oldu.
Kaç adım düzeltmek için almaya gidiyor
doğru yerde beş koymak şeyler?
Üç.
Şimdi ben zorunda çünkü bir iki, üç taşıyın.
Kaç adımlar alacak doğru yerde dört koymak için?
4 artı 5 artı 6, artı 7.
>> Ve bu yüzden matematiksel özdeş olduğunu Biz seçim sıralama için deyimiyle.
Bu dizi var sadece artıyor.
1 artı 2 artı 3 artı 4, ya da tersine, 7 artı 6
artı 5 artı 4 bugünün kadar ekler n sırasına göre amaçları karesi.
>> Yani ben de şart izin kabarcık sıralama n karesi de geçerlidir.
Çünkü kabarcık sıralama, her biri zaman, listede geçmesi
Ben kabaca kaç adım alıyorum?
Her zaman tam anlamıyla oradan oraya yürümek?
Kabaca n adımlar.
Ama kaç kere olabilir listeye geçmesi gerekir?
>> Eh, kabaca n zaman.
Belki n eksi 1, ama kabaca n kere.
Peki, neden?
Peki, kabarcık sıralama ile, eğer Biz kabarcık sıralama ile başlar
olası en kötü listesinde ile Yine tamamen durum
geriye, ne olacak ki?
Ben listede geçmesi ve sayı kimse orada tüm yol aittir.
>> Ama kabarcık sıralama ile, ne kadar bir tane yok Liste boyunca benim ilk geçişte hareket?
Kaç noktalar o olsun Doğru yere yakın?
Sadece bir.
Yani bu yoluyla eğer tür sebebi, Bu algoritma sayesinde her zaman,
David'in alarak kabaca n adımlar.
Ama kaç geçer Liste öyle aracılığıyla
kabarcık biri için almaya gidiyor ait olduğu sola?
>> O, böyle hareket var n alanlarda bu şekilde.
Dolayısıyla, sadece listenin sıralama yapmak için, Ben ileri geri n kez yürümek gerekiyor.
Ve her seferinde, ben n elemanlı bakıyor.
Yani üzerinde n şeyler n kez yapmak n emri karesi.
>> Şimdi, biz bazı göreceğiz şort o
CS50 sonraki sorun gömülü Bunlara, başka bir yaklaşım ayarlamak,
ama şimdi, Sadece düşünelim diğer bazı çalışma süreleri,
Özellikle sıralama olanlar alırsak zaman biraz batmaya.
Ne biz zaten gördüğümüz bir algoritma var Bu n adımlarının sipariş alır?
>> Doğrusal bir numara almalı neler biz bugüne kadar gördüğüm adımlarını?
Bu da ne?
Telefon rehberi arama.
İlk algoritma.
Sağ?
Biz doğrusal konum nerede Mike Smith arıyor?
Gerçekten.
Haftanın sıfır, ben başladığımda Bir seferde bir sayfa açtığımı,
ve hatta bu tür olduğunu söyledi doğrusal bir duygu algoritması,
ve biz o resim vardı Düz kırmızı çizgi ile yönetim kurulu
ve düz sarı çizgi, o gerçekten vardı
n büyük O olan algoritmaları.
>> Bir telefonda Mike Smith'i bulmak Çünkü En kötü durumda n sayfalarının kitabı,
Beni n adımlar olabilir.
Yoklama alma konusunda ne olacak?
Bir iki üç dört beş altı.
Bu çalışma süresi nedir yoklama almak için algoritma?
Çünkü teoride n Big O, ben odadaki herkesi işaret var.
>> Şimdi bir kenara olarak ne hakkında Haftanın sıfırdan diğer optimizasyon?
İki, dört, altı, sekiz, 10, 12.
Bir bilgisayar bilimcisi olur gerçekleştirmek bir dakika bekleyin,
Bu sırasına bulunuyor n, iki aşama ile ayrılır.
Sağ?
Ben bir anda iki kişiyi yapıyorum çünkü.
Ama biz görmezden gidiyoruz Bu alt mertebeden terimler,
ve biz sadece gidiyoruz 2 ile bölme atmak,
ve sadece söylemek n büyük Ey de bu algoritma için.
>> Peki ya bu?
Biz bunlardan bazıları atlamak, ama ne yapacaksınız n log olan bir algoritma oldu?
Bu kabaca n adımları log aldı?
Böl ve fethet.
Kesinlikle.
Telefon rehberi örnekteki gibi Haftanın sıfır ve bugün erken saatlerde,
Nerede biz sorunu bölünmüş Tekrar ve tekrar ve tekrar.
Biz hafta gemide çekti kavisli yeşil hat olarak sıfır,
ve biz o gün olduğunu söyledi logaritmik algoritması.
>> Ve gerçekten de, sayısı adımlar onu bölmek yerine ve fethetmek için gereken,
veya ikili arama olarak biz başlayacağız Telefon defterinde olduğu gibi, çağırarak,
günlük ve adımların sırasına olduğunu.
Ve bu garip biri bir parçasıdır.
>> Bir adım gerekenlere, veya daha özel olarak
adımlar sabit sayıda?
Belki öyle, belki üç var, iki değil, ancak bir bilgisayar bilimcisi sadece
1 büyük O olarak kolaylaştırır, bazı adımları sabit sayısı.
Bunu yapabileceğim bir şey neler var adımlar sabit sayıda alır?
>> Alkışlar çalışma süresi nedir?
Sabit zaman.
Sağ?
Gibi, çalışma süresi ne sadece birini alır bir şey yapıyor
operasyon gibi F Hello World yazdırın.
Yani, sabit zaman olduğu söylenebilir Baskı F az köşe durumda olmadıkça,
Ne çalışma süresi olabilir baskı F aslında olacak?
Ve neden?
Bu durumda n ölçüm nedir?
>> HEDEF KİTLE: [duyulamaz].
DAVID J. MALAN: Kesinlikle.
Karakter sayısı Biz yazdırmak istiyorum.
Yani çok bağlam-duyarlı olduğunu.
Bugün, biz çok odaklanan oldum harfler ve burada gemide sayılar.
Ama aynı zamanda olabilir gerçek bir dize karakter.
Başka var dışarı yüzden döner önemsememe başlayacak tedbir,
ve tam tersi Büyük O, tabiri caizse.
>> Bu omega notasyonu var.
Büyük O, ne demek Oysa Üst koşu zamanında bağlı?
Maksimum, ne kadar zaman bir şey alabilir?
Omega-- üzgünüm bu geliyor tutar up-- bunun tam tersi olan,
Bir alt sınır üzerinde bulunuyor bu sayede Zaman şey miktarı alabilir.
>> So Örneğin, ne bir algoritma var her zaman n karesi adımlar atmaktadır?
Eh, algoritmaların biri gördüğümüz Bugün Aslında, hem de bu olabilir.
Seçim sıralama.
Seçim çeşit çok aptalca.
Hatta hatta algorithm-- üzgünüm eğer Dizi zaten sıralanır ise,
Seçim sıralama gidiyor Liste boyunca yürümeye devam
en küçük olduğundan emin olmak için eleman tekrar ve tekrar ve tekrar.
Ve sen insanlarda bile seyirci, bir dakika bekleyin biliyoruz,
Zaten geçti küçük elemanı, bilgisayar
görünüyor kadar bunu bilmiyor listede tüm yol boyunca.
Benzer şekilde, bir düşük olduğu bağlanmış de dikkate alınabilir
Lineer zaman olabilir.
>> O kadar sürer ne kadar zaman En iyi sıralama n elemanları
kabarcık sıralama gibi bir şey kullanarak dava?
Listeniz zaten sıralanır varsayalım.
Biz kabarcık sıralama alır söyledi n sırası adımları karesi.
Ama zaten ne sıralanmış eğer?
Ne sonra fark varsa dizi aracılığıyla tek geçişli
Bu hiçbir swapları yaptık?
Eğer geçer fazla yapmaya devam etmek gerekir mi?
>> Hayır.
Yani daha düşük bir kabarcık tür üzerinde bağlı doğrusal olduğu söylenebilir.
N Omega.
Ve biz bakabilirsiniz Bunların da diğerleri.
Yani kısaca bir göz atalım Burada sadece bir görselleştirme de
Bu kendilerini ayırt nasıl çalıştığını görmek için.
Ben bu işe buraya gitmek için gidiyorum C50 web sitesinde mevcuttur var sayfa,
ancak çalışma almak için bir acı olacak, denilen bir teknoloji kullandığından beri
Bir Java uygulamaları, bu gün büyük ölçüde desteklenmeyen,
En azından Chrome ve bazı başkaları tarafından.
>> Ve beni go ahead ve bu hız izin yukarı ve neler olup bittiğini açıklar.
Bu balonun bir gösteri sıralama, ilk algoritma biz baktı.
Ve o bir görselleştirme her bulunuyor Bu çubukların bir sayıyı temsil eder.
Büyük bir bar, numara büyük.
Daha küçük çubuk, numara küçük.
Ve hatta, görsel ne görebilirsiniz Bu da, süper hızlı gidiyor
kırmızı çubuk benim gibi olduğunu geri yürüme ve ileri sorunları tespit.
Sen büyük unsurlar olduğunu görebilirsiniz Gerçekten sağa köpüren vardır,
ve daha küçük elementler sol köpüren vardır.
Ve buraya, biz ise aslında daha yakından bakmak,
biz aslında güvenebilirsiniz karşılaştırmalar ve swap sayısı
Bu yapılıyordu.
>> Ama bunun yerine, en bakalım İkinci algoritma at
biz erken baktı bizim Gönüllüler, seçim sıralama.
Görme, sahip olduğu bir çok farklı etki.
Ama içinde, yine çok sezgisel Biz küçük bir sonraki seçerek tutmak
eleman, ve biz biraz şanslıydık.
Bu temelde daha hızlı hissetti.
Ama biz tekrar bu koştum ve yine girdi sürü ile
Biz gerçekten olduğunu görürdünüz Hala n büyük O'da karesi.
>> En son birini yapalım Burada, ekleme sıralama,
hangi üçüncü algoritma oldu Biz ve hatırlama baktı
bu bir ile ilgilenir olduğunu elemanları, onları karşılaşır olarak,
ama sonra belki vardiya şeyler üzerinde yer açmak için
ait oldukları unsurları ekleyerek.
>> Ve bu da vererek biter son sonuç. Şimdi bunların hepsi üç
oldukça hızlı hissettim.
Ve gerçekten de, ben onları koştu oldukça iyi bir klip.
Ama temelde, hepsi değil oldukça korkunç, dürüst olmak gerekirse.
Bu algoritmalar, şimdiye kadar n büyük O bu çalışma karesi
biraz almak Zaman sonunda çalıştırın.
>> Ve gerçekten de, biz görebilirsiniz ve son olarak bu his
Bu üçüncü ve son demo yukarı çekerseniz.
Bu başka bir şeydir O görselleştirme gidiyor
Soldaki kabarcık sıralama göstermek için, Ortada seçim, sıralama
ve bir şey, biri bizim El, daha önce önerilen yükseltir
Sağdaki sıralama birleştirme.
Bir böl ve fethet Sağdaki stratejisi.
Ve bu konum, aslında, bu Çarşamba günü bakacağız.
Ama paralel olarak çalıştırmak için bu zaman izin verin.
Bu kabaca aynı sayıda var elemanları, hepsi aynı anda çalışan.
Seçim vs Kabarcık sıralama Birleştirme çeşit çeşit vs.
>> Şimdi, hepsi koşuyoruz Aynı anda teoride.
CPU çalıştığından Aynı hız, ama sen
Bunun ne kadar sıkıcı hissediyorum çok çabuk olmaya devam,
ve ne kadar hızlı ne zaman biz hafta biraz enjekte
Zero algoritmaları can biz şeyleri hızlandırmak.
>> Ve şimdi karşılaştırmak izin Son bir biçimde bu.
Ben devam edeceğim CS50 web sitesine, için
Biz bugün bu son bağlantı var nerede internette birisi
nazik bir video araya koymak neyin farklı sıralama yakalar
algoritmaları gibi konuştun.
Bu ekleme türüdür.
>> [Bipliyor]
>> Bu sayede bir frekans uyguluyorsanız bar bar yüksekliğine dayalı.
Bu kabarcık tür.
>> [Eğrilmiş Bipliyor]
>> Önümüzdeki o-- yanındaki geliyor yukarı gelecek o-- seçim sıralama,
Nerede yine biz seçme ediyoruz Bir sonraki en küçük elemanı,
ve biz o büyüyen görebilirsiniz Soldan sağa.
>> Bizim kazanan şimdiye kadar bugün, birleştirmeli sıralama.
Bazı şeyleri bölünmesi nasıl dikkat [duyulamaz] yarısı ve dörtte içine.
Biz değil Gnome sıralama, hakkında konuştuk ve görsel oluşturur
ve biraz audally Farklı şekil ve ses.
Ileri ve geri gidiyor, şeyleri temizlemek.
Ayrıca Heapsort check out Bu adamın web sitesinde.
>> Ve bu kadar.
Size yakın zaman göreceksiniz.
>> [Whooshing VE MÜZİK]