>> [Musiqi ifa]
>> DAVID J. Malan: Yaxşı.
Belə ki, geri salamlayıram.
Bu CS50, və deyil Həftənin üç sonu.
>> Belə ki, son bir neçə həftə geri biz kifayət qədər bir az sərf etdik
C, proqramlaşdırma üzrə, sintaksis zaman.
Siz hələ değilseniz və bu, olduqca normal olmaq, Problem Set 2 ilə mübarizə
divar qarşı baş tarpıltı.
Bu sirli-looking hata mesajları var və hataları ki,
olduqca aşağı Chase bilməz.
Çünki arxayın ki, yalnız bir bir neçə həftə vaxt geri baxmaq lazımdır
Sezar kimi şeylər, və [? V-genair?] bəlkə Crack və
siz gəldiniz yalnız nə qədər həyata qısa müddət ərzində.
Hər hansı bir təsəlli var Belə ki, İndi orada asmaq.
>> Bu gün, baxmayaraq ki, biz keçid başlayır şeyi yüksək səviyyədə.
Və biz verilən etmək başlamaq uşaqlar proqram necə və ya
əvvəlindən az ki, rahatlıq səviyyəsi.
Və biz necə biz hesab başlarsınız daha çox proqram hazırlanması haqqında getmək
səmərəli.
Biz optimize haqqında getmək necə bizim alqoritmlər səmərəliliyinin və
ümumiyyətlə həlli maraqlı problemləri.
Və ki, verilən almaq üçün başlanğıc biz istəyirdi, biz bir qədər kod bilər
biz nəzərə nümunələr.
Bu gün Beləliklə, biz klaviatura toxunmayın kodu hər hansı bir formada üçün.
Bu, çox yüksək səviyyədə olacaq, olacaq nəticə etibarilə, problem həll haqqında.
>> Belə ki nöqtəsinə almaq üçün, mənə təklif bildirin ki, aşağıdakı yeddi
düzbucaqlı arxasında, yeddi qapı təmsil olan bütün dəstə var
ədəd, onlardan sayı 50-dir.
Mənə bu bu layihə edək burada da ekran.
Və biz könüllü lazımdır ki, təklif Qarşımda bir sıra tapmaq
görmək üçün burada internet.
Çəhrayı ilə qədər Hadi.
Bütün hüquqlar.
Sizin adınız nədir?
>> Jennifer: [işitilemez]
>> DAVID J. Malan: Üzr istəyirik?
>> Jennifer: Jennifer.
>> DAVID J. Malan: Jennifer.
Bütün sağ, Jennifer.
Cavab gözəl.
Up Hadi.
Belə ki, bu burada yeddi qapı var, və nə Mən burada bizim üçün nə istediğiniz
Sizin sinif yoldaşları bütün qarşısında, Bizə sayı 50 tap.
Bir sıra tapmaq üçün, peek arxasında bilərsiniz sadəcə tıqqıltı ilə bu qapıların hər hansı
qapıları biri və bu onun nömrəsi aşkar edəcək.
Və nin görək necə tez Bizə sayı 50 tapa bilərsiniz.
>> 15.
16.
50.
Qəşəng edilir.
Bütün hüquqlar.
Jennifer üçün alqış dəyirmi.
>> [Alqış]
>> Bütün hüquqlar.
Belə ki, strategiya nə idi , 50 sayı tapmaq?
>> Jennifer: Um, bəlkə əgər fikir -
[Işitilemez]
>> DAVID J. Malan: Oh.
Bu bir ikinci verin.
Belə ki, strategiya üçün idi , 50 sayı tapmaq?
>> Jennifer: Belə ki, yalnız-da başlayacaq görmək başlayan nə ilk sayı
bəlkə, əgər, sonra fikirləşdim onlar sorted edirik, yalnız davam edəcəyik
up yüksək tıqqıltı?
>> DAVID J. Malan: OK.
Və biz gördük görünür halda olması.
Baxmayaraq ki, geri soymaq qat edək bir az bit, və siz getmək istəyirəm
irəli və digər qapıları aşkar seçdiyiniz bilər?
>> Jennifer: Oh, əziz.
>> DAVID J. Malan: Ah.
>> Jennifer: Belə ki, Mən yalnız şanslı var.
>> DAVID J. Malan: Beləliklə, siz xoşbəxt var.
Bütün hüquqlar.
Belə ki, pis deyil.
Amma bir Maraqlıdır fikir, sağ?
, Siz ehtimal və siz almaq əgər Həqiqətən, bir az orada uğurlu.
Amma nömrələri ki, güman əgər sorted, daha dəqiq ola bilər
ki, təsir necə Sizin davranış?
>> Jennifer: onlar sıralanır idi, mən iri bəlkə kiçik düşündüm.
>> DAVID J. Malan: OK.
>> Jennifer: Yoxsa bu qədər başa əgər olan kiçik sonra böyük, həqiqətən böyük.
>> DAVID J. Malan: OK.
Belə ki, kiçik ən böyük, və ya ən böyük kiçik.
Amma mənə təklif ki, siz idi Güman uğursuz kazanılmış və güman ki, onlar
, əslində, sorted deyil, necə bir çox o qapı siz peek idi bilər
ki, pis halda arxasında?
>> Jennifer: Hamısı.
>> DAVID J. Malan: Hamısı.
Elə ümumiləşdirmək edək n kimi.
Orada 7 olmaq olur, lakin qoy daha çox ümumiyyətlə var n qapı var demək
burada ekran.
Belə ki, ən pis halda, siz var ki, 7 qapılar, və ya n qapılar arxasında baxmaq.
Və bu, həqiqətən bir az var ki, uğurlar bu gün, ancaq həqiqətən xətti var
növ alqoritm belə olsa ətrafında atlama cür idi.
Ədalətli mi?
>> Jennifer: Bəli.
>> DAVID J. Malan: Bəli, mənə görək əgər strategiya dəyişikliklər bizə hərəkət əgər
Burada bizim ikinci misal 7 müxtəlif qapılar.
Eyni nömrələri, lakin bu vaxt ayrılır.
Olacaq burada strategiyası nədir fikrinizi yerinə qoymaq üçün çalışırıq nə
Digər nömrələr idi -
>> Jennifer: OK.
>> DAVID J. Malan: - əvvəllər?
>> Jennifer: başlanğıc edək birinci ilə.
>> DAVID J. Malan: Yaxşı.
Birinci ilə başlayın.
4.
İndi harada getmək gedən və niyə?
>> Jennifer: 4 həqiqətən kiçik.
Onlar sort bəlkə kiçik istəyirik, əgər böyük, bu olmalıdır
- iki dəfə ki, ola bilər.
>> DAVID J. Malan: OK.
Gəlin hesab edirəm ki, bax?
>> Jennifer: son bir cəhd edin.
Gözəl.
>> DAVID J. Malan: Çox gözəl işlər.
Bütün hüquqlar.
>> [Alqış]
>> DAVID J. Malan: OK.
Belə ki, əslində bu yapýyorsun sen horribly, çünki
çox yaxşı edir.
Hansı bizə iqtidarında yarpağı müəyyən xal etmək.
Belə ki, burada geri gəzmək üçün cəhd edək.
>> Jennifer: OK.
>> DAVID J. Malan: Çox yaxşı Buna baxmayaraq, işlər.
Belə ki, ilin əvvəlində başlayıb siz onu sonra, siz 4 olduğunu gördüm
sonuna köçürülüb.
Amma xoşbəxt əldə etməyib Güman , orada Güman 50
başqa bir yerdə idi.
Sizin Üçüncü addım olub?
>> Jennifer: əvvəlinə qayıt.
>> DAVID J. Malan: geri dön əvvəlinə.
OK, belə ki, toxunub sonra ki, 8 olan bu qapı.
Bütün hüquqlar.
Belə ki, 50 deyil.
Harada növbəti olardı?
>> Jennifer: Mən olmasaydı onlar çeşidlənir bilirik.
>> DAVID J. Malan: Doğru.
Bəli, əgər bilmək onlar sıralanır idi -
>> Jennifer: Oh, evet, bilirdinizmi.
>> DAVID J. Malan: - amma siz yox idi 50 hələ idi bilirsinizmi?
>> Jennifer: Just davam.
>> DAVID J. Malan: Yaxşı.
OK.
Davam edin.
OK, Mən ilə işləyə bilər.
>> Jennifer: OK.
>> DAVID J. Malan: İndi, yalnız değilseniz davam etmək niyyətindədir, nə sizin
alqoritm daxil dəstək devolving.
>> Jennifer: xətti -.
>> DAVID J. Malan: Bu xətti növü deyil.
Amma qoy, mənə təklif bildirin Mənə yerində qoydu.
Mənə səhifəni yenileyin edək.
eyni sayda eyni təşkili, Eyni qapılar.
Amma ki, ilk gün geri edirəm biz bir telefon kitab parçaladı zaman sinfi
yarım növ, və nə idi bizim strategiyası?
>> Jennifer: ortasında başlayın.
>> DAVID J. Malan: OK.
Belə ki, orta-da başlanır.
Elə davam və simülasyonu imkan verir.
Tərəfindən orta Start ki, qapı aşkar.
Belə ki, 16 saylı.
Belə ki, güclü oğlan nə olardı, edən yarısında telefon kitab parçaladı
növbəti qonağı almaq?
>> Jennifer: Bu yarısında gedin.
>> DAVID J. Malan: Və niyə sağa?
>> Jennifer: onlar olsaydı növ kiçik iri, 50 olmalıdır
ki, sonunda.
>> DAVID J. Malan: Yaxşı.
Ümumilikdə ağlabatan.
Belə ki, bir telefon kitab kimi, siz getmək hüququ kimi sol fərqli, lakin burada
əsas paket edir.
İndi, tullamaq və ya qoparmaq bilər Bu problemin yarısı, siz tərk
7 qapı, lakin həqiqətən, yalnız 3.
Hansı təxminən yarısı Problemin ölçüsü.
Bütün hüquqlar.
Belə ki, indi siz nə sağ getmək sonra həyata?
>> Jennifer: Yəni 16, hələ olduqca kiçik 50 nisbi, belə ki, bəlkə mən cəhd edəcəyik
bu bir kimi.
>> DAVID J. Malan: Yaxşı.
42.
Bütün sağ, indi nə üçün belirten instinkt?
>> Jennifer: I üz atmaq olar Bu və sonra yalnız -
>> DAVID J. Malan: OK.
Yaxşı, Əgər üz atmaq olar orada sol yarısı.
>> Jennifer: - Bu bir seçin.
>> DAVID J. Malan: Və hüququ.
>> Jennifer: Bəli.
>> DAVID J. Malan: çətin belə olsa belə, yalnız var zaman, bəlkə də görmək üçün
7 qapılar, indi haqqında düşünmək Bu ardıcıllıq
yalnız tətbiq alqoritmi.
Əvvəlki halda, etdi böyük idi ki, uğurlu olsun.
Amma bir Heuristic istifadə etdi Mən deyərdim.
Siz instinktlərdən növ istifadə və bu olduqca varsa, bu sıralanır bilmədən
əvvəlində kiçik, təbii ki, biz var sağ üçün daha getmək üçün var.
Amma bəzi mənada, siz xoşbəxt var bəlkə bu sayı 100 idi
və bəlkə 50 ortada çox idi.
Bəlkə 50-burada belə idi.
>> Amma fərqli bir az nə etdi bu dəfə, eyni şey idi
təkrar.
Və mən iddia edirəm ki, nə yalnız olsa telefon təsir etməyib
kitab, məsələn, çox şeydir daha alqoritmik və çox
az xüsusi cased.
Daha az instinktiv.
Belə ki, günün sonunda, necə ki, Siz səmərəliliyini təsvir
Siz getdiyi ilk alqoritm, ki, qarşı, sağ
Burada ikinci alqoritm?
>> Jennifer: Bu bir olmalıdır kimi, bəlkə vaxt yarı bölmək, və ya daha çox, evet.
>> DAVID J. Malan: OK, bəlkə də daha çox.
Ki, bir az daha təkan edək.
Həqiqətən nə, biz bu davam edərsə, məntiq, biz mütləq halved
Bu ikinci alqoritmi vaxt çalışan Bu yarım üz ataraq
nömrələri, ancaq yanında nə idi Jennifer aşkar zaman iteration,
ikinci nömrəsinin?
>> Biz yenə qapı nömrələri halved.
Və sonra, biz bundan sonra nə idi əgər ilə oynamaq daha çox qapı var idi?
Biz onları yenidən yarı bölmək, və ki, və yenidən və yenidən.
Və bu, yalnız sizin uşaqlar kimi idi ilk həftəsində dayanan
aşağı oturan sinif, yarısı, yarım Siz, siz yarım oturaraq
bir tək qədər, oturaraq soul durmuşdu.
Və dedi ki, çalışan zaman ki, etdi addımların sayı
nə sifariş haqqında?
>> HOPARLÖR 1: [işitilemez]
>> DAVID J. Malan: Belə ki, log baza n 2- və ya daha çox sadəcə, n daxil.
Belə ki, loqarifmik bir şey.
Və graph bir düz xətt deyil yalnız pis və pis var ki, o,
deyil ki bu maraqlı curve zaman keçdikcə belə pis almaq.
Belə ki, bu fikir yapışmağa imkan verir.
Nin Jennifer minnətdarlığımı bildirirəm.
Up gələn üçün təşəkkür edirik qədər.
Və, san biridir.
No masa lampaları bu gün, lakin biz CS50 stress toplar var.
>> Jennifer: Yay.
>> DAVID J. Malan: Bütün sağ, burada.
Tətbiq üçün təşəkkür edirik burada stress up.
Bütün hüquqlar.
Elə görək biz indi əgər bir az daha bu rəsmiləşdirilməsi.
Belə ki, yenə, biz yalnız nə idi biz kimi mahiyyətcə eyni şey
ilk həftə.
Əksinə sonunda yalnız xətti ilə biz təsvir edən alqoritm,
əvvəl bu düz xətt kimi, qovuşdurmağımız, biz daha bir qapı qoymaq
ekran, sonra Jennifer ki, potensial baxmaq idi
daha bir qapı arxasında.
Biz daha iki qapı qoymaq, o, ola bilər daha iki qapılar arxasında baxmaq.
>> Belə ki, bu xətti var idi nın ölçüsü arasında əlaqələr
X-ox, demək, problem və bu alır vaxt məbləği
y üzərində həll edir.
Amma mən alluding edilib şəkil Bu yaşıl xətt idi.
Green qəsdən, çünki yalnız daha yaxşı hiss etdim.
Nəzəri olaraq, biz bu alqoritm, nə zaman telefon kitab ilə, biz bunu
Uşaqlar bir-birinə hesablanması, və ikinci halda, zaman Jennifer yalnız
burada o qədər idi ki, bu cür idi əsaslı daha yaxşı.
Yalnız iki dəfə sürətli kimi deyildi.
Bu sürətli kimi hətta dörd dəfə deyildi.
Bu nə tamamilə asılı idi giriş ölçüsü kimi idi, nə qədər
etibarilə etdi addımlar.
>> Və biz bütün etmişdir ki, bu sadə ideya telefon kitab ilə verilən,
eyni tətbiq oluna bilər bu kimi bir şey üçün.
Bu daha Təsadüfi ola bilər Əgər güc kimi, kimi tanınan
uçurum və fəth, təsəvvür edin.
Biz nə fərqli olaraq, əlbəttə, telefon kitab.
>> Amma pseudocode, geri bu idi.
Beləliklə, biz yenidən, lakin geri deyil ilk həftə, hamımız ayağa qalxıb
və sonra yarısı yarısı oturdu siz oturdu, siz yarım oturdu.
Bu alqoritm bir həyata keçirilmişdir ki, bir aldadıcı şəkildə bit, o,
Mənə yalnız bir, sayılması deyil əsaslı, daha səmərəli.
Bu halda, mən yararlanarak edilib ikinci resurs.
Növ, çox CPU'lar, çox beyinləri də çox ağıllı insanlar
otaq mənə bir şey almaq yardım edildi bir şey üçün xətti
bir şey, loqarifmik bir şey yaşıl qırmızı.
>> Amma bu halda, Jennifer tək bilərsiniz fundamental olaraq inkişaf
onun ilk alqoritm icrası ilə yenidən, yalnız bir az daha düşünürük.
İndi, onu həyata keçirmək üçün vaxt gəldiyi zaman bu şeyi həyata figuring
Əgər belə yaza nə kodu xətləri yenə təkrar edə bilərsiniz ki,
yenə və yenə növ bir loop moda.
Siz var etmək fikrində deyilik Çünki Jennifer kimi lüks, üçün, ilk etdi
yalnız IFS bütün dəstə var və demək hmm, bu ilk sayı 4 olduqda,
Mənə sonuna bütün yol jump imkan verir.
Ki sayı çox böyük varsa, Ooh, mənə özbaşına geri hərəkət edək
İkinci element üçün.
Siz bir çox olacaq ki, tapa bilərsiniz daha rəsmiləşdirmək üçün nə biz insanların
çox ağlabatan kimi verilən almaq deneysel çalışmalarını, lakin bir kompüter yalnız
Siz demək nə gedir.
>> İndi bu çox maraqlı var təsiri.
Bu şəklin növ növ deməkdir vizual qorxudaraq, lakin bildiriş, harada
bu diaqramda düz xətt var?
Xətti graph harada biz n zəng ki?
Bəli, bu alt doğru sort var Bu şəkil, sağ?
Biz etdik biz bütün növ var belə X-ox və həyata zoomed
y-ox hansı bir mənada almaq üçün cəhd əyriləri digər növləri kimi baxırıq.
>> Və riyazi xüsusiyyətləri ifadələr bu gün məsələ deyil
çox, lakin bir çox var fark çox pis olduğunu alqoritmlər
Xətti ki, bir şey.
Həqiqətən, Cubed n olduqca pis görünür.
2 n olduqca pis görünür. kvadrat n olduqca pis görünür.
Və biz görəcəksiniz nə o bəzi Əslində bu gün ola bilər.
Və log n pis hiss deyil, n daha yaxşı n daxil baza 2-dir.
Amma bilirsiniz, hətta olardı daha gözəl əgər Jennifer, və ya əgər,
ilk həftə ilə gəlmişdi n daxil daxil ki, bir şey.
>> Belə ki, başqa sözlə, bu bütün var mümkün həllər çeşidini
problemlər, hətta burada, bildiriş nə olacaq.
Bu əyriləri I Uzaklaştırmak zaman, hansı mütləq ola gedir
İndi ekranda isə pis?
Belə n Cubed olduqca görünür an pis.
Amma biz həyata zoom və daha çox görmək əgər olacaq olan x və y-ox,
nəticədə hakim?
Belə ki, həqiqətən ki, 2 çıxır n, və yalnız bu anlamaq olar
bəzi getdikcə böyük sayede nömrələri və görürsünüz ki, 2 ilə
n, həqiqətən, böyük çox daha sürətli olur.
Biz həqiqətən, bir 2 Uzaklaştırmak edin n alqoritm tamamilə gücünü zaptetti.
Mən bu gedir demək üçün vaxt kifayət qədər bir az
kompüter vasitəsilə nehrə etmək.
>> Amma xüsusilə, zamanla görürsünüz gələcək problem dəstləri ilə və hətta
son layihələr, veri edir set, bütün doğru böyük olur?
Hətta Facebook ilk versiyası, dostları sayı, və kimi
qeydiyyatdan keçmiş istifadəçilər sayı, böyük var Əgər telefon bu sort edə bilərsiniz
, xətti axtarış şey həyata və ya çox sadə çeşidlənməsi
biz bu gün görəcəksiniz kimi alqoritmi.
Siz daha düşünür başlamaq üçün və bu problemlər haqqında çətindir.
Və problemlər yerlərdə növləri kimi Facebook və Google və Microsoft,
və iş s məhz sual böyük data növ sort
getdikcə bu gün.
>> Bütün hüquqlar.
Ki, ikinci Jennifer müvəffəqiyyəti Belə ki, alqoritm, səmimi, o qəribə etdi
də ilk dəfə, lakin edək bu uğurlar kimi yazmaq ki, biz
Bu baxımdan edə bilərsiniz.
İkinci halda, o kullanılarak geliştirilebiliyor təkrar və alqoritmi
verilən təkrar, lakin o, etdi biz icazə müəyyən ehtimal
öz, lakin o, bəzi ətraflı istismar o yox idi ki, ikinci dəfə
ilk dəfə.
Nə idi?
>> Siyahısı sorted idi.
Siyahısı sıralaması belə kimi, biz Jennifer edə idi ki, iddia
əsaslı yaxşı.
7 qapılar, bəli ki, maraqlı deyil lakin biz 7 milyon Qapı istəyirik bunu nəzərdə tutur.
N daxil mütləq gedir çox, çox yerinə yetirmək üçün
uzun vadede daha sürətli.
Amma o var idi qapıları onun üçün sıralanacaktır.
İndi bunu azadlığı etdi kompüter ekranında əvvəlcədən
Burada, lakin Jennifer Güman özü bunu etmək idi?
Fərz edək ki, sözügedən qapılarını təmsil bir verilənlər bazası məlumat, və ya
Facebook üçün qeydiyyatdan dostlar, və ya internet hər hansı bir web pages ki,
müxtəlif saytlarda oluna bilər indeks və ya üzərində axtarış.
>> Yalnız bir xammal məlumat var idi ki, Güman müəyyən və sizə qalmış, və ya
Jennifer ki, çeşidlənməsi etməliyəm?
Yəni, daha doğrusu, biz cavab tələb edir ki, sualına, yaxşı, nə qədər vaxt
Jennifer, hətta məni qəbul etdilər ki, əvvəlcədən həmin nömrələri düzmək üçün belə
O yararlana bilərlər ki?
Sağ?
Ki, ima, əlbəttə, Çünki bu düzmək üçün mənə çox bir müddət alır, əgər
the heck siz önem verir ki, kim nömrələri, qədər sürətli 50 kimi bir sıra tapa bilərsiniz,
daha Gökhan halda, sanki daha çox cəmi müddəti overwhelmed
əvvəlcədən şeyi çeşidlənməsi ilə etdi?
>> Belə ki, biz mümkün olmadıqda, Bakalým burada şəkil çəkmək.
Mən bütün dəstə daha çox stress var top, kömək edir ki, əgər
burada buz qırmaq.
Və ağla deyil ki, biz yeddi könüllü lazımdır -
OK, haqqında.
Wow.
Beləliklə, biz sərf yoxdur masa lampaları haqqında, görünür.
Bütün hüquqlar.
Belə ki, necə qarşısında iki haqqında.
Geri iki uşaqlar necə haqqında.
Belə ki, dörd var.
Necə haqqında qarşısında beş, altı və yeddi.
Sağ var.
Sizin dost, siz işarə oldu belə ki, mükafat almaq.
>> Bütün hüquqlar.
Up Hadi.
Və niyə biz sizə yoxdur uşaqlar üzərində burada gəlir.
Mən sizə hər bir sıra gedirəm.
Və irəli getmək və özünüzü təşkil eynilə nə üçün
ekranda təsvir etmişdir.
>> [SƏSLƏRİ INTERPOSING]
>> DAVID J. Malan: Oop, sorry.
Bug.
Bütün hüquqlar.
Yaxşı, burada biz gedin.
Sayı beş.
Altı nömrəni.
Bir, iki, üç, dörd, beş, altı, yeddi.
Oh, bu yöndəmsiz.
>> HOPARLÖR 2: Mən yalnız bir almaq lazımdır -.
>> DAVID J. Malan: Yaxşı iş.
Bütün hüquqlar.
Qoşulduğunuz üçün təşəkkür edirik.
>> [Alqış]
>> OK.
Bütün hüquqlar.
Beləliklə, biz, dörd, iki, altı var bir, üç, yeddi, beş.
Biz yeddi könüllü belə mükəmməl Burada eni bərabər olan
biz oynayırıq ki, array əvvəllər ilə.
Və mən səbəblərdən yeddi seçdi olacaq, yalnız
bir az rahat.
Və mən ilk təklif gidiyorum ki, biz bu yeddi könüllü Sıralama.
Siz ilk istəyirsinizsə baxmayaraq salam. demək
Bu olacaq-ci ildən yöndəmsiz bir neçə dəqiqə.
Özünüzü tətbiq edilməsi.
>> GRACE: Salam, mən Grace edirəm.
Mən Leverett House bir sophomore edirəm.
>> BRANSON: Salam.
Mən Branson edirəm.
Mən Weld bir birinci oldum.
>> Gabe: Salam.
Mən Gabe edirəm.
Mən Cabot kiçik edirəm.
>> NEIL: Mən Neil edirəm.
Mən Matthews bir birinci oldum.
>> JASON: Mən Jason edirəm.
Mən Greenough bir birinci oldum.
>> MIKE: Mən Mike edirəm.
Mən Grays bir birinci oldum.
>> Jess: Mən Jess edirəm.
Mən Leverett bir sophomore edirəm.
>> DAVID J. Malan: Əla.
Bütün hüquqlar.
Yaxşı, bizim bütün təşəkkür edirik İndiyədək burada könüllü.
Və əl-da problem indi gedir Bu uşaqlar düzmək üçün ola bilər, lakin sonra
biz bir az düşünmək lazımdır olacaq necə səmərəli Biz, həqiqətən, haqqında ağır
onlara çeşidlənir.
Belə ki, ilk bu cəhd edək.
Siz uşaqlar bir-birinin nömrələri görə bilərsiniz yalnız guşələrindən ətrafında yerləşdirilməsi ilə.
Irəli getmək və bir neçə saniyə almaq və Sıralama kiçik üzərində edin
doğru ən böyük qalmadı.
Gedin.
>> OK.
Yaxşı.
Ki, həqiqətən darn sürətli idi.
İndi burada kimsə alqoritmi nə idi Bu uşaqlar tətbiq ki?
>> HOPARLÖR 1: böyük ən.
>> DAVID J. Malan: OK.
Böyük ən az həqiqətən növ edir obyektiv, amma ki əmin deyiləm
həqiqətən bir alqoritmi.
Böyük ən az demək deyil Mənə nə addım-addım.
Bəli?
>> HOPARLÖR 1: [işitilemez]
>> DAVID J. Malan: OK.
Sizdən daha bir şəxs kiçik görmək Belə ki, əgər Nömrənizi, sonra hərəkət
onların hüququ.
Belə ki, indi daha ifadəli əldə daha alqoritmi kimi, çünki
o, bu halda, demək olar.
Beləliklə, biz bir növ var şərti tikinti.
Və bu uşaqlar ki, bir neçə etmək görünürdü dəfə, siz bəzi bir az köçürülüb, çünki
bir məsafə.
Belə ki, ehtimalla bir növ var idi onların şüurunda gedən loop.
>> Amma o rəsmiləşdirmək üçün cəhd edək.
Uşaqlar geri sıfırlamak bilər bu tənzimləmə üçün.
Biz bu rəsmiləşdirmək mümkün olmadıqda, Gəlin baxın bit, və sonra sual, yalnız
Bu necə səmərəli edir?
Əlbəttə, biz çox yavaş-yavaş bu nə zaman, bu kimi yaxşı hiss olacaq
alqoritm, lakin nin görək biz əgər dəqiq addımlar bizim barmaqlarını qoymaq.
>> Belə ki, iki uşaqlar dörd və iki edir.
Və ya doğru və ya yanlış qaydada?
Aydındır səhvdir.
Beləliklə, biz dəyişdirildikdə.
İndi kənara hərəkət etmək gidiyorum burada dörd altı, deyirlər.
Əgər doğru və ya yanlış edirsiniz?
>> Gabe: Doğru.
>> DAVID J. Malan: Doğru.
Altı və bir?
Xeyr.
Swap.
Belə ki, iki svop var.
Altı və üç?
Xeyr.
Swap.
Altı və yeddi?
Yaxşı görünür.
Yeddi və beş?
>> Jess: [işitilemez]
>> DAVID J. Malan: OK, dəyişdirmək.
Və çeşidlənir.
Bütün hüquqlar.
Belə ki, açıq-aydın deyil, sağ?
Belə ki, daha orada gedirdi.
Lakin, həqiqətən, bu uşaqlar, hətta yalnız qeyri-iradi.
hərəkət saxlanılır.
Onlar yalnız bir dəfə, dayanmadı onlar bir problem düzəldilməlidir.
Belə ki.
Həqiqətən, Mən gedirəm eyni şey.
Mən geri geri düzmək üçün gidiyorum Bu problemin əvvəlinə,
və ya bu sıra əvvəlində insanlar, onlara zəng başlamaq edək.
>> İndi nə olmalıdır mənim alqoritmi ikinci pass olmaq?
>> HOPARLÖR 1: eyni şey.
>> DAVID J. Malan: eyni şey.
Və bu, mən sağ, istəyirəm baþlýyorum?
Özünüz bunu tapa bilərsiniz tezliklə eyni şey təkrar, var
daha alqoritmi kimi olmaq və daha az insan instinkt.
>> Belə ki, indi, burada biz yenə getmək.
Iki və dörd?
No
Dörd və bir?
Ah, bəzi həqiqətən var idi ediləcək hələ çalışır.
Üçün üç?
Yaxşı.
Dörd və altı?
Altı və beş?
Altı və yeddi?
OK, indi aparılır.
OK, no.
Mən geri getmək üçün var.
>> Belə ki, indi yenə biz bu yapýyorsun bir az daha qəsdən.
İndi, yalnız bir beyin var Bu alqoritm həyata.
Bir CPU, Siz.
Və səmimi, yeganə mənbə var biz imkanına malik olacaq.
Və bir dəfə biz klaviatura geri yoxdur və C kimi bir şey
atılması, biz yalnız bir proqram yazıyorsanız ki, bir zaman bir şey edə bilərsiniz.
Bir an əvvəl bu uşaqlar Halbuki, biz kullanılarak geliştirilebiliyor onların kollektiv brainpower
uşaqlar həftə sıfır ilə nə kimi.
Belə ki, bunu davam edək.
>> İki və bir.
Iki və üç.
Üç və dörd.
Dörd və beş.
Beş və altı.
Altı və yeddi.
Bitti?
Beləliklə, mən deyiləm, lakin mənə oynamaq edək Şeytanın vəkili.
Mən, kompüter Sıralama olan yalnız Bu array vasitəsilə ötürmə etdi
insanlar, mən bitirdim ki, bilirsinizmi?
>> HOPARLÖR 1: Xeyr
>> DAVID J. Malan: Belə ki, niyə?
Mən üçün nə etmək olardı Mən görülən edirəm ki, qəti qənaətə?
Yəqin ki, daha bir keçir.
Sağ?
Çünki əvvəlki bilirik bütün pass bir səhv korrektə edir.
Və o deməkdir ki, bəlkə var hələ də başqa səhv
Mən düzəltmək lazımdır.
Belə ki, mən yalnız rewinding ilə əmin ola bilər, bilər sonra, nəzarət bir-iki, iki və
üç, üç və dörd, dörd və beş, beş və altı, altı və yeddi.
OK, indi heç bir iş etdi.
>> Mən, əlbəttə, Mən heç etdi ki, yadda bilər bir dəyişən kimi bir şey ilə işləmək
bir int kimi.
Bu svop zəng və svop bir dəfə 0 əgər burada almaq və sonra, 0 başladı
Mən davam axmaq olardı geri və irəli, yenidən yoxlanılması və
yenidən və yenidən, sağ?
Bəzi ilə takılıyorum Çünki sonsuz loop növü.
0 svop var Belə ki, tezliklə biz ki, bu tələb edə bilər
alqoritm həqiqətən sona çatdı.
>> İndi bu barədə bir ad qoymaq bildirin.
Mən yalnız biz təklif alqoritmi bubble deyilən bir şey həyata keçirilir
mənada kimi tanınan sort ki, böyük cür ki, nömrələri
qədər üst bubble yol, və ya ədəd serialın sonuna.
Amma bu alqoritm necə səmərəli oldu?
Mən fiziki Neçə addımlar var idi Bu düzmək üçün, məsələn, almaq
yeddi insanlar?
>> Dörd-beş?
OK, çox sonda edir cavab olacaq.
Lakin, sonra xüsusi sayı qədər maraqlı deyil.
İT n kimi ümumiləşdirmək edək.
Burada insanlar N, və onlar ki, əgər at təsadüfi qaydada növ idi
ki, orijinal məqsədilə başlayan.
Yaxşı, nə qədər addımlar var idi ilk pass almaq üçün?
Bu, bir, iki, üç, dörd, beş idi belə altı, onlar yeddi nəfər istəyirik,
ki, altı yeddi var -, n var, belə ki, minus bir ilk dəfə addımlar.
>> İndi neçə addımlar var idi Mən rewound zaman etmək olar?
Bəli, biz həqiqətən iki dəfə arta bilər ki, əgər biz, həqiqətən istəyirdim, amma indi üçün, Ben
yalnız, bütün sağ demək gedir başqa n mənfi 1.
Belə ki, n mənfi 1 almaq üçün gedir takip annoying, belə edək
az up dəyirmi.
Belə ki, 2n addımlar.
Belə ki, 14 addımlar, vermək və ya almaq.
>> Mən neçə dəfə almaq idi bir addım növbəti dəfə?
Bəli, bu Zadaça 3n var.
həqiqətən.
İndi, ən pis halda, üçün Məsələn, neçə dəfə mən var ki,
geri və irəli, geri və irəli getdi dəyişdirmə, bu alqoritm həyata
hər pass insanların təxminən?
Bu, faktiki olaraq, sağ kvadrat n var?
>> Ən pis halda, siz cür bilər, çünki daxilən bu barədə düşünürəm,
bir az ola bilər, baxmayaraq ki, da batmağa vaxt bit
Ən pis halda, hansı ki, bu yeddi adam kimi baxdı
müqavilənin şərtləri onların nömrələri?
Tamamilə geri, sağ?
Və yalnız ki, biclik Adınızı yenidən nə idi?
>> MIKE: Mike.
>> DAVID J. Malan: Mike?
OK, Mike, yalnız mənə artıq qoşula bilər burada yalnız bir ikinci üçün?
Əslində, yox.
Bağışlayın Mike, alaq geri.
Adınız ne yenidən?
>> NEIL: Neil.
>> DAVID J. Malan: Neil.
OK, Neil, siz ilə gəlmək mənim, sənin ağla deyil əgər.
Beləliklə, mən yalnız təklif gidiyorum sadəlik ki, Neil onun indi
ən pis halda mümkün.
Amma həyata necə xatırlayıram mənim alqoritmi.
Mən müqayisə müqayisə müqayisə alıram oh, müqayisə, müqayisə.
İndi bu uşaqlar həyata sifariş, mən düzeltmek.
Belə ki, uşaqlar Swap.
Amma nə qədər uzaq, indi hesab Neil getmək var?
Bu təxminən n oldu.
Bilirsiniz, bu, həqiqətən n deyil.
Bu kimi, n mənfi 1, amma alıram ki, az rahatsız saxlanması track
sayı, elə yalnız N zəng edək.
>> Neil maksimum bir addım hər hərəkət Belə ki, əgər vaxtı və Neil bir addım hərəkət etmək üçün,
Mən bu həqiqətən yorucu pass etmək lazımdır geri və irəli, bu kobud deyil
Bunu, n addımlar, n dəfə cəmi, mənə etmək niyyətindədir, çünki
çox addımlar Neil bütün almaq üçün o aid olduğu yol.
Başqa hər kəs tək edək uşaqlar əgər bütün yaxşı pis əmri verildi.
>> Elə bubble sırala n kvadrat zəng edək.
Bu alqoritm çalışan zaman, Bu alqoritm performans
Bu alqoritm səmərəliliyi, biz daha çox təsvir edir
n kvadrat ümumiyyətlə kimi.
Mən bilər, çünki ki, gözəl deyil səkkiz nəfər, doqquz ilə eyni misal
insanlar, bir milyon adam ki, cavab dəyişmək niyyətində deyil.
>> Uşaqlar ağla deyil əgər Belə ki, edək Siz açılmış harada sizi yenidən.
Və edək iki digər yanaşmalar cəhd biz əsaslı edə bilməz görmek
Bu daha yaxşı.
Bu dəfə Beləliklə, mən təklif etmək gidiyorum müxtəlif alqoritm bir növ.
Ki, keçən dəfə bizdən çox ağıllı idi və uşaqlar üçün sağ idi
yalnız növ sağ instinktlərdən pairwise dəyişdirmə edir.
Amma həqiqətən bu yaxınlaşmaq istəyirdi sadəcə, mənim məqsədi hərəkət etmək
kiçik nömrələr bütün bu yolu və ki, böyük nömrələr bütün təkan
yol, niyə yalnız ki, yoxdur ən yolu mümkün sadəlövh və görmək əgər mən
bir nə daha yaxşı edə bilərsiniz olduqca kompleks alqoritmi?
>> Elə görək.
Dörd olduqca az sayda, belə ki, mən orada an tərk edəcəyik.
Ooh, sayı iki hətta daha yaxşıdır.
Belə ki, yalnız irəli addım edə bilərsiniz bir an üçün?
Bu, hazırda mənim kiçik nömrələnmiş namizəd, mən yadda gidiyorum
ki, bir dəyişən kimi, ilə.
Amma yoxlanılması saxlamaq üçün gedirəm.
Olan kimsə var nömrə kiçik?
Altı, no.
Oh, yenə Neil var.
>> Mən sizə geri itələmək üçün gidiyorum Sıralama konseptual edir.
Neil irəli gələcək.
İndi, mən dəyişən istifadə alıram ki, kiçik olan takip
sayı üçün yenilənir Neil yer.
Yaxşı, gəlin görək.
Üç, yeddi, beş.
OK, mən Neil kiçik idi.
Sadə şey nədir Mənim üçün indi nə etməli?
Mən yalnız mənim vaxt sərf etmək fikrində deyiləm sol Neil bir ləkə burda.
Niyə yalnız Neil qoymaq deyil o aid, hansı yerləşir əlbəttə var?
>> Əvvəlində bütün yol.
Neil Belə ki, mənimlə gəlir.
Və adı daha nə idi?
>> GRACE: Grace.
>> DAVID J. Malan: Grace.
OK.
Grace Belə ki, təəssüf ki, sen yolu cür.
Belə ki, necə biz bu problemi həll edir?
Sağ?
Bu bir sıra deyil, var yalnız yeddi yer.
Rob ilə Xatırladaq ki, biz danışdıq yaş elan və biz yalnız idi
yaş məhdud sayı?
Burada eyni fikri.
Biz yalnız ints bir məhdud var.
Grace bizim növ edir yol, biz necə düzeltirim?
>> Ən sadə yolu kimi deyil Grace, sorry.
Siz artıq getmək olacaq belə ki, biz var edə bilərsiniz.
İndi, bəlkə bu barədə düşünüyorsanız Biz yalnız problem pis etdi.
Və bəlkə biz nə, çünki Grace doğru yerdə idi?
Amma biz o, çünki deyil bilirik başqa, o, olardı
irəli daimi yerinə Bu zaman Neil, sağ?
Biz artıq onun həyata yoxlanılır.
>> Bütün hüquqlar.
Belə ki, indi, Neil doğru yerdə var, Mən bir qədər optimallaşdırılması edə bilərsiniz.
Növbəti dəqiqə, mən ignore gidiyorum Belə kimi birlikdə Neil bütün
onun vaxt sərf, və ya təsadüfən səhv yerdə onu dəyişdirmək.
Belə ki, indi, necə növbəti tapa bilərəm kiçik ki element?
Iki.
Əgər ki, çox yaxşı sıra Əgər irəli addım və istəyirəm
Mən sizə yadda lazımdır.
Altı, heç bir yaxşı.
Dörd, üç, yeddi, beş, heç bir yaxşı.
Beləliklə, siz məni hərəkət edək sağ yer.
Və biz yalnız bu dəfə uğurlu var.
>> İndi bu ignore gidiyorum iki uşaqlar, indi bir daha çox
bu keçir.
Altı ki, olduqca kiçik.
Irəli Hadi.
Oh, sorry.
Grace nömrəsi, daha yaxşıdır belə irəli addım.
Dörd.
Bağışlayın, Grace.
Yenidən geri gedin.
Sayı üç yaxşıdır.
Yeddi.
Beş.
İndi adınızı yenə nə var?
>> JASON: Jason.
>> DAVID J. Malan: Jason.
Belə ki, Jason indi kiçik element mən seçtiniz.
O hara gedir?
Beləliklə, harada altı edir.
Və adı yenə?
>> Gabe: Gabe.
>> DAVID J. Malan: Gabe.
Gabe yolu var.
Etmək asan şey nədir?
Bu iki uşaqlar Swap və davam edir.
Belə ki, indi görək.
Kim kiçik var?
Dörd.
Mənə etmək yalnız cür edək.
Beş kiçik olacaq.
, Siz addım istəyirsinizsə mən növbəti tapmaq irəli, mən nə var
Gabe bu uşaqlar?
Daha Swap.
Belə ki, indi, hələ bir qədər sifariş out.
Mən Gabe ki, kiçik hesab Mən onu həyata pop uşaqlar üzərində hərəkət.
Və etdik.
>> Belə ki, cavab eyni.
Son nəticə eynidir.
Bu iki alqoritmlərin hansı daha yaxşıdır?
İkinci, mən eşitdim.
Niyə?
>> HOPARLÖR 3: Bu addımlar [işitilemez] N oldu.
>> DAVID J. Malan: Bu ən n addımlar var.
Maraqlı.
Belə ki, olsa?
Belə ki, necə mən almısan kiçik element?
Neçə addımlar mənim üçün idi Bu kiçik element tapmaq?
Mən bütün yol baxmaq idi sonunda, sağ?
Ki, ən pis halda, nə Çünki Neil burada olsaydı?
Belə ki, yalnız ən kiçik element tapmaq Mənə n addımlar, və ya n mənfi 1 edir.
Lakin, OK.
Belə ki, Neil düzeltmek.
, Bir dəqiqə və ya belə əvvəl unutmayın.
>> Amma necə Mən növbəti almısan kiçik element?
Bu n mənfi 1, və ya n minus həqiqətən 2, var addımların sayı.
Belə ki, OK.
Belə ki, I 2 minus n idi.
Bütün hüquqlar.
Belə ki, bir az daha yaxşı hiss edir.
Bütün hüquqlar.
Növbəti dəfə Neçə addımlar sayı üç tapmaq olar?
Belə ki, n minus 4.
Belə ki, bir az azalması oldu hər iteration addım.
Beləliklə, bu, doğru daha yaxşı hiss etmir?
Sonuncu dəfə isə, təxminən n dəfə n oldu bu dəfə n mənfi 1, üstəgəl n minus var
2, üstəgəl n mənfi 3, üstəgəl n mənfi 4, nöqtə, nöqtə, nöqtə.
Amma siz lisey geri əgər dərsliklər, kiçik fırıldaqçı
düsturlar var ki, arxa hesabatı, əgər siz ədəd bu seriyası əlavə
addımlar ümumi sayı nə Burada almaq olacaq?
>> Bu, o biri kimi, n mənfi 1, 2 bölünür dəfə n.
Beləliklə, mən çəkmək olar, əgər mənə görək yalnız bir an üçün bu qədər.
Və yenə, mən yuvarlaqlaşdırma cür bəzi Ben ədəd yalnız bizim həyat sadə saxlamaq üçün
amma xatırlayıram kimi, əgər belə bir şey var Mən sonra, n mənfi 1 şeylər n minus
2, sonra n mənfi 3, bu təxminən var 2-dən artıq bu kimi bir şey, və əgər mən
Bunu çoxaltmaq ki həqiqətən n kv.
Bu çox yaxşı hiss deyil. 2-dən artıq n minus n.
>> Amma burada bir şey var.
Informatika, problemləri zaman n zaman maraqlı almaq üçün başlayın
həqiqətən böyük olur.
Və n həqiqətən böyük olur zaman, hansı bu dəyərləri bütün hakim gedir
başqaları?
Bu, sağ kvadrat n növü var?
Bəli, 2 ayırıcı olduqca yaxşıdır.
Amma milyardlarla bəhs edirsinizsə, məlumatların ədəd və ya trilyonlarca
məlumatların ədəd, OK, belə ki, iki dəfə kimi sürətli istəyirik.
Lakin, həqiqətən, böyük sayı əgər umurunda Bu amil olur nə varsa,
daha böyük və daha böyük.
Və şübhəsiz ki, bu, daha çox edir Bu adam daha fərq.
Uşaqlar sağ belə baxmayaraq, ikinci alqoritm, biz zəng edəcəyik
seçim sort, real dünyada, bir bit sürətli potensial, mən deyiləm, çünki
alaraq daha az və az hər dəfə addımlar.
>> Bu, həqiqətən əsaslı sürətli deyil.
Çünki həqiqətən bu həyata oynamaq əgər sonunda n böyük dəyərlər,
gün böyük kifayət n üçün, hələ də var olduqca yavaş hiss edəcəyik.
Yaxşı, mənə bir qoy ki, son keçir.
Mən zəng nə var seçim növ.
Uşaqlar özünüzü yenidən qura bilərsiniz son bir dəfə?
Və bu son halda, gedirəm nəyisə
durub sırala çağırıb.
Durub sort olan konseptual, bir az fərqli.
>> Geri və irəli gedən və daha çox ən kiçik element seçilməsi, Ben
yalnız bu hər biri ilə məşğul olacaqlar Mən onları qovuşana və Insert kimi uşaqlar
onların düzgün yer daxil.
Beləliklə, mən yalnız, Grace ilə başlamaq üçün gidiyorum və mən o dörd nömrəni ki, görürük.
Sayı dörd harada aid edir?
Mən bir şey çeşidlənməsi açılmış yoxdur belə Grace orada qalmaq olur.
Siz ola bilər, əgər İndi, iddia gidiyorum Bu, doğru bir addım atmaq
Mənim sorted siyahısı, bu mənim deyil, çeşidlənməmiş qalan siyahısı.
Belə ki, indi mən gələn davam üçün gidiyorum və adı nə yenidən?
>> BRANSON: Branson.
>> DAVID J. Malan: Branson.
Belə ki, Branson sayı iki.
Beləliklə, mən sizi gidiyorum bir an üçün.
İndi, siz məxsusdur Bu sıra?
Belə ki, lütf sağ.
Belə ki, yenə edilməsi cür istəyirik Grace burada bir çox iş yoxdur.
Biz sizə harada qoymaq edirsiniz?
Belə ki, biz sizə uçmaq olacaq sol və orada Branson daxil edin.
Amma indi iddia edir ki, Uşaqlar edilir.
Ancaq xəbərdarlıq, mən əlavə yer istifadə deyiləm.
Bu hələ 2 elementləri var burada, buraya 5.
Ümumi array ölçüsü 7, belə ki, mən bütün hüququ, aldadıcı deyil?
>> Belə ki, indi biz, burada Gabe ilə var altı nömrəni, harada aid edirsiniz?
Siz daha şanslı var.
Belə ki, orada qalmaq almaq.
Yalnız doğru bir kiçik addım atmaq yalnız sıralaması etdiyiniz aydın etmək.
İndi biz yenə sayı Neil var bir, siz hara gedirik?
Olduğunu görürük başlayacaq lazımdır və indi baxmayaraq ilk bu alqoritm,
nəzər olduqca ağıllı hiss baxmaq baş haqqında budur.
Əgər irəli addım bilər.
>> Biz Neil qoymaq istəyirsiniz?
Belə ki, açıq-aydın burada, belə ki, necə biz Neil alıram?
Bu addım-addım edək.
Siz getmək lazımdır harada Gabe?
Yep, belə ki, böyük bir addım və ya iki yarım addımlar etmək
orada bir addım.
Siz getmək harada Grace?
Yaxşı.
Bir addım belə.
Və nəhayət, Branson?
Başqa bir addımdır.
Və indi biz yer Neil qoya bilər.
>> Belə ki, indi bu məntiqlə davam edir.
Biz Neil dəyişkən deyil baxmayaraq üzərində və üzərində və onu qoymaq üçün
O, ən pis halda, gedir ki, Biz qarşılaşa bilər növbəti sayı ola bilər
sayı ola, demək, bir sıra var idi sıfır, sonra biz bütün keçmək olacaq
Bu uşaqlar.
Bir sıra mənfi var ki Güman bir, sonra biz keçmək lazımdır
bu uşaqlar bütün.
Beləliklə, biz həqiqətən Flipping yalnız cür istəyirik biz istəyirik ki ətrafında problem,
olan hesabına köçürdükdən Seçim prosesi belə durub
Uşaqlar yalnız idi ki, bu cür prosesi, təxminən n mənfi bir şey hərəkət etmək üçün
addımlar sayı.
Və addımlar ki sayı yalnız gedir Mən daha nömrələri seçmək kimi artırmaq,
Mən sizə uşaqlar shoving saxlamaq lazımdır, əgər geri və geri və geri.
>> Belə ki, kədərli şey indi bu bütün alqoritmləri kvadrat n.
Gəlin irəli getmək və şükür bunların uşaqlar, və bu bir az görüntüləmək
fərqli.
Çox yaxşı.
>> [Alqış]
>> Bütün hüquqlar.
Burada gedin.
Üçün təşəkkür edirik -
>> BRANSON: [işitilemez] nömrələri saxlamaq.
>> DAVID J. Malan: Xeyr, siz habelə nömrələri saxlamaq.
Bütün hüquqlar.
Qəşəng edilir.
Bütün hüquqlar.
Beləliklə, biz artıq yekunlaşdırmaq mümkün olmadıqda Bakalým daha sürətlə və daha çox vizual,
dəqiq nə oldu Burada aşağıdakı kimi.
Mən irəli getmək gidiyorum və Firefox qədər çəkin.
Biz bu nümayişin keçid olacaq Kursun saytında.
Java iş almaq üçün bir az rahatsız edici deyil bəzi brauzerlərdə bu gün.
Evdə bu ilə oynamaq yoxdur Belə ki, Firefox istifadə etmək lazımdır bilər həyata
iş almaq üçün.
Və nə mən bu ilə gedirəm nümayiş aşağıdakı kimidir.
>> Altında, mən bütün dəstə var bir başlanğıc və o cümlədən menyu variantları,
düyməsinə dayandırmaq.
Həmçinin, bir kənara kimi, müşahidə bu proqramlara səhv, siz vasitəsi
əslində başlanğıc və ya dayandırmaq bilməz sizə əmr və ya Alt Tut 'düyməsinə halda
plus və zoom ilə, hansı işin daha çox düymələri göstərir.
Oynamaq Belə Bilginize Bu evdə.
İndi yalnız bir Start basın gidiyorum an, bir gecikme ifadə sonra,
, burada 200 ms kimi yalnız belə ki, biz nə görürük.
>> Beləliklə, mən bu vizual olduğunu iddia ilk alqoritm
Bu uşaqlar bubble sort, vasitəsi etdi biz insanların cüt-müdrik dəyişdirildikdə.
Bu görselleştirme üçün əsas fikir ki, bar boyu
sayı ölçüsünü təmsil edir.
Ki taller bar Belə ki, böyük nömrəsi.
Qısa bar, sayı kiçik.
Fark əgər, biz vasitəsilə olacaq Bu alqoritm ilk iteration,
ki, böyük və kiçik ədəd dəyişdirmə kiçik sayı ilk və gəlir
böyük sayı doğru gedir.
>> Və tezliklə biz serialın sonuna almaq kimi yeddi-dən çox ədəd, biz istəyirik
əvvəlinə geri gedir.
Bu təxmin edirik.
Uzaq sol, kiçik oğlan gedir yan dəyişdirmək, və bu
prosesi təkrar.
İndi bu vizual tez olur qazma, mənə davam və dayandırmaq bildirin
bu, çox gecikmə bir şey dəyişmək daha sürətli, yalnız indi üçün bir fikir almaq üçün
Bu alqoritmi.
>> Mən bunu sürətləndi etdik Belə olsa da, bu alınması, mənim prosessor təkmilləşdirilməsi kimi
yeni kompüter.
Mən əsaslı dəyişməyib mənim alqoritm, ancaq həqiqətən daha çox edə bilərsiniz
aydın insanlarla daha çox ki, böyük ədəd, üst qədər burda olunur
və kiçik nömrələri burda olunur aşağı alt.
İndi bu şey burada sıralanır.
Və bir kənara kimi, meydanlarda var orada yalnız bir mühasibat
, nə çox müqayisə saymaq kömək və ya neçə svopları var
həqiqətən böyük işlər görülmüşdür.
>> Yaxşı, biri edək digərləri gördük.
Məni bura bubble sırala basın edək və Mənə seçin bildirin və bu, bütün web page
bir az arabası var.
Nin risk qəbul etsin və yenidən axır.
Orada biz gedin.
Belə ki, seçim sort nə edək.
Bilmirəm niyə menyu orada görünür.
Ki, düzeltmek üçün bir-zoom edək bug, 50 dəyişdirə.
Ah, həqiqətən nə edək çox daha sürətli edir.
Beş ms və ya, və Başlat seçin.
>> Belə ki, bu seçim sortudur.
Belə ki, yenə nə haqqında düşünmək burada insanlar qədər idi.
Biz serialın ilə getdi və seçilmiş daha kiçik element,
və yenidən və yenidən.
İndi mən hələ olduqca pis olduğunu iddia edirlər.
Bu hələ kvadrat N edilib, vermək və ya almaq lakin bu bir az real dünyada idi,
daha sürətli, Mən, həqiqətən, alaraq, çünki hər dəfə addımlar biraz az.
Lakin biz yalnız nə söhbət edirik?
Burada bəlkə 40 və ya belə barlar?
Biz 40 milyon söhbət deyilik.
Belə ki, tamamilə mənə aydın deyil ki, həqiqətən əhəmiyyətli bir gəlir idi.
>> Mənə indi geri və dəyişdirmək edək seçin olan üçüncü alqoritmi,
durub növ.
İndi həqiqətən arabası var, çünki menyu həqiqətən orada olmamalıdır.
Belə ki, indi biz burada geri hərəkət edəcəyik və bu alqoritm başlayın.
Bağırtı, başlamaq və dayandırmaq.
Belə ki, bu bir növ bir çox model var bu, qovuşdurmağımız yenə istəyirik
insanların daxil, və ya Bu halda barlar daxil
onların müvafiq yer.
Və artıq əvvəl həyata Mən ətrafında çevrildi.
Amma bu, çox, nəzəri, hələ kvadrat n.
>> Beləliklə, biz ümumiləşdirmək mümkün olmadıqda Bakalým Bu aşağıdakı kimi.
Mən irəli getmək və yalnız verəcəyəm söhbət ortaq bir yol bizə sort
Bu şeyləri, mənə təqdim etsinlər burada notation yalnız bir bit.
Siz böyük bir şey adlı görmək üzeresiniz O, sözün çünki böyük
O. Bu bir kompüter bir yoldur alim və ya hətta istifadə edir riyaziyyatçı
çalışan zaman təsvir etmək bəzi alqoritmi.
Faktiki Kaç addımlar edir?
>> İndi mən özümü xəcalətli gidiyorum burada yalnız bir anda mənim yazı.
Amma mənə davam və deyirlər ki, qoy Bu burada böyük O olacaq.
Və mənə bir başqa tətbiq edək simvolu kapital Omega.
Omega, qarşı olacaq mahiyyətcə, böyük O Halbuki böyük O. üzrə
vasitələri, ən pis halda, nə qədər vaxt bəzi alqoritmi ilə, bilər
n baxımından, omega gedir nə qədər vaxt güc olmaq
ən yaxşı halda edir.
Və biz biz demək nə görürsünüz yalnız bir anda, ən yaxşı halda.
>> Belə bir şey sadə başlamaq edək.
Mənə bir xətti axtarışı ilə başlamaq edək.
Belə ki, çeşidlənməsi deyil.
Biz bu xətti axtarış arayacaðým.
İndi bir az etmək Bu masa.
İndi, xətti axtarış halda, ən pis halda, nə qədər addımlar
bir tapmaq üçün mənə etmək niyyətindədir ixtiyari seçim sayı?
Və N Toplam qapı var və ya n ümumi sayı.
Ən pis halda.
Neçə addımlar mən üçün gedirəm bir sıra sayı 50 tapmaq üçün almaq
n Qapı?
Və niyə?
Bütün ola bilər, çünki sonunda üzərində üzərində yol.
Jennifer rast O qədər çox kimi, sayı 50-belə, bütün yol üzərində idi
ən pis halda xətti axtarış n böyük O, biz demək lazımdır olunur.
>> Nə yaxşı halda haqqında həqiqətən xoşbəxt almaq əgər?
Bu, sadəcə, bir addım olacaq addımlar və ya sabit bir sayı.
Beləliklə, biz 1 kimi təsvir edəcəyik.
Belə ki, bu olduqca yaxşıdır.
İndi biz bir şey nə idi əgər binar axtarış istəyirsiniz?
Ən pis belə ikili axtarış , iş etdi nə qədər vaxt?
>> [SƏSLƏRİ INTERPOSING]
>> DAVID J. Malan: Belə ki, həqiqətən, mən bir neçə yerdə eşitdim.
Belə ki, həqiqətən, n daxil olmaq və vermək və ya almaq oldu biz yarısında siyahısı bölmək çünki
yenidən və yenidən və yenidən, biz edirik Nəticədə, tapmaq üçün, dəyəri,
orada, ancaq bir kapsayan vardır.
Biz ki, ehtimal nədir binar axtarış verilən almaq?
Bu sıralanır var.
Bu sorted deyil, siz şey ayıra bilərsiniz yeniden yarım, və
tərk edə bilərsiniz və siz doğru getmək bilər, Siz sol və sağ getmək bilərsiniz, ancaq istəyirik
element, əgər tapmaq niyyətində deyil siyahısı sorted deyil, çünki
siz onu əldən bilər.
Sizin Heuristic Çünki sol gedən üçün ya doğru əgər qüsurlu olacaq
həqiqətən sorted deyil.
Belə bir gizli dəyəri növ var bu kimi bir şey istifadə.
>> İndi bizim çeşidlənməsi daxil bildirin alqoritmlər axtarış deyil -
oh, həqiqətən bu boş gedək.
Ən yaxşı halda İkili axtarış?
Yalnız olmaq olur, əgər O, həmçinin 1-in çox serialın ortasında, və ya
telefon kitab orta.
İndi bubble sırala nə edək.
Belə ki, daha, indi biz daxil edirik növ deyil, arar.
>> Ən pis halda, nə çox addımlar idi biz iddia bubble sırala etmək olacaq?
n kare.
Beləliklə, mən ki, cəlb gedirəm.
Ooh, mənim yazı daha pis görünür ki, böyük proqnozlaşdırılır zamanı.
Bütün hüquqlar.
Belə ki, kvadrat n oldu.
Və bubble sırala ən yaxşı halda, neçə addımlar onu gedir?
1, duydum.
>> HOPARLÖR 1: n.
>> DAVID J. Malan: n, duydum.
>> HOPARLÖR 1: 2.
>> DAVID J. Malan: 2, duydum.
3 eşidirlərmi?
Bütün hüquqlar.
Beləliklə, mən n, 2, 1 eşitdim, amma seçin edək o ayrı ən azı ilk
təkliflər, 1.
Bu, çünki pis instinkt deyil cür burada bir model aşağıdakı.
Amma bu, yalnız necə 1 addım sürsə dünya Mən iddia edə biləcək siyahısı
Mən yalnız icazə alıram, çünki, çeşidlənir 1 addım, neçə elementləri etmək
Mən, həqiqətən, kontrol bilər?
Bəli, yalnız 1, hansı n var deməkdir mənfi 1 elementləri ola həyata bilər
üçün, və yalnız sonra iman gedirəm 1 element baxaraq ki,
şey çeşidlənir.
Burada doğru deyil 1 belə.
Belə ki minimal, neçə Mən baxmaq var?
>> [SƏSLƏRİ INTERPOSING]
>> Həqiqətən n mənfi 1, və ya,: DAVID J. Malan n, hər baxmaq lazımdır, çünki
əmin olun element bu qaydada deyil.
Ancaq yenə də, biz dalğa bizim sort olacaq kiçik nömrələri əlləri və
n böyük olur kimi, onlar istəyirik, güman hər halda maraqsız.
Belə ki, bubble sırala var.
İndi, bu son iki nə edək.
Sonra seçim sort və biz edəcəyik durub sort yoxdur.
Və sonra biz əsəcək çox şey şüurunda
bütün bunlar daha yaxşı.
Bütün hüquqlar.
>> Çalışan ən pis halda nədir seçim növ vaxt?
>> HOPARLÖR 4: n kvadrat.
>> DAVID J. Malan: n kvadrat, mən eşitmə alıram.
Amma niyə n daxilən, kvadrat?
>> HOPARLÖR 4: biz yalnız Çünki.
>> DAVID J. Malan: biz yalnız Çünki.
OK.
Cavab Yaxşı.
Amma daxilən, niyə seçim deyil sort n kvadrat?
Biz nə oldu təkrar?
Biz vasitəsilə tarama saxlamaq idi Siz kiçik, siz var
kiçik, siz kiçik var.
Və verilmiş, biz n edə idi addımlar, sonra n sonra mənfi 1, n minus 2.
Amma cür bu bütün əlavə əgər, və ya əlavə etdiyiniz iman onu
əvvəlcədən onları, biz n qaba almaq bəzi kiçik ədəd minus kvadrat.
Mən bu n kvadrat zəng etmək üçün gedirəm.
Amma ən yaxşı seçim növ ilə halda, necə bir çox addımlar
Mənə etmək niyyətindədir?
>> HOPARLÖR 5: [işitilemez]
>> DAVID J. Malan: Bu təəssüf ki, var hələ n kare, sağ?
Mən kiçik seçilməsi alıram Çünki əgər element, və biz, burada yeddi nəfər idi
Mən yalnız bilirəm, bir dəfə mən çox almaq sonunda, ki, mən kiçik gördük
sayı, yerdə o və ya o ola bilər.
Amma necə Mən növbəti tapa bilərəm kiçik nömrə?
Başqa bir keçid var.
Belə ki, ən yaxşı halda, nə edir Seçim Sıralama girdi?
Bu artıq sort siyahısı, bir nömrəli var iki nömrəli, sayı üç, dörd nömrəni.
Amma bir kompüter edirəm.
Mən yalnız bir baxmaq olar bir anda şey.
Bir addım I sort bilməz geri bir insan və demək kimi,
ooh, bu doğru görünür.
>> Mən yalnız düzgün qərar ola bilər olan seçerek seçimi sırala
kiçik nömrəsi.
Amma bir nömrəli ilk tapmaq olsa da, Mən başqa bir şey bilmirəm, əgər
Mən olmayan digər nömrələri, bütün Mən Mən bir sıra təhvil olduğunuz bilirik ki,
olan arxasında qapı və ya bir sıra nömrələri, mən bir bilmək üçün yeganə yol
kiçik idi?
Mən burada bütün yol almaq və həyata varsa, lənətləmək, bir həqiqətən kiçik idi.
>> Amma necə sonra müəyyən yoxdur iki növbəti kiçik?
Eyni təsirsizlik edərək təkrar.
Belə ki, nəhayət, durub növ ilə, necə pis halda,
biz bunu həyata demək idi?
Bu da kvadrat n.
Və haqqında ən yaxşı halda ilə?
Biz cliffhanger kimi tərk edəcəyik.
Biz ki, boş növbəti dəfə doldurmaq lazımdır lakin ilk mənə təklif edək ki, biz
əsaslı daha yaxşı edə Bütün bunlar, bütün sağ?
>> Belə ki, özünüz üçün hesab edirəm ki, nə durub sort olacaq.
Yaxşı, ki, çox dramatik deyil Mən yalnız bir Ben çünki
ki, dəyişiklik gördüm.
Wow.
OK.
Belə ki, burada bir qədər var müxtəlif nümayiş.
Mən burada Yakınlaştırmak varsa, ki görürsünüz sol, biz də, bubble növ var
Biz seçilməsi növ var orta, və sağında, biz bir şey var, biz
hələ baxdı yoxdur Sıralama daxil çağırıb.
Amma biz olduğunuz nə hesab Bu gün indiyə qədər burada edir.
Jennifer ilk mərhələdə gündəmə gələn zaman, biz nömrələrin sıra yolu ilə getdi
yenidən və yenidən, xətti axtarış ilə, və biz böyük O, xətti çalışan zaman var
n, belə danışmaq.
>> Indi ilk həftəsində hesab zaman sinif, biz uçurum və fəth zaman,
və biz telefon kitab, qoparmaq idi və Gökhan, biz kollektiv
üçün olan kullanılarak geliştirilebiliyor əsas fikir, tərəfindən təkrar özünüzü təkrar
Elə-belə, atmaq, atmaq , atmaq problemin yarısı
Ümumiyyətlə, yarım bir problem ayırıcı, və sonra kiçik parça müalicə
konseptual ekvivalent kimi problem başqa, biz birtəhər etdi
əsaslı yaxşı.
Amma bubble sırala ilə, seçim sort, durub növ ilə, biz var ola bilər
Jennifer ki belə faydalıdır.
Biz olduqca çox yalnız geri getdi və irəli bütövlükdə dəfə dəstə və biz
tweaked şeyi bir az bit, dəyişdirmə Bu üçün, bəlkə
daxil və ya seçib.
Lakin günün sonunda, bir çox idi yöndəmsiz gəzinti geri və irəli.
Biz, həqiqətən, leverage bir şey vermədi Jennifer kimi smart bölünməsi kimi etdi
və fəth.
>> Belə növ birləşməsi, əksinə, hansı Gələn həftə qədər görmək olmaz, o gedir
leverage bölməklə əsas ideya giriş, sonra halving, sonra
halving, sonra halving.
Və loop hər iteration üzrə sol yarım çeşidlənməsi və sağ
yarım, sol yarısı sol yarısı, sonra sonra sol və sağ yarım,
sol sağ yarısı yarısı və sağ yarım hüququ yarısı.
Və təkrar təkrar.
>> Belə ki, vizual görürük, lakin bu olacaq Gələn həftə bizi gözləyir budur.
Ümumiyyətlə, biz bir az düşünmək hər hansı belə problem az çətindir.
Biz sol kvadrat n, n var ortada kvadrat və n
sağ n daxil ol.
Belə ki, real cliffhanger var.
Biz bazar ertəsi görəcəksiniz.
>> [Alqış]