[Powered by Google Translate] [Seksyen 3 - Lebih Selesa]
[Rob Bowden - Universiti Harvard]
>> [Ini adalah CS50. - CS50.TV]
>> Jadi soalan pertama pelik worded.
GDB membolehkan anda "debug" program, tetapi, lebih khusus, apakah ia membiarkan anda lakukan?
Saya akan menjawab yang satu, dan saya tidak tahu apa yang sebenarnya dijangka,
jadi saya meneka ia sesuatu yang di sepanjang garisan ia membolehkan anda langkah demi langkah
berjalan melalui program ini, berinteraksi dengan ia, pembolehubah perubahan, melakukan semua perkara ini -
pada dasarnya sepenuhnya mengawal pelaksanaan program
dan memeriksa mana-mana bahagian yang diberikan pelaksanaan program.
Jadi ciri-ciri membolehkan anda debug perkara.
Okay.
Mengapa gelintaran perduaan memerlukan bahawa array perlu diselesaikan?
Siapa yang mahu untuk menjawab bahawa?
[Pelajar] Kerana ia tidak berfungsi jika ia tidak diselesaikan. >> Yeah. [Ketawa]
Jika ia tidak diselesaikan, maka ia adalah mustahil untuk berpecah pada separuh
dan tahu bahawa segala-galanya ke kiri adalah kurang dan segala-galanya ke kanan
adalah lebih besar daripada nilai tengah.
Jadi ia perlu diselesaikan.
Okay.
Mengapa isih gelembung di O n kuasa dua?
Adakah sesiapa yang mula-mula mahu memberikan gambaran peringkat tinggi yang sangat cepat apa jenis gelembung?
[Pelajar] Anda pada dasarnya pergi melalui setiap elemen dan anda menyemak beberapa elemen pertama.
Jika mereka berada di luar di mana anda menukar mereka, maka anda memeriksa unsur-unsur yang akan datang dan sebagainya.
Apabila anda sampai akhir, maka anda tahu bahawa elemen terbesar diletakkan di hujung,
jadi anda mengabaikan bahawa salah maka anda terus melalui,
dan setiap kali anda perlu menyemak satu elemen kurang sehingga anda tidak membuat perubahan. >> Yeah.
Ia dipanggil isih gelembung kerana jika anda flip array di sebelah jadi ia terpulang dan ke bawah, menegak,
maka nilai-nilai yang besar akan tenggelam ke bawah dan nilai kecil akan gelembung sehingga ke atas.
Itulah bagaimana ia mendapat namanya.
Dan yeah, anda hanya pergi melalui.
Anda terus melalui array, bertukar-tukar nilai yang lebih besar
untuk mendapatkan nilai terbesar ke bawah.
>> Mengapa ia O n kuasa dua?
Pertama, adakah sesiapa yang mahu untuk mengatakan mengapa ia O n kuasa dua?
[Pelajar] Kerana setiap untuk menjalankan ia pergi n kali.
Anda hanya boleh memastikan bahawa anda telah mengambil elemen terbesar sepanjang jalan ke bawah,
maka anda perlu untuk mengulangi bahawa sebagai banyak unsur. >> Yeah.
Jadi ingat apa yang besar O bermakna dan apa cara Omega besar.
O besar adalah seperti atas terikat kepada berapa perlahan ia sebenarnya boleh dijalankan.
Jadi dengan mengatakan O n kuasa dua, ia tidak O n atau lain ia akan dapat menjalankan
dalam masa linear, tetapi ia adalah O n cubed
kerana ia disempadani oleh O n cubed.
Jika ia disempadani oleh O n kuasa dua, maka ia disempadani juga oleh n cubed.
Jadi ia n persegi, dan dalam kes terburuk mutlak, ia tidak boleh melakukan lebih baik daripada n kuasa dua,
itulah sebabnya ia O n kuasa dua.
Jadi untuk melihat matematik sedikit bagaimana ia datang n kuasa dua,
jika kita mempunyai lima perkara dalam senarai kami, kali pertama berapa swap boleh kita berpotensi perlu membuat
dalam usaha untuk mendapatkan ini? Mari kita sebenarnya hanya -
Berapa ramai swap kita akan perlu membuat dalam jangka pertama apapun gelembung melalui array?
[Pelajar] n - 1. >> Yeah.
>> Jika terdapat 5 elemen, kita akan perlu untuk membuat n - 1.
Kemudian pada satu kedua berapa swap yang kita akan mempunyai untuk membuat?
[Pelajar] n - 2. >> Yeah.
Dan ketiga akan menjadi n - 3, dan kemudian untuk kemudahan saya akan menulis dua lepas
sebagai maka kita akan perlu untuk membuat 2 swap dan 1 swap.
Saya rasa yang terakhir mungkin atau mungkin sebenarnya tidak perlu berlaku.
Adakah ia swap? Saya tidak tahu.
Jadi ini adalah jumlah swap atau sekurang-kurangnya perbandingan anda perlu membuat.
Malah jika anda tidak menukar, anda masih perlu untuk membandingkan nilai.
Jadi terdapat n - 1 perbandingan dalam jangka pertama melalui array.
Jika anda menyusun semula perkara-perkara ini, mari kita sebenarnya membuat ia enam perkara supaya timbunan perkara baik,
dan kemudian saya akan melakukan 3, 2, 1.
Jadi hanya menyusun semula jumlah ini, kita mahu lihat berapa banyak perbandingan kita membuat
di seluruh algoritma.
Jadi, jika kita membawa lelaki ini di sini,
maka kita masih hanya menjumlahkan perbandingan bagaimanapun banyak terdapat.
Tetapi jika kita jumlah ini dan kita kesimpulan ini dan kita kesimpulan ini,
ia masih masalah yang sama. Kami hanya jumlah kumpulan-kumpulan tertentu.
>> Jadi sekarang kita menjumlahkan 3 n. Ia bukan hanya 3 n.
Ia sentiasa akan menjadi n / 2 n.
Jadi di sini kita berlaku mempunyai 6.
Jika kita mempunyai 10 perkara, maka kita boleh melakukannya kumpulan ini selama 5 pasang perkara yang berbeza
dan berakhir dengan n + n + n + n + n.
Jadi anda sentiasa akan mendapat n / 2 n, dan jadi ini kita akan sedikitpun ia keluar n kuasa dua / 2.
Dan sebagainya walaupun ia adalah faktor separuh, yang berlaku untuk datang dalam
kerana hakikat bahawa melalui setiap lelaran seluruh array kita bandingkan 1 kurang
supaya bagaimana kita mendapat lebih dari 2, tetapi ia masih n kuasa dua.
Kami tidak mengambil berat tentang faktor pemalar setengah.
Jadi banyak barangan O besar seperti ini bergantung pada jenis hanya melakukan ini jenis matematik,
melakukan aritmetik jumlah wang dan barangan siri geometri,
tetapi kebanyakan mereka dalam kursus ini adalah agak mudah.
Okay.
Mengapa adalah jenis kemasukan dalam Omega n? Apakah omega maksudkan?
[Dua pelajar bercakap pada sekali difahami] >> Yeah.
Omega anda boleh berfikir sebagai rendah terikat.
>> Jadi tidak kira bagaimana cekap algoritma apapun kemasukan anda,
tanpa mengira senarai yang diluluskan dalam, ia sentiasa mempunyai untuk membandingkan sekurang-kurangnya n perkara
atau ia mempunyai untuk melelar atas perkara-perkara n.
Mengapa?
[Pelajar] Kerana jika senarai sudah disusun, kemudian melalui lelaran pertama
anda hanya boleh menjamin bahawa elemen yang sangat pertama adalah sekurang-kurangnya,
dan lelaran kedua anda hanya boleh menjamin dua yang pertama adalah
kerana anda tidak tahu bahawa seluruh senarai diisih. >> Yeah.
Jika anda lulus dalam senarai disusun sepenuhnya, sekurang-kurangnya anda perlu pergi ke atas semua unsur-unsur
untuk melihat bahawa tiada apa yang perlu digerakkan.
Jadi memaafkan senarai dan berkata, oh, ini sudah disusun,
ia adalah mustahil untuk anda tahu ia disusun sehingga anda memeriksa setiap elemen
untuk melihat bahawa mereka berada dalam perintah disusun.
Jadi lebih rendah terikat pada apapun kemasukan adalah Omega n.
Apa kes terburuk berjalan masa apapun bergabung,
kes terburuk O besar lagi?
Jadi dalam senario kes terburuk, bagaimana apapun merge berjalan?
[Pelajar] N log n. >> Yeah.
Sorting terpantas algoritma am n log n. Anda tidak boleh melakukan yang lebih baik.
>> Terdapat kes-kes khas, dan jika kita mempunyai masa hari ini - tetapi kita mungkin won't -
kita boleh melihat salah satu yang tidak lebih baik daripada n log n.
Tetapi dalam kes umum, anda tidak boleh melakukan lebih baik daripada n log n.
Dan bergabung apapun yang berlaku kepada menjadi salah satu yang perlu anda tahu untuk kursus ini yang n log n.
Dan sebagainya kita sebenarnya akan melaksanakan bahawa hari ini.
Dan akhirnya, tidak lebih daripada tiga ayat, bagaimanakah pemilihan kerja apapun?
Adakah seseorang mahu menjawab, dan saya akan mengira ayat anda
kerana jika anda pergi ke 3 -
Adakah sesiapa ingat apapun pemilihan?
Apapun pemilihan adalah biasanya agak mudah untuk ingat hanya dari nama.
Anda hanya melelar lebih array, mendapati apa sahaja nilai terbesar atau terkecil -
apa jua perintah yang anda sedang menyusun masuk
Jadi mari kita mengatakan bahawa kita sedang sorting daripada yang terkecil kepada yang terbesar.
Anda melelar lebih array, mencari apa jua elemen minimum,
pilih ia, dan kemudian hanya menukar apa sahaja yang berada di tempat pertama.
Dan kemudian pada pas kedua lebih array, mencari elemen minimum lagi,
pilih ia, dan kemudian swap dengan apa yang di kedudukan kedua.
Jadi kita hanya memilih dan nilai minimum
dan memasukkan mereka ke hadapan array sehingga ia disusun.
Soalan pada itu?
>> Ini tidak dapat dielakkan muncul dalam bentuk yang anda perlu mengisi apabila anda menyerahkan pset.
Mereka pada dasarnya adalah jawapan kepada mereka.
Okay, jadi sekarang pengekodan masalah.
Saya sudah dihantar melalui e-mel - Adakah sesiapa yang tidak mendapat e-mel yang? Okay.
Saya sudah dihantar melalui e-mel ruang bahawa kita akan menggunakan,
dan jika anda klik pada nama saya - jadi saya fikir saya akan berada di bawah
kerana r ke belakang - tetapi jika anda klik pada nama saya, anda akan melihat 2 semakan.
Ulangkaji 1 akan saya sudah disalin dan ditampal kod ke dalam kawasan
untuk perkara carian anda akan mempunyai untuk melaksanakan.
Dan Semakan 2 akan menjadi perkara apapun yang kita laksanakan selepas itu.
Jadi, anda boleh klik Semakan saya pada 1 dan bekerja dari sana.
Dan sekarang kita mahu untuk melaksanakan carian binari.
>> Adakah sesiapa yang mahu hanya memberi pseudokod peringkat tinggi penjelasan
apa kita akan perlu lakukan untuk carian? Yeah.
[Pelajar] Anda hanya mengambil pertengahan array dan lihat jika apa yang anda sedang mencari
adalah kurang daripada itu atau lebih daripada itu.
Dan jika ia kurang, anda pergi ke separuh yang kurang,
dan jika ia lebih, anda pergi separuh yang lebih dan anda mengulangi bahawa sehingga anda hanya mendapat satu perkara.
[Bowden] Yeah.
Perhatikan bahawa pelbagai nombor kita sudah disusun,
dan sebagainya yang bermakna bahawa kita boleh mengambil kesempatan daripada itu dan kita pertama boleh memeriksa,
okay, saya mencari bilangan 50.
Jadi, saya boleh pergi ke tengah-tengah.
Tengah adalah sukar untuk menentukan apabila ia adalah nombor genap perkara,
tetapi mari kita hanya mengatakan kita akan sentiasa menyingkatkan ke tengah.
Jadi di sini kita mempunyai 8 perkara, jadi tengah-tengah akan menjadi 16.
Saya mencari 50, jadi 50 adalah lebih besar daripada 16.
Jadi sekarang saya pada dasarnya boleh merawat pelbagai saya sebagai elemen-elemen ini.
Saya boleh buang segala-galanya dari 16 lebih.
Sekarang pelbagai saya hanya 4 elemen ini, dan saya ulangi.
Jadi maka saya ingin mencari tengah lagi, yang akan menjadi 42.
42 adalah kurang daripada 50, jadi saya boleh buang kedua-dua elemen.
Ini adalah pelbagai baki saya.
Saya akan mencari tengah lagi.
Saya rasa 50 adalah satu contoh yang buruk kerana saya sentiasa membuang perkara-perkara ke kiri,
tetapi dengan langkah yang sama, jika saya mencari sesuatu
dan ia adalah kurang daripada unsur Saya kini melihat,
maka saya akan buang segala-galanya ke kanan.
Jadi sekarang kita perlu untuk melaksanakan bahawa.
Perhatikan bahawa kita perlu lulus dalam saiz.
Kita boleh juga tidak perlu kepada saiz-kod keras.
Jadi, jika kita menghilangkan itu # define -
Okay.
Bagaimana saya boleh baik memikirkan apa saiz array nombor kini?
>> Berapa banyak elemen dalam pelbagai nombor?
[Pelajar] Nombor, kurungan, panjang?
[Bowden] Itu tidak wujud di C.
Perlukan. Panjang.
Tatasusunan tidak mempunyai sifat, jadi tiada harta panjang tatasusunan
yang hanya akan memberi anda walau bagaimana lama ia berlaku.
[Pelajar] Lihat berapa banyak memori ia mempunyai dan membahagikan oleh berapa banyak - >> Yeah.
Jadi bagaimana kita boleh melihat berapa banyak memori ia mempunyai? >> [Pelajar] Sizeof. >> Yeah, sizeof.
Sizeof adalah pengendali itu akan kembali saiz array nombor.
Dan itu akan menjadi integer bagaimanapun banyak terdapat kali saiz integer
kerana itulah berapa banyak memori ia sebenarnya mengambil.
Jadi, jika saya mahu beberapa perkara dalam array,
maka saya akan mahu untuk membahagikan oleh saiz integer.
Okay. Jadi yang membolehkan saya lulus dalam saiz di sini.
Mengapa saya perlukan untuk lulus dalam saiz pada semua?
Mengapa saya tidak boleh hanya melakukan di sini saiz int = sizeof (sisa rumput kering) / sizeof (int)?
Mengapa ini tidak berfungsi?
[Pelajar] Ia bukan satu pembolehubah global.
[Bowden] Haystack wujud dan kita lulus dalam nombor sebagai sisa rumput kering,
dan ini adalah jenis berciri bayangan apa yang akan datang. Yeah.
[Pelajar] Haystack adalah hanya merujuk kepada ia, maka ia akan kembali bagaimana besar rujukan yang.
Yeah.
Saya ragu-ragu dalam syarahan bahawa anda telah melihat timbunan lagi benar-benar, betul-betul?
Kita baru sahaja bercakap mengenainya.
Jadi tindanan adalah di mana semua pembolehubah anda akan disimpan.
>> Mana-mana memori yang diperuntukkan bagi pembolehubah tempatan akan dalam tindanan,
dan setiap fungsi mendapat ruang sendiri pada timbunan, bingkai tindanan sendiri adalah apa ia dipanggil.
Jadi utama mempunyai bingkai tindanan, dan di dalamnya akan wujud pelbagai nombor,
dan ia akan menjadi sizeof saiz (nombor).
Ia akan mempunyai saiz nombor dibahagikan dengan saiz unsur-unsur,
tetapi yang semua kehidupan dalam bingkai tindanan utama.
Apabila kita panggil carian, search mendapat bingkai tindanan sendiri,
ruang sendiri untuk menyimpan semua pembolehubah tempatan.
Tetapi hujah ini - jadi sisa rumput kering bukan satu salinan seluruh array ini.
Kami tidak lulus dalam pelbagai keseluruhan sebagai salinan ke carian.
Ia hanya pas rujukan kepada pelbagai itu.
Jadi carian boleh mengakses nombor-nombor ini melalui rujukan ini.
Ia masih mengakses perkara yang hidup di dalam bingkai tindanan utama,
tetapi pada dasarnya, apabila kita mendapat petunjuk, yang sepatutnya tidak lama lagi,
ini adalah apa petunjuk.
Penunjuk hanya rujukan kepada perkara-perkara, dan anda boleh menggunakan petunjuk untuk mengakses perkara-perkara
yang dalam bingkai tindanan perkara lain '.
Jadi, walaupun nombor tempatan utama, kita masih boleh mengakses melalui penunjuk ini.
Tetapi oleh kerana ia hanya penunjuk dan ia hanya rujukan,
sizeof (sisa rumput kering) hanya mengembalikan saiz rujukan sendiri.
Ia tidak akan kembali saiz perkara yang ia menunjuk ke.
Ia tidak akan kembali saiz sebenar nombor.
Dan sebagainya ini tidak akan bekerja seperti yang kita mahu ia.
>> Soalan pada itu?
Penunjuk akan pergi ke terperinci ketara lebih ngeri dalam minggu akan datang.
Dan ini adalah mengapa banyak perkara yang anda lihat, perkara carian yang paling atau perkara apapun,
mereka hampir semua akan perlu mengambil saiz sebenar array,
kerana dalam C, kita tidak mempunyai idea apa saiz array.
Anda perlu untuk manual lulus ia masuk
Dan anda tidak boleh secara manual lulus di seluruh array kerana anda hanya lulus dalam rujukan
dan ia tidak boleh mendapatkan saiz dari rujukan.
Okay.
Jadi sekarang kita mahu melaksanakan apa yang telah dijelaskan sebelum.
Anda boleh bekerja di atasnya selama satu minit,
dan anda tidak perlu bimbang tentang mendapatkan segala-galanya sempurna 100% bekerja.
Hanya menulis pseudokod separuh untuk bagaimana anda berfikir ia harus bekerja.
Okay.
Tidak perlu benar-benar dilakukan dengan ini lagi.
Tetapi adakah sesiapa yang berasa selesa dengan apa yang mereka miliki setakat ini,
seperti sesuatu yang kita boleh bekerja dengan bersama-sama?
Adakah sesiapa yang mahu untuk sukarelawan? Atau saya secara rawak akan memilih.
Ia tidak perlu untuk menjadi betul-betul oleh apa-apa langkah tetapi sesuatu yang kita boleh mengubah ke dalam keadaan bekerja.
[Pelajar] Pasti. >> Okay.
Jadi, anda boleh menyimpan semakan dengan mengklik pada ikon Simpan sedikit.
Anda Ramya, kan? >> [Pelajar] Yeah. >> [Bowden] Okay.
Jadi sekarang saya boleh melihat semakan anda dan semua orang boleh tarik sehingga semakan.
Dan di sini kita mempunyai - Okay.
Jadi Ramya pergi dengan penyelesaian rekursi, yang pastinya satu penyelesaian yang sah.
Terdapat dua cara yang boleh anda lakukan masalah ini.
Anda boleh melakukannya iterative atau rekursif.
Kebanyakan masalah yang anda hadapi yang boleh dilakukan secara rekursif juga boleh dilakukan iterative.
Jadi di sini kita telah melakukannya rekursif.
>> Adakah seseorang mahu untuk menentukan apa yang ia bermaksud untuk membuat fungsi rekursi?
[Pelajar] Apabila anda mempunyai fungsi panggilan sendiri
dan kemudian memanggil dirinya sehingga ia datang keluar dengan benar dan benar. >> Yeah.
Satu fungsi rekursi hanya fungsi yang menyeru sendiri.
Terdapat tiga perkara yang besar bahawa fungsi rekursi mesti mempunyai.
Yang pertama adalah jelas, ia memerlukan sendiri.
Yang kedua ialah kes asas.
Jadi, pada satu ketika fungsi perlu untuk berhenti memanggil dirinya,
dan itulah apa kes asas adalah untuk.
Jadi di sini kita tahu bahawa kita perlu berhenti, kita harus berputus asa dalam pencarian kami
apabila permulaan bersamaan akhir - dan kami akan pergi ke atas apa yang bermakna.
Tetapi akhirnya, perkara terakhir yang penting untuk fungsi rekursi:
fungsi entah bagaimana mesti mendekati kes asas.
Seperti jika anda sebenarnya tidak mengemaskini apa-apa apabila anda membuat panggilan rekursi kedua,
jika anda benar-benar hanya memanggil fungsi lagi dengan hujah-hujah yang sama
dan tiada pembolehubah global telah berubah atau apa-apa,
anda tidak akan sampai ke kes asas, di mana yang buruk.
Ia akan menjadi satu rekursi tidak terhingga dan limpahan tindanan.
Tetapi di sini kita lihat bahawa kemas kini berlaku kerana kita sedang mengemaskini memulakan + akhir / 2,
kami sedang mengemaskini hujah akhir di sini, kami sedang mengemaskini hujah mula di sini.
Jadi dalam semua panggilan rekursi kita sedang mengemaskini sesuatu. Okay.
Adakah anda ingin untuk berjalan kita melalui penyelesaian anda? >> Pasti.
Saya menggunakan SearchHelp supaya setiap kali saya membuat panggilan ini fungsi
Saya mempunyai permulaan di mana saya mencari dalam pelbagai dan akhir
di mana saya mencari array.
>> Pada setiap langkah di mana ia mengatakan ia adalah elemen tengah, yang merupakan permulaan + akhir / 2,
ialah sama dengan apa yang kita cari?
Dan jika ia, maka kita mendapati ia, dan saya rasa yang mendapat diluluskan sehingga tahap rekursi.
Dan jika itu tidak benar, maka kita memeriksa sama ada yang nilai pertengahan array adalah terlalu besar,
di mana kita melihat separuh kiri array dengan pergi dari awal hingga indeks pertengahan.
Dan sebaliknya kita lakukan separuh akhir.
[Bowden] Okay.
Itulah bunyi yang baik.
Okay, jadi beberapa perkara, dan sebenarnya, ini adalah satu perkara yang sangat peringkat tinggi
bahawa anda tidak akan perlu tahu untuk kursus ini, tetapi ia adalah benar.
Fungsi rekursi, anda sentiasa mendengar bahawa mereka banyak yang buruk
kerana jika anda rekursif memanggil diri anda terlalu banyak kali, anda akan mendapat limpahan timbunan
kerana, seperti yang saya katakan sebelum ini, setiap fungsi mendapat bingkai tindanan sendiri.
Jadi setiap panggilan fungsi rekursi mendapat bingkai tindanan sendiri.
Jadi, jika anda membuat 1,000 panggilan rekursi, anda akan mendapat 1,000 bingkai tindanan,
dan cepat anda membawa untuk mempunyai bingkai tindanan terlalu banyak dan perkara-perkara yang hanya memecahkan.
Jadi itulah sebabnya fungsi rekursi umumnya buruk.
Tetapi terdapat subset bagus fungsi rekursi dipanggil fungsi ekor rekursi,
dan ini berlaku untuk menjadi contoh di mana jika pengkompil notis ini
dan ia sepatutnya, saya fikir dilafaz jika anda lulus-O2 bendera
maka ia akan melihat ini adalah rekursi ekor dan membuat perkara-perkara yang baik.
>> Ia akan menggunakan semula bingkai tindanan yang sama berulang-ulang kali untuk setiap panggilan rekursi.
Dan sebagainya kerana anda sedang menggunakan bingkai tindanan yang sama, anda tidak perlu bimbang tentang
pernah timbunan melimpah, dan pada masa yang sama, seperti yang anda katakan sebelum ini,
di mana apabila anda kembali benar, maka ia telah kembali sehingga semua ini bingkai tindanan
dan panggilan ke-10 SearchHelp telah kembali ke 9, mempunyai untuk kembali ke 8.
Jadi yang tidak perlu berlaku apabila fungsi rekursi ekor.
Dan jadi apa membuat ini ekor fungsi rekursi ialah notis bahawa bagi apa-apa panggilan yang diberikan kepada searchHelp
panggilan rekursi bahawa ia membuat apa ia kembali.
Jadi dalam panggilan pertama untuk SearchHelp, sama ada kita dengan serta-merta mengembalikan palsu,
dengan serta-merta mengembalikan benar, atau kita membuat panggilan rekursi untuk SearchHelp
mana apa kita kembali apa panggilan yang kembali.
Dan kita tidak boleh melakukan ini jika kita melakukan sesuatu seperti int x = SearchHelp, pulangan x * 2,
hanya beberapa perubahan rawak.
>> Jadi sekarang ini panggilan rekursi, int ini x = SearchHelp panggilan rekursi,
tidak lagi ekor rekursi kerana ia sebenarnya tidak perlu untuk kembali
kembali kepada bingkai timbunan sebelumnya supaya bahawa panggilan sebelumnya kepada fungsi
kemudian boleh melakukan sesuatu dengan nilai pulangan.
Jadi ini tidak rekursi ekor, tetapi apa yang kita telah sebelum ini baik ekor rekursi. Yeah.
[Pelajar] Tidakkah kes asas kedua diperiksa pertama
kerana mungkin ada keadaan di mana apabila anda lulus ia hujah
anda telah memulakan akhir =, tetapi mereka adalah nilai jarum.
Soalan itu tidak boleh kita lari ke dalam kes di mana akhir adalah nilai jarum
atau memulakan akhir = sewajarnya, memulakan akhir =
dan anda telah sebenarnya tidak diperiksa bahawa nilai tertentu lagi,
kemudian memulakan + akhir / 2 hanya akan menjadi nilai yang sama.
Tetapi kita sudah dikembalikan palsu dan kita tidak pernah benar-benar diperiksa nilai.
Jadi, sekurang-kurangnya, dalam panggilan pertama, jika saiz adalah 0, maka kita mahu untuk kembali palsu.
Tetapi jika saiz adalah 1, maka mula tidak akan ke hujung sama,
dan kita sekurang-kurangnya akan memeriksa elemen satu.
Tetapi saya fikir anda adalah betul bahawa kita boleh berakhir di dalam kes di mana bermula + akhir / 2,
permulaan berakhir sehingga menjadi sama sebagai permulaan + akhir / 2,
tetapi kita tidak pernah benar-benar diperiksa elemen yang.
>> Jadi, jika kita periksa dahulu adalah elemen tengah nilai kita sedang mencari,
maka kita segera boleh kembali benar.
Lain jika mereka sama, maka tidak ada gunanya meneruskan
kerana kita hanya akan mengemaskini kepada kes di mana kita berada pada pelbagai unsur tunggal.
Jika bahawa elemen tunggal tidak adalah satu yang kita cari,
maka segala-galanya adalah salah. Yeah.
[Pelajar] Masalahnya ialah bahawa sejak saiz sebenarnya adalah lebih besar daripada bilangan elemen dalam array,
sudah terdapat offset - >> Jadi akan saiz -
[Pelajar] Katakanlah (wahai Muhammad) jika array adalah saiz 0, maka SearchHelp sebenarnya akan menyemak sisa rumput kering daripada 0
panggilan pertama.
Array mempunyai saiz 0, jadi 0 adalah - >> Yeah.
Ada satu lagi perkara yang - ia mungkin baik. Mari kita berfikir.
Jadi jika array mempunyai 10 elemen dan satu tengah kita pergi untuk memeriksa ialah indeks 5,
jadi kita memeriksa 5, dan katakan bahawa nilainya adalah kurang.
Jadi kita membuang segala-galanya jauh daripada 5 seterusnya.
Jadi bermula + akhir / 2 akan menjadi akhir baru kami,
supaya yeah, ia sentiasa akan tinggal di luar akhir array.
Jika ia adalah kes jika ia adalah genap atau ganjil, maka kita akan memeriksa, katakan, 4,
tetapi kita masih membuang -
Jadi yeah, akhir sentiasa akan menjadi luar akhir sebenar array.
Jadi elemen kami memberi tumpuan kepada, akhir sentiasa akan menjadi satu selepas itu.
Dan jadi jika permulaan tidak pernah akhir yang sama, kita berada dalam pelbagai saiz 0.
>> Perkara lain saya memikirkan kita sedang mengemaskini bermula untuk memulakan + akhir / 2,
jadi ini adalah kes bahawa saya mempunyai masalah dengan, di mana bermula + akhir / 2
adalah elemen yang kita sedang memeriksa.
Katakan kita mempunyai pelbagai 10-unsur ini. Apa sahaja.
Jadi bermula + akhir / 2 akan menjadi sesuatu yang seperti ini,
dan jika itu tidak nilai, katakan kita mahu untuk mengemaskini.
Nilai adalah lebih besar, jadi kita mahu melihat setengah ini array.
Jadi bagaimana kita hendak mengemaskini permulaan, kita sedang mengemaskini awal hingga kini menjadi elemen ini.
Tetapi ini masih boleh bekerja, atau sekurang-kurangnya, anda boleh melakukan permulaan + akhir / 2 + 1.
[Pelajar] Anda tidak perlu memulakan akhir + [didengar] >> Yeah.
Kami telah diperiksa elemen ini dan tahu ia bukan satu yang kita cari.
Jadi kita tidak perlu untuk mengemas kini mula menjadi elemen ini.
Kita hanya boleh melangkau ia dan mengemas kini mula menjadi elemen ini.
Dan ada pernah kes, katakan, bahawa ini adalah akhir,
demikian maka mula akan ini, mulakan + akhir / 2 akan ini,
bermula akhir + - Ya, saya fikir ia boleh berakhir dalam rekursi tidak terhingga.
Katakan ia hanya pelbagai saiz 2 atau pelbagai saiz daripada 1. Saya rasa ini akan bekerja.
Jadi, pada masa ini, permulaan adalah bahawa elemen dan akhir adalah 1 melebihinya.
Jadi elemen yang kita pergi untuk memeriksa adalah salah satu ini,
dan kemudian apabila kita mengemaskini permulaan, kami mengemas kini mula menjadi 0 + 1/2,
yang akan berakhir kita kembali dengan permulaan menjadi elemen ini.
>> Jadi kita sedang memeriksa unsur yang sama berulang-ulang kali.
Jadi ini adalah kes di mana setiap panggilan rekursi sebenarnya mesti mengemaskinikan sesuatu.
Jadi yang perlu kita lakukan permulaan + akhir / 2 + 1, atau lain ada kes
di mana kita sebenarnya tidak mengemaskini permulaan.
Semua orang melihat bahawa?
Okay.
Adakah sesiapa yang mempunyai soalan mengenai penyelesaian ini atau apa-apa lebih banyak komen?
Okay. Adakah sesiapa yang telah lelaran penyelesaian yang kita semua boleh melihat?
Adakah kita semua melakukannya rekursif?
Atau juga saya rasa jika anda membuka perempuan, maka anda mungkin mempunyai diatasi yang sebelumnya.
Adakah ia menyimpan secara automatik? Saya tidak positif.
Adakah sesiapa yang telah lelaran?
Kita boleh berjalan melaluinya bersama-sama jika tidak.
Idea ini akan menjadi sama.
Lelaran penyelesaian.
Kami akan mahu pada dasarnya melakukan idea yang sama
di mana kita mahu menjejaki akhir baru array dan permulaan yang baru array
dan berbuat demikian berulang.
Dan jika apa yang kita sedang mengesan sebagai permulaan dan akhir yang pernah bersilang,
maka kita tidak mendapati ia dan kita boleh kembali palsu.
Jadi bagaimana saya boleh berbuat demikian? Sesiapa yang mempunyai cadangan atau kod bagi saya untuk tarik sehingga?
[Pelajar] Adakah gelung sementara. >> Yeah.
Anda akan mahu untuk melakukan gelung.
>> Adakah anda mempunyai kod saya boleh tarik ke atas, atau apa yang anda akan mencadangkan?
[Pelajar] Saya fikir begitu. >> Baiklah. Ini menjadikan perkara yang mudah. Apa nama anda?
[Pelajar] Lucas.
Ulangkaji 1. Okay.
Rendah adalah apa yang kita dipanggil bermula sebelum.
Sehingga tidak cukup apa yang kita dipanggil akhir sebelum.
Sebenarnya, akhir kini dalam array. Ia merupakan satu elemen kita harus mempertimbangkan.
Begitu rendah adalah 0, sehingga saiz array - 1,
dan sekarang kita sedang gelung, dan kita memeriksa -
Saya rasa anda boleh berjalan melalui.
Apakah pemikiran anda melalui ini? Berjalan kami melalui kod anda.
[Pelajar] Pasti. Lihatlah nilai sisa rumput kering di tengah-tengah dan membandingkannya dengan jarum.
Jadi, jika ia adalah lebih besar daripada jarum anda, maka anda mahu - oh, sebenarnya, yang harus ke belakang.
Anda akan mahu buang separuh yang betul, dan sebagainya yeah, yang sepatutnya menjadi cara.
[Bowden] Jadi ini harus menjadi kurang? Adakah bahawa apa yang anda katakan? >> [Pelajar] Yeah.
[Bowden] Okay. Kurang.
Jadi, jika apa yang kita melihat adalah lebih kecil daripada apa yang kita mahu,
kemudian yeah, kita mahu buang separuh kiri,
yang bermakna kita sedang mengemaskini segala apa yang kita sedang mempertimbangkan
dengan bergerak rendah ke kanan array.
Ini kelihatan baik.
Saya rasa ia mempunyai isu yang sama bahawa kita berkata pada yang sebelumnya,
di mana jika rendah adalah 0 dan adalah 1, maka rendah + up / 2 akan ditubuhkan untuk menjadi perkara yang sama sekali lagi.
>> Dan walaupun itu bukan kes itu, ia masih lebih cekap sekurang-kurangnya
hanya buang elemen kita hanya melihat di mana kita tahu adalah salah.
Begitu rendah + up / 2 + 1 - >> [pelajar] Itu harus cara lain.
[Bowden] Atau ini perlu - 1 dan satu lagi harus + 1.
[Pelajar] Dan perlu ada double tanda sama. >> [Bowden] Yeah.
[Pelajar] Yeah.
Okay.
Dan akhirnya, sekarang bahawa kita mempunyai ini 1 + - 1 perkara,
ia - ia mungkin tidak - adalah ia pernah mungkin rendah untuk menamatkan dengan nilai yang lebih besar daripada sehingga?
Saya fikir satu-satunya cara yang boleh berlaku - Adakah ia mungkin? >> [Pelajar] saya tidak tahu.
Tetapi jika ia mendapat dipenggal dan kemudian mendapat tolak bahawa 1 dan kemudian - >> Yeah.
[Pelajar] Ia mungkin akan mendapat sehingga merosakkan.
Saya fikir ia harus baik hanya kerana
untuk ia berakhir lebih rendah, mereka akan mempunyai untuk menjadi sama, saya fikir.
Tetapi jika mereka adalah sama, maka kita tidak akan melakukan gelung sementara bermula dengan
dan kita hanya akan kembali nilai. Jadi saya fikir kita baik sekarang.
Perhatikan bahawa walaupun masalah ini adalah tidak lagi rekursi,
jenis yang sama idea memohon mana kita boleh melihat bagaimana ini begitu mudah meminjamkan sendiri
kepada penyelesaian rekursi oleh hakikat bahawa kita hanya mengemaskini indeks berulang kali,
kita membuat masalah yang lebih kecil dan lebih kecil, kami memberi tumpuan kepada subset array.
[Pelajar] Jika rendah adalah 0 dan sehingga adalah 1, kedua-dua mereka akan menjadi 0 + 1/2, yang akan pergi kepada 0,
dan maka seseorang akan menjadi + 1, seseorang akan menjadi - 1.
[Pelajar] mana kita memeriksa kesaksamaan?
Seperti jika satu tengah sebenarnya adalah jarum?
Kami kini tidak berbuat demikian? Oh!
Jika it's -
Ya. Kita tidak boleh hanya melakukan ujian turun di sini kerana katakan pertengahan pertama -
[Pelajar] Ia sebenarnya tidak buang terikat.
Jadi, jika anda buang terikat, anda perlu untuk memeriksa ia mula-mula atau apa sahaja.
Ah. Yeah. >> [Pelajar] Yeah.
Jadi sekarang kita telah dibuang satu kita kini melihat,
yang bererti kita kini perlu juga mempunyai
jika (sisa rumput kering [(rendah + anak) / 2] == jarum), maka kita boleh kembali benar.
Dan sama ada saya meletakkan lain atau hanya jika, ia bermaksud secara literal perkara yang sama
kerana ini akan dikembalikan benar.
Jadi saya akan meletakkan lain jika, tetapi ia tidak mengapa.
>> Jadi lain jika ini, lain ini, dan ini adalah satu perkara yang biasa saya lakukan
di mana walaupun ia adalah kes di mana segala-galanya adalah baik di sini,
seperti rendah tidak boleh lebih dari meningkat naik, ia bukan hujah yang bernilai kira-kira sama ada yang benar.
Jadi anda juga boleh mengatakan manakala yang rendah adalah kurang daripada atau sama dengan
atau semasa rendah adalah kurang daripada
jadi jika mereka yang pernah sama atau rendah berlaku untuk melalukan,
maka kita boleh keluar gelung ini.
Soalan, kebimbangan, komen?
Okay. Ini kelihatan baik.
Sekarang kita ingin melakukan apapun.
Jika kita pergi ke semakan kedua saya, kita lihat nombor-nombor yang sama,
tetapi kini mereka tidak lagi dalam usaha disusun.
Dan kita mahu untuk melaksanakan apapun menggunakan mana-mana algoritma di O n log n.
Jadi algoritma manakah anda fikir kita perlu melaksanakan di sini? >> [Pelajar] Gabung apapun.
[Bowden] Yeah. Gabung apapun adalah O (n log n), supaya apa yang kita hendak lakukan.
Dan masalah itu akan menjadi cantik serupa,
di mana ia mudah meminjamkan sendiri kepada penyelesaian rekursi.
Kita juga boleh tampil dengan penyelesaian lelaran jika kita mahu,
tetapi rekursi akan menjadi lebih mudah di sini dan kita harus lakukan rekursi.
Saya rasa kita akan berjalan melalui apapun merge pertama,
walaupun terdapat video yang indah di merge apapun sudah. [Ketawa]
Jadi bergabung apapun terdapat - Saya membuang begitu banyak kertas ini.
Oh, hanya terdapat satu kiri.
Jadi bergabung.
Oh, 1, 3, 5.
Okay.
Gabung mengambil masa dua tatasusunan yang berasingan.
Individu kedua-dua barisan kedua-duanya disusun.
Jadi ini tatasusunan, 1, 3, 5, disusun. Ini tatasusunan, 0, 2, 4, disusun.
Sekarang apa merge harus lakukan adalah menggabungkan mereka ke dalam pelbagai tunggal yang dirinya disusun.
Jadi kita mahu pelbagai saiz daripada 6 yang akan mempunyai unsur-unsur di dalamnya
dalam perintah disusun.
>> Dan supaya kita boleh mengambil kesempatan daripada hakikat bahawa kedua-dua tatasusunan disusun
untuk melakukan ini dalam masa linear,
masa makna linear jika array ini adalah saiz x dan ini adalah y saiz,
maka jumlah algoritma harus O (x + y). Okay.
Jadi cadangan.
[Pelajar] Bolehkah kita mula dari kiri?
Jadi, anda akan meletakkan 0, ke pertama dan kemudian 1 dan kemudian di sini anda berada di 2.
Jadi ia adalah jenis seperti anda mempunyai tab yang bergerak ke kanan. >> [Bowden] Yeah.
Bagi kedua-dua tatasusunan ini jika kita hanya memberi tumpuan kepada elemen terkiri.
Kerana kedua-dua tatasusunan disusun, kita tahu bahawa ini 2 elemen
adalah unsur terkecil dalam pelbagai sama ada.
Jadi yang bermaksud bahawa 1 daripada 2 elemen tersebut mesti menjadi elemen terkecil dalam pelbagai digabungkan kami.
Ia hanya kebetulan bahawa terkecil adalah salah pada masa yang betul ini.
Jadi kita mengambil 0, masukkan ia di sebelah kiri kerana 0 adalah kurang daripada 1,
supaya mengambil 0, masukkannya ke dalam kedudukan pertama kita, dan kemudian kita mengemaskinikan
kini memberi tumpuan kepada elemen pertama.
Dan sekarang kita mengulangi.
Jadi sekarang kita bandingkan 2 dan 1. 1 adalah kecil, jadi kita akan memasukkan 1.
Kami mengemaskini penunjuk ini menunjukkan lelaki ini.
Sekarang kita melakukannya sekali lagi, jadi 2. Ini akan mengemaskini, bandingkan ini 2, 3.
Ini kemas kini, maka 4 dan 5.
Jadi yang bergabung.
>> Ia perlu cukup jelas bahawa ia adalah masa linear kerana kita hanya pergi di seluruh setiap elemen sekali.
Dan itu adalah langkah terbesar untuk melaksanakan apapun merge melakukan ini.
Dan ia bukan yang keras.
Satu perkara yang pasangan perlu dibimbangkan mari mengatakan kita telah penggabungan 1, 2, 3, 4, 5, 6.
Dalam kes ini kita akhirnya dalam senario di mana satu ini akan menjadi lebih kecil,
maka kita mengemaskini penunjuk ini, yang satu ini akan menjadi lebih kecil, mengemaskini ini,
yang satu ini lebih kecil, dan sekarang anda perlu untuk mengiktiraf
apabila anda telah benar-benar kehabisan unsur-unsur untuk membandingkan dengan.
Oleh kerana kita telah menggunakan pelbagai keseluruhan,
segala-galanya dalam pelbagai ini kini hanya dimasukkan ke sini.
Jadi, jika kita pernah berjalan ke titik di mana salah tatasusunan kami sepenuhnya digabungkan sudah,
maka kita hanya mengambil semua elemen array lain dan memasukkan mereka ke akhir array.
Jadi kita hanya boleh memasukkan 4, 5, 6. Okay.
Itu adalah satu perkara untuk menonton keluar untuk.
Melaksanakan yang harus menjadi langkah 1.
Gabung menyusun maka berdasarkan itu, ia adalah 2 langkah, 2 langkah bodoh.
Mari kita hanya memberi pelbagai ini.
Jadi bergabung apapun, langkah 1 adalah untuk rekursif memecahkan array ke dalam bahagian.
Jadi berpecah pelbagai ini ke dalam bahagian.
Kami kini mempunyai 4, 15, 16, 50 dan 8, 23, 42, 108.
Dan sekarang kita lakukan sekali lagi dan kami berpecah ini ke dalam bahagian.
Saya hanya akan melakukannya di sebelah ini.
Jadi 4, 15 dan 16, 50.
Kami akan melakukan perkara yang sama di sini.
Dan sekarang kita berpecah kepada dua lagi.
Dan kita mempunyai 4, 15, 16, 50.
Jadi yang kes asas kami.
Setelah array daripada 1 saiz, maka kita berhenti dengan membelah menjadi dua.
>> Sekarang apa yang kita lakukan dengan ini?
Kami akhirnya ini juga akan memecahkan ke 8, 23, 42, dan 108.
Jadi sekarang kita berada di titik ini, kini melangkah dua apapun merge hanya penggabungan berpasangan untuk senarai.
Jadi kita mahu untuk bergabung ini. Kami hanya memanggil bergabung.
Kita tahu merge akan kembali ini dalam perintah disusun.
4, 15.
Sekarang kita mahu untuk bergabung ini, dan yang akan kembali senarai dengan mereka dalam usaha disusun,
16, 50.
Kami bergabung mereka - Saya tidak boleh menulis - 8, 23 dan 42, 108.
Jadi kita mempunyai pasangan yang digabungkan sekali.
Sekarang kita hanya bergabung lagi.
Perhatikan bahawa setiap senarai ini disusun dalam dirinya,
dan kemudian kita hanya boleh menggabungkan senarai ini untuk mendapatkan senarai saiz 4 yang disusun
dan bergabung kedua-dua senarai untuk mendapatkan senarai saiz 4 yang disusun.
Dan akhirnya, kita boleh menggabungkan kedua-dua senarai saiz 4 untuk mendapatkan satu senarai sebanyak 8 saiz yang disusun.
Jadi untuk melihat bahawa ini adalah keseluruhan n log n, kita sudah melihat bahawa merge linear,
jadi apabila kita berurusan dengan penggabungan ini, jadi seperti kos keseluruhan merge
untuk kedua-dua senarai hanya 2 kerana -
Atau baik, ia O n, tetapi n di sini adalah hanya 2 elemen, jadi ia adalah 2.
Dan ini 2 akan 2 dan ini 2 akan menjadi 2 dan ini 2 akan menjadi 2,
merentasi semua bergabung yang perlu kita lakukan, kita akhirnya melakukan n.
Seperti 2 + 2 + 2 + 2 8, yang n,
jadi kos penggabungan dalam set ini n.
Dan kemudian perkara yang sama di sini.
Kami akan menggabungkan ini 2, maka ini 2, dan individu bergabung ini akan mengambil empat operasi,
merge ini akan mengambil empat operasi, tetapi sekali lagi, di antara semua ini,
kita akhirnya bergabung n jumlah perkara, dan sebagainya langkah ini mengambil n.
Dan sebagainya setiap peringkat mengambil n unsur yang digabungkan.
>> Dan berapa banyak peringkat yang ada?
Di setiap peringkat, pelbagai kami tumbuh dengan 2 saiz.
Berikut tatasusunan kita daripada 1 saiz, di sini mereka berada saiz 2, di sini mereka berada daripada 4 saiz,
dan akhirnya, mereka sebanyak 8 saiz.
Jadi kerana ia adalah dua kali ganda, ada akan menjadi jumlah log n tahap ini.
Jadi dengan log n peringkat, setiap peringkat individu mengambil n operasi jumlah,
kita dapat log n n algoritma.
Soalan?
Pernahkah orang sudah membuat kemajuan tentang bagaimana untuk melaksanakan ini?
Adakah sesiapa yang sudah dalam keadaan di mana saya hanya boleh tarik sehingga kod mereka?
Saya boleh memberi satu minit.
Yang satu ini akan menjadi lebih lama.
Saya sangat mengesyorkan berulang -
Anda tidak perlu untuk melakukan rekursi untuk merge
kerana untuk melakukan rekursi untuk bergabung, anda akan perlu untuk lulus sekumpulan saiz yang berbeza.
Anda boleh, tetapi ia menjengkelkan.
Tetapi rekursi untuk menyelesaikan sendiri adalah cukup mudah.
Anda hanya benar-benar memanggil apapun pada separuh kiri, jenis pada separuh yang betul. Okay.
Sesiapa yang mempunyai apa-apa yang saya boleh tarik lagi?
Atau lain saya akan memberikan satu minit.
Okay.
Sesiapa yang mempunyai sesuatu yang kita boleh bekerja dengan?
Atau lain kita hanya akan bekerja dengan ini dan kemudian berkembang dari sana.
>> Sesiapa yang mempunyai lebih daripada ini bahawa saya boleh tarik sehingga?
[Pelajar] Yeah. Anda boleh tarik sehingga lombong. >> Baiklah.
Ya!
[Pelajar] Terdapat banyak keadaan. >> Oh, menembak. Bolehkah anda -
[Pelajar] saya perlu untuk menyimpannya. >> Yeah.
Jadi kami lakukan melakukan merge berasingan.
Oh, tetapi ia bukan yang buruk.
Okay.
Jadi apapun sendiri hanya memanggil mergeSortHelp.
Terangkan kepada kami apa mergeSortHelp tidak.
[Pelajar] MergeSortHelp cukup banyak tidak dua langkah utama,
yang menyusun setiap separuh array dan kemudian untuk menggabungkan kedua-dua mereka.
[Bowden] Okay, jadi memberikan saya sesaat.
Saya rasa ini - >> [pelajar] saya perlu -
Yeah. Saya hilang sesuatu.
Di merge, Saya sedar bahawa saya perlu untuk mewujudkan pelbagai baru
kerana saya tidak boleh melakukannya di tempat. >> Ya. Anda tidak boleh. Membetulkan.
[Pelajar] Jadi saya mencipta pelbagai baru.
Saya terlupa pada akhir bergabung semula menukar.
Okay. Kita memerlukan barisan baru.
Dalam apapun merge, ini adalah hampir sentiasa benar.
Sebahagian daripada kos algoritma yang lebih baik masa-bijak
hampir sentiasa perlu untuk menggunakan memori yang sedikit lebih.
Jadi di sini, tidak kira bagaimana anda melakukannya bergabung apapun,
anda pasti akan memerlukan untuk menggunakan beberapa memori tambahan.
Beliau mencipta pelbagai baru.
Dan kemudian anda mengatakan pada akhir kita hanya perlu untuk menyalin pelbagai baru ke dalam pelbagai asal.
[Pelajar] Saya fikir begitu, ya.
Saya tidak tahu jika yang berfungsi dari segi pengiraan oleh rujukan atau apa sahaja -
Ya, ia akan berfungsi. >> [Pelajar] Okay.
Adakah anda cuba berjalan ini? >> [Pelajar] Tidak, belum lagi. >> Okay.
Cuba berjalan ia, dan kemudian saya akan bercakap mengenainya untuk kali kedua.
[Pelajar] saya perlukan untuk mempunyai semua fungsi prototaip dan segala-galanya, walaupun, betul-betul?
Fungsi prototaip. Oh, kamu maksudkan seperti - Ya.
Susun memanggil mergeSortHelp.
>> Jadi dalam usaha untuk menyelesaikan untuk memanggil mergeSortHelp, mergeSortHelp mesti sama ada telah ditakrifkan
sebelum apapun atau kita hanya perlu prototaip. Hanya salin dan tampal bahawa.
Dan begitu juga, mergeSortHelp memanggil bergabung,
tetapi merge belum ditakrifkan lagi, jadi kita hanya boleh membenarkan mergeSortHelp tahu
bahawa itulah yang bergabung akan kelihatan seperti, dan itulah yang.
Jadi mergeSortHelp.
Kami mempunyai isu di sini di mana kita tidak mempunyai kes asas.
MergeSortHelp rekursi, jadi apa-apa fungsi rekursi
akan memerlukan beberapa jenis kes asas untuk tahu bila untuk berhenti rekursif yang menggelarkan diri.
Apa kes asas kami akan di sini? Yeah.
[Pelajar] Jika saiz adalah 1? >> [Bowden] Ya.
Jadi seperti yang kita lihat di sana, kami berhenti array membelah
sebaik sahaja kami mendapat ke dalam tatasusunan 1 saiz, yang tidak dapat dielakkan disusun sendiri.
Jadi, jika saiz sama dengan 1, kita tahu array sudah disusun,
jadi kita hanya boleh kembali.
>> Notis itu tidak sah, jadi kita tidak kembali apa-apa yang tertentu, kita hanya kembali.
Okay. Jadi itulah kes asas kami.
Saya rasa kes asas kami juga boleh jika kita berlaku penggabungan pelbagai 0 saiz,
kita mungkin mahu untuk berhenti pada satu ketika,
jadi kita hanya boleh mengatakan saiz kurang daripada 2 atau kurang daripada atau sama dengan 1
supaya ini akan bekerja untuk pelbagai mana-mana sekarang.
Okay.
Jadi itulah kes asas kami.
Sekarang adakah anda ingin untuk berjalan kita melalui merge?
Apa yang semua kes ini bermakna?
Di sini, kita hanya melakukan idea yang sama, -
[Pelajar] saya perlu lulus saiz dengan semua mergeSortHelp panggilan.
Saya tambah saiz sebagai primer tambahan dan ia bukan di sana, seperti / 2 saiz.
[Bowden] Oh, saiz / 2, saiz / 2. >> [Pelajar] Yeah, dan juga dalam fungsi di atas juga.
[Bowden] Berikut? >> [Pelajar] Hanya saiz. >> [Bowden] Oh. Saiz, saiz? >> [Pelajar] Yeah.
[Bowden] Okay.
Biarkan saya berfikir untuk sesaat.
Adakah kita menghadapi isu?
Kami sentiasa merawat kiri sebagai 0. >> [Pelajar] No
Itulah salah juga. Maaf. Ia harus bermula. Yeah.
[Bowden] Okay. Saya suka yang lebih baik.
Dan akhir. Okay.
Jadi sekarang adakah anda mahu untuk berjalan kita melalui merge? >> [Pelajar] Okay.
Saya hanya berjalan melalui pelbagai baru ini bahawa saya telah mencipta.
Saiznya adalah saiz bahagian array yang kita mahu diselesaikan
dan cuba untuk mencari elemen yang saya perlu meletakkan dalam langkah array baru.
Jadi untuk berbuat demikian, pertama saya memeriksa jika separuh kiri array terus mempunyai apa-apa lagi elemen,
dan jika ia tidak, maka anda pergi ke keadaan yang lain, yang hanya berkata
okay, ia mestilah dalam pelbagai yang betul, dan kita akan meletakkan bahawa dalam indeks semasa newArray.
>> Dan kemudian sebaliknya, saya memeriksa jika sebelah kanan array juga selesai,
di mana saya hanya meletakkan di sebelah kiri.
Yang mungkin tidak benar-benar perlu. Saya tidak pasti.
Tetapi bagaimanapun, dua cek yang kedua-dua adalah lebih kecil di kiri atau kanan.
Dan juga dalam setiap kes, saya incrementing placeholder mana saya kenaikan.
[Bowden] Okay.
Yang kelihatan baik.
Adakah sesiapa yang mempunyai komen atau kebimbangan atau soalan?
Jadi empat kes yang kita perlu untuk membawa perkara-perkara ke dalam hanya - atau ia kelihatan seperti lima -
tetapi kita perlu mempertimbangkan sama ada array kiri telah kehabisan perkara yang kita perlu untuk bergabung,
sama ada array yang betul telah kehabisan perkara yang kita perlu untuk bergabung -
Saya menunjuk pada apa-apa.
Jadi sama ada array kiri telah kehabisan perkara atau array yang betul telah kehabisan perkara.
Mereka adalah dua kes.
Kita juga perlu kes remeh sama ada perkara kiri adalah kurang daripada perkara yang betul.
Kemudian kita mahu untuk memilih perkara kiri.
Mereka adalah kes.
Jadi ini adalah betul, maka itulah.
Array kiri. Ia adalah 1, 2, 3. Okay. Jadi yeah, mereka adalah empat perkara yang kita mungkin mahu lakukan.
Dan kita tidak akan pergi lebih lelaran penyelesaian.
Saya tidak akan mengesyorkan -
Gabung apapun adalah satu contoh fungsi yang kedua-duanya tidak rekursi ekor,
ia tidak mudah untuk membuat ia ekor rekursi,
tetapi juga ia tidak sangat mudah untuk membuat ia lelaran.
Ini adalah sangat mudah.
Ini pelaksanaan apapun merge,
bergabung, tidak kira apa yang anda lakukan, anda akan membina merge.
>> Jadi bergabung apapun yang dibina di atas merge rekursif hanya ketiga-tiga baris.
Iterative, ia adalah lebih menjengkelkan dan lebih sukar untuk berfikir tentang.
Tetapi notis bahawa ia bukan ekor rekursi sejak mergeSortHelp - apabila ia memerlukan dirinya -
ia masih perlu melakukan perkara-perkara selepas ini pulangan panggilan rekursi.
Jadi ini bingkai tindanan mesti terus wujud walaupun selepas memanggil ini.
Dan kemudian apabila anda memanggil ini, bingkai tindanan mesti terus wujud
kerana walaupun selepas panggilan itu, kita masih perlu untuk bergabung.
Dan ia adalah nontrivial untuk membuat ekor ini rekursi.
Soalan?
Semua hak.
Jadi akan kembali untuk menyusun - oh, ada dua perkara yang saya ingin menunjukkan. Okay.
Melangkah kembali kepada apapun, kami akan melakukan ini dengan cepat.
Atau cari. Susun? Susun. Yeah.
Melangkah kembali ke permulaan apapun.
Kami mahu mewujudkan algoritma yang pelbagai array menggunakan algoritma mana-mana
O n.
Jadi bagaimana ini boleh terjadi? Adakah sesiapa yang mempunyai apa-apa jenis -
Saya membayangkan sebelum di -
Jika kita kira-kira untuk memperbaiki dari n log n O n,
kita telah bertambah baik algoritma kami masa bijak,
yang bermaksud apa yang kita akan perlu lakukan untuk membuat sehingga untuk itu?
[Pelajar] Angkasa. >> Yeah. Kami akan menggunakan lebih banyak ruang.
Dan tidak hanya lebih banyak ruang, ia adalah ruang yang lebih pesat.
Jadi saya fikir jenis ini algoritma adalah sesuatu yang pseudo, polinom pseudo -
pseudo - Saya tidak boleh ingat. Sesuatu pseudo.
Tetapi ia adalah kerana kita perlu menggunakan ruang yang begitu banyak
bahawa ini boleh dicapai tetapi tidak realistik.
>> Dan bagaimana kita mencapai matlamat ini?
Kita boleh mencapai matlamat ini jika kita menjamin bahawa mana-mana elemen tertentu dalam array
adalah di bawah saiz tertentu.
Jadi mari kita hanya mengatakan bahawa saiz adalah 200,
mana-mana elemen dalam array adalah di bawah saiz 200.
Dan ini sebenarnya adalah sangat realistik.
Anda dengan mudah boleh mempunyai pelbagai bahawa anda tahu segala-galanya di dalamnya
akan menjadi kurang daripada bilangan tertentu.
Seperti jika anda mempunyai beberapa benar-benar besar-besaran vektor atau sesuatu
tetapi anda tahu segala-galanya akan menjadi antara 0 dan 5,
maka ia akan menjadi ketara lebih cepat untuk melakukan ini.
Dan terikat kepada mana-mana unsur-unsur ialah 5,
jadi ini terikat, yang berapa banyak memori yang anda akan menggunakan.
Jadi terikat ialah 200.
Dalam teori sentiasa ada terikat sejak integer hanya boleh sehingga hingga 4 bilion,
tetapi itu tidak realistik sejak maka kita akan menggunakan ruang
atas perintah daripada 4 bilion. Jadi itulah yang tidak realistik.
Tetapi di sini kita akan mengatakan terikat kami adalah 200.
Helah untuk melakukannya di O n kita membuat satu lagi pelbagai dipanggil tuduhan saiz TERIKAT.
Jadi sebenarnya, ini adalah jalan pintas untuk - Saya sebenarnya tidak tahu jika dilafaz melakukan ini.
Tetapi di GCC sekurang-kurangnya - dilafaz: saya menganggap adakah ia terlalu -
ini hanya akan memulakan array keseluruhan untuk menjadi 0.
Jadi jika saya tidak mahu berbuat demikian, maka saya secara berasingan boleh lakukan untuk (int i = 0;
i <BOUND; i + +) dan tuduhan [i] = 0;
Jadi sekarang semuanya dimulakan kepada 0.
Saya melelar lebih array saya,
dan apa yang saya lakukan ialah saya mengira bilangan setiap - Mari kita pergi ke sini.
Kami mempunyai 4, 15, 16, 50, 8, 23, 42, 108.
Apa yang saya mengira bilangan kejadian setiap unsur-unsur.
Mari kita sebenarnya menambah pasangan lebih di sini dengan beberapa mengulangi.
Jadi nilai kita ada di sini, nilai yang akan menjadi pelbagai [i].
Jadi Val boleh menjadi 4 atau 8 atau apa sahaja.
Dan kini saya mengira berapa banyak nilai yang saya telah melihat,
jadi tuduhan [Val] + +;
Selepas ini dilakukan, tuduhan akan melihat sesuatu seperti 0001.
Mari kita buat tuduhan [Val] - DIIKAT + 1.
>> Sekarang ini hanya untuk mengambil kira hakikat bahawa kita sedang bermula dari 0.
Jadi sekiranya 200 akan menjadi alat nombor satu yang paling kami terbesar,
maka 0-200 adalah 201 perkara.
Jadi tuduhan, ia akan kelihatan seperti 00001 kerana kita mempunyai satu 4.
Kemudian kita akan mempunyai 0001 di mana kita akan mempunyai 1 dalam indeks 8 kiraan.
Kami akan mempunyai 2 dalam indeks 23 kiraan.
Kami akan mempunyai 2 dalam indeks kiraan ke-42.
Jadi kita boleh gunakan kiraan.
Jadi num_of_item = tuduhan [i].
Dan jadi jika num_of_item ialah 2, yang bermakna kita mahu untuk memasukkan 2 nombor i
ke dalam pelbagai disusun kami.
Jadi kita perlu menjejaki sejauh mana kita ke dalam array.
Jadi indeks = 0.
Array - Saya hanya akan menulis.
Count -
pelbagai [index + +] = i;
Adalah bahawa apa yang saya mahu? Saya fikir itulah apa yang saya mahu.
Ya, ini kelihatan baik. Okay.
Jadi tidak semua orang faham apa tujuan pelbagai tuduhan saya?
Ia mengira bilangan kejadian setiap nombor-nombor ini.
Kemudian saya iterating atas yang pelbagai tuduhan,
dan kedudukan engan dalam pelbagai tuduhan
adalah bilangan i adalah yang sepatutnya muncul dalam pelbagai disusun saya.
Itulah sebabnya tuduhan 4 akan menjadi 1
dan tuduhan 8 akan menjadi 1, tuduhan 23 akan menjadi 2.
Jadi itulah berapa ramai daripada mereka yang saya mahu untuk memasukkan ke dalam pelbagai disusun saya.
Kemudian saya hanya berbuat demikian.
Saya memasukkan num_of_item i ke dalam pelbagai disusun saya.
>> Soalan?
Dan sebagainya lagi, ini adalah masa linear kerana kita hanya iterating lebih ini sekali,
tetapi ia juga linear dalam apa nombor ini berlaku untuk menjadi,
dan sebagainya ia banyak bergantung kepada apa yang terikat anda.
Dengan terikat daripada 200, itu bukan yang buruk.
Jika terikat anda pergi ke 10,000, maka itulah sedikit teruk,
tetapi jika terikat anda akan menjadi 4 bilion, yang benar-benar tidak realistik
dan pelbagai ini akan mempunyai untuk menjadi saiz 4 bilion, yang adalah tidak realistik.
Jadi itulah. Soalan?
[Sambutan pelajar didengar] >> Okay.
Saya sedar satu perkara lain apabila kita telah melalui.
Saya rasa masalah ini adalah di Lucas dan mungkin setiap satu kita telah melihat.
Saya benar-benar terlupa.
Satu-satunya perkara yang saya mahu mengulas mengenai adalah bahawa apabila anda berurusan dengan perkara-perkara seperti indeks,
anda tidak pernah benar-benar melihat ini apabila anda menulis untuk gelung,
tetapi dari segi teknikal, apabila anda sedang berurusan dengan indeks,
anda cukup banyak perlu sentiasa berurusan dengan integer tak bertanda.
Sebab untuk ini adalah apabila anda sedang berurusan dengan integer ditandatangani,
jadi jika anda mempunyai 2 integer ditandatangani dan anda menambah mereka bersama-sama
dan mereka akhirnya terlalu besar, maka anda berakhir dengan nombor negatif.
Jadi itulah apa limpahan integer.
>> Jika saya menambah 2 bilion dan 1 bilion, saya berakhir dengan negatif 1 bilion.
Itulah bagaimana integer bekerja pada komputer.
Jadi masalah dengan menggunakan -
Itu denda kecuali jika rendah berlaku untuk menjadi 2 bilion dan sehingga berlaku untuk menjadi 1 bilion,
maka ini akan menjadi negatif 1000000000 dan kemudian kita akan membahagikan bahawa dengan 2
dan berakhir dengan negatif 500 juta.
Jadi ini adalah hanya satu isu jika anda berlaku untuk mencari melalui pelbagai
berbilion-bilion perkara.
Tetapi jika + rendah sehingga berlaku melimpah, maka itulah masalah.
Sebaik sahaja kita membuat mereka tidak bertanda, maka 2 bilion ditambah 1 bilion adalah 3 bilion.
3000000000 dibahagikan dengan 2 adalah 1.5 bilion.
Demikian secepat mereka tidak bertanda, segala-galanya adalah sempurna.
Dan supaya juga satu isu apabila anda menulis anda untuk gelung,
dan sebenarnya, ia mungkin tidak secara automatik.
Ia sebenarnya hanya akan menjerit pada anda.
Jadi, jika nombor ini adalah terlalu besar untuk menjadi hanya dalam integer tetapi ia akan dimuatkan dalam integer bertanda,
ia akan menjerit pada anda, jadi itulah sebabnya anda tidak pernah benar-benar menghadapi isu.
Anda boleh melihat bahawa indeks tidak akan menjadi negatif,
dan sebagainya apabila anda iterating lebih array,
anda hampir sentiasa boleh mengatakan tidak bertanda int i, tetapi anda tidak benar-benar perlu.
Perkara yang akan bekerja cukup banyak seperti juga.
Okay. [Bisikan] Apa masa ia?
Perkara terakhir saya mahu menunjukkan - dan saya hanya akan melakukan ia benar-benar cepat.
Anda tahu bagaimana kita telah # menentukan supaya kita # boleh menentukan MAX sebagai 5 atau sesuatu?
Mari kita tidak melakukan MAX. # Define TERIKAT sebagai 200. Itulah apa yang kami lakukan sebelum ini.
Itu mentakrifkan pemalar, yang hanya akan disalin dan ditampal
di mana sahaja kita berlaku untuk menulis TERIKAT.
>> Jadi, kita sebenarnya boleh melakukan lebih # mentakrifkan.
Kita # boleh menentukan fungsi.
Mereka tidak benar-benar fungsi, tetapi kita akan memanggil mereka fungsi.
Satu contoh akan menjadi sesuatu yang seperti MAX (x, y) ditakrifkan sebagai (x <y y: x). Okay.
Jadi anda perlu mendapatkan digunakan untuk sintaks pengendali pertigaan,
tetapi x kurang daripada y? Kembali y, lain kembali x.
Jadi anda boleh melihat anda boleh membuat fungsi ini berasingan,
dan fungsi boleh menjadi seperti bool MAX mengambil masa 2 hujah, kembali ini.
Ini adalah salah satu yang paling biasa saya lihat dilakukan seperti ini. Kami memanggil mereka makro.
Ini adalah makro.
Ini adalah hanya sintaks untuk ia.
Anda boleh menulis makro untuk melakukan apa sahaja yang anda mahu.
Anda sering melihat makro untuk debugging printfs dan barangan.
Jadi jenis printf, terdapat pemalar khas dalam C seperti menekankan LINE menekankan,
2 underscore LINE menekankan,
dan terdapat juga saya fikir 2 underscore func. Yang mungkin. Sesuatu seperti itu.
Mereka perkara yang akan digantikan dengan nama fungsi
atau bilangan baris yang anda berada di.
Kerap, anda menulis debugging printfs yang turun di sini saya boleh kemudian hanya menulis
Debug dan ia akan mencetak nombor barisan dan fungsi bahawa saya berada di
bahawa ia temui bahawa kenyataan DEBUG.
Dan anda juga boleh mencetak perkara-perkara lain.
Jadi satu perkara yang anda harus berhati-hati jika saya berlaku untuk menentukan # DOUBLE_MAX
sebagai sesuatu seperti 2 * y dan 2 * x.
Jadi untuk apa jua sebab, anda berlaku untuk berbuat demikian banyak.
Jadi ia membuat makro.
Ini sebenarnya dipecahkan.
Saya akan memanggilnya dengan melakukan sesuatu seperti DOUBLE_MAX (3, 6).
Jadi apa yang harus dikembalikan?
[Pelajar] 12.
Ya, 12 perlu dipulangkan, dan 12 dikembalikan.
3 akan diganti bagi x, 6 mendapat digantikan untuk y, dan kita kembali 2 * 6, iaitu 12.
Sekarang apa tentang perkara ini? Apa yang perlu dikembalikan?
[Pelajar] 14. >> Sebaik-baiknya, 14.
Isunya ialah bahawa bagaimana hash mentakrifkan kerja, ingat ia adalah satu salinan literal dan tampal
segala-galanya cukup banyak, jadi apa ini akan ditafsirkan sebagai
adalah 3 kurang daripada 1 campur 6, 2 kali 1 campur 6, 2 kali 3.
>> Jadi untuk sebab ini, anda hampir sentiasa membalut segala-galanya dalam kurungan.
Mana-mana pembolehubah anda hampir sentiasa membalut di dalam kurungan.
Terdapat kes-kes di mana anda tidak perlu, seperti yang saya tahu bahawa saya tidak perlu untuk berbuat demikian di sini
kerana kurang daripada cukup banyak sentiasa hanya pergi ke tempat kerja,
walaupun yang mungkin tidak menjadi kenyataan.
Jika ada sesuatu yang tidak masuk akal seperti DOUBLE_MAX (1 == 2),
kemudian yang akan digantikan dengan 3 kurang daripada 1 bersamaan bersamaan 2,
dan sebagainya maka ia akan melakukan 3 kurang daripada 1, adakah sama bahawa 2,
yang bukan apa yang kita mahu.
Jadi, untuk mengelakkan sebarang masalah pengendali keutamaan,
sentiasa membalut di dalam kurungan.
Okay. Dan itu, 5:30.
Jika anda mempunyai sebarang soalan pada pset, marilah kita tahu.
Ia seharusnya menyeronokkan, dan edisi penggodam juga adalah lebih realistik
daripada edisi penggodam tahun lepas, jadi kami berharap bahawa banyak anda cuba.
Tahun lepas adalah sangat menggalakkan.
>> [CS50.TV]