[Powered by Google Translate] [Həftə, 3 davamı]
>> [David J. Malan - Harvard Universiteti]
>> [Bu CS50 edir. - CS50.TV]
>> Bütün hüquqlar. Geri gəlmisiniz. Bu CS50 və bu həftə 3 sonu.
>> Belə ki, o tanımadığı, keçən il Harvard, İnnovasiya Lab deyirlər nə başlayıb
EBM-nin kampus çayı arasında bir gözəl bina olan və ya i-laboratoriya,
ki, kollec tələbələr, GSAS tələbələr, bütün daxilində kampus tələbələr, açıq
fakültə, o cümlədən və yenilikçi şeyi işləmək üçün bir araya gəlib bir yer var,
xüsusilə sahibkarlıq şeylər
Siz və 0 və ya daha dost sahibkarlıq bir şey bunu düşünür əgər
Bu sinif zamanı bu sinif sonra, və ya kənarda da.
>> Belə ki, onlar J müddət ərzində nə etdiklərindən biri, bu səfərlər edir
New York, Silicon Valley üçün olan biri olan biri.
Space çox məhduddur, lakin MBAs ilə təmasda imkan var
və kampus üzrə və faktiki aspirant bu müvafiq sahələrdə vaxt sərf
, startups qədər söhbət sahibkarlar qədər söhbət və s.
Maraqlı Belə ki, bu URL burada oldu.
O, həmçinin, online slaydlar mövcuddur.
>> Biz ton aşağı ev audio yalnız bir az Ola bilərmi?
Bu cümə nahar üçün bizə qoşulmaq istəyirsinizsə, Fire & Ice ilə 1:15 pm, orada rəhbərlik edin.
Əgər üzr şəklində artıq orada almaq zaman doldurulur.
Amma biz bu ənənə irəli davam edəcəyik.
>> Bu gün biz həll edə bilər ki, müxtəlif problemlərin daha yüksək səviyyədə müzakirəsi davam
ən azı, kodu və daha çox ideyaları bu gün çox az diqqət.
Belə ki, yarım bir telefon kitab cırdı zaman geri həftə 0 edirəm
olan obyektiv, bir şey etmək etiraf bir az dramatik oldu
lakin axtarış mütləq olmalıdır deyil nöqtəsinə göndərmək üçün
Sizcə bilər kimi ilk baxışda kimi Aşkar.
Ümumiyyətlə problem mütləq həmişə yaxşı ola bilər -
Ən bariz həll mütləq yaxşı ola bilər.
Belə ki, bu otaq bizim bütün instinktləri idi, səmimi, bu telefon kitab idi və
çox güman ki, sonra Mike Smith axtarır zaman ortada başlamaq və sol və ya sağ getmək
biz başa baş əlifbasının nə məktub əsaslanır.
>> Amma biz insanlar üçün qəbul ki, sadə ideya uzun verilir
həqiqətən fikrinizi önündə gəlməyə başlamaq lazımdır
problemlərin daha kompleks bir telefon kitab çox almaq kimi, çünki
həmin sadə, parlaq anlayışlar bizə imkan gedir nə
daha mürəkkəb və daha maraqlı problemləri həll etmək,
Bu gün artıq təmin üçün onların arasında bəzi şeyləri biz alırıq.
Hələ web orada pages, və Google və Bing və kimi milyardlarla
kimi, bizim üçün hər şeyi tapa bilərlər.
Yəni bütün mümkün web pages axtarış xətti axtarış istifadə edərək, baş deyil.
Facebook, bütün arkadaşlarınızla dost dost və ya kim sizə edə
və çox bu gün anında zahirən edilə bilər
onlar istifadəçilər milyonlarla olsa da.
>> Və biz, həqiqətən, o miqyaslı problemləri həll necə nəticədə azaldacaq
ideyalarına, biz bu gün bir az daha həftə 0 baxdı və.
Biz bu alqoritm yenidən həyata, lakin geri deyil biz də həftə 0 Bu exercise etdi
biz hər kəs ayağa olduğu, 1 nömrəli almaq
və biz birlikdə nömrələri əlavə, off cütləşmə ilə hər kəs özünü sayı olmuşdur
sonra dəstənin yarısı hər iteration haqqında oturdu.
Beləliklə, biz 500 tələbə 250 125 getdi və s.
Amma biz orada deyib kimi, güclü fikir
idi ki, biz bu problem həcmi iki dəfə əgər
Ədliyyə və ya ec 10 bütün uşaq otağa geri gəlib bizə qoşuldu
yaxşı, biz yəqin ki, bütün ümumi qrup saymaq bilər
loop yalnız 1 daha böyük iteration ilə yalnız bəlkə həcmini ikiqat çünki
və ya ikiqat ölçüdə bir az daha EC 10 işində.
Və biz bir az daha çox vaxt sərf etmək olardı
lakin biz 400 və ya 700 daha addımlar sərf olmazdı.
>> Bir az abstrakt ki, bir yol bu şəkil boya, gəlin hər kəs ayağa deyil bildirin.
Amma bu gün orkestr oturub seçən siz bu ağla olmasaydı, dayanan
biz yüksək şəxs olmayan, aranızda anlamaq bilər edək bax
müqayisəli alqoritm eyni cür etməklə.
Siz orkestr, mənim üzr istəyir, lakin addım 1 oturan etdiyiniz əgər, durmaq;
2 adımda, yaxın siz hər off cüt,
taller olan həyata rəqəm və siz qısa əgər oturub.
Sonra deyirəm.
[Tələbələri murmuring]
>> Okay.
Okay. Bir ayaqda qalıb. Sizin adınız nədir? >> Andrew.
>> Andrew, siz orkestr hissəsində hündür şəxs bu gün.
>> Tebrik edirik. [Alqış və təzahürat] Okay. Bir oturacaq var. Beləliklə, biz Andrew tapılmadı.
Amma nə qədər mənə etmişlər ki, məsələn, Andrew tapmaq
50 + və ya belə insanların bu orkestr bölməsində?
Mən kifayət qədər sadə yanaşma qəbul və burada başlamaq ola bilər.
Və mən 2 nəfər qalxmaq və yalnız müqayisə
və sonra mən bir az qısa kim demək, "Okay, siz aşağı oturmaq"
Mən taller şəxs olan yadda gedirəm.
Sonra təkrar təkrar təkrar, mən uzun adam üçün asmaq
Mən nöqtədə onlardan daha kimsə az taller tapmaq qədər
bu qədər qısa şəxs sonra oturub var.
Amma bu orkestr bölməsində ki, alqoritm, əgər, siz n var
etmək üçün gedən alqoritm neçə addımlar var? >> [Tələbə] N.
>> Bu, ən pis halda, belə danışmaq, çünki doğru, n almaq olacaq
Ən yüksək şəxs yalnız təsadüfi pis luck ilə almaq son şəxsdir.
Belə ki, ən pis halda ki, alqoritm çalışan zaman xətti, o, n var
n kosmik insanların ümumi sayı, problemin ölçüsü yerləşir.
Bu alqoritm haqqında nə?
Bütün siz yenə yarım sonra qalxıb ki, oturdu
Siz yarım oturdu, siz yarım oturdu.
Siz n burada var ki, əgər neçə addımlar lazımdır?
[Tələbə] N log n. Pis olardı. >> N olun.
>> Belə ki, çox logarithm nə xatırlamıram belə, daxil n
İndi, yalnız bu halving və halving və halving üçün elə bağlıdır ki, yüksək qiymətləndiririk.
2 bir amil yoxdur. Bu 3 amil ola bilər.
Amma bu problem ölçüsü burada başlayır ki, bu amil eyni cür bu təkrar var
lakin sonra dərhal sonra burada, burada, sonra sonra burada, burada gedir.
Siz problem kiçik sokması həyata alaraq deyilik, həqiqətən, ona üz Doğrama edirik
bir böyük ilə swoop hər dəfə azalıb.
Belə ki, biz, 12 ½ və ya 13 nəfər daimi, sonra sonra 25, 50 adam var idi
sonra nəhayət yalnız Andrew qaldı daimi qədər irəli 6 ½ və.
Beləliklə, biz n ki, log zəng olacaq, və bu aşağıdakı kimi görüntüləmək bilər.
Xətti alqoritm var qırmızı xətt kimi yerləşir, burada bu şəkil Xatırladaq
sarı xətt biz hesablanması tələbələr üçün istifadə 2s alqoritm tərəfindən hesablanması idi
keçmişdə, bu gün müqəddəs grail bu yaşıl xətt qalmağa davam edir
biz orkestr bölməsində insanların sayı iki dəfə və ya yalnız söylədi,
cəhənnəm, belə bir böyük iş, ayaq-nin bütün otaqda hər kəs yoxdur bildirin
biz təxminən burada necə bir çox insanlar ikiqat, çünki
1 daha iteration, bir problem.
>> Biz Andrew ya kim Andrew çox taller olmaq olur gördük
bu mezzanine və ya balkon edir.
Bir telefon kitab verilmiş biz çox etdi ki, bu sadə fikri Beləliklə,
biz bunu tətbiq edə bilər ki, bir çox müxtəlif yerlər var ki, bilirik.
Ilk həqiqətən çox jarqon - Just bəzi jarqon sillə üçün
Bu şəkil üçün bura gedək.
Hal-hazırda biz, n və n / 2 danışdı və sonra n daxil
biz dövr ərzində olacaq kimi deyil, biz, şübhəsiz ki, ilə gəlmək olar
riyazi düsturlar digər növ vaxt çalışan bu ümumi anlayışı təsvir etmək.
Uzun əvvəl biz görəcəksiniz çünki bu artıq kontekstində həyata
Bu həqiqətən təmsil alqoritmləri.
>> Amma burada qeyd xətti line n, düz xətt, hazırda işarə həqiqətən çox aşağıdır.
Yəni biz yalnız x axis təmsil nə dəyişdirmək ki, optik illüziya növ var
və y ox və biz istədiyiniz istiqamətdə bir düz xətt nöqtə edə bilərsiniz.
Amma indi zahirən düz olan səbəb
biz çox yavaş çalışan dəfə bu graph haqqında otaq etmək üçün lazım çünki edir.
İndi, həyat bəzi olduqca pis alqoritmlər var bilirik ki,
n addımlar daha çox daxil hələ yaxşı, n addımlar və ya olmayan bəziləri.
Belə ki, xətt yuxarıda n burada alt müddətdə n n dəfə log var
və biz bu əvvəl nə deməkdir görəcəksiniz.
Ki, yuxarıda kvadrat n, biz hələ heç n kvadrat alqoritmlər görmədim amma biz üzeresiniz.
Və həqiqətən, pis görünür.
2 da pis hiss edən exponential bir şey ki, n var.
Və hələ, maraqla, sonra irəlidə düşüncə cür edirsinizsə hansı n Cubed, var
Siz tipli n riyaziyyat, 2 əgər həqiqətən, çox straighter olur
siz uzaq kifayət qədər həyata baltalar baxsaq n çox qədər daha yüksək Cubed.
Belə ki, bu baltalar özbaşına x oxunda 2 10 indi görürük.
>> Və nə deməkdir?
Bu otaqda 2 nəfər üçün 10 nəfər deməkdir.
Problem ölçüsü, kontekstində nə ki: bütün x vasitələri var.
Və şaquli ox hazırda saniyə və ya addımlar sayı sayı -
vaxt bəzi vahid.
Lakin 0 60 0 10 olduğunu görürük.
Lakin əgər Excel və ya bir charting proqram güc kimi, zoom həyata biz növ
və biz bildiriş 200,000 qədər getmək ki, 2 kimi n bir şey
tamamilə kvadrat n çalışan dəfə qorxudaraq gedir
n Cubed, n log n - biz bu günə qədər haqqında söhbət etdik hər şey.
Facebook kimi şeylər haqqında danışmağa başlamaq zaman hələ tutmaq deyil
bir çox, bir çox, bir çox insanların bütün qarşılıqlı olduğu,
insanların n hər kimə n dost kimi çox ola bilər
hər kəs dünyada dost-dost növ edir, əgər
yaxşı ki, n dəfə var n artıq, belə kvadrat mümkün dostluq n ki,
ən azı 1 istiqamət, n kvadrat mümkün dostluq edir.
Belə ki, artıq belə danışmaq, Facebook sosial graph axtarış ki,
düsturlar bu cür ifadə etmək başlaya bilərsiniz.
>> Biz geri qayıtmaq və bu, daha konkret edəcəyik
növbəti çox həftə indi üçün, obyektiv
həyata alqoritmlər və kodu haqqında getmək üçün əmin olacaq
bu kimi bir şey kimi daha çox vaxt ayırdığınız qədər sonu.
Ancaq kompüter haqqında maraqlı şey bu sahədə davam əgər
, CS121, CS124 kimi dərsləri nəzəriyyə kursları edilir və bu alaraq,
Bu dünyada mövcud olan bəzi problemlər həqiqətən var ki
əsaslı qədər Bildiyimiz kimi, hər hansı bir sürətli həll edilə bilməz
Bu qrafik ən pis həqiqətən daha göstərir.
Belə insanlar indiyədək var daha yaxşı etmək üçün bu dünyada açıq problemlər bir çox var.
>> Beləliklə, bu nümunə sonra başlamaq edək.
Biz bütün çox yöndəmsiz video haqqında bu kamera ilə Sean mübarizə gördüm.
Sean bu sayı 7 kimi bir board tapmaq həvalə edilmişdir Lakin reallıq idi
Mən "bu kağız parçaları və ya ağ qapılar arxasında yerdə var, bildirib ki, geri
"Sayı 7. Sean, bizim üçün tapa bilərsiniz."
Və izləmək gözəl yöndəmsiz idi
o, həqiqətən bu problem ilə mübarizə idi.
Lakin reallıq Sean otaqda hər kəs həyata bilər kimi də etdilər idi.
O, ola bilər bir az artıq tipik şəxs-dən aldı
lakin o, bəzi oyun bu problem var idi ki, qəbul
o bir şey itkin ehtimal.
Və gözləri yüzlərlə ona aşağı daşıyan ki, kömək etmədi.
>> Problemin giriş təsadüfi ədəd bir dəstə əgər Lakin reallıq idi
və, 1 belə sıra tapmaq üçün xahiş edirik
Bunu ən yaxşı xətti axtarış edir.
Sol başlayın sağa hərəkət və ya sola hərəkət hüququ da başlanır.
Retroaktiv, biz düşünür ola bilər "Sean, niyə yalnız başqa sonunda başlamaq etmədi?"
Yaxşı, 7 kimi asanlıqla təsadüfi burada ola bilərdi
Mən o sonunda başlamaq niyyətindəyik deyil fiqurlu çünki mən qəsdən orada qoyun.
Mən cür vəziyyəti manipulyasiya, lakin təsadüfi şansı 7 yerdə ola bilərdi.
Belə ki, sağ sonundan başlayaraq, sonra daha yaxşı ola bilər
lakin nə, mən başqa yerlərdə 7 hərəkət gələn il?
Bu problem bir əsaslı yeni həll deyil -
1 sonunda və ya digər başlayaraq - Siz heç bir digər fərziyyələr verilmiş etdiyiniz zaman.
Belə Sean nömrələri vasitəsilə axtarır başladı və dedi "5. Yəni burada deyil."
Sonra o, burada getdi və 19 gördü, o, təxminən 20 saniyə üçün durdurulmuş
sonra 13 Bu açdı və o, müəyyən oldu
burada bir model olması üçün görünür deyil.
Bu 1, 2, 3, 4 və ya kimi deyil. Kömək olmayan sayda boşluqlar var idi.
Və çox, mən kağız bu ucuz ədəd istifadə etməsi nömrələri qədər əhatə
Çünki kağız bütün bu ədəd çıxarıldığı halda, faktiki olaraq qəsdən edir
Bizi ən çox, Sean daxil yəqin ki, sort macroscopically ilə baxırdılar olardı
bu yazı taxtası və "Oh, 7 orada açıq-aydın deyil." dedi Biz dərhal bunu etdi.
>> Və ki, insan beyninin müəyyən dərəcədə çalışır yolu ola bilər
lakin əslində, gözləri və ya ağıl, sağdan skimming nömrələri yəqin idi
həyata sağ, orta tərk - bir fizioloji davam edildi
dərhal baş verən kimi hiss ki, bu cür
lakin odds məcburi 7 tapmaq üçün metodologiya bir növ var idi hətta var.
And olsun ki, indi biz seriallarda və data strukturları söhbət edirik ki,
və kompüter yaddaş daxilində, biz insanlar yalnız şey edə
bir zamanda fərdi yaddaş yerlərdə 1 baxmaq edir.
>> Belə ki, hər yeri, habelə kağız bəzi parça ilə əhatə oluna bilər
biz hər halda bunu görmək bilməz. Biz yalnız bir zamanda 1 şey edə bilərsiniz.
Belə ki, bu halda, Sean işində, biz burada getdi və sonra biz burada getdi
və sonra biz burada getdi, burada, burada, burada sonunda ağıllı var
və yalnız cür özbaşına bu atlandı və 7 tapılmadı.
Bu xüsusilə deyildi. Bu çox üçün həyata idi.
Lakin o, nəhayət 7 tapılmadı.
Amma indi paket həqiqətən edə bilərsiniz ən yaxşı heç bir məlumat verilmişdir zaman ki,
təsadüfi sıralanır nömrələri başqa sol başlamaq və ya sağdan başlamaq üçün.
Və ya heck, siz təsadüfi qapılarını aça bilər, hətta sonra nə təsadüfi olmaq deməkdir?
Yaxşı, biz elə burada başlamaq üçün nə deməkdir rəsmiləşdirilməsi istiyorum
sonra burada getmək, sonra bura gedin. Sean böyük idi və bu izləmək üçün yalnız əyləncə idi.
Biz problem bir az dəyişdirmək və Siz bu il Sean yetişdirmək nə əvəzinə, əgər?
Hər kəs səhnəyə gələn və bir az fərqli problemin həlli rahat olacaq
və kamera görünmesini?
>> Uşaqlar olduqca bu gün artıq cəlb edilmişdir, çünki bu və orkestr kənara edək.
Necə haqqında çəhrayı, bu papaq mi? Aşağı Hadi. Sizin adınız nədir? >> Alex. >> Alex. Okay.
Belə ki, Alex bu il Sean olacaq və növbəti bir neçə il görünür
CS50 mühazirələr dəyər.
Alex, siz cavab gözəl. >> Çox cavab Nice.
Sizin üçün əl çağırış siz bir az daha asan var ki
ki, burada eyni nömrələr olunur deyirəm, amma indi sıralanır.
Belə ki, indi sizin məqsədi sayı 7 tapmaqdır.
Və həqiqətən, biz, həqiqətən bu olmalıdır - aldadıcı you're cür kompüter kimi ki, deyil,
nə baxaraq nömrələri bir an əvvəl idi.
Təbaşir bu əslində, bütün çox kömək etmək niyyətində deyil
ancaq orijinal array nə bilmirəm ki, iddia edək.
İndi bilirik Bütün sıralanır ədəd bir sıra var ki
onların arasında boşluqlar ola bilər və qol sayı 7 tapmaqdır.
Necə olan bir ağlabatan insan sayı 7 tapmağa getmək istəyirsiniz?
>> Yüksək aşağı getmək? Okay. >> Yüksək aşağı gedin.
Onların qoparmaq yoxdur. Biz onları yenidən istifadə edə bilərsiniz belə yalnız onlara ucaltmaq edək.
OK, belə 1. Gözləyin. Siz davam əvvəl, aydın yanlış 1 idi.
Belə ki, nə gələn fikrinizi keçir var? Növbəti addım nədir?
Növbəti biridir. Okay. >> Növbəti biridir. Yaxşı. Belə yanlış 3. Növbəti addım nədir?
Davam edin. >> Bütün hüququ. Davam edin. 5.
Belə davam saxlamaq və mənə posterity üçün bu əl bildirin.
7. >> Əla. Çox yaxşı. Sayı 7 tapıldı. [Alqış]
Belə ki, yaxşı idi, lakin Sean çox sayı 7 tapılmadı.
Mən, həqiqətən, məlumat bu əlavə parça istismar yoxdur ki, mübahisə
bu nömrələr sıralanır edir.
Belə ki, biz daha yaxşı edə bilər? Burada hər hansı təkliflər? Bəli, geri.
[Tələbə] Binary axtarış. >> Mən binar axtarış nə heç bir fikrim yoxdur.
>> [Tələbə] ortasında başlayın. >> Ortasında başlayın. Okay. Belə ki, biz orada edə bilərsiniz nin görək.
Siz ortalarından start duyum əvəzinə Belə ki, davam və orta qapı açır.
Onlardan 8 deyil, belə ki, özbaşına bir seçmək üçün olacaq
az sola və ya sağa. Okay. 7! [Alqış] Çox gözəl.
OK, lakin biz bu yerləşir gedirdi?
Gəlin yalnız burada başladı tie break Güman
eyni dərəcədə həm baş bilərdi çünki.
Biz yalnız 7 olduğunu bilmək oldu. Beləliklə, bu 13.
Onlar çeşidlənir və əgər Beləliklə, biz yalnız orta başlayıb
optimal növbəti addım nə olardı?
Sol gedin. Və burada yenə telefon kitab Məsələn gəlir.
13 buradadır və biz siyahısına çeşidlənir bilirsinizsə,
sonra kağız bu ədəd bütün indi bizim üçün maraqsız edir
Biz artıq 7-sol olmalıdır bilirik ki, çünki
bu rəqəmlər sıralanır və biz 13 aşkar edildikdə.
>> Belə ki, burada sizin növbəti hərəkət nədir? >> Sola dön. >> Okay yaxşı.
Hey, hey, hey, gözləmək - Belə sola getmək, və. Bu aldadıcı edir.
Belə ki, 7 aşkar, lakin biz yalnız tətbiq alqoritm nə idi?
Ortada başlayın. >> Yaxşı. Belə ki, eyni fikri məntiqi məsləhət var?
Oh, yalnız bu üçün. Məhz >>. >> Mən burada başlayır. >> Yaxşı.
Belə ki, indi biz daha sola qədər getdi. 3 var.
Lakin maraqlı paket indi sizin qayğı var olmayan var?
Bu 2. >> Bu 2. Belə ki, indi bu bir getmək bilər, bu getmək bilər.
İndi 8 idi ki, problem ölçüsü 4 indi ölçüsü 2 edilib.
Biz olduqca yaxın əldə edirik. Yenə bu 2 elementləri orta gedin.
>> Okay. Belə ki, biz aşağı yuvarlaqlaşdırma istəyirik, çünki indi biz həmişə sol olacaq ki, növ uğursuz var.
İndi biz yalnız 7 bizə tərk, üz və başqa hər şey bu atmaq çünki Lakin gözəl var.
Nin alqış dəyirmi verim. Biz 7 tapılmadı. [Alqış] Okay. Əmin olun.
Yalnız 1 daha ikinci Bekle.
Ki, növbəti proses cür biz bu ki, hiss bir az uzun çəkdi, baxmayaraq
səmimi, ilk instinktlərdən doğru, ən yaxşı idi? Biz dərhal 7 tapılmadı.
Amma biz daha sürətli, daha bu qarşı olursa bu misal nə, 7 aşkar olardı
nömrələr bütün sıralanır əgər çünki çox bir telefon kitab pages kimi,
siz həqiqətən təkrar və yenidən problem yarısında həyata doğramaq bilər.
Və yalnız 8 nömrələri ilə görmək olduqca kimi asan deyil
kimi həqiqətən əyani görmək bir 1000-səhifə telefon kitab qarşı,
amma burada bu halda Sean, 7 üçün axtarış zaman
necə çox pis halda addımlar onu qəbul edərdiniz? >> [Tələbə] 7.
Ən pis halda 7. Yaxşı, ən pis halda heç 7 8 qapı burada var əgər.
Onun 8 addımlar olardı.
>> Belə ki, var n qapılar, əgər bir neçə il əvvəl n addımlar Sean qəbul ola bilər.
İndi halda, bu rəqəmlər ayrılır ki, Alex, verilmiş -
və biz bu hekayə belə uzaq olduğunuz yerdən çıxarmaq bu cür edə bilər -
Alex daha ağıllı alqoritm çalışan zaman nə
ortalarından başlayan və sonra təkrar?
[Tələbə] 3. >> Belə ki, siz 2-1-8-4-dən getmək əgər, təxminən, 3 olacaq.
3 addımlar Belə və ya, ümumiyyətlə, o log n daha var.
Siz halving və halving və halving və halving etdiyiniz istənilən vaxt,
ki, log n bu fikir bir ifadə var.
Və belə ki, yalnız 3 addımlar ki, həqiqətən bunu
bir dəfə biz qapıları halving və halving açıldı
bu Sean təqribən 7 və ya 8 addımlar olardı halbuki.
Belə ki, bizə bu il olan üçün təşəkkür edirik. >> Təşəkkür edirik. Görüşdə siz gözəl.
Alex təşəkkür edirik. >> Eynilə. [Alqış]
>> Hansı sonra bu real dolayısı var?
İndi səmimi, bizim bütün bir şey tapmaq mümkün olan, 8 qapı, deyil ki, təsəvvür
yalnız kağız parçaları qoparmaq və instinktləri ilə gedən olduqca tez arxasında 8 qapı.
Amma bir milyon qapılar nə olur? Ne 4 milyard qapı olur?
4 milyard Qapı halda, siz, həqiqətən, Alex alqoritmi ilə getmək istəyirəm olacaq
biz bu zəng başlamaq və ya daha çox, ümumiyyətlə, bölmək və fəth olacaq kimi ikili axtarış
Siz problem halving və halving saxlamaq yerləşir,
siz 4 milyard qapı varsa, neçə dəfə yarım ildə 4 milyard doğramaq bilər, çünki?
[Tələbə] 32. >> Bu, faktiki 32 var. Siz bir kağız parçası və ya baş bu həyata işləyə bilər.
Siz 250 milyon, nöqtə, nöqtə, nöqtə üçün 4 milyard 2 milyard 1 milyard yarım milyard gedin.
Siz riyaziyyat həyata nə varsa, həqiqətən, 32 almaq olacaq
biz adətən 2 səlahiyyətlərinə saymaq çünki əslində kompüter aiddir.
2, 32, 4 milyard olur.
Belə ki, informatika 2 səlahiyyətləri bu cür uyğun bir çox var.
>> Amma nə 8 milyard haqqında? 8 milyard qapı olduqda neçə addımlar ki, iştirak edir?
[Tələbə] 33. Belə ki, 33 >>. Nə 16 milyard qapı var əgər? Neçə addımlar ki, iştirak edir?
[Tələbə] 34. >> 34. Biz növ bu reklamdan nauseam davam edə bilər. Amma güclü bir şey var.
Siz problem daha çox vəsait milyardlarla təqdim, lakin heç bir böyük olar
yalnız 1 əlavə bite çıxarmaq və beləliklə, bizə ikili axtarış kimi bir şey verir
və ya ümumiyyətlə, bölmək və qalib.
Amma hüququ, burada aldadıcı növü Ben?
Alex alqoritm halda, o, Sean üzərində bir üstünlüyü var idi.
O, bu rəqəmlər sıralanır ki, bilirdi, amma Alex onlara özü sıralama yoxdur.
Əvvəlcədən mən əmin və yazı taxtası və cür gəldi
Mən sıralanır üçün onlara bütün çəkdi, sonra kağız ilə əhatə etmişdir.
Amma ki, mənə nə qədər iş almaq idi?
Bəzi zahirən təsadüfi üçün bu nömrələri ilə off başladı varsa -
Bu halda bu sadə nömrələri, burada 8 vasitəsilə 1 -
biz bu dəyərlərə çeşidlənməsi haqqında necə getmək yoxdur?
Bu tapşırıq verilən insan olsaydı, intuitiv yanaşma nə cür siz edəcək
ədəd bütöv bir dəstə çeşidlənməsi üçün?
Bunlar puzzle ədəd kimi qoyulub. Bəli.
>> [Tələbə] Mən hər bir nömrə almaq və hər bir müqayisə ki,
və sola davam. >> Okay yaxşı.
Belə ki, yanındakı bir müqayisə, hər bir nömrə almaq
və sonra yalnız siz getmək kimi şeylər rejiggering vətəndaşların siyahısı cür boyunca hərəkət saxlamaq.
Belə ki, burada biz cəlb almaq üçün daha çox bəlkə bir neçə insanlar üçün bir şans var.
Biz gəlmək üçün sevgi istəyən 8 çox könüllü var?
Siz ildən bir az daha az təzyiq tək deyilik. 1, 2, 3, 4, 5, 6, 7, 8.
Aşağı Hadi. Siz uşaqlar 8 vasitəsilə ədəd 1 olacaq.
Biz əvvəlcədən bunu eyni şəkildə çox Alex bu çeşidlənməsi edə bilməz əgər in nəzər salaq.
1, 2, 3, 4.
Durmayın, siz ki, əgər burada musiqi stand və mənə arasında mərhələdə xətti
ekranda Slayd kimi eyni qaydada.
Ah-oh.
Biz növbəti misal sizi işləmək lazımdır. Oh, gözləyin, gözləyin. Burada getmək. Gözləyin.
Növbəti Məsələn indi. Burada getmək. Sayı 8. Qədər Hadi.
Bütün hüquqlar. Sort Buna görə özünüzü.
Musiqi tərəfində yalnız bir az sürüşdürərək burada durmaq.
Belə ki, 4, 2, 6 var - orada, burada, orada almaq - 3.
Bəli. Okay. Siz buraya gedin. Xeyr, siz orada qalmaq.
Bəli, doğru var. No səhv edirəm. Hüququ var. OK, çox yaxşı. Okay.
Belə ki, indi-nin artan qaydada onlara sort imkan verir.
>> Mən bunu edə bilərsiniz?
Bir an əvvəl təklif edilmişdir ki, alqoritm niyə biz yalnız müqayisə etməyin idi
sonra bir-birinin yanında növ və olan insanlar, hər hansı bir səhv fix
soldan sağa hərəkət.
Belə ki, burada biz açıq-aydın qırıq, 4 və 2 var. Sizə dəyişdirmək edək. Okay.
Belə ki, indi mən xətt aşağı hərəkət etmək üçün gedirəm. 4 və 6, nope. [Gülüş]
6 və 8, olduqca yaxşı. 8 və 1, mənə uşaqlar dəyişdirmək imkan verir. Bütün hüquqlar.
8 və 3 Beləliklə, uşaqlar dəyişdirmək.
8 və 7, mənə uşaqlar dəyişdirmək imkan verir. 5 və əla 8,.
Mən sizə bir sıralaması siyahısını göstərir.
Bütün hüquqlar. Belə ki, tamamilə.
Amma yaxşı çünki daha böyük nömrələr - hal nöqtəsi 8-ci ildə -
cür sağa sola ərzində bubbled var.
Mən sağ Onlardan 1 var, lakin kifayət qədər problemi həll etməyib bu kimi hiss edir.
>> Biz növbəti bunu nə təklif edərdiniz? >> [Tələbə] bunu edin. >> Biz bunu saxlamaq.
Və yenə reallaşdırmaq, biz yalnız bütün insanların malik şeyi qurmaq
növ ağıllı ki, şəkil əsasında özləri təşkil
indi biz daha çox metodiki olmalıdır.
Biz kodu yazıyoruz sanki bu barədə alqoritmik olmalıdır -
Bu halda şifahi pseudocode edir.
Mənə yalnız bir daha cəhd edək. Bu olduqca yaxşı işləyib. Bu həll etmədi.
Lakin şübhə zaman yalnız cəhd və yenidən cəhd edin. Belə ki, 2 və 4, artıq kömək etmədi.
4 və 6. Ah! Biraz daha yaxşı indi 6 və 1.
6 və yaxşı 3. 6 və 7, 7 və 5, 7 və 8 yaxşı.
O siyahısının sonunda deyil, çünki bilirsiniz, yəqin ki, artıq 8 iqnor edə bilər.
Bəlkə kimsə ona keçmiş gedən narahat yoxdur.
Amma bir təhlükəsiz ehtimal varsa nin görək.
İndi siyahısı - lənətləmək - sıralanır deyil. Nin daha cəhd edək.
2 Belə ki, 4, 4 və 1, 4 və 3.
4 və 6, yaxşı. 6 və 5, yaxşı.
6, 7, 8, yaxşı. Ancaq xəbərdarlıq, mən yalnız indi burada dayandırmaq və indi burada dayandırmaq olar?
[Tələbə] Bəli. >> Evet?
Nə biri orada bütün yol sayı 9 olsaydı?
Bu sıralanır olardı. >> Yaxşı. Bu ətrafında ilk dəfə sıralanır olardı.
Yaxşı. Beləliklə nin yenidən gedək. Biz demək olar ki, orada edirik.
1 və 2, 2 və 3, 3 və 4, 4, 5, 5, 6, 6 və 7, 7 və 8.
>> Indi görülən edirəm amma yenə Mən yalnız bunu deyib alıram nə edə bilər ki, bir kompüter deyiləm
və yalnız xatirə indi faktiki olaraq yalnız iş bir az idi ki.
Something burada dəyişdi.
Mən texniki vizual və ya algorithmically bu siyahı həqiqətən çeşidlənir təsdiq deyil.
Yalnız yaxşı tədbir üçün Belə ki, yalnız bu barədə anal olmaq, bu 1 dəfə daha nə edək.
1 Beləliklə, 2, 2 və 3, 3 və 4. Və nə bilirik?
Yalnız yaxşı tədbir üçün, mən tərəfdən bu dəfə takip gedirəm
Mən iş nə qədər yalnız, belə ki etmək neçə svopları Mən, həqiqətən etdik.
3 və 4, 4, 5, 5, 6, 6 və 7, 7 və 8. No svopları.
Belə ki, indi qanunla yenə bunu bir axmaq olardı
Çünki insanların bu keçid vasitəsilə heç bir iş əgər,
onların heç cür təsadüfi deyil, əgər aydın yenidən baş verəcək ki,
adversarially öz ətrafında hərəkət. Belə ki, indi mən dayandıra bilər.
İndi sual edək, bu, həqiqətən, mənə nə qədər iş almaq idi?
Necə bir çox addımlar idi? >> N kare.
Bəli, belə n kare. Siz haradan kvadrat almaq n var?
Siz hər num yoxlamaq var -
Yoxdur n nömrələri, və digər n nömrələri ilə hər sayı yoxlamaq lazımdır.
Yaxşı. >> Belə ki, kvadrat n edir. >> Yaxşı.
>> Belə ki, çox yaxşı, sağ kvadrat ola n bilər kimi hiss edir?
8 Bu halda, xüsusilə bu uşaqlar var n ki,
amma bu siyahı ilə getdi hər dəfə mən, ikinci qarşı ilk şəxs müqayisə edilmişdir
, təkrar yenidən üçüncü qarşı ikinci və
və mən sonunda əldə zaman, mən nə idi? Mən bunu redid.
Biz bu izahat ümumiləşdirmək Belə ki, biz insanların n
və mən, əlbəttə ki, 8 addımlar n addımlar, bu alqoritm vasitəsilə getmək hər zaman qəbul edirəm.
Amma necə çox pis halda dəfə Mən bu siyahı ilə getmək lazımdır?
[Tələbə] N dəfə. >> Yəqin ki, n, sağa, çünki ən pis halda,
nə yəqin ki, get-getmək bu uşaqlar ən pis halda razılaşma var?
Onlar tamamilə qaydada ləğv edirsinizsə
çünki yalnız əqli let's Güman - adın nədir? >> Bowen.
Bowen. Okay. Belə ki, yalnız bir an üçün artıq burada gəlib Bowen.
>> , Bowen alqoritmi əvvəlində burada olduğunu düşünək
və biz bu alqoritmi görə, burada hər kəs nə bilirik, lakin Bowen yoxdur -
və yalnız mənə cövlan etmək istəyirsinizsə - o ətrafında ilk dəfə olduğu kimi, bubble qədər gedir,
sonuna bütün yol.
Amma Bowen yanındakı adam sayı 7 idi ki, nəzərdə tutur.
Mən geri getmək və geri burada bütün yol getmək deməkdir sayı 7, almaq lazımdır.
İndi sayı 7 olan şəxs ilə həmin stroll var.
Ancaq 6 saylı həmçinin onun yanında idi sonra əgər nə?
Sonra geri getmək və 6 almaq lazımdır.
Belə ki, yenə bu loop hər iteration haqqında Mən n insanların hər söhbət alıram
və mən çəkərək alıram əmin olun bu students N etmək ola bilər
geri geri geri siyahısı çox sonunda ən böyük bütün öğeleri.
Belə n şeyi n dəfə yalnız n dəfə n və ya n kvadrat edir.
>> Belə ki, burada artıq biz artıq log n ki, artıq ki, bir alqoritm n, var,
biz əvvəl etdiyiniz şey, həqiqətən, pis.
Belə Alex cür, mən iş onun üçün yəqin qədər ön bütün etdilər ki, xoşbəxt var
bu ikili axtarış alqoritmi ilə zövq bilər ki, bahalı bütün işləri,
n log olan.
Amma bu ertəsi mövzusu ilə uyğundur.
Biz çalışan zaman sürətləndirmək üçün daha çox bit istifadə, bir az daha çox yer verdi.
Belə ki, çox zaman və məkan arasında ticarət-off var kimi,
vaxt getmək şeyi hazır əldə qarşısında cür işlərin arasında yalnız kompromislər ola bilər
və həqiqətən axtarış kimi bir alqoritm həyata. Nin başqa bir cəhd edək.
Uşaqlar yalnız tez rearranging ağla Əgər özünüzü daha uyğun
olduqca sadə kimi olduğu qədər fərqli bir cəhd edək
super intuitiv olan bütün pairwise səhvlər, yalnız düzeltmek kimi.
Nin yerinə bir az daha qəsdən və bunu edək.
Çox mən təklif edirəm Bu yəqin ki, olduqca asan.
>> Təkrar siyahıdan kiçik adam seçin edək. Belə ki, burada biz gedin.
4, mən bununla belə uzaq gördüm kiçik adam var
mən ruhi yalnız indi sizə işarə edərək, unutmayın ki, gedirəm.
2. Ooh! Sayı 4 Unut. Mən yalnız bu siyahıda yeni kiçik element tapılmadı.
I növ unutmayın gedirəm. 6, 8.
Ooh! 1. Goodbye. Belə ki, indi sayı 1 yadda gedirəm.
Biz 1 kiçik olduğunu bilirik, lakin mən kompüter edirəm. Nə 0 varsa?
Nə -1 var əgər? Mən davam etmək lazımdır.
Belə ki, 3, 7, 5, nope. Okay. Belə ki, 1 saylı kiçik idi.
Mənə siyahıdan seçdiyiniz edək - we'll bu yolla getmək -
və siyahıdan əvvəlində özbaşına sizi.
İndi, bir dəqiqə gözləyin. Cheated I növ.
Bu uşaqlar deyil 8 nəfər bir siyahısını lakin bir sıra təmsil varsa,
Bitişik yaddaş 8 chunks - yalnız bir an geri gücləndirməklə ağla edirsiniz?
Burada sizin üçün heç bir yer həqiqətən var.
Belə ki, necə biz kosmik edə bilərəm - adın nədir? >> Sammy. >> Sammy.
Necə Sammy üçün yer edə bilərəm?
>> Biz məndən əvvəl olan n hərəkət. Okay. >>
Beləliklə, biz ondan əvvəl olan n insanların hərəkət edə
uşaqlar sola 1 qəsdən, dramatik addım istəyirəm əgər.
Onlar bütün uyum etdi, lakin son dəfə bir neçə kodu yazdı
Bütün bir dəfə bir çox şeyi hərəkət və sort bilməz.
Biz bir dəfə bir dəfə hər kəs hərəkət, bir loop bunu bilər.
Uşaqlar, sağ geri gücləndirməklə ağla deyil ki, əgər
və Sammy, sizin üçün heç bir otaq var, çünki siz geri addım bilər,
indi bunu edək. Harada Sammy bir an əvvəl idi? Hüququ var.
Belə ki, orada bir boşluq var. Belə ki, Sammy nin spot hərəkət edə bilər.
İndi növbəti şəxsə və indi artıq gələn şəxs, növbəti şəxs. İndi Sammy üçün otaq var.
Tamaşaçılar indi, bəziləri - yaxşı idi ki, düzgün idi ki,
bunu hiss vaxt aparan bir az - nə sürətli var? Bəli.
[Tələbə] yeni array? >> Nədir ki? >> [Tələbə] yeni array? >> Okay yaxşı.
>> Yalnız ticarət-off bu mövzu ilə Beləliklə, ardıcıl, niyə yalnız bir yeni array yoxdur
və sonra Sammy Məsələn, bu insanlar qarşısında yer üzgüçülük olunacaq
və biz yalnız tamamilə yeni bir sıra yanacaqdoldurma başlaya bilərsiniz. Bu çox iş olardı.
Ancaq mən bu gün daha çox yer sərf maraqlı deyiləm. Başqa yanaşma nədir?
[Tələbə] Swap. Okay. >> Biz yalnız bu 2 uşaqlar dəyişdirmək bilər. Sizin adınız nədir?
Mario. >> Mario. Mario Belə ki, hal-hazırda burada idi.
Sammy, yalnız bir an geri edə bilər? Mario burada idi.
Siz Sammy olduğu gedən ağla deyil ki, əgər biz, artıq sizin üçün otaq yoxdur
biz burada Sammy qoymaq lazımdır və indi Sammy nin dəyişdirmə əməliyyatı çox daha sürətli idi ki, mübahisə ediyorum.
Biz bu uşaqlar dəyişdirmək, və ya bəlkə 2 Bu uşaqlar dəyişdirmək üçün 1 əməliyyat etdi
lakin daha yaxşı hiss edir ki, 1, 2, 3, 4 etmədi. İndi, bir dəqiqə gözləyin.
Sayı 4 əvvəlinə yaxın cür idi, çünki mən cür problem pis etdi.
İndi sayı 4 Bu məqsədlə bir az daha yaxın, lakin mən, həqiqətən bilmək və ya qayğı etməyib.
Beləliklə, bu sayı 4 bir az uzaq onun nəzərdə yer edir ki, yalnız pis şans deyil.
Beləliklə, bu alqoritm təkrar indi edək.
>> Kimi uzun o hekayə idi, recap üçün bütün biz siyahısına vasitəsilə gəzmək oldu
kiçik saylı şəxs axtarır.
İndi yenə bunu edək. Biz artıq Sammy narahat yoxdur.
Biz yalnız burada edə bilərsiniz. Ooh! Sayı 2. Olduqca az sayda var.
6, 8, 4, 3, 7, 5. OK, yaxşı.
Və təşəkkürlə, təsadüf ilə mən hərəkət yoxdur - >> Willie.
Willie o indi sağ yer var çünki.
Yenə bunu edək və bu 2 uşaqlar bilməz.
6. Olduqca az sayda var. Ooh! 8 mütləq böyükdür.
4. 4 diqqət edək. Ooh! 3 hətta yaxşıdır.
7 və 5. Beləliklə, biz indi nə etməliyəm - >> Roger. >> Roger?
Nin 6 saylı onu dəyişdirmək edək.
Belə ki, 6 və 3 dəyişdirmək istəyirsinizsə,
İndi cür, o olmalıdır yerləşir yaxın olduğunu 6 uğurlu kazanılmış etdik
lakin burada yalnız təsadüf edir. Belə ki, indi burada gedək.
8 olduqca kiçik rəqəmdir. Ooh! 4 kiçik.
6, 7, 5. İndi nə etməliyəm? >> Swap. Məhz >>.
Belə ki, indi daha sürətli bu cür etmək edək.
8, 6, 7, 5. 5 hara edir? Yaxşı. Okay.
6, 7, 8. 6 o harada qalmaq olur. Sizin adınız nədir? >> Rosalie.
Rosalie o harada qalmaq olur. 7 olur - Bakalým. 7, 8. Okay.
Belə ki, 7 o harada qalmaq olur. Sizin adınız nədir? >> Amna. >> Amna.
>> Belə ki, Amna o harada qalmaq olur və o, indi harada sayı 8 olunur.
OK, yaxşı. Biz yalnız baxmayaraq, burada özümüz üçün iş oluşturuyorsanız kimi hiss edir.
Hansı nəticədə bu alqoritm çalışan vaxt var?
Biz 8 lakin n bu insanlar haqqında düşünüyorsanız? >> Bu n var.
Bu addımlar n edir, lakin biz hər bir zaman kontrol edirik.
Okay. N lakin hər dəfə kontrol edirik?
Bu addımlar n varsa OK, lakin, yalnız 1, 2, 3, 4 giderek size sort edə bilməzdi?
Oh! OK, böyük bir fərq var.
Belə n niyə kvadrat? Həqiqətən nə olub?
Bu siyahıda n insanlar, lakin siyahıda ən kiçik adam tapmaq
ən pis halda, nə qədər addımlar mənim üçün? >> N.
>> N, doğru, ən pis halda, sayı 1, orada bütün yol, çünki
Mən onu almaq və ya onun getmək üçün var.
Və sonra nəhayət 1 kiçik idi həyata zaman, onları dəyişdirmək olduqca sürətli deyil.
Amma indi başdan başlamaq və kim axtarmaq lazımdır?
2 olan növbəti kiçik adam. Ən pis halda 2 harada?
Aman Allah. Sonda onu da burada bütün yoludur.
İndi mən yalnız başqa n addımlar, bir n addımlar etdik.
Və biz n insanlar var və ən pis halda kiçik adam üz n addımlar varsa,
daha n dəfə n, və biz yenə kvadrat n.
Bu yaxşı hiss deyil.
Və əslində, hətta ən yaxşı halda - onlar off sıralanır başlamaq Güman -
Mənə bu n insanlar düzmək üçün bu alqoritmi istifadə üçün neçə addımlar edir?
N kare. >> Eşitdim n kare. N kare Niyə?
Siz hələ hər bir dəfə yoxlamaq var. >> Bəli.
Və onları dəyişdirmək lazımdır. Biz insanlar ələmə növü var >> baxmayaraq
mənada vizual biz bu çeşidlənir ki yalnız cür edə bilər ki,
kompüter ki, ağıllı deyil.
O, burada və burada və burada baxmaq olacaq
lakin nə axtaran kiçik element olarsa,
yalnız nə nöqtə ilə ən kiçik element aşkar bilirəm ki? Bir sonunda istəyirik.
Amma bu nöqtədə yalnız hazırda kiçik element gördük.
Siz mütləq dünya haqqında başqa bir şey bilmirəm.
Belə ki, təkrar və yenidən getmək üçün var.
>> Mən, tamam, 2 yoxlanılması edirəm, çünki mən həqiqətən bu dəfə lal baxmaq Belə ki, ən kiçik istəyirik,
lakin mən hələ ümumi ki, bilmirəm.
3, 4, 5, 6, 7, 8. OK, yaxşı. 2 həqiqətən kiçik idi.
İndi növbəti kiçik görər. Okay.
3, hazırda kiçik istəyirik. Bakalým. 4, 5, 6, 7, 8. OK, daha uğurlu var.
3 doğru yerdə həqiqətən idi. Amma yenə bunu və təkrar saxlamaq üçün gedirəm.
Necə heç belə biraz daha yaxşı edə bilər?
Əvəzində qədər pairwise kiçik olan böyük insanların bubble olan
əvəzinə, sonra kiçik adam seçilməsi siyahısını geri və irəli gedən,
niyə biz əvəzinə addım yeni siyahısını addım bu insanlar daxil deyil?
Bu cəhd edək. İndi mənə bu şey durub sırala zəng edək.
Belə ki, burada biz burada. Sayı 1. Mən bu siyahıda hər kəsdən qayğı yoxdur.
Mənim məqsədi hazırda bir sorted siyahısı əvvəlində sayı 1 qoymaq üçün.
Mən yalnız yaddaş 8 chunks çünki Mən təklif gedirəm
özbaşına İndi, mənim guya çeşidlənməmiş siyahısı arasında divar am
və mən iddia gedirəm mənə arxasında olan hər kəs çeşidlənir.
Belə ki, indi biz sayı 1 var.
Mən sıralanır siyahısı onu əlavə etmək istəyirəm, mən yalnız burada mənim divar hərəkət etmək gidiyorum belə
və indi bu siyahıya çeşidlənir iddia, bu siyahı çeşidlənməmiş edir - ən azı indiyə qədər mən bildiyiniz kimi.
Mən bir dəfə bütün nömrələri görmək bilməz.
>> İndi sayı 2 qarşılaşma baş verir. Mən onunla nə etməliyəm?
Mən sıralanır siyahısına İndi daxil edin. Amma ki, nə qədər asan bilərsiniz.
Mən sadəcə baxmaq lazımdır. Sayı 1 var. Oh, açıq-aydın 2 ədəd 1-yan gedir.
İndi 3-nə etməliyəm? Mən sıralanır siyahısına daxil etməzdən. Amma bu super asan idi.
Bu asan super, bu super asan, bu super asan, super asan, super asandır.
İndi hər şey mənə arxasında çeşidlənir və neçə addımlar idi?
[Tələbələri] N. >> Belə ki, yalnız n edir. Biz uğurlu var.
Yalnız n niyə oldu? >> [Tələbə] siyahısını sıralanır Çünki.
Siyahısı artıq çeşidlənir. Beləliklə, biz xoşbəxt var.
Amma biz bir alqoritm uğurlar belə çalışmalarını sürdürür ki, bu zaman nəzərdə
lazımsız vaxt israf deyil ki, ən yaxşı ssenari.
Beləliklə, biz indi bubble növ zəng lazımdır nə
Ü pairwise qədər bubble insanlar cür.
Biz təkrar kiçik adam yoluşdurmaq Biz indi seçim sort var.
Onların mənsub olduğu biz növ fəal insanlar qoymaq harada və indi biz durub sırala var
getdikcə sıralanır siyahısı.
Biz bilər, burada bu uşaqlar üçün alqış bir tur. [Alqış]
Nin Burada 5 dəqiqə fasilə etmək edək.
Və biz geri gələndə, biz su bu alqoritmlərin bütün əsəcək
yaxşı bir şey. Bütün hüquqlar. Çox təşəkkür edirik. Siz suvenirlər kimi bu davam edə bilərsiniz.
Bütün hüquqlar. Biz geri.
>> Və real sürətli recap, biz, çeşidlənməsi bu 3 müxtəlif yanaşmalar var idi
olan bütün point nöqtəsinə almaq üçün olduğu Alex kimi kimsə
Sean bilər kimi kimsə daha sürətli nömrə bir siyahısı axtarmaq bilər.
Biz 8 ədəd belə sadə nümunələri olsa da,
asanlıqla 8 web pages, 8 milyard web pages, extrapolate bilər
Facebook və ya 800 milyon dostlar.
Belə ki, bu alqoritmlərin əlbəttə, dəyərlər bu cür miqyaslı bilər
və fikir etibarilə eynidir.
Belə ki, bubble sırala biz cür böyük adam qədər bubbled olduğu ilk
pairwise insanların dəyişdirmə hüququ bütün yol.
Sonra yerləşir Mən bir az daha şüurlu biz seleksiya sort arayacaðým nə idi
yenə siyahısını axtarır təkrar kiçik sayı seçilməsi və saxlanılır
olan məntiqi nəticə siyahısını nəhayət sıralanır olunur.
Sonra üçüncü, mən, onların müvafiq yer insanları daxil
və biz siyahısına artıq sıralanır ki, bir çox göstərdi Məsələn etdi
ancaq mesaj göndərmək idi ki, durub sırala işində,
siz þanslý bilər.
Nömrələri artıq ayrılır, bu, yalnız daha çox təsdiq siz n addımlar olacaq
seleksiya sort isə bir az daha tunel görmə edirik
və siz heç siyahı artıq sıralanır ki, dərk etmirlər.
Belə ki, burada fəaliyyət bubble sırala bax edək.
Aşağıdakı Məsələn, biz şaquli bar görmək üzeresiniz
biz görüntüləmək baş çeşidlənməsi üzrə çeşidləyə bilərsiniz, belə ki, onun yüksəkliklərdə ədəd təşkil edir.
Bu kiçik bar, sayı kiçik; böyük bar, böyük sayı.
>> Və biz bu default sürətli oynamaq lazımdır.
İndi bir az sürətli hərəkət edəcək, ancaq qırmızı 2 bar göstərən nə edir
yan-yana müqayisədə olunur.
Siz yaxından izləmək varsa, nə olar ki, barlar üçün həyata, əgər
bir kiçik, sol sağ üçün böyük bir köçürülüb olur
və sonra irəli saxlamaq.
Biz təkrar bunu Belə ki, qeyd edir ki, kiçik bar
sol yol inching saxlamaq gedir
və ən böyük bar sağ yol inching saxlamaq niyyətindəyik.
And olsun ki, biz bir model sağ tərəfində bütün yol bax başlayaraq edirik
kimi biz 8 gördüm və sonra 7 nəticədə bizim insan siyahısı uzaq sonuna qədər burda.
Belə ki, bu çox tez bir az yorucu olacaq, belə ki, məni bir an bu dayandırmaq bildirin.
Mənə çox daha sürətli olmaq üçün sürətli dəyişiklik edək.
Mən alqoritm dəyişən deyiləm, mən yalnız animasiya sürətli baş qəbul edirəm.
Hələ bubble sırala eyni alqoritmi,
indi siz bizim şifahi nümayiş daha sürətli edə bilərsiniz
ən böyük elementləri həqiqətən üst qədər burda olunur.
>> Bir kənara, bu az aşağı sol meydan və sağ alt
siz yapýyorsun nə qədər müqayisə üçün yalnız az xatırlatmaları var.
Amma indi, biz forma alaraq ki, piramidanın diqqət və orada gedir.
Kiçik element sol, sağ ən böyük və başqa arasında hər şeyi edir.
İndi əvəzinə seçim cür nəzər salaq.
Mən irəli getmək və Stop edib gedirəm. Biz barlar yeni bir təsadüfi toplusunu olacaq.
Seçim növ geri, təkrar-təkrar siyahısını keçir
kiçik element həyata Yolma. Belə ki, burada seçim sortudur.
Biz pairwise müqayisə deyilik, çünki indi baş var az iş kimi görünür
lakin biz yalnız sol sağ kiçik elementləri albalı toplama və sort edirik.
Ki, çox az vaxt bir dichotomy artıq var belə.
Alqoritm bubble sırala kimi, n kvadrat vaxt deyilir Məhz
və seçim sort kimi, bu ən pis halda çalışan dəfə həqiqətən.
Məsələn, halda, demək seçim cür imkan
Mən, həqiqətən, kiçik adam seçilməsi edirəm və burada ona verilməsi
sonra təkrar edirəm, sonra, təkrar edirəm
amma edə bilər yüngül optimallaşdırma var idi.
>> Bu halda Sammy - Mən sayı burada 1 köçürülüb kimi -
Mən bundan sonra onunla nə ehtiyac idi? >> [Tələbə] onu buraxın.
Sağ, onu tərk edirsiniz? Heç bir şey.
Mən kiçik element seçilmiş əgər çünki Mən heç Sammy danışmaq lazım deyil
və burada onu qoymaq, niyə tullantıların zaman mənim bütün siyahısını sonuna gedir?
Növbəti iteration məni həqiqətən yalnız sayı 3, 2 nömrəli yalnız hərəkət etsinlər.
Belə ki, əslində, mən n şeyi n dəfə bunu deyil.
1 əşyalar, sonra n - - 2 əşyalar, sonra n - 3 şey, mən sonra n şeyi, n edirdi
sonra n - 4, nöqtə, nöqtə, nöqtə.
Biz yalnız deməkdir ki, həndəsi silsilə bir az var
siz tədricən kiçik nömrələri qədər əlavə edirik.
Not n + n + n + n lakin n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Və ümumiyyətlə olmaq nə işləyir -
Mən yalnız bir an üçün burada board qədər mess gedirəm -
/ 2 - o n kimi bir şey (1 n) olmaq üçün iş olacaq
bütün istifadə etmək vərəqələri olduğu bir riyaziyyat kitabının geri baxmaq əgər biz yalnız cür
düsturlar üçün.
Yalnız bir şey ekliyorsanız n + n - 1 + n - 2, bu kimi bir şey ola işləyir.
Biz yalnız bu cür həyata çoxaltmaq varsa ki, 2 kvadrat minus n / n oldu.
Mən də, deyərək n kvadrat saxlanılır və mən ruhi qısa alaraq cür idi ki
Əslində, n minus kvadrat N 2 bölünür həqiqətən addımlar doğru sıra çünki
biz həqiqətən hesablanmışdır əgər seçim sort kimi alqoritm edəcək
o müqayisələr bütün və biz bunu idi az məşğul bütün iş.
Ancaq səmimi bir n heck qayğıları olan bir milyon və ya bir milyard kimi olur
2 bölünür milyard kvadrat minus bir milyard edirik, əgər?
Kare A milyard böyük bir sayı.
Siz ilə bir milyard off bilər - n. Belə bir böyük deyil.
Belə ki, daha böyük nömrələr almaq, az əhəmiyyətli bu aşağı sifarişli şərtləri var.
Siz addımlar nömrələri quadrillions bəhs edirsinizsə, siz 2 bölmək əgər kim qayğıları?
>> Belə ki, ümumiyyətlə, kompüter alimləri, hər şey amma ən böyük müddətli tullamaq edirlər
və biz yalnız növ dünya sadələşdirmək və demək ki, alqoritm
təxminən n kvadrat addımlar atmışdır. Yəni alqoritm çalışan zaman.
Belə ki, biz bəzi konkret nümunələr yalnız bir anda bu qayıda bilərsiniz
amma indi ki, intuitiv motivasiya sort yalnız bizim dünya sadələşdirilməsi arxasında var
və daha bütün bu xülya düsturlar nəzərə almaq çox ən mühüm şərtləri haqqında söhbət.
Belə ki, seçim cür idi və biz bir az uğurlu var.
Nin durub sırala baxaq. Mənə davam və bu həmçinin başlamaq edək.
İndi baş verən model qeyd, bir az fərqli
və biz, təsadüfi nömrələri ilə açılmış
lakin biz, həqiqətən, pis halda addımların sayı saymaq olarsa,
siyahısı sağ üçün tamamilə açılmış, əgər
biz yalnız daha çox həyata n addımlar olacaq.
>> Lakin siyahı geri həqiqətən olsaydı - məsələn, burada bu halda -
biz, həqiqətən, bu halda bir çox iş var sonra bildiriş.
Bu bir daha iş növü kimi və bu cür siz hiss etməlidir
sol bu kiçik elementləri almaq və biz uğursuz var, çünki ki etmək.
Siyahısı əks təsadüfən sıralanır edilib.
Əksinə, durub sırala biz burada biz insanlar ilə nə taklit əgər
başlamaq sıralanır hər kəs ilə başlayan və sonra, burada, olduqca yaxşı alqoritm var?
Artıq, əslində, sıralanır edir.
Belə ki, bu şeyi bizə alaraq dəqiq nə qədər vaxt ümumiləşdirilməsi cəhd edək
əslində çox sadə olan bir jargon və bit və ya notation təqdim
və fanciness cür təklif edir.
Burada Bu şey, bu böyük O ekranda, kompüter alim ümumiyyətlə istifadə edəcəyik
alqoritm və ən pis halda çalışan zaman təsvir etmək.
>> Yenə, ən pis halda, bu tamamilə kontekstində asılı deyil.
Biz ən pis halda ilə nə demək tamamilə söhbət sorun əsasında dəyişir.
Amma çeşidlənməsi halda, nə pis mümkün ssenari var?
Yalnız bizim üçün çox iş deməkdir kimi hiss çünki hər şey geri edir.
Düşünürəm ki, biz bu günə qədər gördüm ki, alqoritmlər bir neçə aşağı jotted etdik:
xətti axtarış, telefon kitab və ya kağız parçaları kimi ikili axtarış
sonra bubble sırala seçim sort və durub sort kimi biz insanlar gördüm
və sonra 1 digər nəticədə növ daxil adlanan olacaq ki.
Belə ki, ən pis halda xətti axtarış, neçə addımlar bu sayı 7 tapmaq sürer
Sean üzlü kimi n qapı var əgər? >> [Tələbə] N.
N. Biz n böyük O yazmaq olacaq.
Mən yalnız bir blanklara doldurmaq üçün gedirəm. Bu blanklarının bir grid edir.
Lakin xətti axtarış ən yaxşı halda, 7, siyahı çox əvvəlində ola
və Sean siyahısı əvvəlində axtarır açılmış ola bilər.
Siz xətti axtarış istifadə edərək, yalnız sağ və ya sol bəlkə sağ kontrol edirik əgər -
onlar ekvivalent edirik - ən yaxşı halda necə bir çox addımlar güc xətti axtarış
Sean nin alqoritmi kimi, almaq? Sadəcə 1 addım.
>> Mən omega notation var ki, gedirəm.
Bu kapital omega edir.
Omega yalnız ən yaxşı halda zaman çalışan deyərək sexy yoldur.
Belə ki, ən yaxşı halda çalışan zaman bir addım və ya daimi sayı addımlar -
Bu halda 1 - amma ən pis halda, böyük O, həqiqətən n addımlar var.
Və burada bu, teta, biz, həqiqətən, indi baxmaq fikrində deyilik.
Bu xüsusi misal üçün müvafiq deyil.
Amma indi ikili axtarış edək.
Binar axtarış ilə ən pis halda, nə qədər addımlar bu sayı 7 tapmaq üçün almaq niyyətindədir
və ya biz aradığınız nə? >> [Tələbə] Giriş n.
Hələ Alex uğursuz var kimi çünki log n almaq niyyətindədir
biz həqiqətən şəkildə problemi ilə işləyərkən
və o, o baxdı son qapı qədər sayı 7 tapmadı
baxmayaraq, ədalət də, o, yol boyunca müəyyən qapılar tullamaq var
ən pis halda ikili axtarış log n çalışan zaman var.
Və yenə bu ayırıcı və fəth danışır.
Amma nə yaxşı halda haqqında?
O mərhələyə qədər gəlib və Alex həqiqətən doğru olduğunu ən yaxşı halda yaşadı.
Olan ikili axtarış neçə addımlar idi? >> [Tələbə] 1.
1, yalnız o uğurlu var, çünki.
Omega ən yaxşı halda ssenariləri aiddir, çünki ki, gözəl var
yalnız təsadüfi lal uğurlar belə ən yaxşı halda giriş.
>> İndi, bu da indi izin boş yalnız cür olacaq.
Bubble sırala haqqında indi?
Bubble sırala ilə ən pis halda, hər kəs sırayla edir
biz bubbling bir çox var.
Amma nə qədər addımlar pis halda etmək niyyətindədir ki? >> Kare [tələbə] N.
Bu barədə düşünüyorsanız, çünki bu, n kare olub
siyahısını tamamilə geri olduqda - 8 buraya, 1 burada artıq -
şey bubble başlamaq kimi, 8 nömrəli bu yol, bu şəkildə hərəkət edir
Bu yol, bu yol, lakin burada pis halda sayı 7 edir?
Burada o, orada hələ də. Belə ki, biz təkrar etmək lazımdır.
1 addımlar, sonra n - - 2 addımları biz sonra n addımlar n aldığı ki var.
Və bunun üçün mənim söz əgər - siz cür ki, həyata çoxaltmaq əgər
o təxminən biz yalnız indi üçün ignore lazımdır ki, bəzi digər şərtlərinə sonunda kvadrat n oldu -
sonra ən pis halda bubble cür kvadrat n, vermək və ya almaq.
Amma bubble sırala ilə ən yaxşı halda haqqında nə?
Nə yaxşı ssenari deyil? Nömrələr Bütün artıq sıralanır.
Mən istifadə Heuristic, mən istifadə hilesi nə idi
Mən heç bir iş idi və buna görə də erkən dayandırmaq ki, həyata keçirilməsi üçün?
[Tələbə] bir dəfə yoxlayın. >> Dəfə yoxlayın. Amma yol boyu nə edirdi?
Mən qəbul neçə svopları takip saxlanılması edilib.
Və mən barmaqları hər hansı svopları sayılır əgər, sonra heç bir iş etdik həyata keçirilir.
Mən, əlbəttə, daha heç bir iş etmək üçün cəhd deyil, mən yalnız dayandıra bilər.
>> Belə ki, bubble sırala ən yaxşı halda siyahı artıq sıralaması zaman,
Siz ən yaxşı halda zaman çalışan ki, omega notation nə demək istərdiniz?
Bu, sadəcə n edir. Biz bəzi işlər var, amma biz yalnız iş 1 stroll yetmeyecek var.
Və burada da mən bu hissəsi boş buraxın gedirəm.
İndi seçim sort.
Seçim sort mənim təkrar kiçik adam Yolma idi.
Və biz idi çalışan zaman nə demək idi?
Idi n pis halda kare.
Və təəssüf ki, ən yaxşı halda da kvadrat n oldu
Mən bütün dünya ələmə baxış sort yoxdur çünki;
Mən yalnız həqiqətən kiçik adam gördük tam iteration sonra bilirik.
Belə seçim sort cür ki, mənada gücünü zaptetti
lakin alt intuitiv və bu növüdür.
Siz bütün loops üçün nested bir neçə yazmaq çünki qədər kod olduqca asan
adətən, bu kiçik element axtarır keçir
və o, siyahının sonunda yer aldığı kiçik element qoyur.
Belə ki, burada çox ticarət-off olmalıdır olacaq.
Siz düşünmək və həqiqətən kodu yazmaqla bir şey inkişaf edir, vaxt məbləği
Bir alqoritm daha yaxşı və daha sürətli performans istəyirsinizsə çox yaxşı çox vaxt bilər.
>> Ancaq kodu şey həqiqətən yalnız cür əgər sürətli və çirkli
və yalnız növ, siz hesab edə bilərsiniz stupidest mümkün fikir almaq
kodu bir neçə dəqiqə çəkə bilər, amma böyük data dəsti ilə
Sizin alqoritm run saat bilər.
Və hətta mən məzunu məktəb bəzən bu ticarət-off edəcək.
Bu 3am olardı, mən çox böyük data set təhlil etməyə çalışırdı
Mən edirdi təhlükəsizlik araşdırma ilə bağlı və ya 5 dəqiqə sərf edilib
tweaking məlumatları təhlil və yatmaq mənim proqram
dərhal çalışır və yatmaq deyil, və ya yalnız sağ əldə 8 saat sərf edirlər.
Və orada da şüurlu qərar növü var.
Az inkişaf zaman, daha çox yuxu.
Retrospect, mən yəqin ki, həvəsləndirmək lazımdır ki,
Burada məqsəd kodu keyfiyyət optimize zaman,
lakin çox real dünyanın bir çox ağlabatan ticarət-off edir.
Az vaxt az, performans və ya əksinə.
Belə ki, burada biz nəhayət teta haqqında danışmaq imkanı.
Theta notation kompüter elm söhbət yetişdirmək bilərsiniz bir şeydir
böyük O və omega eyni olmalıdır nə zaman.
Siz teta həqiqətən bu sıx bağlı cür ki, mesaj göndərmək üçün deyirəm.
Ssenari yaxşı və ya pis asılı olmayaraq, bu kvadrat n edir.
Belə ki, burada bu hekayələr yalnız müvafiq deyil.
Insertion sort, biz baxdı son bir
harada yalnız sağ yer hər kəs daxil edilib.
Biz burada gördüyümüz kimi ən yaxşı halda nə durub növ çalışan zaman idi?
[Tələbə] ən yaxşı halda? >> Ən yaxşı halda.
>> Ən yaxşı halda hər kəs sıralanır çünki, N edilib
və Sammy və başqa heç bir həqiqətən bütün hərəkət idi.
Onlar doğru yerdə artıq idi.
Ən yaxşı halda belə durub sort, bu halda, n.
Amma ən pis halda kvadrat N növü var. Niyə?
Insanlar mənim siyahısı əks qaydada deyil,
Mən ilk sayı 8 ilə başlamaq və mən burada olan sağ mövqeyi, onu daxil və ya öz.
Yan hərəkət I növ. Bu uşaqlar, o, çeşidlənməmiş ya o çeşidlənir.
Amma indi kim növbəti tapmaq üçün nə? >> [Tələbə] 7.
Ən pis halda 7 bu əks qaydada çünki.
>> Belə ki, burada 7 deyil. 7 harada aid deyil? Əlbəttə, məni arxasında.
Amma indi 7 faktiki olaraq, dərhal məni arxasında lakin sayı 8 arxasında deyil məxsusdur
Mən "deyə Pardon, 8 nömrəli var ki, bu yol hərəkət edin bilər
"7 yer açmaq üçün?" İndi 6 üzləşir.
"Oh, sayı 8 və 7 saylı pardon, siz 6 otaq etmək üçün hərəkət edə bilər?"
Belə ki, başqa sözlə, durub sırala ilə, mən çox hərəkət etdiklərini deyiləm, baxmayaraq ki,
arxamda insanların daha çox iş və kimsə zaman dəyəri var ki.
Bu kompüter vaxt başa olacaq.
Belə ki, durub sırala halda, biz hələ də əziyyət çəkirlər.
Siz addımlar ümumi sayı əlavə başlamaq, biz təxminən n kvadrat vuruş son
Bu uşaqlar ki siyahısına geri daxil etmək insan üçün otaq etmək lazımdır, çünki.
Və bu halda teta yalnız əl-da xüsusi hekayə tətbiq deyil.
Bu gözəl və yaxşı bütün var. Biz çalışan zaman söhbət bu 3 müxtəlif yolları var.
Biz həqiqətən bir alqoritm qədər kod cəhd Amma bu həqiqətən real olaraq nə deməkdir?
>> Orada daha yaxşı alqoritm var ki, mənə təklif edək
özü bəzi ticarət-off var.
Biz bu cür daxil zəng olacaq, və bu sehirli alqoritm növ var
yalnız daha sürətli birtəhər işləyir, və ən azı pseudocode ilə ifadə etmək üçün asandır.
Bu alqoritm birləşmə sort həyata keçirilməsi aşağıdakı kimi olacaq.
Bir ağlı başında olma çek var birinci - nə n nömrələri, n insanlar, - siz n elementləri verilmiş olduğunuzda.
N 2-dən az olarsa, sort yalnız dayanır daxil. Bu danışmaq, geri qaytarır.
N 2-dən az olduğu halda niyə dayandırmaq olar? >> [Işitilemez tələbə cavab]
Sağ. Və yenə n siyahısında sayı deyil, n siyahı ölçüsü.
N 2-dən az olarsa, o, listenizi ya 1 deməkdir
1 sıra əgər burada açıq-aydın, sıralanır edirsinizsə
və ya düzmək üçün heç bir şey yoxdur bu halda 0,
biz baza halda bu cür lazımdır.
Siyahısı əlaqəsi yalnız var ki, qısa deyil, sanki bir şey yoxdur. Qayıt.
Əks halda elementləri sol yarım sort, sonra elementləri hüququ yarım sort
sonra 2 sıralanır yarıya indirir daxil.
>> Mən necə elementləri sort isteyen edirəm elə bu cür bir az etmək kimi görünür
və "sağ yarım sort, sol yarım Sırala." mənə izah edirik
Mən kimi oldum "Bütün hüququ. Necə sol yarım sort yoxdur?"
"Işlər, sonra sol yarısının, sol yarım sırala sol yarım hüququ yarım sort və".
Siz cyclically bu sort nə deməkdir müəyyən cür etdiyiniz
lakin bu halda həqiqətən parlaq olduğunu çıxır.
Bu həqiqətən başa heç vaxt bu sonsuz dövrü deyil
zaman son deyil, çünki? >> [Tələbə] siz 1 şey çatmaq zaman.
Siz 1 şey çatdıqda.
8 xalqı ilə başlamaq bilər və demək baxmayaraq Belə ki, "bu insanların sol yarım sırala
Bu 4 nəfər, "sonra demək," necə sol yarım sort yoxdur? "
"Yaxşı, burada 2 nəfər sort". Və sonra, gibisin "Bütün hüququ, gözəl."
"Necə bu insanların sol yarım sort yoxdur?"
"Yalnız burada 1 nəfər sort". İndi parlaq nazil nədir?
Mən 1 nəfər düzmək lazımdır. Done. Mən heç bir işi yoxdur.
Ancaq indi bu şəxs düzmək üçün var, lakin onlar bir şəxsin, heç bir istəyirik.
>> Belə ki, sehrli yəqin bu üçüncü addım var: sıralanır yarıya indirir daxil.
Belə ki, daxil sort bu parlaq fikir edir ki, bir böyük problem qırmaq əgər
2 kiçik, eyni ölçülü problemlərini
və sonra sonunda kiçik həllər birlikdə yapışqan yalnız növ
Mən ki, biz daha yaxşı [tıqqıltı səs] çox edə bilərsiniz ki, təklif
seleksiya sort və ya durub sırala dən.
Mən, həqiqətən, yarım saat üçün məhəl olduğunuz, lakin mən, həqiqətən neler bilmirəm
Bu gün xaricində. [Whirring səs] [gülüş]
Belə ki, biz dost Rob Bowden bir az köməyi ilə bu edə bilərsiniz əgər in görək.
Birləşmə sort prosesində 2 böyük addımlar var.
Birincisi, davamlı yarıya indirir daxil fincanların siyahısı split
biz onlara yalnız 1 fincan ilə siyahıları bir dəstə qədər.
Siyahısını tək sayda varsa, narahat olmayın
və onların arasında mükəmməl təmiz cut edə bilməz.
Yalnız özbaşına əlavə kubok daxil daxil olan siyahısı seçin
Belə nin bu siyahıları split imkan verir.
İndi 2 siyahıları var.
İndi biz 4 siyahıları var.
İndi biz hər siyahısında bir fincan 8 siyahıları var.
Belə ki, 1 adım üçün deyil.
Addım 2 biz dəfələrlə biz əvvəl öyrənildi birləşmə alqoritmi istifadə siyahıları cüt birləşməsi.
108 və 15 Birləşdirən biz siyahısına 15, 108 ilə qədər.
50 və 4 birləşmə biz 4, 50 ilə qədər.
8 və 42 Birləşdirən biz 8, 42 ilə qədər.
Və 23 və 16 birləşmə biz, 16 ilə 23 qədər.
İndi bütün siyahıları ölçüsü 2 daşıyır.
4 siyahıları hər çeşidlənir edək ki,
biz yenə siyahıları cüt birləşməsi başlaya bilərsiniz.
15 və 108, 4 və 50 Birləşdirən biz ilk, sonra 15, 4 almaq
sonra 50, sonra 108.
8, 42 və 16, 23 Birləşdirən biz ilk sonra 8, 16, almaq
sonra 23, sonra 42.
Belə ki, indi biz size 4 yalnız 2 siyahıları ki, hər biri çeşidlənir.
Belə ki, indi biz bu 2 siyahıları daxil.
İlk 4 almaq, sonra 8 almaq, onda biz 15 almaq
və 16 və 23, 42 və 50 və 108.
Və biz tamamlayın. İndi sıralanır siyahısı var.
>> Rob biz hələ həyata deyil ki, bir şey istifadə edərək cür idi.
Bu təklif edilib, ancaq həqiqətən bunu etmədi.
O, təklif edir ki, fincan ilə fiziki bir şey edirdi
o zaman başqa bir resurs sərf edilib. >> [Tələbə] Space. >> Bu yer idi.
Burada yer olduğu o bi səviyyədə masa bu cür idi ki,
və burada yer əslində o iki dəfə çox yer istifadə edir eyham edilmişdir
daxil sort, bubble sırala və ya seçimi sırala - - İndiyədək bizim alqoritmlərin heç kimi
lakin o, geri və irəli hərəkət şeyi cür bu əlavə yer yararlanarak edilib
üçün hər şeyi tutarken.
Biz bir sorted siyahısı var kimi hiss baxmayaraq bir müddət etmişdir kimi, bu hiss.
Əslində, nə Rob edirdi məhz bu alqoritm idi.
O, ilk, ölçüsü n problemi etdi sol yarısı və sağ yarım onu ​​bölünür.
O fincan köçürülüb zaman var. Sonra prosesi təkrar.
O, burada artıq burada 2 2 dəstləri daxil 4 bölünür.
Sonra prosesi təkrar və o müxtəlif fincan hər 1 2 dəst daxil 2 bölünür.
Parlaq imkan yaranır yerləşir ki var.
Hekayə ki nöqtədə Rob, ölçüsü 1, 8 siyahıları idi
olan bütün artıq sıralanır idi.
>> Belə ki, nə o, nə davam etdi?
Pairwise bu sorted siyahısı və bu sorted siyahısı etmiş və onlara birləşdi.
Sonra o, bu etmiş və onlara birləşdi, bu bir və onlara birləşdi
bu bir və onlara birləşdi.
Və o, nə gələcək mi?
O böyük siyahıları yenidən birləşdi və sonra böyük siyahıları yenidən birləşdi.
İndi yalnız daxilən bu barədə düşünmək Əgər, o, həqiqətən nə idi?
O yarısında yarısında yarısında yarısında problem ayırıcı edilib
bu super kiçik siyahıları almaq üçün.
Sonra o, ikiqat, cüt cüt cüt birləşdirən cür idi.
O, biz belə uzaq gördüm kimi çox iş kimi iki dəfə edirdi
parçala və fəth, lakin böyük cəlb bir şey ilə.
Iki dəfə çox iş belə böyük deyil. Bu yalnız daimi amil var.
Və daha əvvəl hesab ifadə kimi, yalnız daimi amillər həyata keçməyə gedirəm
dəfə 2 kimi. Kim qayğıları? Hələ addımlar çox olan dəfə 2, 2 milyard varsa.
Belə ki, bu birləşmə addım əsas fikir görünür.
Nin qarşısında yalnız sayca bu vasitəsilə gəzmək edək - Oh ki, hələ davam deyil.
Bu sayı yalnız həqiqətən bunu oynayır necə vasitəsilə gəzmək edək.
Bu əsasən yalnız bir az yoxsul adam animasiya edir.
Bu təklif edək.
Birləşmə növ çalışan zaman - biz yalnız bu söhbət bir yol lazımdır.
Bu riyaziyyat deyil, bu özümüzü ifadə yığcam şəkildə yalnız növüdür.
Beləliklə T dəfə təmsil n nə təmsil? >> [Tələbə] Bu həcmi -
>> [Malan] problemin həcmi, insanların sayı.
Mən n insanlar düzmək üçün çalışan zaman zaman 0 məbləği olacaq iddia edirəm
N 1 stəkan və ya fincan varsa, düzmək üçün heç bir şey yoxdur, çünki 2-dən azdır. əgər
Amma ümumiyyətlə, mən çalışan zaman n elementləri düzmək üçün təklif gedirəm
bu sol yarım sort üçün lazım vaxt plus sağ yarım olacaq
plus - bu əlavə + n var? >> [Tələbə] Merge sort.
[Malan] Burada n / 2 elementlər varsa, çünki həqiqətən, birləşmə var
və burada n / 2 elementlər var, onları daxil etmək üçün nə qədər vaxt lazımdır?
Just Rob kimi, burada artıq bu qırpmaq üçün, bəlkə, buraya dərmək
burada dərmək, buraya dərmək, buraya qırpmaq.
Siz bir fincan hər toxunmaq lazımdır.
4 fincan müsbət 4 fincan var, əgər ki, 8 stəkan deyil
və ya ümumiyyətlə, 8 n fincan.
Belə ki, birləşmə addım biz, n kimi ifadə edə bilər
və sanki neçə dəfə fiziki toxunub Rob daxildir
o Styrofoam fincan biri.
Belə ki, indi bir ixtiyari Məsələn nə edək.
16 stəkan varsa, nə Rob-nin alqoritm, 16 stəkan istifadə edərək, çeşidlənməsi ilə çalışan zaman?
8 stəkan düzmək üçün edir zaman 2 dəfə tutar
burada biz burada 8 stəkan, çünki, 8 stəkan.
Mən belə biz bu an üçün T kimi ümumiləşdirmək edirik, edir ki, nə qədər bilmirəm.
Kim nə bilir?
Amma indi recursively ya təkrar-təkrar eyni sual və sıralayabilirsiniz.
8 stəkan düzmək üçün nə qədər vaxt lazımdır?
Demək gedirəm 8 stəkan, 4 stəkan müsbət 4 fincan düzmək üçün edir müddəti edir
sonra onları birlikdə birləşdirilməsi.
Fine. Biz artıq bir dövrü nəzərə alırıq. 4 fincan düzmək üçün necə sürer?
4 fincan sort üçün lazım vaxt 2 fincan plus 2 fincan çeşidlənməsi üstəgəl birləşmə prosesdir.
Fine. 2 fincan düzmək üçün necə sürer?
2 fincan 1 fincan düzmək üçün edir müddəti plus başqa bir fincan sort edir zaman
üstəgəl bu daxil edir müddəti olan yalnız 2-dir.
>> Fine. Son sual. 1 fincan düzmək üçün necə sürer?
Burada biz əvvəllər edib istədiyiniz proqnozlaşdırılır ki, baza haldır.
Bu problemlərin kiçik düzmək üçün heç bir iş görür ki,
vasitəsilə indi ki, dərəcəli məktəb stil növ,
biz yalnız da geri bu rəqəmlər sayede başlamaq bilərsiniz
Biz indi 1 T nə, mən 1-T 0 plug bilər.
Mən ali qədər plug bilər 2 T, mənə cavab verəcək.
Bu mənə daha yüksək qədər plug bilər 4 T, verəcək.
Bu mənə daha yüksək qədər plug bilər 8 T, verəcək.
Mən, həqiqətən, bu cavab sayede ki, riyaziyyat həyata əgər,
Mən 16 T 64 deyil almaq.
Və 64 nə təmsil edir?
T 16 deyil, Bəli, o, 16 dəfə 4 var.
Mən bu şey çalışan zaman sort daxil adlı indi iddia -
və biz belə uzaq gördüm olanları fanciest olacaq -
adlı olacaq n log n edilir
neçə dəfə yarım stəkan bütün dəstə split Rob bilər, çünki? N olun.
Bu telefon kitab misal kimi eyni, bu öz-özünə hesablanması misal kimi eyni.
>> Neçə dəfə yarısında bir şey bölmək olar?
Lakin, bu birləşmə addım var.
Siz təkrar və yenidən yarısı daxil fincan bölmək ola bilər
ancaq olacaq hər dəfə daxil etmək.
Və biz n fincan birləşmə n addımlar atır ki, əvvəllər bildirib
bir fincan yoluşdurmaq var, çünki bir fincan yoluşdurmaq və siz bir dəfə hər bir fincan toxunmaq var
yalnız Rob kimi etdi.
Biz bir şey log n dəfə edirik və biz bu tekrarlamalar hər n şeyi edirik Beləliklə, əgər,
o halvings hər biz n dəfə log n var.
Biz bu misalda 16-plug Belə ki, əgər 16 dəfə, 16 giriş -
Mən baza tərtib deyil etdik, çünki bu artıq işə görə narahat deyil -
lakin 16 baza 2 günlük dəfə 4 64 16 4.
Amma əksinə, biz 16 nömrələri ilə bubble sırala ya seçilməsi sort və ya durub sırala istifadə əgər,
n 16 Əgər çalışan zaman nə olardı?
Bu 256 olan 16 kvadrat ola bilər, siz olduqca bütün riyaziyyat əməl etməyib, hətta, ki,
256 64 böyükdür. Bu həqiqətən burada sehrli paket var.
Və pset sizi iradə kimi kiçik nümunələri bu ilə iş ki, həyata
daha intuitiv bütün edir.
Amma həqiqətən bu alqoritm hissi baxımından deməkdir ki, nə bu:
Biz, həqiqətən, burada birləşmə sort baxsaq - mənim burada bu pəncərə onu qoparmaq imkan -
bu bu alqoritmlərin bütün 3. qovuşdurmağımız bir az fərqli nümunəsidir -
bubble, seçilməsi, və birləşməsi - yan yalnız yan.
>> Onlar təsadüfi bar ilə başladı və yaxşı.
Heç bir başqa bir əsas üstünlüyə malikdir.
Mən bir anda gedirəm bu animasiyalar hər basın - Start Start Start -
Mən kimi sürətli kimi, belə ki, eyni zamanda təxminən, onlar bütün başlanğıc,
və vaxt çalışan bubble sırala nin pis halda nə ki, hesab edək? >> Kare [tələbə] N.
N kare. Vaxt çalışan seçimi sort ən pis halda? N kare.
Və birləşmə cür aydın deyil - siz kifayət qədər bütün riyaziyyat əməl etməmişlər, hətta indi,
daha intuitiv zamanla olmaq lazımdır - biz iddia, n dəfə log n.
Və log n çox ciddi az n sonra biz böyük nömrələri var, çünki
n dəfə log n n dəfə daha kiçik n və ya n kvadrat edir.
Belə ki, nə o, həqiqətən çalışan zaman baxımından daha yaxşı alqoritm olmaq hiss etmir
n dəfə log n kimi kare n fərqli? Burada getmək. Basın, basın basın.
>> Bu birləşmə sort kimi bir şey istifadə etmək nə deməkdir var.
Biz bir an var. Burada nə görmək edək.
Kimin pul bubble sırala edir [chuckles]?
Bu olduqca bəzən daxil asılıdır.
Bakalým.
Hadi. O qədər alıcı var kimi hiss edir. >> [Tələbə] bubble sırala Go!
[Tələbələri murmuring]
[Malan] Bəli, Bəli.
[Murmuring tələbələr] getmək, getmək, Go!
[Alqış] [bütün təzahürat]
Belə ki, indi 1 son final demo ilə, əgər riyaziyyat ətrafında fikrinizi kesmek üçün bir az çətin deyil
və ya orada vizual növ, siz həqiqətən sürətlə eşitmək bilər
fərqli müxtəlif alqoritmləri.
Bu, həqiqətən, asılı səslənir ki, hazırlanmış animasiya kimsə
dəyişdirmə prosesi və bar hündürlüyü.
Biz burada görürsünüz ki, bir neçə çeşidlənməsi alqoritmlərin insanlar fikir ki, orada var.
Bu ilk bir durub sırala olacaq və bu yolu gedəcək
və necə bu müxtəlif alqoritmləri iş səsli hissi verir.
Burada durub sortudur.
[Elektron səs siqnalı]
[Malan] Bubble sort.
[Elektron səs siqnalı sürətli]
[Malan] Seçim sort.
[Elektron səs siqnalı sürətli]
[Malan] Merge sort.
[Elektron səs siqnalı]
[Gülüş] [səs siqnalı aşağı yavaşlatır]
[Malan] Gnome sort.
[Elektron səs siqnalı]
>> Bu CS50 edir. Gələn həftə görəcəksiniz. [Alqış və təzahürat]
>> [CS50.TV]