[Powered by Google Translate] [Bölmə 3 - Daha Rahat]
[Rob Bowden - Harvard Universiteti]
>> [Bu CS50 edir. - CS50.TV]
>> Belə ki, ilk sual qəribə mətni olunur.
Gdb daha çox xüsusi bir proqram "debug", lakin imkan verir, bu nə imkan vermir?
Mən bir cavab olacaq və mən məhz gözlənilir nə bilmirəm
Mən bu xətləri boyunca onun bir təxmin edirəm siz addım-addım təmin edir
ilə qarşılıqlı, proqram vasitəsilə gəzmək, dəyişiklik dəyişənlərin, bütün bu şeylər -
əsasən tamamilə proqramı icrasına nəzarət
və proqramın icrasına hər hansı bir hissəsi yoxlayın.
Belə ki, həmin xüsusiyyətlər şeyi debug imkan verir.
Okay.
Niyə ikili axtarış bir sıra sıralanır tələb edir?
Kim ki, cavab istəyir?
[Tələbə] Əgər sıralanır deyil, əgər iş deyil, çünki. >> Bəli. [Gülüş]
O sıralanır deyil, onda yarı bölmək mümkün deyil
və sol ki, hər şeyi bilmək az və sağ hər şey
orta dəyəri böyükdür.
Belə ki sıralanır lazımdır.
Okay.
Nə kvadrat n O bubble sırala edir?
Hər kəs ilk bubble sırala nə çox tez yüksək səviyyəli xülasə vermək istəyir?
[Tələbə] Siz əsasən hər element vasitəsilə getmək və ilk bir neçə elementləri işarələyin.
Onlar sizin onları dəyişdirmək harada bitti, onda növbəti bir neçə elementlər və s yoxlayın.
Əgər sonunda çatmaq zaman, sonra ən böyük element sonunda yerləşir bilirik ki,
belə ki, bir zaman siz keçir saxlamaq ki, ignore
və hər dəfə sizə heç bir dəyişikliklər etmək qədər bir az element yoxlamaq lazımdır. >> Bəli.
Onun tərəfində array çevirmek əgər belə aşağı və, çünki bubble sırala şaquli deyirlər
sonra böyük dəyərləri alt endirmək və kiçik dəyərlər üst bubble qədər olacaq.
Bu onun adı var nə var.
Və Bəli, yalnız keçir.
Siz böyük dəyər dəyişdirmə, serialın keçir saxlamaq
alt ən böyük dəyərlər almaq üçün.
>> Nə kvadrat n Ey edir?
Birincisi, hər kəs o n O kvadrat görə demək istəyir?
[Tələbə] hər run üçün n dəfə gedir, çünki.
Siz yalnız, siz aşağı ən böyük element bütün yolu qəbul etdiyiniz arxayın ola bilərsiniz
sonra bir çox elementləri üçün təkrar var. >> Bəli.
Belə böyük O deməkdir və nə böyük Omega vasitələri nə unutmayın.
Böyük O həqiqətən çalıştırabilirsiniz necə yavaş dair bağlı yuxarı kimi.
Beləliklə kvadrat n bu O dedi ki, n Ey deyil və ya başqa run bilər
xətti vaxtında, lakin n Cubed Ey edir
o n Cubed Ey ayrılır, çünki.
Bu kare n Ey ilə həmsərhəddir edir, onda n Cubed də əhatə edir.
Belə ki, kvadrat n və mütləq ən pis halda kvadrat n daha yaxşı edə bilməz
bu kare N O nə edir.
Belə ki, n kvadrat olmaq üçün gəlir necə yüngül riyaziyyat görmək
biz siyahısında beş şey varsa, ilk dəfə neçə svopları biz potensial etmək lazımdır bilər
Bu almaq üçün? Nin həqiqətən yalnız edək -
Neçə svopları biz array vasitəsilə bubble sırala ilk run etmək üçün gedir?
[Tələbə] n - 1. >> Bəli.
>> 1 - 5 elementlər var, biz n etmək lazımdır olacaq.
Sonra ikinci bir neçə svopları biz etmək üçün gedir?
[Tələbə] n - 2. >> Bəli.
Və üçüncü n olacaq - 3, sonra rahatlığı üçün mən son iki yazacaq
sonra biz 2 svopları və 1 mübadilə etmək lazımdır olacaq.
Mən son bir və ya həqiqətən nə etmək lazımdır bilər danışarlar.
Bir svop mı? Bilmirəm.
Belə ki, bu ümumi svopları məbləğləri və ya etmək üçün ən azı müqayisə edir.
Siz dəyişdirmək bile, hələ dəyərləri müqayisə etmək lazımdır.
Belə ki, n var - serialın vasitəsilə ilk run 1 müqayisə.
Bu şeyi yeniden varsa, hər şeyi gözəl stack up belə nın həqiqətən altı şeyi edək
və sonra, 2 1 3 edəcəyik.
Belə ki, yalnız bu məbləğdə rearranging, biz etmək neçə müqayisə görmək istəyirəm
bütün alqoritm edir.
Biz aşağı burada, bu uşaqlar gətirmək əgər,
sonra biz hələ də orada idi lakin çox müqayisə cəmlənməsi edirik.
Lakin biz bu yekunlaşdırmaq və bu yekun və bu yekun əgər,
hələ də eyni problem var. Biz yalnız xüsusi qruplar edib.
>> Belə ki, indi biz 3 n-nin cəmlənməsi edirik. Bu yalnız 3 n-nin deyil.
Bu həmişə n / 2 n nin olacaq.
Belə ki, burada biz 6 üçün baş verir.
10 şeylər idi, onda biz şeyi 5 müxtəlif cüt üçün qruplaşdırılması edə
və n + n + n + n + n son.
Beləliklə, siz həmişə n / 2 n nin almaq olacaq və bu, biz n kvadrat / 2 onu jot lazımdır.
Və belə gəlmək olur ki, yarısı amil belə olsa
serialın üzərində hər iteration vasitəsilə biz 1 az müqayisə ki, çünki
belə ki, 2-dən çox almaq necə, ancaq hələ kvadrat n.
Biz yarım daimi amil haqqında qayğı yoxdur.
Bu kimi böyük O məhsullarının bir çox riyaziyyat bu cür bunu yalnız cür əsaslanır Belə ki,
hesab məbləğləri və həndəsi silsilə stuff bunu,
lakin bu, əlbəttə onların ən sevimli sadə edir.
Okay.
Nə durub sırala n Omega edir? Omega nə deməkdir?
[Dəfə danışan iki tələbələri - anlaşılmaz] >> Bəli.
Omega siz aşağı bağlı kimi hesab edə bilər.
>> Belə ki, durub sırala alqoritm necə səmərəli olursa olsun,
asılı olmayaraq qəbul ki, siyahı, həmişə ən azı n şeyi müqayisə edir
və ya n şeyə təkrarlamaq var.
Niyə ki?
[Tələbə] Çünki siyahısı artıq çeşidlənir, onda vasitəsilə ilk iteration
siz yalnız ilk element ən ki, təmin edə bilər
və ikinci iteration yalnız ilk iki təmin edə bilər
siz siyahısına qalan çeşidlənir bilirik ki, çünki. >> Bəli.
Siz ən azı bir tam sıralanır siyahısına keçmək Əgər bütün elementləri üzərində getmək
heç bir şey ətrafında köçürülüb lazımdır görmək.
Belə ki, siyahıda keçən və oh, bu, artıq çeşidlənir söyləyərək
siz sıralanır oldu bilmək üçün hər element yoxlamaq qədər mümkün deyil
onlar sıralanır üçün olduğunu görürük.
Belə ki, durub sırala dair bağlı alt n Omega edir.
Ən pis halda, birləşmə növ zaman nə qaçış var
ən pis halda yenə böyük O olan?
Belə ki, ən pis halda, birləşmə sort necə çalışır?
[Tələbə] N log n. >> Bəli.
Sürətli ümumi çeşidlənməsi alqoritmlərin n log n. Siz daha yaxşı edə bilməz.
>> Var xüsusi hallarda və biz bu gün vaxt varsa - lakin biz yəqin ki, won't -
biz n log n daha yaxşı ki, bir görürdü.
Amma ümumi halda, siz n log n daha yaxşı edə bilməz.
Və daxil sort siz n log n ki, bu kurs üçün bilmək lazımdır biri olur.
Və biz, həqiqətən, bu gün həyata olacaq.
Və, nəhayət, artıq üç cümlə, necə seçim sırala çalışır?
Kimsə cavab istəyirəm varmı, mən sizin cümlələr saymaq lazımdır
çünki 3 üzərində getmək əgər -
Hər kəs seçilməsi cür xatırlamaq varmı?
Seçim sırala yalnız adı yadda adətən olduqca asandır.
Siz yalnız array üzərində təkrarlamaq, nə ən böyük dəyəri və ya kiçik tapmaq -
Daxil çeşidlənməsi etdiyiniz nə üçün
Belə ki, biz kiçik olan böyük üçün çeşidlənməsi edirik deyək.
Siz minimum element nə axtarır, serialın üzərində təkrarlamaq
seçin və sonra yalnız ilk növbədə nə onu dəyişdirmək.
Və sonra serialın üzərində ikinci aşırımı da, yenə minimum element axtarmaq
seçin və sonra ikinci mövqe nə ilə dəyişdirmək.
Belə ki, yalnız toplama və minimum dəyərlər seçimi
və serialın qarşısında onları daxil o çeşidlənir qədər.
Ki Suallar?
>> Bu qaçılmaz siz pset təqdim etdiyiniz zaman doldurmaq üçün formalarda görünür.
Bu əsasən o cavab var.
Okay, indi problemlər kodlaşdırma.
Mən artıq e-poçt artıq göndəriləcək - hər kəs e-poçt almaq etmədikmi? Okay.
Mən artıq, e-poçt artıq biz istifadə olacaq ki, yer göndəriləcək
mənim adını basın əgər - belə mən aşağı ola gedirəm hesab
Çünki geri r - Siz mənim adını basın əgər ancaq 2 dəyişiklikləri görürsünüz.
Revision 1 Mən artıq sitemizi və məkanı nəzərə kodu yapışdırılır olacaq
axtarış şey üçün siz həyata keçirilməsi üçün var olacaq.
Və Revision 2 biz bundan sonra həyata keçirən cür şey olacaq.
Beləliklə, siz mənim Revision 1 basın və oradan işləyə bilər.
İndi biz ikili axtarış həyata istəyirəm.
>> Hər kəs yalnız bir pseudocode yüksək səviyyədə izahat vermək istəyir
nə biz axtarışı üçün var olacaq? Bəli.
[Tələbə] Siz yalnız array ortasında almaq və aradığınız nə varsa bax
daha az və ya daha çox.
Və az varsa, siz az olan yarım getmək
daha varsa və daha çox olan yarım getmək və təkrar ki, yalnız bir şey almaq qədər.
[Bowden] Bəli.
Bizim nömrələri array artıq çeşidlənir edək ki,
və, belə ki, biz istifadə edə bilər və biz ilk yoxlamaq bilər o deməkdir ki,
tamam, mən sayı 50 arıyorum.
Mən orta getmək bilər.
Orta, bu şeyi daha sıra zaman müəyyən etmək çətindir
ancaq biz həmişə orta kəsmək lazımdır deyək.
Belə ki, burada biz 8 şeylər var, belə ki, orta 16 olardı.
50 arıyorum, belə ki, 50, 16-dən çox deyil.
Belə ki, indi mən əsasən bu elementlər kimi array müalicə edə bilər.
Mən 16-dan artıq hər şey tullamaq olar.
İndi sıra yalnız bu 4 elementlər və mən deyirəm.
Beləliklə, mən yenidən orta tapmaq istəyirsinizsə, bu 42 olacaq.
42 50-dən az, belə ki, mən bu iki element tullamaq olar.
Bu mənim qalan sıra edir.
Mən orta tapmaq üçün gedirəm.
Mən həmişə sol şeyi atmaq çünki mən, 50 pis nümunə oldu tahmin
eyni ölçü ilə, əgər mən bir şey arıyorum
və bu, hazırda da arıyorum element az deyil
sonra sağ hər şey tullamaq gedirəm.
Belə ki, indi biz həyata lazımdır.
Biz ölçüsü keçmək lazımdır ki, görürsünüz.
Biz də ağır kodu ölçüsü lazımdır bilməz.
Ki canini qurtar əgər # define -
Okay.
Necə gözəl nömrələri array həcmi hazırda nə anlamaq olar?
>> Nömrələri array neçə elementlər var?
[Tələbə] Nömrələr, mötərizədə. Uzunluğu?
[Bowden] C. Bu mövcud deyil
Lazımdır. Uzunluğu.
Diziler xüsusiyyətləri yoxdur, seriallarda heç uzunluğu əmlak var belə
ki, yalnız bu olur Lakin uzun verəcək.
[Tələbə] var nə qədər yaddaş baxın və nə qədər ilə bölmək - >> Bəli.
Belə ki, necə biz var nə qədər yaddaş bilərsiniz? >> [Tələbə] Sizeof. >> Bəli, sizeof.
Sizeof nömrələri serialın ölçüsü qayıtmaq niyyətində olan operatordur.
Və lakin çox integers olacaq ki, bir dəfə tam həcmi var
ki, həqiqətən up alaraq necə çox yaddaş var-ci ildən.
Mən array şeyi sayı istəyirəm əgər,
sonra mən tam həcmi ilə bölmək istəyirəm gedirəm.
Okay. Belə ki, mənə burada ölçüsü keçmək imkan verir.
Niyə bütün ölçüsü keçmək lazımdır?
Niyə yalnız int ölçüsü burada edə bilməz = sizeof (ot tayası) / sizeof (int)?
Niyə bu işləmir?
[Tələbə] Bu qlobal dəyişən deyil.
[Bowden] ot tayası var və biz ot tayası kimi nömrələri keçən edirik
və bu gəlmək ne foreshadowing növü. Bəli.
[Tələbə] ot tayası yalnız ona istinad edir, belə ki, arayış nə qədər böyük qayıtmaq istəyirəm.
Bəli.
Mən, həqiqətən, doğru hələ yığını gördüm ki, mühazirə şübhə?
Biz yalnız bu barədə danışıq etdik.
Sizin dəyişənlərin bütün saxlanılır gedir yerləşir Belə yığını deyil.
>> Yerli dəyişənlər üçün ayrılmış ki, hər hansı bir yaddaş yığını gedir
və hər bir funksiyası yığını öz kosmik alır, öz yığını çərçivəsində bu deyirlər edir.
Belə ki, əsas onun yığını çərçivəsində malikdir və daxili, bu nömrələr sıra mövcud gedir
və ölçüsü sizeof (ədəd) ilə olacaq.
Bu elementlərin ölçüsü bölünür nömrələri ölçüsü olacaq
lakin əsas nin yığını çərçivəsində bütün həyatını ki.
Axtarış zəng zaman, axtarış, öz yığını çərçivəsində olur
öz kosmik onun yerli dəyişənlərin bütün saxlamaq üçün.
Amma bu arqumentləri - belə ot tayası bütün bu array surəti deyil.
Axtarış bir surəti kimi bütün array keçmək yoxdur.
Bu yalnız array istinad keçir.
Belə ki, axtarış bu istinad vasitəsilə bu nömrələri istifadə edə bilərsiniz.
O, yenə də əsas nin yığını çərçivə içərisində yaşamaq şeylər daxil oldu
lakin əsasən, biz göstəricilərinə almaq zaman ki, tezliklə olmalıdır
bu göstəricilər nə edir.
Pointers yalnız şeyə istinad edir, və siz hər şeyi əldə etmək göstəricilərinə istifadə edə bilərsiniz
digər şeylər "yığını çərçivəsində var.
Ədəd əsas yerli olsa Belə ki, biz hələ də bu göstərici vasitəsilə əldə edə bilərsiniz.
Amma bu yalnız bir göstərici var və yalnız bir istinad var-ci ildən,
sizeof (ot tayası) yalnız istinad özü ölçüsü qaytarır.
Bu işarə oldu şey həcmi qayıtmaq deyil.
Bu nömrələr faktiki ölçüsü qayıtmaq deyil.
Biz bunu istəyirik və bu iş etmək niyyətində deyil.
>> Ki Suallar?
Pointers gəlmək həftə daha çox Qori ətraflı daxil getdi olacaq.
Niyə görmək şeyi, ən axtarış şeyi və ya sort çox şey, və bu
onlar demək olar ki, bütün serialın faktiki ölçüsü lazımdır olacaq
C, çünki biz serialın ölçüsü nə heç bir fikrim yoxdur.
Siz özünüz daxil keçmək lazımdır
Yalnız istinad keçən edirik, çünki özünüz bütün array keçmək bilməz
və istinad olan ölçüsü ala bilmir.
Okay.
Belə ki, indi biz əvvəl izah nə həyata istəyirəm.
Siz bir dəqiqə üçün iş bilər
və hər şey mükəmməl 100% iş əldə narahat yoxdur.
Sadece bunu etməlidir necə yarısı pseudocode yazmaq.
Okay.
Tamamilə hələ bu edilə ehtiyac yoxdur.
Ancaq hər kəs, onlar indiyə qədər nə ilə rahat hiss etmir
bir şey kimi biz birlikdə işləyə bilər?
Hər kəs könüllü istəyir? Və ya təsadüfi aparacaqlar.
Bu hüququ heç bir tədbir ancaq bir iş dövlət dəyişə bilərsiniz bir şey olmalıdır deyil.
[Tələbə] Sure. Okay. >>
Beləliklə, siz az Save icon tıklayarak təftiş saxlaya bilərsiniz.
Siz sağ, Ramya mi? >> [Tələbə] Bəli. >> [Bowden] Okay.
Belə ki, indi mən sizin təftiş bilərsiniz və hər kəs yenidən qoparmaq bilər.
Burada biz - Okay.
Belə Ramya mütləq etibarlı həll olan recursive həlli ilə getdi.
Bu problem edə bilər iki yolu var.
Siz ya iteratively və ya recursively bunu edə bilərsiniz.
Siz recursively edilə bilər ki, qarşılaşma ən problemlər də iteratively edilə bilər.
Belə ki, burada biz recursively bunu etdik.
>> Kimsə bir funksiyası recursive etmək nə deməkdir müəyyən etmək istəyir?
[Tələbə] bir funksiyası var zaman özü zəng
doğru və düzgün yerinə gələnə qədər və sonra özü zəng. >> Bəli.
A recursive funksiyası yalnız özü tutan bir funksiyası var.
Rekursiv funksiyası olmalıdır ki, üç böyük şeylər var.
Ilk aşkar, o, özü çağırır.
İkinci baza haldır.
Belə ki, bir nöqtədə funksiyası, özü zəng dayandırmaq lazımdır
və ki, əsas işi budur.
Belə ki, burada biz dayandırmaq lazım bilirik ki, biz axtarış imtina etməlidir
Axırıncı bərabərdir zaman - və biz o deməkdir ki, nə artıq getmək lazımdır.
Amma nəhayət, recursive funksiyaları üçün vacibdir ki, son şey:
funksiyaları birtəhər əsasında halda yanaşmaq lazımdır.
, Ikinci recursive zəng zaman həqiqətən bir şey yenilənməsi değilseniz kimi,
siz sözün yalnız həmin dəlilləri ilə yenidən funksiyası zəng etdiyiniz
və qlobal dəyişənlər, dəyişdirilə və ya bir şey var
Əgər baza halda olmaq heç vaxt bu halda ki, pis edir.
Bu sonsuz recursion və bir yığın daşqın olacaq.
Lakin burada biz başlamaq + sonuna / 2 təzələyirik ildən yeniləmə baş verən bax
biz burada start arqument təzələyirik, burada son arqument təzələyirik,.
Belə ki, bütün recursive zənglər biz bir şey təzələyirik,. Okay.
Əgər həll vasitəsilə bizə gəzmək istəyirsiniz? >> Sure.
Mən hər dəfə mən bu funksiya zəng ki SearchHelp kullanıyorum
Mən sıra arıyorum yerləşir başlanğıc və son var
harada Mən array arıyorum.
>> Bu bir başlanğıc edən orta element, + sonuna / 2 var deyərək yerdə hər addım da,
ki, aradığınız nə bərabərdir?
Ki, onda biz bunu gördük və mən recursion səviyyəsi qədər qəbul olur ki danışarlar.
Ki, doğru deyil, onda biz, array ki, orta dəyəri çox böyük yoxlamaq
halda biz start orta index gedərək serialın sol yarım oldu.
Və başqa biz sonuna yarım edin.
[Bowden] Okay.
Bu yaxşı səslənir.
OK, bir neçə şeyi ki, və əslində, bu, çox yüksək səviyyədə şey
ki, bu kurs üçün bilmək lazımdır heç vaxt, lakin o, doğrudur.
Rekursiv funksiyaları, siz həmişə bir pis məşğul olduğunu eşitmək
siz recursively özünüzü çox dəfə zəng etsəniz, yığın daşqın almaq çünki
Mən əvvəl qeyd etdiyim kimi bəri, hər funksiyası öz yığını çərçivəsində olur.
Belə ki, recursive funksiyası hər zəng öz yığını çərçivəsində olur.
Əgər 1000 recursive zəng etmək Beləliklə, əgər 1000 yığını çərçivəsində almaq
və tez bir çox yığını çərçivəsində və hər şeyi yalnız qırmaq olan gətirib çıxaracaqdır.
Recursive funksiyaları ümumiyyətlə pis nə ki, var.
Amma recursive funksiyaları gözəl alt quyruq-recursive funksiyaları var adlanır
və bu compiler bu bildirişlər əgər olduğu bir nümunə olur
və lazımdır, mən hesab edirəm - cingilti siz bu-O2 bayrağı keçmək əgər
sonra bu quyruq recursive olduğunu qeyd və hər şeyi yaxşı edəcək.
>> Hər recursive zəng üçün daha çox və eyni yığını çərçivəsində təkrar edəcək.
Eyni yığını çərçivəsində istifadə etdiyiniz ildən Beləliklə, siz narahat ehtiyac yoxdur
əvvəl bildirib kimi heç coşğun yığın və eyni zamanda,
Əgər doğru qayıtmaq yerləşir dəfə, sonra bu yığını çərçivəsində Bütün qayıtmaq var
və SearchHelp 9 qayıtmaq üçün var 10 zəng, 8-ci qayıtmaq üçün var.
Belə ki funksiyaları quyruq recursive zaman nə lazım deyil.
Və nə bu funksiya quyruq recursive edir xəbərdarlıq edir ki, searchHelp üçün hər hansı bir zəng üçün
edilməsi olan recursive zəng qaytarılması nə edir.
Belə SearchHelp üçün ilk zəng, biz dərhal, yalan qayıtmaq
dərhal doğru qayıtmaq, ya da SearchHelp üçün rekursiv zəng
biz qaytarılması etdiyiniz zəng qaytarılması nə edir.
Biz int x = SearchHelp, qayıdış x * 2 kimi bir şey idi, əgər biz bunu bilmədi
yalnız bir təsadüfi dəyişiklik.
>> Belə ki, indi bu recursive zəng, bu int x = SearchHelp recursive zəng,
faktiki qayıtmaq yoxdur, çünki quyruq artıq recursive edir
geri bir əvvəlki yığını çərçivə ki funksiyası əvvəlki zəng
sonra qaytarılması dəyəri bir şey edə bilərsiniz.
Beləliklə, bu quyruq recursive deyil, qəşəng quyruq recursive əvvəl biz nə. Bəli.
[Tələbə] ikinci baza halda ilk yoxlanılır olmamalıdır
Siz dəlil keçmək Ü bir vəziyyət ola bilər, çünki
siz = sonunda başlamaq, lakin onlar iynə dəyər var.
Sonunda iynə dəyər olduğu sual biz halda daxil edə bilməz edilib
ya = sonunda başlamaq müvafiq = sonunda başlamaq
və həqiqətən, hələ ki, xüsusi dəyər yoxlanılır deyil
sonra + sonuna / 2 başlamaq yalnız eyni dəyər olacaq.
Amma biz artıq saxta geri etdik və həqiqətən dəyəri kontrol, heç vaxt.
Ölçüsü 0 əgər Belə ki, ən azı, ilk zəng, sonra saxta qayıtmaq istəyirəm.
Ölçüsü 1 olsa, sonra başlanğıc, bərabər son niyyətində deyil
və biz ən azı bir element yoxlamaq lazımdır.
Amma siz + sonuna / 2 başlamaq biz bir halda başa bilər ki, doğru hesab
start up start + sonuna / 2 eyni olan bitir
lakin biz həqiqətən ki element yoxlanılır heç vaxt.
>> Beləliklə, biz ilk yoxlamaq əgər orta element, biz aradığınız dəyəri
sonra biz dərhal doğru ola bilər.
Onlar bərabər etdiyiniz Else, onda davam heç bir məqam yoxdur
biz yalnız biz bir-element array üzrə olduğu bir halda yeniləmə olacaq ildən.
Ki, bir element biz aradığınız bir deyil
sonra hər şey səhvdir. Bəli.
[Tələbə] şey, ölçüsü ildən sıra elementlərin sayı əslində daha böyük olduğunu
bir ofset artıq var - >> Beləliklə ölçüsü olacaq -
[Tələbə] serialın ölçüsü 0 idi De sonra SearchHelp həqiqətən 0 ot tayası kontrol
ilk zəng.
>> Bəli - The array ölçüsü 0 var, 0 belə.
Başqa bir şey var - bu yaxşı ola bilər. Nin hesab edək.
Serialın 10 elementlər var idi və biz yoxlamaq olacaq orta göstərici 5, belə əgər
biz 5 kontrol edirik və dəyəri az olduğunu demək edək.
Belə ki, 5 irəli uzaq hər şeyi ataraq edirik.
Belə ki, son / 2 yeni son olacaq + başlamaq,
Bəli, belə ki, həmişə serialın sonuna kənarda qalmaq olacaq.
Hətta və ya tək idi, bir halda ki, onda biz, demək, 4 yoxlamaq olardı
lakin biz hələ atmaq edirik -
Bəli, belə ki, son zaman array faktiki son kənarda olacaq.
Biz əsas diqqəti elementləri Belə ki, son həmişə sonra bir olacaq.
Start heç bərabər sonunda əgər Beləliklə, biz size 0 bir sıra var.
>> Mən düşünürdüm başqa şey biz başlamaq üçün start təzələyirik + sonuna / 2, edir
Bu + sonuna / 2 başlamaq harada ilə sorun yaşıyorum iddia edir
biz yoxlanılması olduğunuz elementidir.
Gəlin biz bu 10 element array idi deyirlər. Neyse.
Belə ki, son / 2 Bu kimi bir şey olacaq + başlamaq,
və dəyəri deyil, biz yeniləmək istəyirlər.
Dəyəri böyükdür, belə ki, biz serialın bu yarım baxmaq istəyirəm.
Beləliklə, biz start təzələyirik, necə, indi bu element ola start təzələyirik,.
Amma bu hələ iş bilər, və ya ən azı, siz start edə + sonuna / 2 + 1.
[Tələbə] Sən + sonunda başlamaq üçün ehtiyac yoxdur [işitilemez] >> Bəli.
Biz artıq bu element yoxlanılır və biz aradığınız bir deyil bilirik var.
Beləliklə, biz bu element ola start yeniləmə ehtiyac yoxdur.
Biz yalnız skip və bu element olmaq başlamaq təkmilləşdirə bilər.
Və bir halda heç yoxdur, bu son idi ki, deyək,
bu olardı belə sonra başlamaq, + Axırıncı / 2 bu olardı,
+ sonunda başlamaq - Bəli, mən bu sonsuz recursion ildə başa bilər.
Yalnız ölçüsü 2 və ya ölçüsü 1 bir sıra bir sıra var edək deyirlər. Mən bu iş olacaq.
Belə ki, hal-hazırda başlanğıc element və sonunda o kənarda 1 olmasıdır.
Beləliklə, biz yoxlamaq olacaq ki, element, bu biri
və sonra start yeniləmə zaman, biz 0 + 1/2 olmaq start təzələyirik
olan başlanğıc bu element olan bizə geri bitirmək üzrədir.
>> Yəni biz yenidən üzərində eyni element kontrol edirik.
Beləliklə, bu, hər recursive zəng həqiqətən bir şey yeniləmək lazımdır belədir.
Beləliklə, biz bir halda var start + sonuna / + 1, 2 və ya başqa nə etmək lazımdır
biz həqiqətən start yenilənməsi deyilik.
Hər kəs ki?
Okay.
Hər kəs bu həll və ya daha çox şərh sualınız varmı?
Okay. Hər kəs bir biz bütün baxmaq olar ki, həll iterativ varmı?
Biz bütün recursively bunu mi?
Ya da mən sizə onunku açıldı, onda sizin əvvəlki overridden ola bilər danışarlar.
Avtomatik qənaət mu? Mən müsbət deyiləm.
Hər kəs iterativ varmı?
Biz onun vasitəsilə gəzmək əgər bilməz.
Ideyası, eyni olacaq.
Həll iterativ.
Biz əsasən eyni fikri etmək istəyirəm olacaq
biz serialın yeni sonuna track və serialın yeni başlanğıc saxlamaq istədiyiniz
və üzərində edin.
Biz başlanğıc və sonunda heç kəsişmək kimi track saxlanılması ne varsa,
sonra biz bunu tapa bilmədi və biz yalan ola bilər.
Belə ki, necə ki etməliyəm? Hər kəs qoparmaq mənim üçün təklif və ya kodu var?
[Tələbə] bir müddət loop edin. >> Bəli.
Siz loop etmək istəyirəm edir.
>> Mən qoparmaq bilər kodu var idimi, ya nə təklif gedirdi?
[Tələbə] Mən belə düşünürəm. >> Bütün hüququ. Bu şeyi daha asan edir. Adı nə idi?
[Tələbə] Lucas.
Revision 1. Okay.
Aşağı biz əvvəl başlamaq deyilən budur.
Up biz əvvəl son deyilən olduqca nə deyil.
Əslində, son array ərzində indi. Biz hesab etməlidir bir element var.
Belə ki, aşağı 0 deyil, qədər serialın ölçüsü - 1,
və indi biz loop və biz yoxlanılması olunur -
Mən sizə onun vasitəsilə gəzmək bilər danışarlar.
Bu vasitəsilə düşüncə nə idi? Kodunuzu vasitəsilə bizə tamamlayın.
[Tələbə] Sure. Ortasında ot tayası dəyəri baxın və iynə müqayisə.
Oh, həqiqətən ki, geri olmalıdır - sizin iynə daha əgər Beləliklə, sonra istəyirəm.
Siz sağ yarım tullamaq istəyirəm olacaq, və yeah ki, yol olmalıdır.
[Bowden] Beləliklə, bu daha az olmalıdır? Siz dedi ki, nə? >> [Tələbə] Bəli.
[Bowden] Okay. Az.
Nə biz aradığınız biz istədiyiniz nə daha kiçik Beləliklə, əgər,
sonra Bəli, biz, sol yarım tullamaq istəyirəm
olan biz nəzərə etdiyiniz hər şey təzələyirik deməkdir
serialın sağ aşağı hərəkət.
Bu yaxşı görünür.
Hesab edirəm ki, biz əvvəlki bildirib ki, eyni məsələ var
Ü aşağı 0 və 1 ilə qədər aşağı, sonra edir + up / 2 yenə eyni şey olacaq qurmaq gedir.
>> Və bu halda belə, bu, ən azı daha səmərəli
yalnız element tullamaq biz yalnız biz yanlış olduğunu hansı baxdı.
Belə ki, aşağı + up / 2 + 1 - >> [tələbə] Bu başqa cür olmalıdır.
[Bowden] Yaxud bu olmalıdır - 1 və digər bir + 1 olmalıdır.
[Tələbə] Və ikiqat olmalıdır giriş bərabərdir. >> [Bowden] Bəli.
[Tələbə] Bəli.
Okay.
Və nəhayət, indi biz bu + 1 var - 1 şey,
o - bu ola bilər - bu, aşağı üçün daha çox dəyəri ilə başa heç mümkündürmü?
Mümkün mü - Mən ola bilər ki, yalnız yol mi? >> [Tələbə] Mən bilmirəm.
Amma qaralar olur və sonra mənfi olur ki, əgər sonra 1 və - >> Bəli.
[Tələbə] Bu bəlkə qədər messed almaq olardı.
Mən bunu yalnız yaxşı olmalıdır
o aşağı sonuna qədər onlar bərabər olmalıdır deyə düşünürəm.
Onlar bərabər, əgər Ancaq sonra biz başlamaq üçün isə loop etməzdilər
və biz yalnız dəyəri geri olardı. Mən indi yaxşı olduğunuzu düşünürəm.
Qeyd edək ki, bu problem artıq recursive deyil, baxmayaraq
biz bu asanlıqla özü verir necə görə bilərsiniz ideyaların eyni cür tətbiq
biz yalnız yenidən üzərində göstəriciləri təzələyirik ki, bir recursive həll etmək,
biz problem kiçik və kiçik edirik, biz serialın alt diqqət edirik.
[Tələbə] aşağı 0 və 1 ilə qədər deyil, onlar həm 0 + 1/2, 0 getmək olardı olardı
və sonra bir + 1 olardı olardı - 1.
[Tələbə] Harada biz bərabərlik yoxlanılması olunur?
Orta əslində iynə əgər istəyirsiniz?
Hal-hazırda bunu deyilik? Oh!
It's varsa -
Bəli. Gəlin ilk orta demək çünki aşağı burada test yalnız bilməz -
[Tələbə] Bu əslində bound tullamaq deyil kimi.
Siz bound tullamaq Belə ki, siz ilk və ya hər hansı bunu yoxlamaq lazımdır.
Ah. Bəli. >> [Tələbə] Bəli.
İndi biz hazırda baxdı bir atılmalıdır ki,
olan biz indi də lazımdır deməkdir
(ot tayası [(aşağı + up) / 2] == iynə), sonra biz doğru qayıtmaq bilər.
Mən başqa və ya əgər qoymaq olub, bu sözün eyni şey deməkdir
bu doğru geri olardı, çünki.
Mən başqa varsa qoymaq lazımdır, lakin bu məsələ deyil.
>> Belə ki, daha bu, başqa bu və bu mən ortaq bir şey varsa,
harada hər şey burada yaxşı olduğu halda belə,
aşağı yuxarı daha çox ola bilməz kimi, bu doğru olub dəyər mühakimə deyil.
Aşağı-dən az və ya bərabər olduğu halda, Beləliklə, siz həmçinin demək olar
və ya aşağı-dən az olduğu halda
onlar bərabər və ya aşağı olduqda belə, yuxarı keçmək olur
sonra biz bu loop həyata qıra bilər.
Suallar, narahatlıqlar, şərh?
Okay. Bu yaxşı görünür.
İndi sırala etmək istəyirəm.
Biz mənim ikinci versiya getmək varsa, bu eyni nömrələr bax
lakin indi onlar sıralanır üçün artıq var.
Və biz n log n O, hər hansı bir alqoritmi istifadə sort həyata istəyirəm.
Biz burada həyata olan alqoritm Belə düşünürsünüz? >> [Tələbə] Merge sort.
[Bowden] Bəli. Birleştirme cür ki, biz nə olacaq nə, O (n log n) edir.
Və problem, olduqca oxşar olacaq
harada asanlıqla recursive həllinə özü verir.
Biz istəyirsinizsə Biz də bir iterativ həll ilə gəlmək olar
lakin recursion burada daha asan olacaq və biz recursion etməlidir.
Ki, biz ilk birləşmə sort vasitəsilə gəzmək olacaq tahmin
birləşmə sort bir sevimli video artıq olsa. [Gülüş]
Belə ki, var sort daxil - Mən bu kağız qədər israf edirəm.
Oh, yalnız bir sol yoxdur.
Belə ki, daxil.
Oh, 1, 3, 5.
Okay.
Merge iki ayrı serialların edir.
Fərdi bu iki serialların sıralanır də.
Beləliklə, bu sıra, 1, 3, 5, sıralanır. Bu array, 0, 2, 4, sıralanır.
İndi nə birləşmə etməlidir özü sıralanır ki, bir sıra onları birləşdirmək edir.
Beləliklə, biz bu daxilində bu elementlər üçün gedir ki, ölçüsü 6 bir sıra istəyirəm
sıralanır üçün.
>> Və biz bu iki serialların ayrılır ki, istifadə edə bilər
xətti vaxt bunu,
xətti zaman məna bu array x və bu ölçüsü y olduqda,
sonra ümumi alqoritm O (x + y) olmalıdır. Okay.
Təklif edir.
[Tələbə] biz sol başlamaq bilərmi?
Belə ki, aşağı ilk və sonra 1 0 qoymaq lazımdır və sonra burada 2 istəyirik.
Belə ki, doğru hərəkət ki, nişanı var kimi növü var. >> [Bowden] Bəli.
Biz yalnız leftmost element diqqət bu serialların hər üçün.
Həm serialların sıralanır Çünki biz bilirik ki, bu 2 elementləri
ya sıra kiçik elementləridir.
Belə ki, o 2 elementləri 1 bizim birləşmiş array ən kiçik element olmalıdır deməkdir.
Bu, sadəcə belə kiçik hüququ bu dəfə bir ki, baş verir.
0 az 1 çünki Belə ki, biz, 0 almaq sol onu daxil
belə, 0 almaq bizim ilk mövqe onu daxil, sonra biz bu yeniləmə
İndi ilk element diqqət.
İndi biz deyirəm.
Belə ki, indi biz 2 müqayisə və 1. 1 kiçik, belə ki, biz 1 daxil olacaq.
Biz bu oğlan işaret üçün bu göstərici yeniləmə.
İndi yenə bunu, 2 belə. Bu, yeniləmə, bu 2, 3 müqayisə edəcək.
Bu yenilikləri, 4 və 5.
Belə ki, birləşmə deyil.
>> Bu yalnız bir dəfə hər bir element üzrə getmək ildən xətti vaxt ki, olduqca aydın olmalıdır.
Və bu birləşmə sort bu edir həyata ən böyük addımdır.
Və bu çətin deyil.
Narahat bir neçə şeyi edək biz 1, 2, 3, 4, 5, 6 birləşməsi idi demək deyil.
Bu halda biz, bu kiçik olacaq yerləşir ssenari ildə başa
sonra biz bu göstərici yeniləmə, bu kiçik olacaq, bu yeniləmə,
bu bir kiçik, və indi tanımaq üçün
həqiqətən ilə müqayisə elementləri tökülmək etdik zaman.
Biz bütün bu array istifadə ildən,
Bu array hər şey indi yalnız burada daxil.
Biz daim Diziler biri tamamilə artıq birləşmə nöqtəyə, daxil əgər
sonra biz yalnız başqa array bütün elementləri almaq və serialın sonunda onları yerləşdirin.
Beləliklə, biz yalnız, 5, 6 4 əlavə edə bilərsiniz. Okay.
Yəni üçün baxın bir şeydir.
O 1 addımı olmalıdır həyata keçirilməsi.
Birleştirme ki əsaslanır sonra sort, o, 2 pillə, 2 səfeh addımlar var.
Gəlin bu array verir.
Belə ki, sort daxil addım 1 recursively yarıya indirir daxil array qırmaq edir.
Belə ki, yarıya indirir bu array parçalanması.
Biz indi 4, 15, 16, 50 və 8, 23, 42, 108 var.
İndi yenə bunu və biz yarıya indirir bu split.
Mən bu tərəfində bunu yalnız lazımdır.
50, 4, 15 və 16 belə.
Biz burada eyni şey olardı.
İndi biz yenə yarıya indirir daxil parçalanması.
Və biz 4, 15, 16, 50 var.
Belə ki, bizim əsas haldır.
Bu serialların ölçüsü 1 olduğunda, biz yarıya indirir daxil parçalanması ilə dayandırmaq.
>> İndi bu nə etməliyəm?
Biz bu da 8, 23, 42, və 108 daxil qırmaq olacaq son.
Belə ki, indi biz bu nöqtədə olduğunu, indi birləşmə növ iki yalnız siyahıları cüt birləşməsi olunur addım.
Beləliklə, biz bu daxil etmək istəyirik. Biz yalnız daxil çağırırıq.
Biz birləşməsi sıralaması üçün bu qayıdacaq bilirəm.
4, 15.
İndi biz bu daxil etmək istəyirəm ki, bu, sorted üçün həmin siyahısı qayıdacaq
16, 50.
Biz o daxil - Mən yaza bilməz - 8, 23 və 42, 108.
Beləliklə, biz bir birləşmiş cüt var.
İndi biz yalnız yenidən daxil.
Özlüyündə bu siyahıları hər çeşidlənir edək ki,
və sonra yalnız sıralanır olan ölçüsü 4 bir siyahısını almaq üçün bu siyahıları daxil edə bilərsiniz
və sorted ki ölçüsü 4 bir siyahısını almaq üçün bu iki siyahıları daxil.
Və, nəhayət, biz sıralanır ki, ölçüsü 8 bir siyahısını almaq üçün ölçüsü 4 bu iki siyahıları daxil edə bilərsiniz.
Belə ki, bu ümumi n log n ki, biz artıq birləşmə xətti olduğunu gördüm,
belə zaman belə birləşmə ümumi dəyəri kimi, bu birləşmə ilə məşğul olduğunuz
Bu iki siyahıları üçün yalnız 2 çünki -
Və ya yaxşı, bu n O, ancaq burada n yalnız bu 2 elementlər, belə ki, o, 2 deyil.
Və bu 2 2 olacaq və bu 2 2 olacaq və bu 2 2 olacaq
biz nə etmək lazımdır ki, əlaqələnir bütün arasında, biz n bunu son.
Bəyəndim 2 + 2 + 2 + 2 n olan 8, edir
bu dəsti birləşməsi dəyəri n.
Və sonra burada eyni şey.
Biz sonra bu 2, bu 2 daxil olacaq, və fərdi birləşmə, dörd əməliyyatları keçiriləcək
Bu birləşmə, bütün bunlar arasında, bir daha dörd əməliyyatları aparmaq, ancaq
biz birləşmə n ümumi şeyi başa, və bu addım n edir.
Və hər səviyyədə birləşdi olan n elementləri edir.
>> Və necə bir çox səviyyədə var?
Hər səviyyədə, bizim array ölçüsü 2 artır.
Burada bizim seriallarda ölçüsü 1, burada onlar ölçüsü 2 istəyirik, burada onlar, ölçüsü 4 istəyirik
və nəhayət, onlar ölçüsü 8 istəyirik.
Bu misli belə bəri, Giriş n bu səviyyədə ümumi olmalıdır edir.
Belə ki, log n səviyyəsi, hər fərdi səviyyədə qəbul n ümumi əməliyyatları ilə,
biz n log n alqoritm almaq.
Suallar?
Insanlar artıq bu həyata dair irəliləyiş varmı?
Mən yalnız onların kodu qoparmaq bilər artıq bir dövlət hər kəs varmı?
Mən bir dəqiqə verə bilər.
Bu, bir daha olacaq.
Mən qayıtmaq gəlir -
Siz birləşməsi üçün recursion nə yoxdur
birləşməsi üçün recursion etmək üçün, müxtəlif ölçülü bir dəstə keçməli olacaq.
Siz, lakin bu annoying var.
Amma sort özü üçün recursion olduqca asandır.
Siz yalnız sözün doğru yarısında sort, sol yarısında cür adlandırırlar. Okay.
Hər kəs hələ qoparmaq bilər bir şey var?
Və ya başqa bir dəqiqə verəcəyik.
Okay.
Hər kəs biz ilə işləyə bilər bir şey var?
Və ya başqa biz yalnız bu iş və oradan da genişləndirmək lazımdır.
>> Hər kəs mən qoparmaq bilər ki, bu daha çox var?
[Tələbə] Bəli. Siz mina qoparmaq bilər. >> Bütün hüququ.
Bəli!
[Tələbə] şərtlər var idi. >> Oh, vur. Siz -
[Tələbə] Mən saxlamaq lazımdır. >> Bəli.
Belə ki, ayrı-ayrılıqda birləşmə etmək idi.
Oh, lakin bu pis deyil.
Okay.
Belə ki, sort yalnız mergeSortHelp zəng özü edir.
MergeSortHelp nə bizə izah edir.
[Tələbə] MergeSortHelp olduqca çox iki əsas addımlar edir
olan serialın hər yarım sort və sonra hər ikisi daxil edir.
[Bowden] Okay, belə ki, mənə ikinci verir.
Mən bu düşünün - >> [tələbə] Mən lazımdır -
Bəli. Mən bir şey itkin alıram.
Birləşmə, mən yeni bir sıra yaratmaq lazımdır ki, həyata
I yer bunu bilməzdi. >> Bəli. Siz edə bilərsiniz. Düzeltin.
[Tələbə] Mən yeni bir sıra yaratmaq.
Mən yenidən dəyişmək üçün daxil sonunda unuttum.
Okay. Biz yeni array lazımdır.
Birləşmə sort, bu demək olar ki, həmişə doğrudur.
Daha yaxşı bir alqoritm vaxt müdrik dəyəri Kateqoriya
demək olar ki, həmişə bir az daha çox yaddaş istifadə ehtiyac olunur.
Belə ki, burada, siz necə olursa sort daxil,
siz qaçılmaz bəzi əlavə yaddaş istifadə etmək lazımdır.
O, yeni bir sıra yaradıldı.
Və sonra sonunda biz yalnız orijinal sıra yeni array surəti lazımdır deyirlər.
[Tələbə] Mən Bəli, belə düşünürəm.
Ki, arayış və ya hər hansı hesablama baxımından işləri Bilmirəm -
Bəli, bu iş olacaq. >> [Tələbə] Okay.
Bu çalışan cəhd mi? >> [Tələbə] Xeyr, yoxdur. Okay. >>
Bu qaçış cəhd edin, və sonra ikinci bu barədə danışmaq lazımdır.
[Tələbə] Mən doğru olsa da, bütün funksiya prototipləri və hər şey lazımdır?
Funksiyası prototipləri. Bəli - Oh, siz kimi nəzərdə tuturam.
Sort mergeSortHelp çağırır.
>> Belə ki, sort mergeSortHelp zəng etmək üçün, mergeSortHelp ya müəyyən edilmiş olmalıdır
sort əvvəl və ya biz prototip yalnız lazımdır. Sadəcə surəti və yapışdırıb.
Və eyni, mergeSortHelp, daxil zəng
lakin birləşmə hələ müəyyən olunmayıb, belə ki, biz yalnız mergeSortHelp bildirin bilər
ki, daxil nə kimi baxmaq edir ki, ki, ki,.
MergeSortHelp belə.
Biz baza halda olduğu Biz burada bir məsələ var.
MergeSortHelp recursive, belə ki, hər hansı bir recursive funksiyası
recursively özü zəng dayandırmaq üçün zaman bilmək baza halda bir növ lazımdır gedir.
Bizim baza halda burada nə olacaq? Bəli.
[Tələbə] ölçüsü 1 varsa? >> [Bowden] Bəli.
Biz orada gördüm Belə ki kimi, biz parçalanması serialların dayandırdı
bir dəfə biz istər-istəməz özlərini sıralanır olan ölçüsü 1, diziler nəzərə almışdır.
Ölçüsü 1 bərabərdir Belə ki, biz, array artıq çeşidlənir bilirik
biz yalnız ola bilər.
>> Boşluq var bildirək ki, biz xüsusi bir şey yoxdu, yalnız geri.
Okay. Belə ki, bizim əsas işi var.
Düşünürəm ki, biz, ölçüsü 0 bir sıra birləşdirilməsi üçün baş əgər baza halda da ola bilər tahmin
biz yəqin ki, bir anda dayandırmaq istəyirəm
biz yalnız az 2 və ya daha az və ya 1-bərabər ölçüsü demək olar
bu artıq heç bir array üçün işləyəcək ki,.
Okay.
Belə ki, bizim əsas işi var.
İndi birləşmə vasitəsilə bizə gəzmək istəyirsiniz?
Bütün bu hallarda nə deməkdir?
Burada, biz yalnız, eyni ideya edirik ki, -
[Tələbə] Mən bütün mergeSortHelp zənglər ölçüsü keçən lazımdır.
Mən əlavə əsas kimi ölçüsü əlavə və ölçüsü / 2 kimi yoxdur.
[Bowden] Oh, ölçüsü / 2, ölçüsü / 2. >> [Tələbə] Bəli, və həmçinin yuxarıda funksiyası.
[Bowden] Burada? >> [Tələbə] Just ölçüsü. >> [Bowden] Oh. Size, ölçüsü? >> [Tələbə] Bəli.
[Bowden] Okay.
Mənə bir ikinci hesab edək.
Biz bir məsələ daxil edirsiniz?
Biz həmişə 0 kimi sol müalicə edirik. >> [Tələbə] saylı
Bu çox yanlış. Bağışlayın. Bu başlanğıc olmalıdır. Bəli.
[Bowden] Okay. Mən daha yaxşı istəyirəm.
Və sonu. Okay.
Belə ki, indi birləşmə vasitəsilə bizə gəzmək istəyirsiniz? >> [Tələbə] Okay.
Mən yalnız mən yaratdıq ki, bu yeni array vasitəsilə gəzinti edirəm.
Onun ölçüsü biz sıralanır istədiyiniz serialın hissəsinin ölçüsü
Mən yeni array addım qoymaq lazımdır ki element tapmaq üçün çalışırıq.
Serialın sol yarısı daha çox elementləri üçün davam etsəniz bunu ilk mən yoxlanılması deyiləm,
bu deyil, əgər, sonra yalnız deyir ki, başqa şəraiti, enmək
tamam doğru array olmalıdır və biz newArray cari index ki qoymaq lazımdır.
>> Serialın sağ da başa əgər, sonra başqa, mən, nəzarət edirəm
Bu halda mən yalnız sol qoydu.
Bu həqiqətən lazım ola bilər. Mən əmin deyiləm.
Amma hər halda, iki olan digər iki çek sol və ya sağ kiçik.
Həmçinin hər bir halda, mən arttırmayı hansı tutucu incrementing alıram.
[Bowden] Okay.
Bu yaxşı görünür.
Hər kəs şərh və ya narahatlıqlar və ya sualınız varmı?
Və ya beş kimi görünür - - biz yalnız meydana şey gətirmək üçün olan dörd hallarda Beləliklə
lakin biz, sol sıra biz daxil etmək lazımdır şeyi tökülmək olub olmadığını hesab etmək
hüququ sıra biz daxil etmək lazımdır şeyi tükendi olub -
Mən heç işarə edirəm.
Belə ki, sol array şeyi tökülmək və ya sağ array şeyi tükendi olub.
Bu iki halda olur.
Biz də sol şey düzgün az olub və mənasız işi lazımdır.
Sonra sol şey seçmək istəyirik.
Bu hallar var.
Belə ki, bu idi hüququ var ki.
Array ayrıldı. Bu 1, 2, 3 var. Okay. Belə ki, Bəli, o biz edə bilərsiniz dörd şey.
Və biz bir həll iterativ artıq getmək deyil.
Mən tövsiyə deyil -
Birleştirme növ recursive həm quyruq deyil ki, funksiyası bir nümunəsidir
, o, quyruq recursive etmək asan deyil
həm də o iterativ etmək çox asan deyil.
Bu çox asandır.
Birləşmə növ bu həyata keçirilməsi,
, nə olursa olsun daxil, siz birləşmə qurmaq olacaq.
>> Belə birləşmə üst inşa sort recursively yalnız bu üç xətləri edir birleştirir.
Iteratively, bu barədə düşünmək daha annoying və daha çətindir.
Amma mergeSortHelp ildən recursive quyruq deyil ki, qeyd - bu özü çağırır zaman -
hələ bu recursive zəng qaytarır sonra şeyə ehtiyacı var.
Beləliklə, bu yığını çərçivəsində hətta bu zəng sonra mövcud davam etməlidir.
Və sonra bu zəng zaman yığın çərçivəsində mövcud davam etməlidir
hətta zəng sonra, biz hələ də daxil etmək lazımdır, çünki.
Və bu quyruq recursive etmək nontrivial edir.
Suallar?
Bütün hüquqlar.
Belə ki, sort geri gedir - oh, mən göstərmək istəyirəm iki şey var. Okay.
Sort geri gedir, biz tez bu edəcəyik.
Və ya axtarış. Sort? Sort. Bəli.
Növ əvvəlinə geri gedir.
Biz hər hansı bir alqoritm istifadə edən növləri sıra alqoritm yaratmaq istəyirəm
n O.
Belə ki, necə bu mümkündür? Hər kəs hər hansı varmı -
Mən əvvəl hinted -
Biz n log n n Ey təkmilləşdirilməsi haqqında danışırsınızsa,
bizim alqoritm zaman-müdrik, yaxşılaşmışdır
hansı ki üçün etmək üçün nə etmək lazımdır nə gedir? deməkdir
[Tələbə] Space. >> Bəli. Biz daha çox yer istifadə olacaq.
Və hətta daha çox yer, bu dözərək daha çox yer var.
Mən alqoritm bu cür yalançı bir şey, yalançı polynom hesab -
yalançı - Mən xatırlayıram bilməz. Pseudo bir şey.
Biz çox yer istifadə etmək lazımdır, çünki bu
bu mümkün deyil, real deyil.
>> Və biz buna nail edirsiniz?
Biz təmin əgər biz buna nail olar ki, array hər hansı xüsusi element
aşağıda müəyyən bir ölçüsü.
Belə ki, yalnız ölçüsü 200 olduğunu deyək
bir sıra hər hansı bir element altında ölçüsü 200 manatdır.
Bu, həqiqətən, çox realdır.
Siz çox asanlıqla siz hər şeyi bilirsiniz ki, bir sıra ola bilər
bir az olacaq.
Bəzi tamamilə kütləvi vektor və ya bir şey varsa, kimi
amma hər şeyi, 0 və 5 arasında olacaq bilirik
sonra bunu əhəmiyyətli dərəcədə daha sürətli olacaq.
Və elementlərin hər hansı bir bağlı, 5
bu bound belə ki, istifadə etmək olacaq nə qədər yaddaş var.
Belə ki, bound 200 manatdır.
Bir tamsayı yalnız 4 milyard ola bilər-ci ildən nəzəriyyə bir bound, həmişə var
lakin sonra biz kosmik istifadə istədiyiniz ildən real deyil
4 milyard sifarişi. Belə ki, qeyri-real edir.
Lakin burada biz bound demək lazımdır 200 manatdır.
N O bunu üçün oyun biz ölçüsü sayar bağlı deyilən bir sıra olun.
Yəni əslində, bu bir qısa yoldur - cingilti bu əgər mən həqiqətən bilmirəm.
Amma ən azı GCC ildə - Ben fərz cingilti bunu edir -
Bu yalnız 0s olmaq üçün bütün array başlamaq olacaq.
Mən bunu istəmirəm Belə ki, sonra ayrıca edə (int i = 0;
i <BOUND i + +) və sayır [i] = 0;
Belə ki, indi hər şey 0 başlatılmış olunur.
Mən array üzərində təkrarlamaq
və nə edirəm mən hər sayını hesablamaq edirəm ki, - burada enmək edək.
Biz 4, 15, 16, 50, 8, 23, 42, 108 var.
Mən hesablanması edirəm bu elementlərin hər halları sayı.
Nin həqiqətən bəzi təkrar burada bir neçə əlavə edək.
Biz burada dəyəri Belə ki, dəyəri [i] array olacaq.
Belə ki, val 4 və ya 8 və ya hər hansı ola bilər.
İndi mən gördüm nə qədər ki, dəyəri hesablanması alıram
sayar belə [val] + +;
Bunu sonra sayar 0001 kimi bir şey baxmaq niyyətindədir.
Sayar nə edək [val] - + 1 almalıdır.
>> İndi biz 0-dan başlayaraq edirik ki, hesablamaq üçün yalnız var.
Belə ki, əgər 200, bizim ən çox olacaq
sonra 0 200 201 şeylər edir.
Bir 4 Çünki sayar Belə ki, 00001 kimi baxmaq lazımdır.
Sonra biz sayı 8 indeksinin 1 olacaq yerləşir 0001 lazımdır.
Biz sayı 23 indeksinin 2 olacaq.
Biz sayı 42 indeksinin 2 olacaq.
Beləliklə, biz count istifadə edə bilərsiniz.
Belə num_of_item = sayar [i].
Və num_of_item 2 belə, biz sayı i 2 daxil etmək istəyirəm o deməkdir ki,
bizim sıralanır array daxil.
Belə ki, biz array daxil nə qədər takip lazımdır.
Belə ki, index = 0.
Array - Mən yalnız yazmaq lazımdır.
Nömrəsi -
array [index + +] = i;
Mən istəyirəm nə ki? Hesab edirəm ki, mən istədiyiniz nə hesab edirəm.
Bəli, bu yaxşı görünür. Okay.
Belə ki, hər kəs mənim sayar array məqsədi nə başa düşmək olur?
Bu ədəd hər halları sayı hesablanması edir.
Sonra ki, sayıları array üzərində iterating am
və sayıları array ildə İTH mövqe
mənim sıralanır array görünür ki i var sayı.
4 sayar 1 olacaq Ona görə
və 8 sayar 1 olacaq, 23 sayar 2 olacaq.
Belə ki mən sıralanır array daxil istəyirəm necə onları bir çox var.
Mən yalnız bunu.
Mən mənim sıralanır massivinə var num_of_item daxil edirəm.
>> Suallar?
Biz yalnız bir dəfə bu artıq iterating çünki Və yenidən, bu, xətti dəfə
lakin, bu sayı nə də xətti var
və belə ağır sizin bağlı nə asılıdır.
200 bound ilə ki, pis deyil.
Sizin bound 10,000 olacaq, onda ki, bir az pis
Sizin bound, 4 milyard olacaq amma tamamilə real deyil
və bu serialın gerçək olan ölçüsü 4 milyard olmaq üçün gedir.
Belə ki, var. Suallar?
[Işitilemez tələbə cavab] >> OK.
Biz keçir zaman mən başqa bir şey həyata keçirilir.
Mən problem Lucas və yəqin ki, biz gördük hər biri idi.
Mən tamamilə unuttum.
Mən şərh istədi yalnız odur ki, siz göstəriciləri kimi şeyi ilə məşğul olduğunuz zaman
Siz loop üçün yazılı etdiyiniz zaman siz, həqiqətən, bu görmək heç
lakin texniki, zaman, bu göstəriciləri ilə məşğul olduğunuz
Siz olduqca çox həmişə imzalanmamış integers ilə məşğul olmalıdır.
Əgər imzalanmış integers ilə məşğul olduğunuz zaman bu səbəb deyil
2 imzalanmış integers var və onlara birlikdə əlavə əgər
və onlar çox böyük başa, sonra bir mənfi sıra son.
Belə ki, tam daşqın nə var.
>> I 2 milyard, 1 milyard əlavə, mən mənfi 1 milyard son.
Bu integers kompüter iş necə.
Istifadə ilə problem Beləliklə -
Bu, aşağı 2 milyard olur istisna olmaqla, gözəl və qədər 1 milyard olur
bu 1 milyard mənfi olacaq və sonra biz bölmək olacaq ki, 2 ilə
və mənfi 500 milyon ilə başa.
Belə ki, bu bir sıra vasitəsilə axtarış üçün baş, əgər yalnız bir məsələ
şeyi milyardlarla.
Aşağı + qədər daşqın olur əgər Ancaq sonra bir problem var.
Kimi tezliklə biz onları imzasız etmək, sonra 2 milyard plus 1 milyard 3 mlrd.
2 bölünür 3 milyard 1,5 mlrd.
Onlar imzasız edirik ki, tezliklə, hər şey idealdır.
Siz loops üçün yazıyoruz zaman ki, həmçinin bir məsələdir
və həqiqətən, yəqin ki, avtomatik olaraq bunu edir.
Bu, faktiki olaraq yalnız siz fəğan edəcək.
Bu sayı yalnız bir tam olmaq çox böyük amma əgər Belə ki, bir imzasız tam uyğun olardı
bu da fəğan, siz həqiqətən məsələ daxil heç nə ki, belə.
Siz, bir index mənfi olacaq heç vaxt görə bilərsiniz
və belə ki, bir sıra üzərində iterating etdiyiniz zaman
demək olar ki, həmişə i int imzasız deyə bilərsiniz, ancaq siz həqiqətən yoxdur.
Things kimi də olduqca çox iş gedir.
Okay. [Fısıltıyla] Nə vaxt?
Və yalnız həqiqətən sürətli edəcəyik - Mən göstərmək istədim son şey.
Siz biz # 5 və ya bir şey kimi MAX müəyyən edə bilərsiniz ki, biz # müəyyən necə bilirik?
MAX nə edək. # 200 kimi bağlı müəyyən. Yəni biz əvvəl nə var.
Yalnız kopyalanamaz və yapışdırılır olacaq bir sabit, müəyyən
biz bağlı yazmaq nə yerdə.
>> Belə ki, biz, həqiqətən, # müəyyənləşdirir daha çox edə bilərsiniz.
Biz # funksiyaları müəyyən edə bilərsiniz.
Onlar, həqiqətən, funksiyaları deyilik, amma biz onlara funksiyaları zəng edəcəyik.
Məsələn MAX (x, y) kimi bir şey olardı (?: X x <y y) kimi müəyyən edilir. Okay.
Beləliklə, ternary operator syntax istifadə almaq lazımdır
lakin x y azdır? Y qayıt başqa x qayıtmaq.
Belə ki, bu ayrı bir funksiyası edə bilərsiniz
bool MAX 2 arqumentlər edir kimi və funksiya ola bilər, bu qaytarın.
Bu kimi işlər görürəm ən ümumi olanları biridir. Biz onların makro çağırırıq.
Bu makro edir.
Bu yalnız bunun üçün sintaksis edir.
Siz istədiyiniz nə üçün makro yaza bilərsiniz.
Siz tez-tez printfs və stuff ayıklama üçün makro görürük.
Printf növü Belə ki, vurğulamaq LINE vurğulamaq kimi C xüsusi sabitləri var
2, LINE vurğulamaq vurğulayır
və I 2 FUNC vurğulayır düşünmək də var. Bu ola bilər. Kimi bir şey.
Həmin şeylər funksiyası adı ilə əvəz olunacaq
və ya siz olduğunuzu line sayı.
Tez-tez aşağı burada mən yalnız yazmaq ki, hata printfs yazmaq
Debug və xətt nömrəsi və mən olmaq baş verən funksiyası çap edəcək
ki debug bəyanat rast edir.
Və siz də başqa şeylər çap edə bilərsiniz.
Beləliklə, siz diqqət etsinlər bir şey I # DOUBLE_MAX müəyyən baş əgər
2 * y və 2 kimi bir şey kimi * x.
Belə ki, hər hansı səbəbdən, bir çox bunu baş verir.
Belə ki, makro etmək.
Bu əslində pozuldu.
Mən DOUBLE_MAX (3, 6) kimi bir şey etməklə zəng olardı.
Belə ki, nə qaytarılmalıdır?
[Tələbə] 12.
Bəli, 12 qaytarılmalıdır, 12 qaytarılır.
3 x ilə əvəz olur, 6 y üçün əvəz və biz 12 olan 2 * 6, geri olur.
İndi nə bu? Nə geri olmalıdır?
[Tələbə] 14. >> İdeal, 14.
Bu məsələ işin müəyyən necə hash, bir hərfi surəti və yapışdırıb var unutmayın ki,
olduqca çox hər şey, belə ki, nə bu kimi təfsir edilə gedir
1 plus 6, 2 dəfə 1 plus 6, 2 dəfə 3-dən 3 azdır.
>> Belə ki, bu səbəbdən demək olar ki, həmişə mötərizədə hər şeyi kesmek.
Demək olar ki, həmişə mötərizədə bükələnmək hər hansı dəyişən.
Mən burada bunu etmək lazım deyil ki, bilmək kimi yoxdur hallar var,
az olduğu üçün olduqca çox zaman yalnız iş gedir,
baxmayaraq ki, hətta doğru ola bilər.
DOUBLE_MAX (1 == 2) kimi gülünc bir şey varsa,
sonra 3-dən az 1 ilə əvəz almaq olacaq ki, 2 bərabərdir bərabərdir
və belə sonra ki, bərabər 2, 1-dən 3 az nə yazmayıb olacaq
olan biz istədiyiniz nə deyil.
Belə ki, hər hansı operator üstün problemlərin qarşısını almaq üçün,
həmişə parantez bükələnmək.
Okay. Və bu, 5:30 bu.
Siz pset hər hansı bir sualınız varsa, bizə bildirin.
Bu fun olmalıdır və hacker nəşr də daha realdır
Ötən il də hacker nəşr daha sizə bir çox cəhd ümid edirik.
Ötən il çox böyük idi.
>> [CS50.TV]