>> [MÜZİK OYUN]
>> ANDI PENG: bölümün haftada 3 hoşgeldiniz.
Tüm Geldiğiniz için teşekkürler, çocuklar, Bu erken başlangıç ​​saatinden bugün.
Biz güzel, küçük var Samimi grup bugün.
Yani umarım alırsınız kaplama, belki erken,
Biraz erken bugün.
Yani hızlı, sadece bazı gündem bugün duyurular.
Başlamadan önce, biz konum biraz üzerinde gidecek
bazı kısa lojistik sorunlar, pset sorular, debrief, böyle şeyler.
Ve sonra sağ dalış olacak.
Biz GDB adında bir hata ayıklayıcı kullanacağız Bizim kod debunking başladığı David
Geçen gün derste açıkladı.
Biz bir türlü dört türleri üzerinde gidersiniz.
Biz oldukça hızlı bir şekilde üzerlerine gidersiniz onlar oldukça yoğun konum beri.
Ama biliyorum tüm slaytlar ve Kaynak kodu çevrimiçi her zaman vardır.
Yani için, senin okuman de, çekinmeyin Geri dönüp bu bir göz atın.
>> Biz aracılığıyla gidersiniz asimptotik gösterimi, hangi
sadece bir fantezi yoludur diyerek "çalıştırıcıları,"
Biz büyük O, sahip olduğu hangi Davut konuşmasında açıkladı.
Ve biz de Omega, sahip olduğu Alt bağlı çalışma zamanı olduğunu.
Ve biz biraz daha fazla konuşacağız derinlemesine nasıl bu çalışmaları ile ilgili.
Ve son olarak, biz, ikili arama üzerinden gidersiniz Çünkü zaten size bir sürü
senin psets baktı muhtemelen biliyorum senin pset öyle bir sorudur.
Böylece tüm mutlu olacağım Bu, bugün kapsayacak.
>> Ve son olarak, başına sizin bölüm geribildirim, ben aslında
yaklaşık 15 dakika sol son biraz üzerinde gitmek
pset3 lojistik, herhangi bir soru, belki rehberlik biraz eğer sen,
Biz programlamaya başlamadan önce.
Yani yoluyla almak için çalışalım oldukça hızlı bir şekilde malzeme.
Ve sonra biz biraz zaman geçirebilirsiniz pset için daha fazla soru alıyor.
TAMAM.
>> Çabuk, bu nedenle sadece bir kaç önce biz duyurular bugün başlıyor.
Birincisi, yapım hoş geldiniz senin psets iki aracılığıyla o.
Ben Senin- evet, izin 's bir göz attım O biri için bir alkış olsun.
Aslında, gerçekten gerçekten etkilendim.
Ben sizin için ilk pset kademeli Geçen hafta ve siz inanılmaz yaptım.
>> Stil noktası oldu birkaç yorum dışında.
Daima konum olun kodunuzu yorumlama.
Ama psets noktada idi.
Ve keep it up.
Ve bu kadar sınıf öğrencisi için iyi Sizler koyarak görüyoruz
senin tarzında kadar çaba kodunuzu ve tasarım
Görmek için biz istiyoruz söyledi.
Yani benim şükran boyunca geçirerek TA geri kalanı için.
>> Ancak orada bir Birkaç debrief soruları
Ben sadece üzerinde gitmek istiyorum Her iki hayatımı yapacak
ve diğer bir sürü TA 'biraz daha kolay yaşıyor.
Öncelikle, ben fark ettik bu Geçmiş senin kaç hafta--
üzerinde check50 çalışan edilmiştir Size önce kodu göndermek?
TAMAM.
Yani herkes check50 yapıyor olmalı, Aslında bir secret-- çünkü--
Bizim doğruluk parçası olarak check50 çalıştırmak kodunuzu test etmek için komut.
Kod başarısız Yani eğer check50, büyük olasılıkla,
muhtemelen gidiyor hem de bizim onay başarısız.
Bazen siz doğru cevaplar var.
Benzeri, açgözlü olarak, bazı Doğru numaraları var,
Sadece bazı ekstra şeyler çıktı.
Ve bu ekstra şeyler Aslında denetimi başarısız,
Bilgisayar yok, çünkü gerçekten aradığını biliyorum.
Ve böylece sadece kadar devam edecektir çıkış yok olduğunu görmek
cevabı ne bekliyoruz maç olabilir ve bu yanlış işaretlemek için.
>> Ve ben ne olduğunu biliyorum senin davaların bazıları bu hafta.
Bu yüzden geri ve elle gitti Herkesin kod regraded.
Gerçi Gelecekte, , emin olun lütfen
Çalıştırdığınız konum kodunuzu 50 kontrol edin.
Ta için tür bir ağrı çünkü regrade elle geri dönüp zorunda
Her için her pset Tek küçük cevapsız örneği.
Yani herhangi bir puan sürmedi.
Ben belki çıkardım düşünüyorum Bir veya tasarım için iki.
Gerçi Gelecekte, eğer Eğer check50 başarısız ediyoruz
noktalar alınacaktır doğruluğu kapatır.
>> Bundan başka, psets olan öğlen Cuma nedeniyle.
Ben yedi dakika olduğunu düşünüyorum Biz size geç ödemesiz dönem.
Harvard zaman başına, onlar izin konum yedi dakika geç her şeyi olacak.
Yani burada Yale'de, yaparız hem de buna uygun.
Ama hemen hemen, 12:07 at, daki pset değilse,
o kadar geç işaretlenmesi için gidiyor.
Süre böylece Ve işaretlenir gibi geç, TA-- ben
hala psets derecelendirilmesi olacak.
Yani hala notu görürsünüz.
Ancak, o biliyor dönem sonunda
tüm geç psets sadece olacak bilgisayar tarafından otomatik olarak sıfırlanan.
>> Biz iki nedenden dolayı bunu.
Bir, bazen olsun Dekanın bahaneler gibi, mazur,
Daha sonra bu konuda henüz bilmiyorum.
Yani biz derecelendirilmesi emin olmak ister Her ihtimale karşı her şeyi olduğu gibi, ben
Bir dekanın bahane eksik.
Ve ikincisi, tutmak Zihin, hala can
tek pset damla olduğunu Tam kapsam noktaları vardır.
Ve böylece biz sınıf gibi senin psets hepsi sadece
senin kapsamı en emin olun etmek Orada ve bunları çalışıyoruz.
Geç oldu, bu yüzden bile hala edeceğiz kapsam noktaları için kredi almak sanırım.
>> Hikaye Yani ahlaki, yapmak emin psets zamanında bulunmaktadır.
Ve zamanında değilse, büyük değil biliyorum.
Evet, ben geçmeden önce, herkes var pset geribildirim ile ilgili herhangi bir sorunuz var mı?
Evet.
>> HEDEF KİTLE: Eğer biz dedin psets birini bırakabilirsiniz?
>> ANDI PENG: Evet.
Yani dokuz psets genel var dönem boyunca.
Ve sen kapsamı varsa points-- böylece kapsam, sadece bir
hemen hemen, sen çalıştığınız Sorun, sen zamanında koyarak
Eğer ettik olduğunu gösteriyor gösterdi Eğer spec okudum.
Bu hemen hemen kapsamı var.
Ve yerine ise kapsam noktaları, biz
en düşük bırakabilirsiniz Tam kapsam dışında biri.
Yani sizin avantajı var tamamlamak ve her pset deneyin.
>> Hatta upload-- hiçbiri eğer Onları hepsini upload çalışır.
Ve sonra biz umarım yapabileceksiniz Size bu noktaların bazıları geri ver.
Güzel.
Başka soru?
Büyük.
>> İkincisi, ofis birkaç hours-- ofis saatleri hakkında hızlı notlar.
Yani ilk hafta erken gelir.
Kimse de hiç bir Pazartesi günleri çalışma saatleri.
Christabel geldi Çalışma saatleri dün gece.
Evet, Christabel.
Ve biz ofiste neler var mıydı Saat dün gece, Christabel?
>> HEDEF KİTLE: Biz dondurma vardı.
>> ANDI PENG: Peki bu doğru, biz ofis saatlerde dondurma dün gece.
Ben size söz edemesek Biz ofis saatlerde dondurma olacak
Her hafta, sana söz veriyorum ne önemli ölçüde olacak olmasıdır
TA oranı daha iyi öğrencisi.
Okunaklı gibi, bire üç gibi.
, O kontrast Oysa Perşembe, yaklaşık 150 var
Gerçekten çocuklar ve hiçbir dondurma vurguladı.
Ve bu sadece herkes için verimli değil.
Hikayenin Yani ahlaki, erken gelmek olduğunu Mesai saatleri ve iyi şeyler
olacak.
>> Ayrıca, soru sormak için hazırlanan gelir.
Bilirsin?
Ne olursa olsun, TA, ben diyerek edilmiştir düşünüyorum,
biz birkaç öğrencilere alıyorum oldum 10:50 gibi, Perşembe günü gelip kim
spec okumak zorunda değil Bana yardım gibi olmak, bana yardım et.
Ne yazık ki bu noktada, var çok değil biz size yardım etmek yapabilirsiniz.
Yani hafta erken gel lütfen.
Mesai saatleri erken gel.
Soru sormak için hazırlıklı gelin.
Olarak emin olun size Bir öğrenci, nerede
Eğer böylece gerekir TA, birlikte size rehberlik edebilir
Ne çalışma saatleri olan gerektiği için ayrılacak.
>> İkincisi, bu yüzden profesörler biliyorum testlerle bize sürpriz istiyorum.
Ben bir profesör olanlar vardı yo gibi, bu arada,
O ara sınav hatırlıyorum Bir sonraki Pazartesi var.
Evet, o vize hakkında bilmiyordum.
Yani o olacağım TA Bu size tüm bu sınav hatırlatıyor
Bilirsin, çünkü 0--, biz CS sensin.
Şimdi bitti diziler var ki olsun bu test 0 neden, eh, 1 yarışması değil?
TAMAM.
Oh, o birinde bazı chuckles var.
TAMAM.
>> Yani yarışması 0 ise 14 Ekim olacak Eğer Pazartesi-Çarşamba bölümünde konum
ve 15 Ekim sen iseniz Salı-Perşembe bölümü.
Bunun için geçerli değildir Harvard'da o sizin
Hepinizin olacağım düşünüyorum Kim-- 14 sınavlar alarak.
>> Yani evet, gelecek hafta, eğer David, derste, gider
evet, bu konuda öylesine bilgi yarışması önümüzdeki hafta, tüm
Çünkü şok olmayacak Eğer bölüme geldi
ve sen bunu biliyorsun senin Quiz 0 iki hafta içinde.
Ve biz inceleme olacak oturumları ve her şey.
Hakkında hiçbir endişe Bunun için korkmak.
Herhangi bir sorunuz herhangi bir sorunuz before-- Tüm ilgili lojistik konulara,
sınıflandırma, mesai saatleri, bölümler?
Evet.
>> HEDEF KİTLE: sınav So derste olacak?
>> ANDI PENG: Evet.
Yarışması Yani, sanırım, 60 Bu zaman diliminde ayrılan dakikalar
Sadece alacağım konferans salonunda.
Yani gelmek zorunda değilsiniz rastgele 7:00 gibi, üzerinde.
Hepsi iyi.
Evet.
Güzel.
>> Pekala.
Yani biz gidiyoruz Size bir kavramını tanıtmak
David tür zaten bu hafta Bu geçmiş hafta derste değindi.
Bu GDB denir.
Ve nasıl bir çoğunuz, süre daki psets yazma tabii ki,
diyor büyük bir düğme fark var IDE üstünde "Debug"?
TAMAM.
Yani şimdi biz aslında ortaya çıkarmak için alırsınız Ne o düğmenin gizem aslında
yapar.
Ve ben bir olduğunu garanti Güzel, güzel bir şey.
>> Şimdiye kadar, bence yukarı Yani iki şey var oldu
Öğrenciler genellikle olmuştur psets ayıklarken yapıyor.
Bir, onlar da eklemek printf () - böylece her birkaç satır,
onlar printf () eklemek - ah, bu değişken nedir?
Ah, bu değişken nedir şimdi-- ve ne tür ilerlemesini görmek için
kodunuzu olarak çalışır.
Ya da çocuk yapmak İkinci yöntem ise Onlar sadece her şeyi yazmanızı
ve sonra sonunda böyle gidin.
Umarım işe yarıyor.
Ben size garanti, GDB iyidir Bu yöntemlerin her ikisi birden.
Evet.
Yani bu senin en iyi arkadaşın olacak.
Bu güzel bir şey, çünkü Bu görsel görüntüler hem
ne Kod yapıyor belirli bir noktada
yanı ne gibi tüm senin değişkenler taşıyoruz,
değerleri ne gibi belirli bir noktada.
Ve bu şekilde, gerçekten can kodunuzda kesme noktası ayarlamak.
Sen satır hattı üzerinden çalıştırabilirsiniz.
Ve GDB için sadece sahip olacak Eğer, sizin için görüntülenir
ne tüm değişkenlerin , ne yapıyoruz,
Ne kodunda oluyor.
Ve bu şekilde, bu kadar çok daha kolay görmek için
Ne printf-ing yerine oluyor ya da ifadeleri yazıyorlar.
>> Yani biz daha sonra bu bir örnek yapacağız.
Yani bu biraz soyut gibi görünüyor.
Endişeye gerek yok, biz örnekler yapacağız.
Ve böylece esasen, üç büyük, Eğer GDB ihtiyaç duyacağınız işlevleri en sık kullanılan
Sonra, üzerinde Step vardır, ve düğmeler adım.
Ben sından gidiyorum Orada, aslında, hemen şimdi.
>> Yani siz tüm görebilirsiniz ya da ben biraz yakınlaştırmak gerekir?
Arkada, bunu görebiliyorum?
Ben yakınlaştırmak mıyım?
Birazcık?
Tamam iyi.
Oraya gidiyoruz.
TAMAM.
>> Yani, gözlerimi burada var açgözlü için uygulanması.
Ve çocuklar bir sürü yazdı iken Bu form-- while döngüsünde açgözlü
yapmak için mükemmel kabul edilebilir bir yoldur sadece etmektir yapmak için başka bir yol dökersin--
modulo içinde bölün.
O zaman olabilir, çünkü senin değer ve sonra kalanını var.
Ve sonra sadece can Hepsini bir araya ekleyin.
Ben ne yapıyorum mantığı mı Burada herkese mantıklı,
Başlamadan önce?
Biraz?
Güzel.
Büyük.
Bu oldukça seksi bir parça kod, ben söyleyebilirim.
Sanki David, şunları söyledi Bir süre sonra, ders,
Tüm kod görmeye başlarsınız güzel bir şey olarak.
Ve bazen güzel gördüğünüzde Kod, böyle harika bir duygu.
>> Yani ancak bu kod çok iken güzel, düzgün çalışmıyor.
Yani bu konuda check50 çalıştırın.
50 20-- OOP yi kontrol edin.
2?
Bu pset2 mi?
Evet.
Ah, pset1.
TAMAM.
Bu yüzden check50 çalıştırın.
>> Ve siz burada gördüğünüz gibi, bu durumlarda bir kaç başarısız oluyor.
Ve sizin bazı için Sorunun setleri yapmanın elbette,
ah, neden çalışmıyor gibi sen.
Neden bazıları için çalışıyor değerler değil başkaları için?
Peki, GDB size şekil yardımcı oluyor neden bu girişler çalışma değildi.
>> TAMAM.
Yani, birini görelim Ben check50 başarısız oldu çekler
0.41 giriş değeri oldu.
Doğru cevap Böylece Eğer almak gerekir bir 4'tür.
Ama onun yerine ben yazdırmak ne am yanlış 3-n vardır.
Yani sadece, Sadece elle çalışmasına izin check50 çalıştığından emin olun.
En ./greedy yapalım.
Oops, ben açgözlü yapmak zorundasınız.
Oraya gidiyoruz.
Hemen ./greedy.
>> Ne kadar borçlu olduğunu?
En 0.41 yapalım.
Ve evet, biz burada göremiyor bu 3 çıkış var olduğunu
ne zaman doğru cevap, Aslında, 4 olması gerekmektedir.
Öyleyse GDB girelim ve biz nasıl Bu sorunu gidermekle ilgili gidebilirsiniz.
>> Ilk adım So her zaman kod hata ayıklama
Bir kesme noktası ayarlamak için, veya bir nokta hangi sen
bilgisayar veya istediğiniz ayıklayıcı bakarak başlamak için.
Bunu yaparsanız Yani gerçekten Senin sorunun ne olduğunu biliyorum,
Genellikle, tipik şey istiyoruz yapmak ana bizim kesme ayarlamaktır.
Yani siz bu görebiliyorsanız Orada kırmızı düğme,
evet, beni batıyordu bir ana işlevi için breakpoint.
Bunu tıklatın.
>> Ve sonra benim Debug düğmesi kadar gidebilir.
O düğmesine basın.
Ben eğer bana geri yakınlaştırın edelim.
Oraya gidiyoruz.
Yani biz, burada, sağda bir panel var.
Arkada, çocuklar için üzgünüm, sen Gerçekten çok iyi göremiyorum.
Ancak esas olarak, tüm Bu sağ panel yapıyor
Her iki vurgulanan takip edilir kod satırı satır,
Bilgisayar şu anda çalışmakta olduğunu, de sizin tüm değişkenler olarak
Buraya.
>> Yani sent, sikkeler, n var, tüm farklı şeyler beyan
Bu noktada.
Endişeye gerek yok, çünkü biz aslında var henüz değişkenlere onları başlatıldı.
Bilgisayarınızda Yani senin Bilgisayar sadece görüyor,
oh, 32767 son kullanılan işlev oldu benim bilgisayar bu bellek alanı.
Cent şu anda nerede ve böylece bu.
Ama hayır o bir kez, kodu çalıştırmak o başlatılmış olmalıdır.
>> Yani tarafından, çizgi üzerinden gidelim çizgi, burada ne oluyor.
TAMAM.
Buraya kadar Yani üç vardır Ben sadece açıkladı düğmeleri.
Sen, Çal, veya Çalıştır işlevi var düğme, sen düğme üzerinde Adım var
ve ayrıca düğme içine adım var.
Ve esas olarak, tüm üç Onları sadece kod geçmesi
ve farklı şeyler yapmak.
>> Yani tipik hata ayıklama yaparken, biz sadece Çal vurmak istemiyorum,
Oynat sadece çalışır çünkü Bunun sonuna kadar kodu.
Ve sonra aslında olmaz bildiklerini Sorununuz
Birden kesme noktası ayarlamak sürece olduğunu.
Birden kırılma noktaları ayarlarsanız, Sadece otomatik olacak
tek kesme çalıştırmak, sonraki, bir sonraki.
Ancak bu durumda biz ettik sadece bir tane, çünkü biz
yolumuza çalışmak istiyoruz Yukarıdan aşağıya aşağıya.
Yani biz bu düğmeye görmezden gidiyoruz Şu anda bu programın amaçları için.
>> Fonksiyonu üzerinde Step Yani sadece her hattı üzerinden adım
ve ne söyler Bilgisayar yapıyor.
Işlevi içine Adım gider Gerçek işlevi
Bu kod hattınıza var.
Yani, örneğin, printf () gibi, Doğru, bir işlevdir?
Ben fiziksel olarak adım isteseydim printf () fonksiyonu içine
Aslında parçasının içine giderdim printf () Yazılı ve görmek oldu kod
Orada neler oluyor.
>> Ama genellikle, biz varsayalım Biz size kod çalışır.
Biz () çalışıyor printf varsayalım.
Biz GETINT () çalıştığını varsayalım.
Yani hiç gerek yok Bu fonksiyonların adım.
Ama işlevleri varsa Kendinizi yazdığınız
Denetlemek istediğiniz Neler üzerinden,
Eğer adım isteyeyim Bu işlevi.
>> Yani şu anda biz sadece gidiyoruz Bu kod parçası üzerinden adım.
Yani görelim.
Ah, baskı, "Ah hai, nasıl fazla bir değişiklik borçlu olduğunu? "
Biz umurumda değil.
Biz çalıştığını biliyorum, bu yüzden üzerine adım.
>> Yani n, bizim şamandıra olanı Biz initialized-- ettik ya declared--
üstünde yukarı, şimdi sen GetFloat bu eşit ().
Yani o aşkın çekilsin.
Ve biz görmek alt burada, program
Bir değer girişine bana sormadan olduğunu.
Yani girişi en istediğimiz değeri izin 0.41 olan burada test etmek.
Büyük.
>> Şimdi n- siz görüyorsunuz Burada, bottom-- azından var:
stored-- çünkü biz Henüz yuvarlak değil, bu kadar
Böyle devi saklanır 0,4099999996 olan şamandıra,
yeterince yakın olan bizim amaçları, şu anda 0.41 kadar.
Ve sonra biz, sonra da göreceksiniz biz Programın içinde adım devam
Bundan sonra, n haline gelmiştir yuvarlak ve sent 41 olmuştur.
Büyük.
Yani bizim yuvarlama en çalışma olduğunu biliyoruz.
Biz olduğunu biliyorum cent doğru sayıda,
bu nedenle bu olduğunu biliyorum gerçekten sorun.
>> Yani biz adım devam Bu programda üzerinde.
Biz buraya gidin.
Ve böylece bu kod satırından sonra, biz Biz kaç dörtte bilmeli.
Biz üzerinden adım.
Ve biz, aslında, bir tane var mı bakın çeyrek biz 25 çıkartılır çünkü
41 bizim başlangıç ​​değerinden.
Ve bizim sent için 16 sol var.
>> Herkes nasıl anladı mı Program sayesinde artırıyor
ve neden sent şimdi 16 oldu ve neden şimdi, sikkeler 1 haline gelmiştir?
Herkes bu mantığı takip ediyor?
Güzel.
Bu noktanın Yani Programın çalışma, değil mi?
Biz tam olarak yaptığını biliyorum biz bunu istediğini.
Ve biz aslında değil mi oh, yazdırmak zorunda ne
Bu noktada sent olan Bu noktada paralar budur.
>> Biz programa geçiyoruz devam.
Adım atmak.
Güzel.
Biz Dimes üzerine gitmek.
Büyük.
Biz almış olduğunu görüyoruz Bir kuruş için 0,10 $ kapatır.
Ve şimdi biz iki sikke var.
Bu doğru.
>> Biz pennies gidip gördüğümüz biz cent üzerinde kaldı ettik.
Hmm, bu garip.
Burada Programda, ben gerekiyordu Benim pennies çıkarılır olması.
Belki de sadece değildim Bu hat hakkını yapıyor.
Ve ne yazık ki, gördüğünüz Burada biz biliyorum çünkü
biz adım olduğunu hatlar 32 ve 33 vasıtasıyla,
Bu nerede bizim programı yanlış değişkenler çalıştırmak vardı.
Yani biz bakmak ve oh görebilirsiniz, Burada sent çıkarılarak ediyorum
ama aslında değilim Benim jeton değeri ekleyerek.
Ben sent ekliyorum.
Ve ben eklemek istemiyorum cent, ben sikke eklemek istiyorum.
Bu yüzden sikke olduğunu değiştirirseniz, Biz bir çalışma programı var.
Ben check50 çalıştırabilirsiniz.
Sadece GDB sağ dışarı çıkabilirsiniz Burada ve daha sonra tekrar check50 çalıştırın.
Ben sadece bu yapabilirim.
Ben açgözlü yapmak zorundasınız.
0,41.
Ve burada, bu baskı var Doğru cevap dışarı.
>> Siz gördüğünüz gibi, GDB Gerçekten güçlü bir araçtır
biz bu kadar kod varken için oluyor ve pek çok değişken
o kadar, bizim için zor olduğunu Bir insan, takip etmek.
GDB bilgisayar, debugger, yeteneği vardır
her şeyi takip etmek.
Herhalde Visionaire içinde, çocuklar, biliyorsun Bazı segmentasyon hataları vurdu olabilir
Çalışmakta çünkü senin dizi sınırlarının dışına.
Sezar örnekte, bu Tam burada neler uyguladık.
>> Yani kontrol etmek için unuttum ne olursa olacağını ben
İki komut satırı argümanlarını yoktu.
Ben sadece bu kontrol koymadı.
Ben Debug-- çalıştırırsanız Ve bu yüzden set Benim kesme Orada sağa.
Ben Debug çalıştırın.
>> TAMAM.
Evet.
Yani aslında, GDB gerekiyordu Orada bana sahip
Orada bir segmentasyon hatamdı.
Ben neler olduğunu bilmiyorum Orada, ama ben bunu çalıştırdığınızda
o çalışıyordu.
Eğer aracılığıyla kod satırlarını çalıştırdığınızda ve GDB aniden, size çıkmak olabilir
kadar gidip kırmızı hata ne bak.
Bu, hey, sen anlatacağım bir segment hataya vardı,
hangi erişmek için çalıştı anlamına gelir olmasaydı bir dizide yer.
Evet.
>> Bir sonraki sorun Yani Bu hafta ayarlamak, siz
Muhtemelen bir sürü olacak değişkenler etrafında yüzen.
Emin olmak için gitmiyoruz Ne hepsi belli bir noktada demek.
Yani GDB gerçekten bulmaktan size yardımcı olacaktır hepsi eşit ne olduğunu
ve görsel görmek mümkün.
Herkes nasıl karıştırılır Bu herhangi bir çalışma oldu?
Güzel.
Pekala.
Yani bundan sonra, biz Sağ dalmaya gidiyorum
içine farklı dörttür Bu hafta türlü çeşitleri.
Kaçınız, ilk Tüm biz başlamadan önce,
pset3 için tüm spec okudum?
TAMAM.
Sizlerle gurur duyuyorum.
Bu sınıfın yarısı, gibi hangi son kez önemli ölçüde daha fazla olduğunu.
>> Böylece, harika çünkü ne zaman Biz içeriği hakkında konuşmak
lecture-- veya üzgün olarak, section-- de hoşuma
Bunun bir çok ilişki geri pset ne olduğu
ve istediğiniz nasıl senin pset o uygulamak.
Eğer sahip gelmek Yani eğer spec okumak, o olacak
anlamak için çok daha kolay olacak Ben dediğimde neden bahsettiğimi,
hey oh, bu gerçekten olabilir bu tür uygulamak için iyi bir yer.
Okudum sizin kim yüzden senin pset bir parçası olarak, biliyoruz spec,
Eğer zorunda gidiyoruz türden bir tür yazın.
Yani bu çok yararlı olabilir Size bir sürü bugün.
>> Yani biz başlayacağız, esasen, en basit tip
tür, seçim sıralama.
Tipik algoritma Biz bu konuda gitmek istiyorum nasıl
Bu-- Davut bütün bu geçti ders, bu yüzden çabuk birlikte hareket edeceğiz
burada-- Eğer, esasen değerler dizisi var.
Ve sonra bulmak En küçük sıralanmamış değer
ve bu değer ile takas İlk sıralanmamış değer.
Ve sonra sadece tekrar tutmak Listenizdeki geri kalanı ile.
>> Ve burada bir görsel açıklama Bunun işe yarayacağını nasıl.
Biz Yani örneğin, başlamak için Beş elemanlı bir dizi, endeksi ile
4 0, 3, 5, 2, 6 ve 4 değerlerini bu yüzden şimdi array-- yerleştirilir,
biz sadece varsaymak gidiyoruz hepsi unsorted olduğunu
biz başka türlü test değil çünkü.
>> Peki nasıl bir seçim çeşit olur iş o ilk olur ise
bütünüyle koşuyoruz sıralanmamış dizinin.
Bu küçük değerini almak istiyorum.
Bu durumda, 3 içinde sağ Şimdi, en küçüğüdür.
Bu 5 alır.
Hayır, 5 edemememden büyük değildir veya üzgün, 3 edemememden az değil.
Yani asgari değeri hala 3 olduğunu.
Ve sonra 2 olsun.
Oh, gördüğü bilgisayar, 2 3'ten az olduğunu.
2 şimdi asgari değeri olmalıdır.
Ve böylece ilk değere sahip 2 takas.
>> Yani bir geçtikten sonra, biz gerçekten görüyoruz Bu 2 ve 3 takas.
Ve biz sadece yapmaya devam edeceğiz Bu yine dizinin geri kalanı ile.
Yani biz sadece aracılığıyla çalıştırmak için gidiyoruz dizinin son dört indeksler.
Biz 3 olduğunu görürsünüz Bir sonraki en düşük değer.
Yani biz 4 ile bu takas için gidiyoruz.
Ve sonra biz sadece devam için gidiyoruz Sonunda kadar çalışan, sen
Sıralanmış bir dizi olsun hangi 2, 3, 4, 5 ve 6 her sıralanır.
Herkes anladı mı mantığını Bir seçim sıralama nasıl çalıştığını?
>> Sadece çeşit var asgari değeri.
Ne olduğunu takip ediyoruz.
Bunu bulmak zaman, sen takas array-- ilk değeri
ya da değil, ilk value-- Dizideki bir sonraki değeri.
Güzel.
>> Yani adamlar olarak tür kısa bir bakış gördüğümüz,
biz bu pseudocode gidiyoruz.
Yani arkada siz isterseniz Bir masada bir grup, herkes oluştururlar
Biraz ortağı oluşturabilir, ben gidiyorum Sana üç dakika gibi adamlar vermek
Sadece konuşmak için mantık, İngilizce,
biz uygulamak mümkün olabilir ve nasıl pseudocode seçim tür yazmak için.
Ve şeker var.
Gelip şeker alınız.
Eğer arka konum ve isterseniz şeker, sana şeker atmak olabilir.
Aslında, sen-- serin yapmak.
Ah özür dilerim.
TAMAM.
>> Biz, isterseniz Yani Bir sınıf, yazma pseudocode
birine yaklaştığınızda nasıl için Bu sorun, sadece çekinmeyin.
Ben sadece dolaşmak ve edeceğiz, sırayla, gruplar sormak
sonraki hat için Biz ne yapıyoruz olmalıdır.
Siz başlatmak istiyorsanız Yani off ilk şey ne
Eğer çalıştığınız zaman yapmak Bu programı çözmek için bir yol uygulamak
seçici bir listeyi sıralamak için?
Sadece biz varsayalım Diyelim bir dizi, tamam mı?
>> HEDEF KİTLE: Bazı oluşturmak istiyorsanız çeşit [duyulamaz] sen o
senin tüm dizi boyunca çalışan.
>> ANDI PENG: Doğru.
Yani yineleme yapmak istiyorum gidiyoruz Her uzayda, değil mi?
Harikulade.
Siz bana vermek istiyorsanız Bir sonraki arkasında, evet LINE.
>> HEDEF KİTLE: Onları kontrol tüm küçük için.
>> ANDI PENG: Orada gidiyoruz.
Bu yüzden geçmesi ve kontrol etmek istediğiniz Minimum değer, doğru olduğunu görmek?
Ben o kısaltmak için gidiyorum "min."
Siz sonra ne yapmak istiyorsun Eğer minimum değeri buldum?
>> HEDEF KİTLE: [duyulamaz]
ANDI PENG: Yani istediğiniz gidiyoruz Bu dizinin ilk ile geçiş
sağ?
Bunu söylemek için gidiyorum, başlangıç.
Pekala.
Yani şimdi ilk takas ettik biri, ne bundan sonra ne yapmak istiyorsun?
Yani şimdi biz biliyoruz ki burada bu Doğru, küçük değeri olmalı?
Sonra ek dinlenmesi ayıklanmamış var dizinin.
Yani eğer, burada ne yapmak istediğinizi adamlar bana bir sonraki satıra vermek istiyorum?
HEDEF KİTLE: Öyleyse yineleme istediğiniz dizinin geri kalanı ile.
ANDI PENG: Evet.
Ve böylece yineleme yok neler tür muhtemelen gerekir ima?
Ne tür--
>> HEDEF KİTLE: Ah, ek bir değişken?
ANDI PENG: Muhtemelen döngü başka, değil mi?
Bu yüzden belki de istediğiniz gidiyoruz through-- harika yineleme.
Ve sonra geri dönmek için gidiyoruz ve muhtemelen yine en az kontrol
sağ?
Ve tekrar tutmak için gidiyoruz Bu, döngüler çünkü sadece gidiş
Doğru, çalışmasını sağlamak için?
>> Yani siz, biz gördüğünüz gibi sadece genel bir pseudocode var
İstediğimiz nasıl bu program bakmak için.
Burada bu yineleme, biz ne tipik bizim kod yazmak gerekiyor
biz yineleme yapmak istiyorsanız Yapının dizi, ne tür?
Ben Christabel düşünüyorum Daha önce bu dedi.
>> HEDEF KİTLE: döngü için.
>> ANDI PENG: döngü için?
Kesinlikle.
Yani bu muhtemelen bir döngü için olacak.
Ima edecek buraya bir çek nedir?
Genellikle, kontrol etmek istiyorsanız bir şey bir şey varsa else--
>> HEDEF KİTLE: Eğer.
>> ANDI PENG: Bir eğer, değil mi?
Burada takas Ve sonra, biz olacak Daha sonra üzerine gitmek David çünkü
yanı sıra ders bu geçti.
Ve sonra ikinci yineleme implies--
>> HEDEF KİTLE: döngü için bir başka.
>> ANDI PENG: Tam, döngü --another.
Biz arıyoruz Yani eğer Bu doğru, biz
muhtemelen olduğunu görebiliyorum for döngüsü iç içe geçmiş bir ihtiyacımız olacak
Orada bir koşullu deyimi ile ve daha sonra kod gerçek bir parçası olduğunu
değerleri takas olacak.
Yani sadece genel yazdım Burada pseudocode kodu.
Ve sonra biz aslında gidiyoruz fiziksel olarak, bir sınıf olarak,
Bu bugün uygulamaya çalışın.
Şimdi bu IDE içine dönelim.
>> Ah ah.
Neden vardır değil-- bu olmasıdır.
TAMAM.
Üzgünüm, bana biraz daha yakınlaştırmak için çalışalım.
Oraya gidiyoruz.
Burada yapıyorum All I yarattık olduğunu adında bir program "seçimi / sort.c."
Ben dokuz bir dizi oluşturduk değerleri, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Şu anda, olarak yapabilirsiniz Onlar sırasız olarak, bkz.
n sayı olacak ki Size değerlerin miktarını söyler
Eğer dizide var.
Bu durumda, dokuz değerlerine sahiptir.
Ve sadece burada bir for döngüsü var Bu sıralanmamış dizi yazdırır.
>> Ve sonunda, ben de bir var Sadece tekrar yazdırır döngü.
Yani teorik olarak, bu program ise sonunda, düzgün çalıştığını,
Bir döngü için basılmış görmelisiniz burada 1, 2, 3, 4, 5, 6, 7, 8,
9 sırayla tüm doğru vardır.
>> Yani biz burada bizim pseudocode var.
Ben sadece ki-- herkes istiyor mu volunteers-- sormak gidecek
eğer ne tip tam söyle Biz öncelikle, sadece yineleme istiyorum
Bu dizinin başından aracılığıyla?
Ben kod satırı neler var Muhtemelen burada ihtiyacımız olacak?
>> HEDEF KİTLE: [duyulamaz]
>> ANDI PENG: Evet, hissediyorum ücretsiz aşağıdaki amaçlara üzgünüm, seni
up-- hissediyorum durmak zorunda değilsiniz Sesinizi biraz yükseltmek için ücretsiz.
>> HEDEF KİTLE: int i eşittir İçin 0--
>> ANDI PENG: Evet, iyi.
>> İZLEYİCİ i dizi uzunluğundan daha kısadır.
>> ANDI PENG: Yani tutmak Burada akla çünkü biz
bir işlev yok Bize bir dizi uzunluğu söyler,
biz zaten var Bu depolar değer.
Sağ?
Başka bir şey tutmak için Bir dizideki zihinli bölgesindeki
Dokuz değerler, indeksler nelerdir?
Sadece bu dizi 3 0 oldu diyelim.
Geçen görüyoruz endeks aslında 3'tür.
Orada olsa bile, 4 değil, Dizideki dört değer.
>> Buraya Yani, biz çok dikkatli olmak zorundayız uzunluk ne için bizim durumun
olacak.
>> HEDEF KİTLE: Bu n eksi 1 olmaz mıydı?
ANDI PENG: Gidiyor Tam n eksi 1,.
Bu mantıklı, neden mı o n eksi 1, herkes?
Diziler sıfır endeksli çünkü öyle.
Onlar 0'dan başlar ve 1 n eksi kadar çalıştırın.
Evet, bu biraz zor.
TAMAM.
Ve daha sonra--
HEDEF KİTLE: Isnt'1 o Zaten olsa halledilir,
Sadece daha az ya da "demiyorum tarafından Eşit daha az "ve sadece diyerek" mı? "
>> ANDI PENG: Bu bir var Gerçekten iyi bir soru.
Yani evet.
Ama aynı zamanda, biz yol olduğunu kontrol hakkının uygulanması,
Eğer iki değeri karşılaştırmak gerekir.
Yani aslında istediğiniz "ayarından" boş bırakın.
Karşılaştırmak Çünkü eğer bu bir sen gitmiyorsun
ondan sonra bir şey var Doğru, karşılaştırmak?
Evet.
Yani i ++.
En bizim parantez ekleyelim.
Whoops.
Büyük.
Bu yüzden başlangıcı var Bizim dış döngünün.
Yani şimdi biz muhtemelen istiyoruz tutmak için bir değişken oluşturmak
En küçük değer parça, değil mi?
Herkes bana vermek istiyor mu Bu yapardı kod satırı?
Biz gidiyoruz biz neye ihtiyacım var bir şey saklamak istiyorum?
>> Sağ.
Bunun için belki daha iyi bir isim "temp" göre-- olur tamamen works--
belki daha doğrusu olacağını adında bir, Biz küçük value-- istiyorsanız
>> HEDEF KİTLE: Dk.
ANDI PENG: min, oraya gidiyoruz.
dk iyi olurdu.
Ve işte, biz ne bunu başlatmak istiyor?
Bu biraz zor.
Çünkü şu anda en Bu dizinin başında,
Eğer doğru bir şey, baktım değil mi?
Otomatik Peki, eğer Biz sadece ben 0 eşittir konum
Biz başlatmak için ne istiyorsun bizim ilk minimum değer?
HEDEF KİTLE: i.
ANDI PENG: i tam.
Christabel, neden istiyoruz i bunu başlatmak için?
>> HEDEF KİTLE: iyi, Çünkü Biz 0 ile başlıyoruz.
Karşılaştırmak için bir şey var, çünkü Yani o, en az 0 sona erecek için.
>> ANDI PENG: Kesinlikle.
Yani tam olarak doğru.
Biz aslında Çünkü Henüz bir şey baktı
Bizim en küçük değeri nedir bilmiyorum.
Biz sadece bunu başlatmak istiyor Ben, hangi anda, burada.
Ve biz devam ettikçe Bu dizi aşağı doğru hareket,
her ile, göreceksiniz ki Ek geçiren, ben artırır.
Ve böylece bu noktada, ben muhtemelen gidiyor
Minimum olmak istiyorum, o ne olursa olsun olacak çünkü
ayıklanmamış dizinin başlangıcıdır.
Güzel.
>> Yani şimdi eklemek istediğiniz burada bir döngü için de bu
yineleme yapmak için gidiyor ayrımı yapılmamış diğer veya bu dizinin geri kalanı.
Herkes bana bir vermek istiyor mu Bu yapardı kod satırı?
Hint-- burada ne aşağı gerekiyor?
Ne döngüsü için bu gidecek?
Evet.
HEDEF KİTLE: Yani biz isterdim Farklı bir tamsayı olması,
gerisini biz içinden koşuyoruz çünkü yerine i dizisi, belki bir
j.
>> ANDI PENG: Evet, j bana iyi geliyor.
Eşittir?
>> HEDEF KİTLE: Yani, çünkü i olmak artı 1 olur Bir sonraki değerde başlıyoruz.
Ve sonra bunu tekrar end-- için, j n eksi 1, ve sonra j ++ daha az.
ANDI PENG: Büyük.
>> Ve sonra burada, bizim istediğimiz gidiyoruz Bizim koşul karşılandığında olup olmadığını görmek için kontrol etmek,
sağ?
İstediğiniz Çünkü minimum değeri değiştirmek
o aslında daha küçük olursa neler Eğer doğru, karşılaştırarak, değil mi?
Peki biz burada istiyorum yapacaksın?
Görmek için kontrol edin.
Deyimi ne tür Muhtemelen gidiyoruz
ti kullanmak istediğiniz biz şeyi kontrol etmek istiyor?
>> HEDEF KİTLE: Bir deyimi ise.
>> ANDI PENG: Bir if ifadesi.
Yani ve-- ve olacak ne İçeri istiyoruz durum
Bizim ise ifadenin?
>> HEDEF KİTLE: Eğer j değeri ben- değerinden daha azdır
>> ANDI PENG: Kesinlikle.
Yani ve-- nedenle bu dizi "dizi" denir.
Büyük.
Bu neydi array-- Yani eğer?
Tekrar söyle.
>> İZLEYİCİ: dizi-j daha az ise Dizi-i, o zaman min değiştirmek istiyorsunuz.
Yani dk j olacaktır.
>> ANDI PENG: mantıklı mı?
TAMAM.
Ve şimdi burada, biz aslında Doğru, takas uygulamak istiyor?
Yani, derste, hatırlama David, o zaman O Şeyin ne takas çalışıyordu
bu-- portakal suyu ve milk--
>> HEDEF KİTLE: O Brüt.
>> ANDI PENG: Evet, bu tür brüt oldu.
Ama oldukça iyi kavram süresini gösteren.
Yani burada değerlerinin düşünüyorum.
Bir dizi var dakika, i bir dizi,
ya da biz burada takas çalışıyorlardı neyse.
Ve muhtemelen içine dökün olamaz Aynı anda birbirine doğru?
Bu yüzden neler olduğunu Burada oluşturmanız gerekir
Doğru değerleri takas etmek için?
>> HEDEF KİTLE: Geçici değişken.
>> ANDI PENG: Geçici değişken.
O yüzden int temp yapalım.
Bu bir iyi olurdu, bakın dur ki-- zaman o da neydi?
TAMAM.
Yani bu bir daha iyi olurdu Zaman değişken "temp." isim
O yüzden int temp yapalım.
Biz ne yapacağız Buraya eşit temp ayarlamak?
HEDEF KİTLE: Min?
ANDI PENG: Bu biraz zor.
Aslında sonunda önemli değil.
O ne önemi yok sırası takas tercih
sürece emin konum olarak sen Eğer takas şeyin takip.
>> HEDEF KİTLE: Bu dizi-i olabilir.
>> ANDI PENG: Evet, dizi-i yapalım.
Ve sonra bir sonraki çizgi ne kodun burada olmasını ister misin?
HEDEF KİTLE: dizi-i dizi-j eşittir.
ANDI PENG: Ve son olarak?
HEDEF KİTLE: dizi-j dizi-i eşittir.
HEDEF KİTLE: Ya dizi-j eşittir Dizi-temp-- veya geçici.
>> ANDI PENG: Tamam.
Yani bu çalışmasına izin ve görmek işe gidiyor eğer.
Nerede oluyor?
Oh, bu bir sorun.
Biz konum, hat 40, Bkz Dizi-j kullanmaya çalışıyorum?
Ama nerede sadece j mevcut mu?
>> HEDEF KİTLE: döngü içinde.
ANDI PENG: Doğru.
Peki ne yapmamız ihtiyacımız olacak?
>> HEDEF KİTLE: Şeyin dışına Define
HEDEF KİTLE: Evet, var sanırım Açıklamada, sağ ise başka kullanılır?
Yani böyle, eğer minimum-- tamam, düşüneyim.
>> ANDI PENG: Beyler, denemek bir göz Let en almaya
biz burada bir şey ne yapabiliriz ki bakın?
>> HEDEF KİTLE: Tamam.
Minimum eşit değildir Yani eğer en az ise j-- kadar hareketsiz ben-
o zaman biz takas olmazdı.
>> ANDI PENG: ben bu eşit mi?
Burada ne demek istiyorsun?
>> HEDEF KİTLE: Ya evet, eğer Asgari evet, eşit değildir i yapar.
ANDI PENG: Tamam.
Peki bizim sorunlar tür, çözer.
Ama bu yine de çözmez j beri j-- ne olur sorunu
bunun dışında mevcut değildir, ya Eğer biz onunla yapmak istiyorsun?
Dışarıda beyan?
Şimdi bu çalışan deneyelim.
Ah ah.
Bizim sıralama çalışmıyor.
>> Eğer, bizim ilk harfini görebileceğiniz gibi Dizi bu değerleri vardı.
Ve daha sonra o olmalı 1, 2, 3, 4, 5, 6, 7, 8, 9 olmuştur.
Çalışmıyor.
Ahh.
Biz ne yaptık?
HEDEF KİTLE: Debug.
ANDI PENG: Pekâlâ, bunu deneyebilirsiniz.
Biz hata.
Biraz uzaklaştırmak.
En Bizim kesme noktası ayarlamak edelim.
En da-- OK gidelim.
>> Biz zaten biliyoruz çünkü Yani bu çizgiler, 15 ile 22 arasındaki,
Ben yapıyorum, tüm çünkü working-- vardır sadece aracılığıyla ve printing-- yineleme
Devam edin ve bu atlayabilirsiniz.
Hattı 25 başlayalım.
Oop, bana bunu kurtulmak edelim.
>> HEDEF KİTLE: Yani kırılma noktası en hata ayıklama nerede başlar?
ANDI PENG: Ya durur.
HEDEF KİTLE: Ya durur.
ANDI PENG: Evet.
Birden fazla kesme noktalarını ayarlayabilir ve Sadece diğerine atlayabilir.
Ama bu durumda biz bilmiyoruz nerede hata oluyor.
Yani biz sadece istiyoruz yukarıdan aşağıya başlar.
Evet.
TAMAM.
>> Yani burada bu hat, biz adım atabilirsiniz.
Sen, burada görebilirsiniz Biz bir dizi var.
Bu değerler dizisinde olduğu.
Görüyor musun, ne kadar endeks 0, bu oh value-- tekabül
Ben yakınlaştırmak için denemek için gidiyorum.
Üzgünüm, gerçekten zor Dizi indeksi 0 see-- için,
biz 4 arasında bir değere sahiptir ve Daha sonra böyle devam eder vb.
Bizim yerel değişkenler var.
Şu anda ben eşittir Biz olmak istiyoruz 0.
>> Ve o yüzden atlama devam edelim.
Minimum 0'a eşittir hangi biz de olmak istiyoruz.
Ve sonra bizim ikinci girin Döngü, dizi-j dizi-i daha az ise,
hangi değildi.
Peki nasıl gördün o atlanır?
>> HEDEF KİTLE: Yani eğer gerekir Minimum tüm ki- gerektiği değil
döngüsü için ilk içinde olması?
ANDI PENG: Hayır, çünkü Hala test etmek istiyorum.
Her bir karşılaştırma yapmak istiyorum Zaman, bunun üzerinden çalıştırmak sonra bile.
Sadece bunu yapmak istemiyorum İlk Geçişkenliğin üzerinde.
Sen bunu yapmak istiyorum Yine her ek pas.
Yani kontrol etmek istiyorum içinde senin durum.
Yani biz sadece gidiyoruz Buradan çalışmaya devam.
Ben adamlar sana bir ipucu vereyim.
Bu gerçeği ile ilgisi yoktur o zaman Eğer, senin koşullu kontrol ediyoruz
Eğer kontrol değilsin Doğru indeksi için.
Yani şu an için kontrol ediyoruz j dizi dizini dizisi daha az
i indeksi.
Ama ne kadar yapıyorsun for döngüsü başlangıcı?
Eğer i eşit j ayarı değil misin?
>> Evet, bu yüzden biz aslında can Burada hata ayıklayıcı çıkın.
Yani bizim pseudocode bir göz atalım.
For-- biz gidiyoruz Ben 0 eşittir başlayacak.
Biz 1 n eksi kadar gidiyoruz.
Kontrol edelim, biz bu hakkı var mı?
Evet, bu doğru oldu.
>> O zaman burada içinde biz konum Minimum değer yaratmak için gidiyor
ve i, eşit olarak ayarlayın.
Biz bunu?
Evet, yaptım.
Şimdi bizim iç için döngü, biz konum j yapacağım ben n eksi 1 eşittir.
Biz bunu?
Nitekim, biz bunu yaptık.
>> Yani ancak, biz burada ne karşılaştırdığınız?
>> HEDEF KİTLE: j artı 1.
ANDI PENG: Kesinlikle.
Ve sonra ayarlamak istediğiniz gidiyoruz j artı 1 de eşit minimum.
Yani gerçekten çabuk geçti.
Siz anladınız mı neden j artı 1 var?
TAMAM.
>> Senin dizide, So aracılığıyla ilk geçiş,
senin for döngüsü, int i 0 eşittir, hadi izin ver
Bu henüz bir değişiklik olmamıştır varsayalım.
Biz tamamen, bir dizi var, Sadece dört ayrımı yapılmamış diğer unsurlar, değil mi?
Bu yüzden ben 0 eşit başlatmak istiyor.
Ve ben gidiyor sadece Bu döngü içinde çalışır.
Ve böylece ilk geçişte, biz gidiyoruz "min" adlı bir değişkeni başlatmak için
bu da, çünkü i eşittir Biz minimum değeri yoktur.
Yani hem 0'a eşit anda bu.
Ve sonra içinden gideceğiz.
Ve biz yine yineleme yapmak istiyorum.
Şimdi buldum bu ne bizim asgari Biz yineleme yapmak istiyorum, bir
o karşılaştırarak eğer tekrar sağa, görmek?
Yani j, burada, gidiyor Eşit i, 0 olan.
Ve sonra eğer dizi j artı ben, hangi daha az olarak, önümüzdeki bitti biridir
ne şimdiki asgari daha değer takas etmek istediğiniz vardır.
>> Yani sadece biz ettik diyelim 2, 5, 1, 8, olduğu gibi, var.
Şu anda, ben eşittir 0 ve j, 0 ile eşittir.
Ve bu bizim minimum değerdir.
Dizi-j Eğer artı ben-- biri eğer öyleyse biz bakıyoruz biri peşinde
, bir öncekinden daha büyüktür asgari olmaya gidiyor.
>> Yani burada biz 5 görüyoruz daha az değildir.
Yani 5 değil gidiyor.
Biz 1 sağ, 2'den az olduğunu görüyoruz?
Yani şimdi bizim minimum olduğunu biliyoruz 0, 1, 2, endeks değeri olacak.
Evet?
Ve sonra, buraya geldiğinizde Doğru değerleri takas edebilirsiniz.
>> Yani siz sadece j yapıyorduk zaman daha önce, sen bir de aradılar değil
ondan sonra.
Sen aradılar Aynı değer, hangi
Sadece bir şey yapmıyorum neden olduğunu.
Bu herkese mantıklı mı, Neden biz artı orada 1 gerekiyordu?
TAMAM.
Şimdi yapmak yoluyla Sadece çalışmasına izin Emin kod kalanı doğrudur.
Neden oluyor?
Ah, burada dk.
Biz yanlış bir değer karşılaştırarak bulundu.
Oh hayır.
>> Oh evet, burada biz yanı sıra yanlış değerler takas.
Biz i ve j bakarak çünkü.
Bunlar biz kontrol edildi olanlardır.
Biz aslında takas etmek istiyorum Asgari, mevcut asgari,
ne olursa olsun, bir dışındadır.
Ve siz aşağı gördüğünüz gibi Burada, biz sıralanmış bir dizi var.
Sadece yapmak zorunda Aslında o zaman
biz kontrol edildi Biz karşılaştırarak değerleri
Doğru değerlere bakarak değildi.
Aynı biri aradılar Burada, aslında takas değil.
Sen bir sonrakine bakmak zorunda ona ve sonra takas edebilirsiniz.
Yani bu tür buydu önce kodu adamcağız.
Ve ben burada yaptım herşey ayıklayıcı sizin için yapmış olabilir
Ben sadece bunu yaptım Yönetim Kurulu, daha kolay çünkü
çalışırken ziyade görmek için debugger yakınlaştırmak için.
Bu herkese mantıklı mı?
Güzel.
>> Pekala.
Biz bahsediyoruz taşıyabilirsiniz asimptotik gösterimi, hangi
demenin süslü bir yoludur bu tür tüm runtimes.
Yani derste, David biliyorum, runtimes değindi.
Ve o bütün formülü geçti ve runtimes nasıl hesaplanacağını.
Bu konuda hiçbir endişe.
Eğer gerçekten meraklı iseniz çalıştığını nasıl,
bölümünden sonra benimle konuşmak için çekinmeyin.
Biz üzerinden yürüyebilir Birlikte formülleri.
Ama hepinizin gerçekten var biliyorum n üzerinde 2 karesi olduğunu
n karesi ile aynı şeydir.
En çok sayıda Çünkü üs, çoğu yetişir.
Ve böylece bizim amaçlı, biz umurumda tüm
büyüyen bu dev sayıdır.
>> Peki en iyi durumda Seçim tür zamanı?
Eğer sahip gidiyoruz Bir listede yineleme
ve daha sonra üzerinden yineleme Bu listenin geri kalanı,
kaç kere Eğer, büyük ihtimalle gidiyor
by case-- bölgesindeki durum iyi, üzerinden çalıştırmak sorry--?
Belki daha iyi bir soru sormak, en kötü durum nedir
Seçim tür zamanı.
HEDEF KİTLE: n karesi.
ANDI PENG: Bu n sağ karesi oluyor.
Bu gibi Yani kolay bir yolu düşünmek, Eğer döngüler için iç içe iki tane var her zaman,
o n karesi alınacak gidiyor.
Sen çünkü sadece bir kez daha üzerinden çalışan,
geri gitmek zorunda etrafında ve bunun üzerinden çalıştırmak
bir kez daha, her değeri içinde.
Yani bu durumda, sen n koşuyoruz Zaman n, üzgünüm bu-- hangi karesi
n Zaman n, n karesi eşittir hangi.
>> Ve sıralama da biraz anlamda benzersiz
bu ise önemli değil değerler sırayla zaten.
Hala zaten üzerinden çalıştırmak için gidiyor.
Sadece bu 1, 2, 3, 4 oldu diyelim.
Ne olursa olsun o oldu olsun veya olmasın Sipariş, hala ile koştu olurdu
ve hala minimum değeri kontrol etti.
Bu yapmış olur çek aynı sayıda
her zaman, hatta eğer Aslında bir şey dokunmadı.
>> Böyle bir durumda Yani, en iyi ve en kötü çalışma zamanları, aslında eşdeğerdir.
Yani beklenen çalışma zamanı Seçim tür,
hangi biz sembolü ile tayin teta, teta, bu durumda,
Ayrıca n karesi olacaktır.
Bütün bunlar üç n karesi olacaktır.
Neden herkes açık mı Çalışma zamanı n karesi nedir?
>> Pekala.
Yani ben sadece hızlı bir şekilde çalıştırmak için gidiyorum türlü geri kalanında.
Algoritması kabarcık, hatırlamak sort--
Bu birincisi oldu Davut derste gitti.
Esasen, size adım Tüm liste üzerinden
ve seni swap-- Bir seferde ikisini karşılaştırın.
Ve bir daha büyük ise Senden sadece onları takas.
Bu büyük iseniz Yani, takas olur.
Ben burada resmi var.
>> Yani sadece 8, 6, 4, 2 vardı diyelim.
Sen 8 ve 6 karşılaştırmak istiyorsunuz.
Onları takas gerekiyordu.
Sen 8 ve 4 karşılaştırmak istiyorsunuz.
Onları takas gerekiyordu.
Eğer 8 takas varsa ve 2, onları da değiştirin.
Böyle bir anlamda Yani, gördüğünüz Uzun bir süre boyunca oynanan,
nasıl kabarcık değerleri tür için olduğu biter, bunu neden diyoruz
kabarcık sıralama.
>> Biz sadece yeniden aracılığıyla aday olacağını İkinci geçiş ve üçüncü geçiren,
ve bizim dördüncü pas.
Esasen, kabarcık sıralama sadece çalışır Artık swapları yapmazlar kadar.
Bu anlamda Yani, bu sadece bir Bunun için genel bir sözde kod.
Endişeye gerek yok, bunların hepsi online olacak.
Biz aslında bu üzerinde gitmek zorunda değilsiniz.
>> Biz sadece bir sayaç başlatılamıyor 0 başlar değişken.
Ve biz tüm dizi boyunca yineleme.
Ve bir değer eğer bu bu-- eğer bir değer, bu değerin daha büyüktür
Onları takas için gidiyoruz.
Ve sonra sadece sensin devam edecek.
Ve saymak için gidiyoruz.
Ve sadece yapmaya devam edeceğiz Bu sayaç yüksek olduğunda
anlamına gelir, 0, daha Her zaman takas var
Eğer gitmek istediğini biliyorum sırt ve tekrar kontrol edin.
Sen biliyorsun kadar kontrolünü tutmak istiyorum Bu artık takas gerekmez.
>> Yani iyi ve en kötü ne Olgu kabarcık sıralama için runtimes?
Ve hint-- bu aslında farklı anlamda seçim tür gelen
Bu iki cevaplar aynı olmadığını.
Içinde neler olacağını düşünün bir olgu zaten sıralama eğer.
Ve ne düşündüğünüzü o olsaydı ne olurdu
bunun içinde bu kriteri değildi.
Ve ne tür çalıştırabilirsiniz Bu yüzden aracılığıyla bu oluyor.
Ben, 30 gibi, sizi vereceğim saniyeden düşünmek.
>> TAMAM.
Herkes ne bir tahmin var mı kabarcık tür kötü durumda çalışma zamanı nedir?
Evet.
>> HEDEF KİTLE: Bu gibi n kat Would n eksi böyle 1 falan mı?
Gibi, çalışan her zaman, o tek takas az gibi, sadece var
ne olursa olsun o oldu.
>> ANDI'nin PENG: Evet, yani tamamen haklısın.
Ve bu iyi bir örnek aşağıdadır Bu sorunun cevabı aslında daha karmaşık oldu
birden biz vermek gerekir.
Bu yüzden ben run-- gidiyor Burada tüm bu silmek için gidiyoruz.
Herkes iyi mi?
Ben bu silebilir miyim?
TAMAM.
Sen n üzerinden çalıştırmak için gidiyoruz Zaman ilk kez, değil mi?
Ve onlar üzerinden çalıştırmak için gidiyoruz n eksi 1 ikinci kez, değil mi?
Ve sonra tutacaklar n madeni 2, vesaire, gidiyor.
David nerede bir konferans, bu yaptım Tüm bu değerleri toplasaydınız,
Eğer bir şeyi almak da-- Evet-- aslında sadece azaltan 2'ye üzerinde
n aşağı karesi.
Bir almak için gidiyoruz Orada garip kısmı.
Ve böylece sadece biliyorum n her zaman karesi
kesir önceliklidir.
Böylece bu durumda, en kötü Çalışma zamanı n karesi olacaktır.
O inen olsaydı Sipariş, seni düşünüyorum
Bir takas her zaman yapmak zorunda.
>> Potansiyel, ne olurdu, En iyi durumda çalışma zamanı?
Liste zaten olsaydı, diyelim sırayla, çalışma zamanı ne olurdu?
>> HEDEF KİTLE: n.
ANDI PENG: Tam, n var.
Ve neden n?
HEDEF KİTLE: Çünkü sen sadece Her bir kez kontrol etmek zorunda.
ANDI PENG: Kesinlikle.
Mümkün olan en iyi çalışma zamanında Yani Bu liste zaten olsaydı
sorted--, en 1, 2, 3 diyelim 4-- sen sadece aracılığıyla gitmek istiyorum, sen denetlemek
oh, hepsi başarmak, görecekti.
Ben takas yoktu.
Bitirdim.
Yani bu durumda, sadece n var: ya da adım sayısı sadece
İlk listede kontrol etmek vardı.
>> Ve sonra, şimdi vurmak Ekleme sıralama,
Algoritma bölmek için esasen Bir sıralı ve sıralanmamış kısmına.
Sonra, tek tek, sıralanmamış değerler
bunların uygun takılı Listenin başında pozisyonları.
>> Yani, örneğin, bir var 3 listesi, 5, 2, 6, 4 yeniden.
Biz şu anda olduğunu biliyorum ayıklanmamış biz sadece ettik çünkü
ona bakmaya başladı.
Biz bir göz atın ve biz biliyoruz İlk değer, doğru sıralanır?
Yalnızca bir dizi bakıyorsanız boyut, bir, sen o tür olduğunu biliyorum.
>> Öyleyse biz biliyoruz Diğer dört unsorted vardır.
Biz geçmesi ve biz bu değeri görüyoruz.
Hadi geri dönelim.
5 bu değeri görüyor musun?
Biz ona bir göz atın.
Biz 3 karşılaştırın.
Biz daha büyük olduğunu biliyorum 3, bu yüzden o sıralanmış olduğunu biliyorum.
Yani biz şimdi biliyoruz ki ilk iki sıralanır ve son üç değillerdir.
>> Biz 2 bakabilirsiniz.
Biz ilk 5 ile kontrol edin.
O 5 daha az mı?
O değil.
Yani biz aşağı seyir tutmak zorunda.
Sonra 3 kapalı 2 kontrol edin.
O daha az mı?
Hayır.
Yani 2 eklenecek olduğunu biliyorum ön içine 3 ve 5
hem dışarı itti gerekir.
6 ve 4 ile tekrar yapın.
Ve biz sadece, esasen kontrol tutmak biz sadece kontrol nerede, kontrol edin.
Ve bu sağ gelene kadar pozisyon, biz tür sadece
doğru pozisyonda takın, hangi onun adı nereden geldi olduğunu.
>> Yani bu sadece algoritma var, pseudocode başına, tür,
Biz uygulamak nasıl Bir ekleme sıralama.
Pseudocode burada.
Tüm çevrimiçi olduğunu.
Endişeye gerek yok siz iseniz Bu aşağı kopyalamaya çalışırken.
Yani bir kez daha, aynı sorum Ne iyi ve en kötü çalıştırıcıları olurdu
Ekleme sıralama için?
Bu son soruya çok benzer.
Ben, 30 gibi, sizi vereceğim saniye de bu konuda düşünmek için.
>> Herkes istiyor mu Tamam Bana kötü runtime ver?
Evet.
>> HEDEF KİTLE: n karesi.
>> ANDI PENG: Bu n karesi oluyor.
Ve neden n karesi edilir?
>> İZLEYİCİ: in Çünkü Ters sipariş var
bu-- hangi n kez geçmesi n
ANDI PENG: Evet, kesinlikle.
Kabarcık tür Yani aynı şey.
Bu liste ise azalan, sen
İlk kez kontrol etmek zorunda olacak.
Sonra her ek değer, sen
sahip oluyor karşı kontrol etmek Doğru her değeri?
Ve böylece tamamen, sen yapmak için gidiyoruz bir n pas kez başka n, pas hangi
n karesi edilir.
Ne iyi durumda olacak?
Evet.
>> İZLEYİCİ: n eksi 1 nedeniyle İlki zaten karesi edilir.
>> ANDI PENG: Yani, yakındır.
Bu sorunun cevabı aslında n.
Birincisi ise nedeniyle sıralanmış, onu actually-- olmayabilir
biz sadece lucked bu örnek, bu 2
En küçük sayı oldu.
Ama bu her zaman böyle olmayacak.
2 zaten başlangıçta sıralanır ise ama sen, bakmak ve burada 1 var
1 bunu çarpmak için gidiyor.
Ve sonuna kadar gidiyor yukarı neyse çarptı.
>> En iyi senaryo Yani aslında sadece n olacak.
Eğer varsa 1, 2, 3, 4, 5, 6, 7, 8, sen
ile koşacağız Bu listenin tamamını kez
herşey para cezası olmadığını görmek için kontrol etmek.
Çalışan herkes açık mı hem de seçim zamanları?
Ben gidiyorum biliyorum Bu gerçekten hızlı.
Ama biliyor musun, eğer biliyor genel kavramlar, sen iyi olmalıdır.
TAMAM.
Yani, tıpkı belki sizi vereceğim, Bir dakika sizin komşular konuşmak için
ne sadece bazı temel farklar
sıralar bu tipleri arasında.
Biz yakında gidersiniz.
HEDEF KİTLE: Tamam, evet.
ANDI PENG: Evet.
TAMAM.
Serin, en bir sınıf olarak yeniden bir araya edelim.
TAMAM.
Yani bu tür bir oldu anlamda açık uçlu soru
onlara verilen cevapların çok şey var.
Ve biz kısaca bazıları üzerine gidersiniz.
Ben sadece sizi almak istedim farklılaşmış düşünmeye
tür üç tip.
Ve ben de, büyük duydum ne tür birleştirme mu sorum?
Büyük soru, çünkü ne gelecek koruyorsun.
>> Yani tür birleştirme Bu fonksiyonlar tek tür
Çok farklı, diğer türlü gelen.
Siz see-- gibi David o demo yaptın
o bütün serin olduğu yerde birleştirme nasıl görme sesleri
sıralama sonsuz gibi, koştu Diğer iki tip daha hızlı?
TAMAM.
Yani birleştirme nedeni var sıralama bu uçurumu uygulayan
ve biz ettik kavramını fethetmek derste çok konuşulacak.
Biz çalışmak ister bu anlamda akıllı, sen bölmek zaman değil, daha
ve sorunları fethetmek ve onları kırmak aşağı ve sonra onları biraraya koymak
İyi şeyler hep olur.
>> Birleştirme yolu So sıralama esas işleri
bir böler olmasıdır yarısında sıralanmamış dizi.
Ve o diziler iki yarısını var.
Ve bu sadece bu iki yarıyı sıralar.
Bu sadece, ikiye bölünmesi tutar yarısı yarısında herşey sıralanır kadar
ve daha sonra ardışık Hepsini bir araya koyar.
>> Yani gerçekten soyut.
Yani bu pseudocode sadece bir parçasıdır.
Bu mantıklı mı o çalışıyor yolu?
Yani sadece bir var diyelim n elemanlı dizi, değil mi?
Burada n, 2 den az ise, geri dönebilir.
Bildiğiniz Çünkü varsa tek bir şey, o sıralanması gerekir.
Else, sol yarısını sıralamak, ve o zaman doğru yarısını sıralamak,
ve sonra birleştirme.
>> Bu gerçekten çok kolay görünüyor Yani, gerçekte, bu konuda düşünme var
Zor tür. Eğer gibisin Çünkü, iyi, bu tür bir kendi üzerine çalışıyor.
Sağ?
Bu kendi üzerine çalışıyor.
Yani bu anlamda, David dokundu sınıfta yineleme sırasında.
Ve bu kavram daha bahsedeceğiz.
Bu o, bu iki satır var Burada, aslında sadece program
Bunu söylüyorum, kendisini çalıştırmak için Farklı girişi ile.
Yani oldukça kendini çalıştırmak daha n elemanlarının tamamı,
Eğer içine yıkmak sol yarım ve sağ yarım
ve sonra tekrar çalıştırın.
>> Ve sonra biz, görsel ona bakacağız Ben görsel bir öğrenci olduğum için.
Bu benim için daha iyi çalışır.
Yani biz burada bir görsel örneğe bakacağız.
>> Altı takımından biz bir dizi var diyelim elementler, 3, 5, 2, 6, 4, 1, sıralanır.
Pekâlâ, bu sayfada çok şey var.
Siz bakabilirsiniz Yani eğer Burada ilk adım, 3, 5, 2, 6, 4, 1,
Eğer ikiye ayırabilirsiniz.
3, 5, 2, 6, 4, 1 vardır.
Bu sizi aren't-- biliyorum Onlar sıralanmış veya değil bilmiyorum,
böylece yarısında, onları parçalayarak tutmak, devre, devre sonunda kadar
Eğer sadece bir eleman var.
Ve bir unsur her zaman doğru, sıralanır?
>> Yani biz biliyoruz ki 3, 5, 2, 4, 6, 1, kendileri tarafından, sıralanır.
Ve şimdi biz onları birlikte tekrar koyabilirsiniz.
Yani biz 3, 5 biliyoruz.
Biz birlikte bu koymak.
Biz sıralı olduğunu biliyoruz.
Hala orada 2 kullanıcısının.
Birlikte 4 ve 6 koyabilirsiniz.
Biz, bu sıralanmış olduğunu biliyorum bu yüzden bir araya koymak.
Ve 1 var.
>> Ve sonra sadece bakmak Burada bu iki yarısı.
3, 5, 2, 2, 3, 5 sahiptir.
Sadece karşılaştırabilirsiniz Her şeyin başında.
Bu sıralanır Çünkü biliyoruz ki ve bu sıralanmış olduğunu biliyorum.
O zaman bile gerek yok 5 karşılaştırmak, sadece 3 karşılaştırın.
Ve 2 bu nedenle, 3'den daha düşük bir Eğer 2 sonunda gitmek gerekir biliyorum.
>> Oradaki aynı şey.
1 Buraya gitmek gerekir.
Gittiğiniz zaman Ve sonra koymak Birlikte bu iki değer,
Bu sıralanır biliyoruz ve Bunu sıralanır biliyoruz.
O zaman 1 ve 2, 1, 2'den küçük olduğunda.
Yani 1 söyler Bu ucunda gitmeli
Hatta 3 ya da 5 bakmadan.
Ve sonra 4'e, sadece can Burada doğru gidiyor, kontrol edin.
Sen 5 bakmak zorunda değilsiniz.
6 ile aynı şey.
Bilirsin 6-- sadece bu bakılması gerek yoktur.
>> Ve böylece bu şekilde, sen Sadece kendini kurtaran
adımları çok size karşılaştırarak yaparken.
Her karşılaştırmak zorunda değilsiniz diğer elementlerin karşı element.
Sadece olanları karşılaştırmak Eğer karşı karşılaştırmak gerekir.
Yani soyut bir kavram türüdür.
Endişeye gerek yok öyle değil eğer çok doğru henüz size isabet.
Ama genelde, bu nasıl bir birleştirme tür çalışır.
Sorular, hızlı soru, Ben geçmeden önce?
Evet.
>> HEDEF KİTLE: Yani sizi söyledi 1 ve 4 ve 6
ve koyun.
Böylece those-- değildir değildir Eğer onlara bakarak
değil bütün olarak ayrı unsurları olarak?
ANDI PENG: Evet.
Peki ne oluyor Bunu temelde
yepyeni bir dizi yaratıyor.
Yani, burada, ben olduğunu biliyorum büyüklüğü 3 iki dizileri, değil mi?
Yani biliyorum benim sıralı dizi Altı unsurları olması gerekir.
Yani sadece bir oluşturmak yeni bellek miktarı.
Yani bir tür gibisin bellek savurgan olma
ama bu önemli değil çok küçük olduğu için.
Yani 1 bakmak ve 2 bak.
Ve sen 1 2'den az olduğunu biliyorum.
Yani 1 gitmek gerektiğini biliyorum tüm bu başlangıcı.
>> Hatta gerek yok 3 ve 5 bak.
Yani 1 gidiyor biliyorum.
Sonra temelde 1 kesmek.
Bu bizim için ölü gibi, var.
Sonra biz sadece 2 var, 3, 5, ve daha sonra 4 ile 6.
Ve sonra, seni biliyor Karşılaştırmak 4 ve 2,
oh, 2 oraya gitmeli.
Yani 2 aşağı plop, bunu kesmek.
Yani o zaman sadece 3 var ve 4 ve 6 5.
Ve sen sadece onu doğrama tutmak dizinin koyun kadar.
>> HEDEF KİTLE: Yani sadece zaman konum [duyulamaz] karşılaştıran?
>> ANDI PENG: Kesinlikle.
Yani bu anlamda, sen Sadece karşılaştırma esas olarak
Diğer sayıda karşı bir numara.
Ve biliyorum çünkü o, seni olarak sıralanmış olduğunu
bakmak zorunda değilsiniz tüm numaraları.
Sadece İlki bakmak zorunda.
Ve sonra sadece plop olabilir Onları aşağı, bilirsin çünkü
ait oldukları gereken yere ait oldukları.
Evet.
İyi soru.
>> Ve sonra sizin varsa Biraz iddialı,
Bu kod bakmak için çekinmeyin.
Bu aslında Fiziksel uygulanması
Biz birleştirme sıralama yazardı nasıl.
Ve bunu çok kısa olduğunu görebilirsiniz.
Arkasında Ama fikirleri oldukça karmaşıktır.
Yani bu dışarı çizim gibi hissediyorum Ödevini bu gece, çekinmeyin.
>> TAMAM.
Yani David de konuşmasında bu gitti.
En iyi durumda nelerdir çalıştırıcıları, en kötü durum runtimes,
ve birleştirme tür beklenen runtimes?
Birkaç saniye düşünmek.
Bu oldukça zor, ancak tür Bu konuda sezgisel düşünüyorsanız.
Pekala.
>> HEDEF KİTLE: En kötü durum n log n mı?
ANDI PENG: Kesinlikle.
Ve neden n log n olduğunu.
>> HEDEF KİTLE: Öyle değil mi çünkü o katlanarak hızlı olur
bu yüzden o bir fonksiyonu gibi yerine sadece basit n olma
karesi ya da bir şey?
ANDI PENG: Kesinlikle.
Peki nedeni Bu konuda çalışma zamanı n log
sen ne çünkü-- n Bu adımların hepsi yapıyorsun?
Sen sadece sağ, ikiye kesme değil mi?
Ve böylece biz yapıyoruz o yapıyor bütün bu log
yarısında bir sorun bölünmesi olduğunu, yarısında, yarısında, daha fazla devrede.
Ve bu anlamda, ne tür can Doğrusal modelini ortadan
biz kullanıyorum.
Eğer doğrayın zaman Çünkü yarıda işler, bu bir günlük var.
Bu sadece matematiksel var Bunu temsil yolu.
>> Ve sonunda, sonunda, sen Sadece son bir pas içinden yapma
Doğru, sırayla hepsini koymak için?
Ve böylece sadece varsa bir şey kontrol o n var.
Ve böylece ne tür konum İkisi birlikte çarparak.
Eğer bu son var gibi Yani var n bir günlüğü ile buraya n adet kontrol
tam buraya.
Ve sen çarpın eğer Onları, bu n log var.
>> Ve böylece en iyi ve en kötü durumda Olgu ve tüm n log n beklendiği.
Başka bir tür gibi de var.
Bu seçim tür gibi Bunun anlamda
Ne önemli değil sizin Liste sadece gidiyor, bir
Aynı şeyi her zaman yapmak.
TAMAM.
Olsa bile, siz gördüğünüz gibi Biz n through-- gidince sıralar
karesi, çok verimli değil.
Ve hatta bu n günlük n En verimli değil.
Siz merak ediyorsanız, sıralama mekanizmaları var
they o kadar verimli ki Neredeyse esasen düz çalışma zamanında.
>> Bazı günlüğünü n 's var.
Bazı günlük günlüğü n 's var.
Biz onların üzerine dokunmayın Şu anda bu sınıfta.
Ama siz fikriniz yoksa, ne, google çekinmeyin
En verimli ayırma mekanizmaları.
Ben orada, bilmiyorum Bazı gerçekten komik olanlar,
da-- bazı gerçekten var insanlar yapmak komik olanları.
Ve acaba onlar Hiç düşündüm.
Bazı yedek varsa Yani, google Zaman üzerine, bazı komik yolları nelerdir
Bu gibi people-- verimli ways-- insanlar
türlü uygulamak mümkün olmuştur.
TAMAM.
Ve burada sadece kullanışlı küçük bir grafik var.
Ben, o sınav 0 evvel, hepiniz biliyoruz Odanızda muhtemelen çalışıyor olacak
Bu ezberlemek.
Yani sizin için orada güzel.
Sadece made-- mantık unutma Neden bu numaraları meydana bulundu.
Hep kayıp ediyorsanız, sadece yapmak emin türlü ne olduğunu biliyoruz.
Ve içinden çalıştırabilirsiniz kafanızda onları
neden bu anlamaya cevaplar bu cevaplar.
>> Pekala.
Yani biz taşımak için gidiyoruz Sonunda, arama için, üzerinde.
Çünkü sizin gibi kim pset okudum,
arama da bir parçasıdır Bu haftaki sorunu ayarlar.
Sen uygulamak istenir aramalarda iki tür.
Bir doğrusal arama ve tek bir ikili arama motorudur.
>> Yani doğrusal arama oldukça kolaydır.
Sadece elemanı aramak istediğiniz Eğer alırsanız bir listenin görmek için.
Sadece yineleme yapmak zorunda.
Ve bir şey eşitse, Sadece doğru, dönebilirsiniz?
Ama biz çoğu olduğumuzu bahsediyoruz ilgilenen
ikili arama, hangi haklı olduğunu bölmek ve fethetmek hangi mekanizma
Davut derste gösteren oldu.
>> Telefon rehberi örneği hatırla O kadar getiren tutar olduğunu,
o tür mücadele biri Geçtiğimiz yıl biraz
Eğer yarıda sorunu bölmek nerede, yarısında, yarısında, tekrar ve tekrar,
Eğer aradığınızı bulana kadar?
Ve sen var hem de bunun zamanı.
Ve gördüğünüz, bu kadar önemli ölçüde daha verimli
arama başka tür daha.
>> Bu yüzden hakkında gitmek yolu bir ikili arama uygulanması
, biz bir dizi olsaydı, endeksi 0 ila 6, yedi elemanları,
Biz haklıydın--, ortada bakabilirsiniz üzgünüm, bizim soru varsa birinci--
biz soru sormak istiyorum yapar Dizi, 7 öğe içeren
Açıkçası, insan olmak sahip olan ve Küçük bir dizi böyle, bizim için kolay
evet demek.
Ama yol bir ikili uygulamak Arama ortada bakmak olacaktır.
>> Biz endeksi 3 olduğunu biliyoruz Orta, çünkü biz
Yedi unsurlar olduğunu biliyoruz.
Ne 7 bölü 2?
Fazladan 1 olduğunu kesmek olabilir.
Sen ortasında 3 var.
Yani 7 eşit 3 dizi?
Bu doğru, değil mi?
Ama biz çeklerin birkaç yapabilirsiniz.
3 7 günden az ya da dizi 7'den büyük 3 dizi?
>> Ve biz daha az 7'den olduğunu biliyorum.
Yani bildiğimiz ah, o olmalı, o sol yarısında vermeye.
Biz olması gerektiğini biliyoruz Sağ yarısında, değil mi?
Yani biz sadece yarım dizi kesmek olabilir.
Biz bile gerek yok Artık bakmak.
Biz biliyoruz çünkü Bizim problem-- yarısı
Biz cevap olduğunu biliyoruz bizim sorunumuz sağ yarısı.
Yani biz şimdi o bak.
>> Yani şimdi biz bakmak geriye ne orta.
Bu endeks 5.
Biz yine aynı kontrol yapmak ve biz daha küçük olduğunu görüyoruz.
Yani biz bu sol için sabırsızlanıyoruz.
Ve sonra biz o çeki görüyoruz.
Dizi değeri de var 7 eşit endeksi 4?
İşte bu.
Bu yüzden, gerçek iade edebilirsiniz çünkü Bizim listede değer bulundu.
Ben geçti yol mu Herkese bu mantıklı?
TAMAM.
Ben gibi, belki sizi vereceğim üç, dört dakika anlamaya
nasıl bu pseudocode.
>> Yani bir yazmak istedim hayal döndürülen işlev olarak adlandırılan arama ()
Bir değer, bir Boolean değeri, Bu gibi doğruydu ya da false--
Bulduğunuz true değer, değil mi, eğer yanlış.
Ve sonra vardı değeri geçirilen bir
değerler, içine aradığını hangi array-- oh, ben kesinlikle koymak olduğunu
yanlış yerde olduğunu.
TAMAM.
Neyse ki olmalı değerlerin sağında olmuştur.
Sonra int n sayısı Bu dizideki elementlerin.
Nasıl hakkında çalışıyor gitmek bu sorunun pseudocode?
Sana gibileri vereceğim üç dakika bunu yapmak için.
Hayır, ben Sadece-- olduğunu düşünüyorum evet, sağ burada bir tane var.
İZLEYİCİ: I Can?
ANDI PENG: Evet, seni aldım.
Bu çalışma var mı?
Tamam iyi.
>> TAMAM.
Pekala çocuklar, biz konum bunu dizginlemek için gidiyor.
TAMAM.
Yani biz bu güzel var varsayıyorum İçinde n değerlerindeki küçük dizisi.
Ben çizgiler çizmek değil.
Ama biz hakkında nasıl gitmek Bu yazmaya çalışıyorum?
Herkes istiyor mu Bana ilk satırı ver?
Bana vermek istiyorsanız Bu pseudocode ilk satırı.
>> HEDEF KİTLE: [duyulamaz]
HEDEF KİTLE: Sen istersin through-- yineleme
HEDEF KİTLE: Sadece başka bir döngü için?
HEDEF KİTLE: --for.
>> ANDI PENG: Yani bu biraz zor.
İstediğiniz about-- düşünün Bu döngü çalışmaya devam etmek
Tekrar tekrar ne zamana kadar?
>> HEDEF KİTLE: [duyulamaz] kadar değeri, bu değere eşittir.
ANDI PENG: Kesinlikle.
Yani aslında sadece write-- olabilir biz daha fazla kolaylaştırabilirsiniz.
Biz sadece doğru, bir while döngüsü yapabilirim?
Yani sadece loop-- olabilir Biz bir süre olduğunu biliyorum.
Ama şu an için, ben gidiyorum Ne aracılığıyla - "döngü" demek?
Döngü ne until-- Bizim biten durumu?
Ben bunu duydum düşünüyorum.
Birinin bunu söylemek duydum.
>> HEDEF KİTLE: Değerler orta eşittir.
ANDI PENG: daha söyle.
Kadar Veya: İZLEYİCİ değeri aradığınız
Orta değer eşittir.
>> ANDI PENG: orada burada değil ne olur?
Ne eğer aradığınız değer Bu dizide aslında değil mi?
HEDEF KİTLE: Sen 1 dönmek.
>> ANDI PENG: Ama biz ne istiyoruz Biz bir durum varsa kadar döngü?
Evet.
>> HEDEF KİTLE: Sadece bir değer var Kadar?
ANDI PENG: You can döngü until-- öylesine sen olduğunu biliyorum
Doğru, maksimum değere sahip olacak?
Ve sen gidiyoruz biliyorum sağ dk değeri var mı?
Ayrıca, bu şey, çünkü Ben, daha önce söylemeyi unuttum
olduğunu şey İkili arama hakkında kritik
diziniz zaten sıralanmış olmasıdır.
Yapmanın yolu yok çünkü Bu onlar sadece rastgele değerler iseniz.
Biri olmadığını bilmiyorum diğerinden daha büyük, değil mi?
>> Yani biliyorum senin max ve senin dakika sağ, burada?
Eğer ayar için gidiyoruz senin dakika ve mid-- içinde max
Sadece varsayalım senin orta değeri doğru var-- olduğunu
temelde gidiyoruz döngü minimum kadar
Doğru, senin max ile aynı ya da yaklaşık senin max senin dakika aynı değilse.
Sağ?
Bu olduğu zaman çünkü, bunu biliyorsun sonunda aynı değeri isabet ettik.
Yani min kadar döngü istiyorum , daha az ya da eşit olduğu aşağıdaki amaçlara hop
olmayan eşit ya da daha az, max Etrafta başka yoludur.
>> Mantıklı mı?
O hakkı elde etmek için bir kaç denemeden aldı.
Ama döngü senin max değeri kadar esas olarak hemen hemen daha azdır
veya daha da az eşit değil mi?
Bildiğiniz o zaman Eğer yakınsama ettik.
HEDEF KİTLE: Ne zaman olur maksimum değer minimum daha az olması?
ANDI PENG: Eğer tutarsanız , ayarlayarak hangi
biz gidiyoruz ne bu yapıyor olması.
bu mantıklı mı?
Asgari ve azami sadece vardır biz muhtemelen tamsayılar
istediğiniz devam etmek oluşturmak için Biz arıyoruz nerede iz.
Dizi varolduğundan ne olursa olsun biz yapıyoruz ne.
Gibi, biz aslında fiziksel değiliz Doğru, dizinin kapalı doğrama?
Biz sadece ayar ediyoruz nerede arıyoruz.
bu mantıklı mı?
>> HEDEF KİTLE: Evet.
>> ANDI PENG: Tamam.
Bizim için döngü koşulu ise Yani, Bu döngü içinde ne istiyorsun?
Ne yapmak isteyen olacak?
Yani şimdi, elimizdeki maksimum ve min, sağ,
Muhtemelen burada bir yerde yukarı yarattı.
Biz muhtemelen istediğiniz gidiyoruz Doğru bir orta bulmak?
Nasıl olacak orta bulmak mümkün?
Matematiksel-- neler var
HEDEF KİTLE: Max artı 2 bölü min.
ANDI PENG: Kesinlikle.
bu mantıklı mı?
Ve siz neden biz görüyorsunuz biz bunu neden sadece use-- vermedi
yerine yapmanın sadece n 2 bölü?
N değeri, çünkü bu Aynı kalmaya gidiyor.
Sağ?
Ama bizim en az ayarlamak gibi Maksimum değerler, onlar değiştirmek için gidiyoruz.
Sonuç olarak da, bizim orta Çok değişecek.
İstediğimiz İşte bu yüzden Burada bu hakkın yapmak.
TAMAM.
>> Ve sonra, şimdi biz evet our-- buldum.
>> HEDEF KİTLE: Sadece hızlı bir sorum ne zaman min ve max söylüyorlar,
biz varsayıyoruz Zaten sıralanmış oluyor?
>> ANDI PENG: Evet, bu aslında bir bir ikili arama için ön koşul,
Eğer varsa o olarak sıralanmış bilmek.
Bu yüzden sıralama Hangi, sen yazma senin Sorun ikili arama önce ayarlayın.
TAMAM.
Yani şimdi biz nerede bizim orta noktası biliyorum , burada ne yapmak istiyorsun nedir?
>> HEDEF KİTLE: Biz karşılaştırmak istediğiniz diğeri söyledi.
ANDI PENG: Kesinlikle.
Yani karşılaştırmak için gidiyoruz değerine orta, değil mi?
Ve bu ne anlatıyor bize karşılaştırmak?
Ne biz sonradan yapmak istiyorsun?
>> HEDEF KİTLE: değer büyükse orta yerine, biz bunu kesmek istiyorum.
ANDI PENG: Kesinlikle.
Değer büyükse yüzden orta yerine, biz konum
Bunları değiştirmek istediğiniz olacak Minimum ve maxes, değil mi?
Ne değiştirmek istiyorsun?
Bildiğimiz Yani değeri bir yerde Burada, biz değiştirmek için size ne?
Bizim değiştirmek istiyorum Minimum doğru, orta olmak?
Ve sonra başka, bu öyle ise Yarım, ne değiştirmek istiyorsun?
>> HEDEF KİTLE: Maksimum.
ANDI PENG: Evet.
Ve sonra sadece gidiyoruz Sağ döngü tutmak için?
Çünkü artık bir yineleme sonra aracılığıyla, burada max var.
Ve sonra bir orta yeniden hesaplayabilirsiniz.
Sonra da karşılaştırabilirsiniz.
Ve devam edeceksin dakika ve maxes kadar
esasen birbirine yaklaştı.
Bunu biliyor Ve o zaman bunun sonu isabet ettik.
Ve ya bunu buldum ya o noktada değil.
>> Bu herkese mantıklı mı?
TAMAM.
Bu, oldukça önemli Eğer gerekecek çünkü
kodunuzu bu gece bunu yazmak için.
Ama siz çok iyi olması Eğer ne yapmaları gerektiğini duygusu,
hangisi iyi.
TAMAM.
Yani biz yedi hakkında var dakika bölümüne ayrıldı.
Yani biz hakkında konuşmak için gidiyoruz biz yapıyor olacak bu pset.
Böylece pset iki yarıya ayrılmıştır.
İlk yarı gerektirir Bir find uygulanması
hangi doğrusal bir arama yazmak, ikili arama ve sıralama algoritması.
>> Yani bu ilk Bir pset nerede zaman
ne denir biz sizi vererek olacağım Dağıtım kodu, kodu
Biz ön yazdım, ama sadece kapalı bazı parçaları bıraktı
sizin için yazma bitirmek için.
Bu bak sen guys, So Kod, gerçekten korkuyor alabilirsiniz.
Eğer, ahh, ben tıpkı ediyorsanız Bu ne yaptığını bilmiyorum,
Ben gibi görünüyor, bilmiyorum çok karmaşık, ahh, rahatla.
Tamam.
Spec okuyun.
Spec tam size açıklayacaktır Bu programların hepsi ne yapıyorsun.
>> Örneğin, generate.c bir programdır senin pset ile gelecek.
Aslında dokunmak yok, ama yok Eğer ne yaptığını anlamak gerekir.
Ve generate.c, bu yapıyor hepsi bu Ya rastgele sayılar üreten
veya bir gibi bunu bir tohum verebilir onu alır danışıklı sayı,
ve daha numaraları üretir.
Yani belirli bir yolu var generate.c uygulanması hangi
Sadece bir sayı demet yapabilir Eğer başka yöntemler üzerinde test etmek için.
>> Yani eğer istedim, için örneğin sizin bulmak sınamak,
Eğer generate.c çalıştırmak isteyeyim, , sayılar bir demet oluşturur
ve sonra yardımcıları işlevi çalıştırın.
Sen nerede yardımcıları işlevi aslında fiziksel kod yazma.
Ve bir kütüphane dosyası olarak yardımcıları düşünüyorum O bulmak çağırıyor yazıyoruz.
Böylece helpers.c içinde, sen olacak arama ve sıralama yapın.
>> Ve sonra aslında gidiyoruz Sadece birlikte hepsini koyun.
Nasıl spec anlatacağım Komut satırında koymak.
Ve olmadığını test etmek mümkün olacak veya değil sıralama ve arama çalışıyoruz.
Güzel.
Herkes zaten başladı ve karşılaşılan sorunlar veya sorular
bu ile şu anda var mı?
TAMAM.
>> HEDEF KİTLE: Bekleyin.
Bir sorum var.
>> ANDI PENG: Evet.
>> İZLEYİCİ: Ben yapmaya başladı helpers.c lineer arama
ve gerçekten çalışma değildi.
Ama daha sonra, biz sadece öğrendim silmek ve ikili arama yapmak zorundayız.
Bu işe yaramazsa Yani bu önemli mi?
>> ANDI PENG: Kısa cevap hayır.
Ama beri Ben- konum
HEDEF KİTLE: Ama kimse Aslında kontrol.
ANDI PENG: Biz asla konum Bu göreceğiz.
Ama muhtemelen yapmak istiyorum emin arama çalışıyor.
Doğrusal Çünkü eğer arama çalışmıyor,
sonra şansını ikili vardır Arama yanı sıra işe gitmiyor.
Eğer benzer Çünkü her ikisi de mantık.
Ve hayır, gerçekten önemli değil.
Yani sadece onlar size döneceğiz sıralama ve ikili arama vardır.
Evet.
>> Ve ayrıca, çocuklar bir sürü vardı helpers.c derlemek için çalışıyor.
Aslında izin yok , bunu helpers.c çünkü
Bir ana fonksiyonu yoktur.
Ve böylece sadece gereken aslında derleme olmak
aramaları bulmak, çünkü üretmek ve bulmak helpers.c ve içindeki işlev görür.
Bu hata ayıklama yapar Yani popo bir ağrı.
Ama bu yapmamız gereken budur.
HEDEF KİTLE: Sadece Tamam, yapmak?
ANDI PENG: Sadece can evet, hem de tüm yapmak.
TAMAM.
Yani ne açısından bu kadar pset tüm yapmak istiyor.
Eğer herhangi bir sorunuz varsa, hissetmek bölümünden sonra bana sormak için ücretsiz.
Ben 20 dakika gibi, burada olacağım.
>> Ve evet, pset en Gerçekten o kadar kötü değil.
Sizler Tamam olmalıdır.
Bunlar, sadece yönergeleri izleyin.
Tür mantıklı bir duygusu var ne gerektiği gerçekleşiyor ve iyi olacak.
Çok Korkma.
Kod bir çok şey var zaten orada yazılı.
Eğer yapmazsam çok Korkma bütün bunlar ne anlama geldiğini anlamak.
Bir çok şey varsa, o tamamen iyi.
Ve çalışma saatleri geliyor.
Biz bir göz atın yardımcı olacağız.
>> HEDEF KİTLE: Ekstra ile fonksiyonları, biz o kadar görünüyorum?
>> ANDI'nin PENG: Evet, bu kod bulunmaktadır.
15 oyunun, yarım In o zaten sizin için yazılmış.
Yani bu fonksiyonlar Zaten kodu.
Evet.
Pekala.
Peki, iyi şanslar.
Bu iğrenç bir gün.
Yani umarım siz de hissetmiyorum içeride kalan ve kodlama kötü.