[Powered by Google Translate] [Bagian 3 - Lebih Nyaman]
[Rob Bowden - Harvard University]
>> [Ini adalah CS50. - CS50.TV]
>> Jadi pertanyaan pertama anehnya worded.
GDB memungkinkan Anda "debug" program, tetapi, lebih khusus, apa yang membiarkan Anda lakukan?
Saya akan menjawab pertanyaan itu, dan aku tidak tahu apa yang sebenarnya diharapkan,
jadi aku menebak itu sesuatu sepanjang garis itu memungkinkan Anda langkah demi langkah
berjalan melalui program ini, berinteraksi dengan itu, variabel perubahan, melakukan semua hal ini -
pada dasarnya benar-benar mengontrol pelaksanaan program
dan memeriksa setiap bagian tertentu dari pelaksanaan program.
Jadi fitur tersebut memungkinkan Anda men-debug hal.
Oke.
Kenapa pencarian biner mengharuskan array akan diurutkan?
Siapa yang ingin menjawab itu?
[Mahasiswa] Karena tidak bekerja jika tidak diurutkan. >> Ya. [Tertawa]
Jika tidak diurutkan, maka itu tidak mungkin untuk membagi menjadi dua
dan tahu bahwa segala sesuatu ke kiri kurang dan segala sesuatu ke kanan
lebih besar dari nilai tengah.
Jadi perlu diurutkan.
Oke.
Mengapa gelembung semacam di O n kuadrat?
Apakah ada yang pertama ingin memberikan gambaran tingkat tinggi yang sangat cepat seperti apa gelembung?
[Mahasiswa] Anda pada dasarnya pergi melalui setiap elemen dan Anda memeriksa beberapa elemen pertama.
Jika mereka keluar dari mana Anda menukar mereka, maka Anda memeriksa beberapa elemen berikutnya dan seterusnya.
Ketika Anda mencapai akhir, maka Anda tahu bahwa elemen terbesar ditempatkan di akhir,
sehingga Anda mengabaikan yang satu maka Anda terus berjalan melalui,
dan setiap kali Anda harus memeriksa satu elemen kurang sampai Anda membuat tidak ada perubahan. >> Ya.
Ini disebut bubble sort karena jika Anda membalik array pada sisinya jadi naik dan turun, vertikal,
maka nilai-nilai yang besar akan tenggelam ke dasar dan nilai-nilai kecil akan menggelembung ke atas.
Begitulah mendapat namanya.
Dan ya, Anda hanya pergi melalui.
Anda terus melalui array, swapping nilai yang lebih besar
untuk mendapatkan nilai terbesar ke bawah.
>> Mengapa O n kuadrat?
Pertama, apakah ada yang ingin mengatakan mengapa O n kuadrat?
[Mahasiswa] Karena untuk menjalankan setiap ia pergi n kali.
Anda hanya dapat yakin bahwa Anda telah mengambil elemen terbesar semua jalan ke bawah,
maka Anda harus mengulangi bahwa untuk sebagai banyak unsur. >> Ya.
Jadi ingat apa big O berarti dan apa artinya Omega besar.
The O besar adalah seperti batas atas seberapa lambat itu benar-benar dapat dijalankan.
Jadi dengan mengatakan itu O n kuadrat, tidak O dari n atau yang lain itu akan dapat menjalankan
dalam waktu linier, tetapi O n potong dadu
karena dibatasi oleh O n potong dadu.
Jika itu dibatasi oleh O n kuadrat, maka itu dibatasi juga oleh n potong dadu.
Jadi adalah n kuadrat, dan dalam kasus terburuk mutlak tidak dapat berbuat lebih baik dari n kuadrat,
itulah sebabnya mengapa itu O n kuadrat.
Jadi untuk melihat matematika sedikit pada bagaimana keluar menjadi n kuadrat,
jika kita memiliki lima hal di daftar kami, pertama kalinya berapa banyak swap bisa kita berpotensi perlu membuat
dalam rangka untuk mendapatkan ini? Mari kita sebenarnya hanya -
Berapa banyak swap yang kita akan harus membuat dalam jangka pertama bubble sort melalui array?
[Mahasiswa] n - 1. >> Ya.
>> Jika ada 5 elemen, kita akan perlu membuat n - 1.
Kemudian pada kedua berapa banyak swap yang akan kita harus membuat?
[Mahasiswa] n - 2. >> Ya.
Dan yang ketiga akan menjadi n - 3, dan kemudian untuk kenyamanan saya akan menulis dua terakhir
sebagai maka kita akan perlu untuk membuat 2 swap dan 1 swap.
Saya kira yang terakhir mungkin atau mungkin tidak benar-benar perlu terjadi.
Apakah swap? Saya tidak tahu.
Jadi ini adalah jumlah total swap atau setidaknya perbandingan Anda harus membuat.
Bahkan jika Anda tidak swap, Anda masih perlu untuk membandingkan nilai.
Jadi ada n - 1 perbandingan dalam jangka pertama melalui array.
Jika Anda mengatur ulang hal-hal ini, mari kita benar-benar membuatnya enam hal sehingga hal-hal menumpuk dengan baik,
dan kemudian saya akan melakukan 3, 2, 1.
Jadi hanya menata ulang jumlah ini, kita ingin melihat berapa banyak perbandingan kita buat
dalam algoritma keseluruhan.
Jadi jika kita membawa orang-orang ini ke sini,
maka kita masih hanya menjumlahkan perbandingan namun banyak ada.
Tetapi jika kita jumlah ini dan kami jumlah ini dan kami jumlah tersebut,
itu masih masalah yang sama. Kami hanya jumlah kelompok-kelompok tertentu.
>> Jadi sekarang kita menjumlahkan 3 s n. Ini bukan hanya 3 s n.
Ini selalu akan menjadi n / 2 n.
Jadi di sini kita kebetulan memiliki 6.
Jika kita memiliki 10 hal, maka kita bisa melakukan pengelompokan ini untuk 5 pasang yang berbeda dari hal-hal
dan berakhir dengan n + n + n + n + n.
Jadi Anda akan selalu mendapatkan n / 2 n, dan jadi ini kita akan menuliskan itu keluar ke n kuadrat / 2.
Dan jadi meskipun itu faktor setengah, yang kebetulan datang di
karena dari fakta bahwa melalui setiap iterasi atas array kita membandingkan 1 kurang
jadi itu bagaimana kita mendapatkan lebih dari 2, tetapi masih n kuadrat.
Kami tidak peduli tentang faktor konstan setengah.
Jadi banyak hal O besar seperti ini bergantung pada hanya semacam melakukan semacam ini matematika,
berhitung aritmatika dan barang-barang seri geometris,
tapi kebanyakan dari mereka dalam kursus ini adalah cukup sederhana.
Oke.
Mengapa insertion sort di Omega n? Apa omega artinya?
[Dua siswa berbicara sekaligus - dimengerti] Ya >>.
Omega Anda bisa memikirkan sebagai batas bawah.
>> Jadi tidak peduli seberapa efisien penyisipan algoritma semacam Anda,
terlepas dari daftar yang disahkan pada, selalu memiliki untuk membandingkan setidaknya n hal
atau harus iterate atas hal-hal n.
Mengapa demikian?
[Mahasiswa] Karena jika daftar tersebut sudah diurutkan, kemudian melalui iterasi pertama
Anda hanya dapat menjamin bahwa elemen pertama adalah yang paling,
dan iterasi kedua Anda hanya dapat menjamin dua yang pertama adalah
karena Anda tidak tahu bahwa sisa daftar diurutkan. >> Ya.
Jika Anda lulus dalam daftar benar-benar diurutkan, setidaknya Anda harus pergi ke semua elemen
untuk melihat bahwa tidak ada yang perlu dipindahkan sekitar.
Jadi melewati daftar dan mengatakan oh, ini sudah diurutkan,
tidak mungkin bagi Anda untuk tahu itu diurutkan sampai Anda memeriksa setiap elemen
untuk melihat bahwa mereka berada di urutan diurutkan.
Jadi batas bawah pada insertion sort adalah Omega dari n.
Apa kasus terburuk waktu berjalan semacam gabungan,
kasus terburuk O menjadi besar lagi?
Jadi dalam skenario terburuk, bagaimana gabungan semacam dijalankan?
[Mahasiswa] N log n. >> Ya.
Algoritma tercepat pemilahan umum n log n. Anda tidak bisa berbuat lebih baik.
>> Ada kasus-kasus khusus, dan jika kita punya waktu hari ini - tapi kami mungkin won't -
kita bisa melihat salah satu yang tidak lebih baik dari n log n.
Tetapi dalam kasus umum, Anda tidak dapat melakukan lebih baik daripada n log n.
Dan menggabungkan semacam kebetulan yang Anda harus tahu untuk kursus yang n log n.
Dan jadi kita benar-benar akan menerapkan hari ini.
Dan akhirnya, dalam waktu tidak lebih dari tiga kalimat, bagaimana cara kerja semacam seleksi?
Apakah seseorang ingin menjawabnya, dan saya akan menghitung kalimat Anda
karena jika Anda pergi lebih dari 3 -
Apakah ada yang ingat semacam seleksi?
Seleksi semacam ini biasanya cukup mudah diingat hanya dari nama.
Anda hanya iterate atas array, menemukan apa nilai terbesar adalah atau terkecil -
urutan apapun yang Anda menyortir masuk
Jadi katakanlah kita sedang disortir dari terkecil sampai terbesar.
Anda iterate atas array, mencari apa pun elemen minimum,
pilih, dan kemudian hanya swap apa yang ada di tempat pertama.
Dan kemudian pada lulus kedua atas array, mencari elemen minimum lagi,
pilih, dan kemudian swap dengan apa yang ada di posisi kedua.
Jadi kita hanya memilih dan memilih nilai minimum
dan memasukkan mereka ke depan array sampai itu diurutkan.
Pertanyaan itu?
>> Ini pasti muncul dalam bentuk Anda harus mengisi ketika Anda mengirimkan pset tersebut.
Mereka pada dasarnya jawaban kepada mereka.
Oke, jadi sekarang masalah coding.
Saya sudah dikirim keluar melalui email - Apakah ada yang tidak mendapatkan email itu? Oke.
Saya sudah dikirim keluar melalui email ruang yang kita akan menggunakan,
dan jika Anda klik pada nama saya - jadi saya pikir saya akan berada di bagian bawah
karena r mundur - tetapi jika Anda klik pada nama saya Anda akan melihat 2 revisi.
Revisi 1 ini akan saya sudah disalin dan disisipkan kode ke Spaces
untuk hal pencarian Anda akan harus melaksanakan.
Dan Revisi 2 akan menjadi hal semacam itu kami menerapkan setelah itu.
Jadi, Anda dapat mengklik Revisi saya 1 dan bekerja dari sana.
Dan sekarang kita ingin menerapkan pencarian biner.
>> Apakah ada yang ingin hanya memberikan penjelasan tingkat tinggi pseudocode
dari apa yang kita akan lakukan untuk pencarian? Ya.
[Mahasiswa] Anda hanya mengambil bagian tengah dari array dan melihat apakah apa yang Anda cari
kurang dari itu atau lebih dari itu.
Dan jika itu kurang, Anda pergi ke babak yang kurang,
dan jika lebih, Anda pergi ke babak yang lebih dan anda ulangi sampai Anda hanya mendapatkan satu hal.
[Bowden] Ya.
Perhatikan bahwa nomor array kita sudah diurutkan,
dan sehingga berarti bahwa kita dapat mengambil keuntungan dari itu dan pertama-tama kita bisa memeriksa,
oke, saya sedang mencari nomor 50.
Jadi aku bisa pergi ke tengah.
Tengah sulit untuk menentukan ketika itu bahkan jumlah hal,
tapi mari kita katakan saja kita akan selalu memotong ke tengah.
Jadi di sini kita memiliki 8 hal, sehingga tengah akan menjadi 16.
Saya sedang mencari 50, jadi 50 lebih besar dari 16.
Jadi sekarang saya pada dasarnya dapat memperlakukan array saya sebagai elemen-elemen ini.
Aku bisa membuang segala sesuatu dari 16 lebih.
Sekarang array saya hanya ini 4 elemen, dan saya ulangi.
Jadi saya ingin mencari tengah lagi, yang akan menjadi 42.
42 kurang dari 50, sehingga saya dapat membuang dua elemen.
Ini adalah array tersisa saya.
Aku akan menemukan tengah lagi.
Saya kira 50 adalah contoh buruk karena saya selalu membuang hal-hal ke kiri,
tetapi dengan ukuran yang sama, jika saya sedang mencari sesuatu
dan itu kurang dari elemen Saat ini saya melihat,
maka aku akan membuang segala sesuatu ke kanan.
Jadi sekarang kita perlu untuk mengimplementasikan itu.
Perhatikan bahwa kita harus lulus dalam ukuran.
Kita juga bisa tidak perlu keras-kode ukuran.
Jadi jika kita menyingkirkan # define -
Oke.
Bagaimana saya bisa baik mencari tahu apa ukuran dari array angka saat ini?
>> Berapa banyak elemen dalam array nomor?
[Mahasiswa] Bilangan, kurung,. Panjang?
[Bowden] Itu tidak ada di C.
Perlu. Panjang.
Array tidak memiliki sifat, sehingga tidak ada properti panjang array
yang hanya akan memberi Anda namun lama akan terjadi.
[Mahasiswa] Lihat berapa banyak memori yang dimilikinya dan dibagi dengan berapa banyak - Yeah >>.
Jadi bagaimana kita bisa melihat berapa banyak memori yang dimilikinya? >> [Mahasiswa] sizeof. >> Ya, sizeof.
Sizeof adalah operator yang akan mengembalikan ukuran dari array angka.
Dan itu akan menjadi bilangan bulat namun banyak ada kali ukuran integer
karena itulah berapa banyak memori itu benar-benar mengambil.
Jadi jika saya ingin beberapa hal dalam array,
maka aku akan ingin membagi dengan ukuran integer.
Oke. Jadi yang memungkinkan saya lulus dalam ukuran sini.
Mengapa saya harus lulus dalam ukuran sama sekali?
Kenapa aku tidak bisa hanya melakukan di sini ukuran int = sizeof (tumpukan jerami) / sizeof (int)?
Mengapa hal ini tidak bekerja?
[Mahasiswa] Ini bukan variabel global.
[Bowden] Haystack ada dan kami sedang lewat di angka sebagai tumpukan jerami,
dan ini adalah semacam bayangan apa yang akan datang. Ya.
[Mahasiswa] Haystack hanyalah referensi untuk itu, sehingga akan kembali seberapa besar referensi yang.
Ya.
Saya ragu dalam kuliah bahwa Anda telah melihat tumpukan belum benar-benar, benar?
Kami baru saja berbicara tentang hal itu.
Jadi tumpukan adalah di mana semua variabel Anda akan disimpan.
>> Setiap memori yang dialokasikan untuk variabel lokal akan di stack,
dan fungsi masing-masing mendapat ruang sendiri di tumpukan, stack frame sendiri adalah apa namanya.
Jadi utama memiliki stack frame, dan di dalamnya akan ada array angka,
dan itu akan menjadi ukuran sizeof (angka).
Ini akan memiliki ukuran angka dibagi dengan ukuran elemen,
tapi itu semua hidup dalam bingkai tumpukan utama itu.
Ketika kita sebut pencarian, pencarian akan stack frame sendiri,
ruang sendiri untuk menyimpan semua variabel lokal.
Tapi argumen ini - sehingga tumpukan jerami bukanlah salinan dari seluruh array.
Kami tidak lulus dalam seluruh array sebagai copy ke dalam pencarian.
Itu hanya melewati referensi ke array.
Jadi pencarian dapat mengakses nomor melalui referensi ini.
Ini masih mengakses hal-hal yang hidup dalam stack frame utama itu,
tetapi pada dasarnya, ketika kita sampai ke pointer, yang harus segera,
ini adalah apa pointer.
Pointer hanya referensi untuk hal-hal, dan Anda dapat menggunakan pointer untuk mengakses hal-hal
yang berada dalam bingkai tumpukan hal-hal lain '.
Jadi meskipun angka adalah lokal untuk main, kita masih dapat mengaksesnya melalui pointer ini.
Tapi karena itu hanya pointer dan itu hanya referensi,
sizeof (tumpukan jerami) hanya mengembalikan ukuran dari referensi itu sendiri.
Ini tidak mengembalikan ukuran hal itu menunjuk ke.
Ini tidak mengembalikan ukuran sebenarnya angka.
Dan jadi ini tidak akan bekerja seperti yang kita inginkan.
>> Pertanyaan itu?
Pointer akan pergi ke detail signifikan lebih berdarah dalam beberapa pekan yang akan datang.
Dan inilah mengapa banyak hal yang Anda lihat, hal pencarian sebagian besar atau hal-hal semacam,
mereka hampir semua akan perlu mengambil ukuran sebenarnya dari array,
karena dalam C, kita tidak tahu apa ukuran array.
Anda perlu secara manual lulus masuk
Dan Anda tidak dapat secara manual lulus dalam seluruh array karena Anda hanya lewat dalam referensi
dan itu tidak bisa mendapatkan ukuran dari referensi.
Oke.
Jadi sekarang kita ingin menerapkan apa yang telah dijelaskan sebelumnya.
Anda dapat bekerja di dalamnya selama satu menit,
dan Anda tidak perlu khawatir tentang mendapatkan segalanya dengan sempurna 100% bekerja.
Hanya menulis dengan pseudocode setengah untuk bagaimana Anda pikir itu harus bekerja.
Oke.
Tidak perlu harus benar-benar dilakukan dengan ini.
Tapi tidak ada yang merasa nyaman dengan apa yang mereka miliki sejauh ini,
seperti sesuatu yang kita dapat bekerja dengan bersama-sama?
Apakah ada yang ingin menjadi sukarelawan? Atau aku akan memilih secara acak.
Ini tidak harus menjadi benar dengan setiap tindakan, tetapi sesuatu yang kita dapat memodifikasi ke dalam keadaan bekerja.
[Mahasiswa] Tentu. Oke >>.
Jadi bisa Anda menyimpan revisi dengan mengklik ikon Simpan kecil.
Kau Ramya, kan? >> [Mahasiswa] Ya. >> [Bowden] Oke.
Jadi sekarang saya dapat melihat revisi Anda dan semua orang dapat menarik revisi.
Dan di sini kita memiliki - Oke.
Jadi Ramya pergi dengan solusi rekursif, yang pasti solusi yang valid.
Ada dua cara yang dapat Anda lakukan masalah ini.
Anda dapat melakukannya iteratif atau rekursif.
Sebagian besar masalah yang Anda temui yang bisa dilakukan secara rekursif juga bisa dilakukan secara iteratif.
Jadi di sini kita sudah melakukannya secara rekursif.
>> Apakah seseorang ingin mendefinisikan apa artinya untuk membuat fungsi rekursif?
[Mahasiswa] Bila Anda memiliki fungsi panggilan sendiri
dan kemudian menyebut dirinya sampai keluar dengan benar dan benar. >> Ya.
Sebuah fungsi rekursif hanya fungsi yang memanggil dirinya sendiri.
Ada tiga hal besar yang fungsi rekursif harus memiliki.
Yang pertama adalah jelas, itu menyebut dirinya.
Yang kedua adalah kasus dasar.
Jadi di beberapa titik fungsi perlu berhenti menyebut dirinya,
dan itulah yang kasus dasar adalah untuk.
Jadi di sini kita tahu bahwa kita harus berhenti, kita harus menyerah dalam pencarian kami
saat start sama end - dan kami akan pergi ke apa artinya.
Tapi akhirnya, hal terakhir yang penting untuk fungsi rekursif:
fungsi entah bagaimana harus mendekati kasus dasar.
Seperti jika Anda tidak benar-benar memperbarui apa-apa ketika Anda membuat panggilan rekursif kedua,
jika Anda benar-benar hanya memanggil fungsi lagi dengan argumen yang sama
dan tidak ada variabel global telah berubah atau apa,
Anda tidak akan pernah mencapai kasus dasar, dalam hal yang buruk.
Ini akan menjadi rekursi tak terbatas dan stack overflow.
Tapi di sini kita melihat bahwa pembaruan yang terjadi karena kita mulai memperbarui + end / 2,
kami meng-update argumen akhir di sini, kami meng-update argumen start di sini.
Jadi dalam semua panggilan rekursif kita memperbarui sesuatu. Oke.
Apakah Anda ingin berjalan kita melalui solusi Anda? Tentu >>.
Saya menggunakan SearchHelp sehingga setiap kali saya membuat panggilan fungsi
Saya memiliki awal di mana saya sedang mencari dalam array dan akhir
di mana saya sedang mencari array.
>> Pada setiap langkah di mana itu mengatakan itu adalah elemen tengah, yang merupakan awal + akhir / 2,
adalah bahwa sama dengan apa yang kita cari?
Dan jika sudah, maka kami menemukan itu, dan saya rasa itu akan diteruskan sampai tingkat rekursi.
Dan jika itu tidak benar, kemudian kita cek apakah nilai tengah dari array terlalu besar,
dalam hal ini kita melihat kiri setengah dari array dengan pergi dari awal sampai indeks tengah.
Dan jika kita melakukan setengah akhir.
[Bowden] Oke.
Boleh juga.
Oke, jadi beberapa hal, dan benar-benar, ini adalah hal yang sangat tinggi tingkat
bahwa Anda tidak akan pernah perlu tahu untuk kursus ini, tapi itu benar.
Fungsi rekursif, Anda selalu mendengar bahwa mereka transaksi yang buruk
karena jika Anda rekursif menyebut dirimu kali terlalu banyak, Anda mendapatkan stack overflow
karena, seperti yang saya katakan sebelumnya, setiap fungsi mendapat tumpukan bingkai sendiri.
Jadi setiap panggilan dari fungsi rekursif mendapat tumpukan bingkai sendiri.
Jadi jika Anda membuat panggilan rekursif 1.000, Anda mendapatkan 1.000 frame stack,
dan cepat Anda memimpin untuk memiliki frame tumpukan terlalu banyak dan hal-hal hanya istirahat.
Jadi itulah mengapa fungsi rekursif umumnya buruk.
Tapi ada subset bagus fungsi rekursif disebut ekor-rekursif fungsi,
dan ini terjadi untuk menjadi salah satu contoh di mana jika kompilator pemberitahuan ini
dan seharusnya, saya pikir - di dentang jika Anda lulus dengan O2-flag
maka akan melihat ini adalah ekor rekursif dan membuat hal-hal yang baik.
>> Ini akan menggunakan kembali stack frame yang sama berulang-ulang untuk setiap panggilan rekursif.
Dan jadi karena Anda menggunakan stack frame yang sama, Anda tidak perlu khawatir tentang
pernah menumpuk meluap, dan pada saat yang sama, seperti Anda katakan sebelumnya,
di mana setelah Anda kembali benar, maka harus kembali sampai semua frame tumpukan
dan panggilan 10 untuk SearchHelp harus kembali ke 9, harus kembali ke 8.
Sehingga tidak perlu terjadi bila fungsi rekursif ekor.
Dan jadi apa yang membuat ekor fungsi rekursif adalah pemberitahuan bahwa untuk setiap panggilan yang diberikan kepada searchHelp
panggilan rekursif bahwa itu adalah apa yang membuat itu kembali.
Jadi dalam panggilan pertama untuk SearchHelp, kita baik segera kembali palsu,
segera kembali benar, atau kita membuat panggilan rekursif untuk SearchHelp
di mana apa yang kita kembali adalah apa panggilan yang kembali.
Dan kita tidak bisa melakukan ini jika kita melakukan sesuatu seperti int x = SearchHelp, kembali x * 2,
hanya beberapa perubahan acak.
>> Jadi sekarang ini panggilan rekursif, int ini x = SearchHelp panggilan rekursif,
tidak lagi ekor rekursif karena sebenarnya tidak harus kembali
kembali ke stack frame sebelumnya sehingga bahwa panggilan sebelumnya untuk fungsi
kemudian dapat melakukan sesuatu dengan nilai kembali.
Jadi ini bukan ekor rekursif, tapi apa yang kita miliki sebelum yang baik ekor rekursif. Ya.
[Mahasiswa] Bukankah kasus dasar kedua diperiksa terlebih dahulu
karena mungkin ada situasi di mana ketika Anda lulus argumen
Anda telah mulai akhir =, tetapi mereka nilai jarum.
Pertanyaan itu tidak bisa kita lari ke kasus di mana akhirnya adalah nilai jarum
atau mulai akhir =, tepat, mulai akhir =
dan Anda belum benar-benar memeriksa nilai tersebut belum,
kemudian mulai + end / 2 hanya akan menjadi nilai yang sama.
Tapi kami sudah kembali palsu dan kami tidak pernah benar-benar memeriksa nilai.
Jadi setidaknya, pada panggilan pertama, jika ukuran 0, maka kita ingin kembali palsu.
Tetapi jika ukuran 1, maka awal tidak akan berakhir sama,
dan kami setidaknya akan memeriksa satu unsur.
Tapi saya pikir Anda benar dalam bahwa kita bisa berakhir dalam kasus di mana mulai akhir + / 2,
start akhirnya menjadi sama dengan start + end / 2,
tapi kami tidak pernah benar-benar memeriksa elemen.
>> Jadi jika kita periksa dulu adalah elemen tengah nilai yang kita cari,
maka kita segera bisa kembali benar.
Lain jika mereka sama, maka tidak ada gunanya melanjutkan
karena kita hanya akan update ke kasus di mana kita berada pada array tunggal-elemen.
Jika elemen tunggal bukanlah satu yang kita cari,
maka semuanya salah. Ya.
[Mahasiswa] Masalahnya adalah bahwa karena ukuran sebenarnya lebih besar dari jumlah elemen dalam array,
sudah ada offset ke - >> Jadi akan ukuran -
[Mahasiswa] Katakanlah jika array adalah ukuran 0, maka SearchHelp sebenarnya akan memeriksa tumpukan jerami dari 0
pada panggilan pertama.
Array memiliki ukuran 0, sehingga 0 adalah - >> Ya.
Ada hal lain yang - mungkin baik. Mari kita pikirkan.
Jadi jika array memiliki 10 elemen dan yang tengah kita akan memeriksa adalah indeks 5,
jadi kita memeriksa 5, dan mari kita mengatakan bahwa nilai kurang.
Jadi kita membuang segalanya dari 5 dan seterusnya.
Jadi mulailah + end / 2 akan menjadi akhir baru kami,
sehingga yeah, itu selalu akan tinggal di luar akhir array.
Jika itu terjadi jika itu genap atau ganjil, maka kita akan memeriksa, katakanlah, 4,
tapi kami masih membuang -
Jadi ya, akhirnya selalu akan berada di luar akhir yang sebenarnya dari array.
Jadi unsur-unsur yang kita berfokus pada, akhir selalu akan menjadi satu setelah itu.
Dan jadi jika awal tidak pernah berakhir yang sama, kita berada dalam berbagai ukuran 0.
>> Hal lain yang saya berpikir adalah kita memperbarui start untuk start + end / 2,
jadi ini adalah kasus yang Saya mengalami kesulitan dengan, di mana mulai + end / 2
adalah elemen kita memeriksa.
Katakanlah kita memiliki array 10-elemen. Apapun.
Jadi mulailah + end / 2 akan menjadi sesuatu seperti ini,
dan kalau itu tidak nilai, katakanlah kita ingin mengupdate.
Nilai lebih besar, jadi kami ingin melihat ini setengah dari array.
Jadi bagaimana kita meng-update start, kami meng-update mulai sekarang menjadi elemen ini.
Tapi ini masih dapat bekerja, atau setidaknya, Anda bisa melakukan start + end / 2 + 1.
[Mahasiswa] Anda tidak perlu mulai akhir + [tak terdengar] >> Ya.
Kami telah memeriksa elemen ini dan tahu itu bukan satu yang kita cari.
Jadi kita tidak perlu memperbarui mulai menjadi elemen ini.
Kami hanya bisa melewati itu dan memperbarui mulai menjadi elemen ini.
Dan apakah ada yang pernah kasus, katakanlah, bahwa ini adalah akhir,
sehingga kemudian mulai akan hal ini, mulailah + end / 2 akan hal ini,
mulai akhir + - Ya, saya pikir itu bisa berakhir di rekursi tak terbatas.
Mari kita mengatakan itu hanya sebuah array ukuran 2 atau array ukuran 1. Saya pikir ini akan bekerja.
Jadi saat ini, awal adalah bahwa elemen dan akhir adalah 1 melampauinya.
Jadi elemen yang kita akan memeriksa satu ini,
dan kemudian ketika kita update awal, kami meng-update mulai menjadi 0 + 1/2,
yang akan berakhir kita kembali dengan mulai menjadi elemen ini.
>> Jadi kita memeriksa unsur yang sama berulang-ulang.
Jadi ini adalah kasus di mana setiap panggilan rekursif harus benar-benar memperbarui sesuatu.
Jadi kita perlu melakukan start + end / 2 + 1, atau yang lain ada kasus
di mana kita tidak benar-benar memperbarui awal.
Semua orang melihat itu?
Oke.
Apakah ada yang memiliki pertanyaan tentang ini solusi atau komentar lagi?
Oke. Apakah ada yang telah berulang-ulang solusi yang kita semua dapat melihat?
Apakah kita semua melakukannya secara rekursif?
Atau juga saya kira jika Anda membuka miliknya, maka Anda mungkin memiliki diganti sebelumnya Anda.
Apakah itu secara otomatis menyimpan? Aku tidak positif.
Apakah ada yang telah berulang?
Kita bisa berjalan melalui bersama-sama jika tidak.
Idenya akan menjadi sama.
Iterative solusi.
Kita akan ingin pada dasarnya melakukan ide yang sama
di mana kita ingin melacak akhir baru array dan awal baru dari array
dan melakukannya berulang-ulang.
Dan jika apa yang kita melacak sebagai awal dan akhir yang pernah berpotongan,
maka kita tidak menemukan itu dan kita bisa kembali palsu.
Jadi bagaimana saya melakukan itu? Ada yang punya saran atau kode bagi saya untuk menarik?
[Mahasiswa] Lakukan loop sementara. >> Ya.
Anda akan ingin melakukan loop.
>> Apakah Anda memiliki kode saya bisa menarik, atau apa yang akan Anda sarankan?
[Mahasiswa] Saya kira begitu. >> Baiklah. Hal ini membuat segalanya lebih mudah. Siapa nama Anda?
[Mahasiswa] Lucas.
Revisi 1. Oke.
Rendah adalah apa yang kita disebut mulai sebelum.
Up adalah tidak cukup apa yang kita disebut akhir sebelum.
Sebenarnya, akhirnya sekarang dalam array. Ini adalah elemen yang harus kita pertimbangkan.
Jadi rendah adalah 0, naik adalah ukuran array - 1,
dan sekarang kita looping, dan kami memeriksa -
Saya kira Anda bisa berjalan melalui itu.
Apa yang dipikirkan Anda melalui ini? Berjalan kami melalui kode Anda.
[Mahasiswa] Tentu. Lihatlah nilai tumpukan jerami di tengah dan membandingkannya dengan jarum.
Jadi jika itu lebih besar dari jarum Anda, maka Anda ingin - oh, sebenarnya, yang harus mundur.
Anda akan ingin membuang bagian kanan, dan begitu ya, yang harus jalan.
[Bowden] Jadi ini harus kurang? Adalah bahwa apa yang Anda katakan? >> [Mahasiswa] Ya.
[Bowden] Oke. Kurangi sedikit.
Jadi jika apa yang kita sedang melihat lebih kecil dari apa yang kita inginkan,
maka yeah, kami ingin membuang kiri setengah,
yang berarti kita memperbarui segala sesuatu yang kita sedang mempertimbangkan
dengan memindahkan rendah di sebelah kanan array.
Ini terlihat bagus.
Saya pikir itu memiliki masalah yang sama bahwa kita mengatakan pada yang sebelumnya,
di mana jika rendah adalah 0 dan up adalah 1, kemudian rendah up + / 2 akan dibentuk menjadi hal yang sama lagi.
>> Dan bahkan jika itu tidak terjadi, itu masih lebih efisien setidaknya
hanya membuang elemen kita hanya melihat yang kita tahu adalah salah.
Begitu rendah + up / 2 + 1 - >> [mahasiswa] Itu harus menjadi cara lainnya.
[Bowden] Atau ini harus - 1 dan yang lainnya harus + 1.
[Mahasiswa] Dan harus ada ganda tanda sama. >> [Bowden] Ya.
[Mahasiswa] Ya.
Oke.
Dan akhirnya, sekarang kita memiliki + 1 - 1 hal,
itu - itu tidak mungkin - itu pernah mungkin untuk rendah berakhir dengan nilai yang lebih besar dari atas?
Saya pikir satu-satunya cara yang bisa terjadi - Apakah mungkin? >> [Mahasiswa] Saya tidak tahu.
Tetapi jika mendapat dipotong dan kemudian mendapat minus yang 1 dan kemudian - >> Ya.
[Mahasiswa] Ini mungkin akan mendapatkan kacau.
Saya pikir itu harus baik hanya karena
untuk itu berakhir lebih rendah mereka akan harus sama, saya pikir.
Tetapi jika mereka adalah sama, maka kita tidak akan melakukan loop sementara untuk memulai dengan
dan kami hanya akan kembali nilai. Jadi saya pikir kita baik sekarang.
Perhatikan bahwa meskipun masalah ini tidak lagi rekursif,
yang sama berlaku apabila ide kita bisa melihat bagaimana hal ini begitu mudah cocok
untuk solusi rekursif oleh fakta bahwa kami hanya memperbarui indeks berulang-ulang,
kita membuat masalah yang lebih kecil dan lebih kecil, kami berfokus pada subset dari array.
[Mahasiswa] Jika rendah adalah 0 dan sampai 1, mereka berdua akan menjadi 0 + 1/2, yang akan pergi ke 0,
dan kemudian satu akan + 1, satu akan menjadi - 1.
[Mahasiswa] mana kita memeriksa kesetaraan?
Seperti jika yang sebenarnya tengah jarum?
Kami saat ini tidak melakukan hal itu? Oh!
Jika ini kan -
Ya. Kita tidak bisa hanya melakukan tes di sini karena katakanlah tengah pertama -
[Mahasiswa] Ini benar-benar seperti tidak membuang terikat.
Jadi jika Anda membuang terikat, Anda harus dicek dulu atau apa pun.
Ah. Ya. >> [Mahasiswa] Ya.
Jadi sekarang kita telah dibuang yang saat ini kami melihat,
yang berarti kita sekarang harus juga memiliki
if (tumpukan jerami [(low + up) / 2] == jarum), maka kita bisa kembali benar.
Dan apakah saya menempatkan lain atau hanya jika, itu berarti harfiah hal yang sama
karena ini akan kembali benar.
Jadi saya akan menaruh lain jika, tapi itu tidak masalah.
>> Jadi lain jika hal ini, lagi ini, dan ini adalah hal yang umum saya lakukan
mana bahkan jika itu adalah kasus di mana segala sesuatu baik di sini,
seperti rendah tidak dapat lebih besar dari atas, itu bukan alasan layak tentang apakah itu benar.
Jadi Anda mungkin juga mengatakan sementara rendah kurang dari atau sama dengan
atau sementara rendah kurang dari
jadi jika mereka pernah sama atau rendah terjadi untuk dilewatkan,
maka kita bisa keluar dari lingkaran ini.
Pertanyaan, kekhawatiran, komentar?
Oke. Ini terlihat bagus.
Sekarang kita ingin melakukan semacam.
Jika kita pergi ke revisi kedua saya, kita melihat angka-angka yang sama,
tapi sekarang mereka tidak lagi dalam rangka diurutkan.
Dan kita ingin menerapkan semacam menggunakan algoritma di O n log n.
Jadi mana algoritma yang Anda pikir kita harus melaksanakan sini? >> [Mahasiswa] Merge sort.
[Bowden] Ya. Merge sort adalah O (n log n), sehingga itulah yang akan kita lakukan.
Dan masalahnya akan menjadi sangat mirip,
mana dengan mudah cocok untuk solusi rekursif.
Kita juga bisa datang dengan solusi berulang jika kita ingin,
tapi rekursi akan lebih mudah di sini dan kami harus melakukan rekursi.
Saya kira kita akan berjalan melalui gabungan semacam pertama,
meskipun ada video indah di gabungan semacam sudah. [Tertawa]
Jadi menggabungkan semacam ada - Saya membuang-buang begitu banyak makalah ini.
Oh, hanya ada satu kiri.
Jadi bergabung.
Oh, 1, 3, 5.
Oke.
Merge mengambil dua array terpisah.
Individual kedua array keduanya diurutkan.
Jadi ini array, 1, 3, 5, diurutkan. Ini array, 0, 2, 4, diurutkan.
Sekarang apa yang harus Anda lakukan adalah menggabungkan menggabungkan mereka ke dalam sebuah array tunggal yang diurutkan itu sendiri.
Jadi kami ingin sebuah array ukuran 6 yang akan memiliki unsur-unsur di dalamnya
dalam rangka diurutkan.
>> Dan jadi kita bisa mengambil keuntungan dari fakta bahwa dua array diurutkan
untuk melakukan hal ini dalam waktu linier,
berarti waktu linier jika array ini adalah x ukuran dan ini adalah ukuran y,
maka algoritma total harus O (x + y). Oke.
Jadi saran.
[Mahasiswa] Bisakah kita mulai dari kiri?
Jadi Anda akan menempatkan 0 turun pertama dan kemudian 1 dan maka di sini Anda berada di 2.
Jadi itu seperti Anda memiliki tab yang bergerak ke kanan. >> [Bowden] Ya.
Untuk kedua array jika kita hanya fokus pada elemen paling kiri.
Karena kedua array diurutkan, kita tahu bahwa elemen 2
adalah elemen terkecil dalam array baik.
Jadi itu berarti bahwa 1 dari mereka 2 elemen harus menjadi elemen terkecil dalam array gabungan kami.
Kebetulan bahwa terkecil adalah satu di waktu yang tepat ini.
Jadi kita ambil 0, masukkan di sebelah kiri karena 0 adalah kurang dari 1,
sehingga mengambil 0, masukkan ke posisi pertama kami, dan kemudian kami memperbarui ini
sekarang fokus pada elemen pertama.
Dan sekarang kita ulangi.
Jadi sekarang kita bandingkan 2 dan 1. 1 lebih kecil, jadi kita akan memasukkan 1.
Kami memperbarui pointer ini untuk menunjuk ke orang ini.
Sekarang kita melakukannya lagi, sehingga 2. Ini akan memperbarui, membandingkan 2, 3.
Ini update, kemudian 4 dan 5.
Jadi itu adalah gabungan.
>> Ini harus cukup jelas bahwa itu adalah waktu linier karena kita hanya pergi di setiap elemen sekali.
Dan itu adalah langkah terbesar untuk menerapkan semacam gabungan yang melakukan hal ini.
Dan itu tidak sulit.
Beberapa hal yang perlu dikhawatirkan adalah mari kita mengatakan kami penggabungan 1, 2, 3, 4, 5, 6.
Dalam hal ini kita berakhir di skenario di mana yang satu ini akan menjadi lebih kecil,
maka kami memperbarui pointer ini, yang satu ini akan menjadi lebih kecil, update ini,
yang satu ini lebih kecil, dan sekarang Anda harus mengenali
ketika Anda sudah benar-benar kehabisan elemen untuk membandingkan dengan.
Karena kita telah menggunakan ini seluruh array,
segala sesuatu dalam array ini sekarang hanya dimasukkan ke sini.
Jadi jika kita pernah mengalami titik di mana salah satu dari array kita benar-benar bergabung sudah,
maka kita hanya mengambil semua elemen dari array lain dan memasukkan mereka ke akhir array.
Jadi kami hanya bisa memasukkan 4, 5, 6. Oke.
Itulah salah satu hal yang harus diperhatikan.
Menerapkan langkah yang harus 1.
Gabung mengurutkan maka berdasarkan itu, itu 2 langkah, 2 langkah konyol.
Mari kita beri array ini.
Jadi menggabungkan semacam, langkah 1 adalah untuk rekursif memecah array menjadi dua bagian.
Jadi membagi array ini menjadi dua bagian.
Kami sekarang memiliki 4, 15, 16, 50 dan 8, 23, 42, 108.
Dan sekarang kita melakukannya lagi dan kami berpisah ini menjadi dua bagian.
Aku hanya akan melakukannya di sisi ini.
Jadi 4, 15 dan 16, 50.
Kami akan melakukan hal yang sama di sini.
Dan sekarang kita membaginya menjadi dua bagian lagi.
Dan kami memiliki 4, 15, 16, 50.
Jadi itu adalah kasus dasar kami.
Setelah array ukuran 1, maka kita berhenti dengan membelah menjadi dua bagian.
>> Sekarang apa yang kita lakukan dengan ini?
Kami akhirnya ini juga akan terurai menjadi 8, 23, 42, dan 108.
Jadi sekarang kita berada di titik ini, sekarang langkah kedua dari gabungan semacam hanya penggabungan pasangan untuk daftar.
Jadi kami ingin menggabungkan semua. Kami hanya memanggil bergabung.
Kita tahu merge akan kembali ini dalam rangka diurutkan.
4, 15.
Sekarang kita ingin menggabungkan ini, dan itu akan kembali daftar dengan mereka dalam rangka diurutkan,
16, 50.
Kami menggabungkan mereka - saya tidak bisa menulis - 8, 23 dan 42, 108.
Jadi kita memiliki pasangan gabungan sekali.
Sekarang kita hanya bergabung lagi.
Perhatikan bahwa masing-masing daftar yang diurutkan dalam dirinya sendiri,
dan kemudian kami hanya dapat menggabungkan daftar ini untuk mendapatkan daftar ukuran 4 yang diurutkan
dan menggabungkan kedua daftar untuk mendapatkan daftar ukuran 4 yang diurutkan.
Dan akhirnya, kita dapat menggabungkan dua daftar ukuran 4 untuk mendapatkan salah satu daftar ukuran 8 yang diurutkan.
Jadi untuk melihat bahwa ini adalah keseluruhan n log n, kita sudah melihat bahwa merge adalah linear,
jadi ketika kita sedang berhadapan dengan penggabungan ini, sehingga seperti biaya keseluruhan merge
untuk kedua daftar hanya 2 karena -
Atau juga, itu O n, namun n disini hanya 2 elemen tersebut, sehingga 2.
Dan ini akan menjadi 2 2 2 dan ini akan menjadi 2 dan ini akan menjadi 2 2,
sehingga di semua gabungan yang perlu kita lakukan, kita akhirnya mengerjakan n.
Seperti 2 + 2 + 2 + 2 adalah 8, yang adalah n,
sehingga biaya penggabungan di set ini adalah n.
Dan kemudian hal yang sama di sini.
Kita akan menggabungkan semua 2, maka 2, dan individual gabungan ini akan mengambil empat operasi,
ini merge akan mengambil empat operasi, tetapi sekali lagi, antara semua ini,
kita akhirnya penggabungan n hal total, sehingga langkah ini membutuhkan n.
Dan sehingga setiap tingkat membutuhkan n elemen yang bergabung.
>> Dan berapa banyak tingkat yang ada?
Pada setiap tingkat, array kita tumbuh dengan ukuran 2.
Berikut array kami adalah ukuran 1, di sini mereka ukuran 2, di sini mereka ukuran 4,
dan akhirnya, mereka ukuran 8.
Jadi karena itu adalah dua kali lipat, ada yang akan menjadi total log n tingkat ini.
Jadi dengan log n tingkat, masing-masing tingkat individu mengambil n operasi total,
kita mendapatkan log n n algoritma.
Pertanyaan?
Apakah orang-orang sudah membuat kemajuan tentang bagaimana menerapkan ini?
Apakah ada yang sudah dalam keadaan di mana saya hanya dapat menarik kode mereka?
Aku bisa memberikan satu menit.
Yang satu ini akan menjadi lebih lama.
Saya sangat merekomendasikan kambuh -
Anda tidak perlu melakukan rekursi untuk penggabungan
karena untuk melakukan rekursi untuk menggabungkan, Anda akan harus melewati sekelompok ukuran yang berbeda.
Anda dapat, tapi menjengkelkan.
Tapi rekursi untuk semacam itu sendiri cukup mudah.
Anda hanya benar-benar memanggil semacam di kiri setengah, seperti pada bagian kanan. Oke.
Ada yang punya apa-apa aku bisa menarik belum?
Atau aku akan memberikan satu menit.
Oke.
Ada yang punya sesuatu yang kita dapat bekerja dengan?
Atau kita hanya akan bekerja dengan ini dan kemudian berkembang dari sana.
>> Ada yang punya lebih dari ini bahwa saya bisa menarik?
[Mahasiswa] Ya. Anda dapat menarik tambang. >> Baiklah.
Ya!
[Mahasiswa] Ada banyak kondisi. >> Oh, menembak. Dapatkah Anda -
[Mahasiswa] Saya harus menyimpannya. >> Ya.
Jadi kita lakukan penggabungan secara terpisah.
Oh, tapi itu tidak terlalu buruk.
Oke.
Jadi semacam itu sendiri hanya menelepon mergeSortHelp.
Jelaskan kepada kami apa mergeSortHelp tidak.
[Mahasiswa] MergeSortHelp cukup banyak melakukan dua langkah utama,
yaitu untuk mengurutkan masing-masing setengah dari array dan kemudian untuk menggabungkan keduanya.
[Bowden] Oke, jadi beri aku detik.
Saya pikir ini - >> [mahasiswa] saya perlu -
Ya. Aku kehilangan sesuatu.
Pada menggabungkan, saya menyadari bahwa saya perlu membuat sebuah array baru
karena saya tidak bisa melakukannya di tempat. >> Ya. Anda tidak bisa. Benar.
[Mahasiswa] Jadi saya membuat sebuah array baru.
Aku lupa pada akhir bergabung untuk re-ubah.
Oke. Kita perlu sebuah array baru.
Dalam gabungan semacam, ini hampir selalu benar.
Bagian dari biaya algoritma yang lebih baik waktu-bijaksana
hampir selalu perlu untuk menggunakan memori sedikit lebih.
Jadi di sini, tidak peduli bagaimana Anda lakukan menggabungkan semacam,
Anda pasti akan perlu menggunakan beberapa memori tambahan.
Dia menciptakan sebuah array baru.
Dan kemudian Anda katakan pada akhirnya kita hanya perlu menyalin array baru ke array yang asli.
[Mahasiswa] Saya kira begitu, ya.
Saya tidak tahu apakah yang bekerja dalam hal menghitung dengan referensi atau apa pun -
Ya, ia akan bekerja. >> [Mahasiswa] Oke.
Apakah Anda mencoba menjalankan ini? >> [Mahasiswa] Tidak, belum. Oke >>.
Coba jalankan itu, dan kemudian saya akan berbicara tentang hal ini untuk kedua.
[Mahasiswa] Saya perlu memiliki semua prototipe fungsi dan segalanya, meskipun, kan?
Prototipe fungsi. Oh, maksudmu seperti - Ya.
Urutkan memanggil mergeSortHelp.
>> Jadi agar semacam untuk memanggil mergeSortHelp, mergeSortHelp baik harus telah didefinisikan
sebelum semacam atau kita hanya perlu prototipe. Cukup copy dan paste.
Dan sama, mergeSortHelp memanggil bergabung,
namun menggabungkan belum ditetapkan belum, jadi kami hanya bisa membiarkan mergeSortHelp tahu
bahwa itulah yang menggabungkan akan terlihat seperti, dan itulah yang.
Jadi mergeSortHelp.
Kami memiliki masalah di sini di mana kita tidak memiliki kasus dasar.
MergeSortHelp adalah rekursif, sehingga setiap fungsi rekursif
akan memerlukan beberapa jenis kasus dasar untuk mengetahui kapan harus berhenti menyebut dirinya secara rekursif.
Apa yang kasus dasar kami akan di sini? Ya.
[Mahasiswa] Jika ukurannya 1? >> [Bowden] Ya.
Jadi seperti yang kita lihat di sana, kami berhenti membelah array
setelah kami masuk ke array ukuran 1, yang pasti akan diurutkan sendiri.
Jadi jika ukuran sama dengan 1, kita tahu array sudah diurutkan,
jadi kami hanya bisa kembali.
>> Perhatikan itu batal, sehingga kita tidak kembali sesuatu yang khusus, kita hanya kembali.
Oke. Jadi itu yang terjadi dasar kami.
Saya kira kasus dasar kami juga bisa jika kita kebetulan penggabungan array ukuran 0,
kita mungkin ingin berhenti di beberapa titik,
jadi kami hanya dapat mengatakan ukuran kurang dari 2 atau kurang dari atau sama dengan 1
sehingga ini akan bekerja untuk array setiap saat.
Oke.
Jadi itu yang terjadi dasar kami.
Sekarang Anda ingin berjalan kita melalui penggabungan?
Apa semua kasus itu?
Sampai di sini, kita hanya melakukan ide yang sama, -
[Mahasiswa] Saya harus melewati ukuran dengan semua panggilan mergeSortHelp.
Saya menambahkan ukuran sebagai primer tambahan dan itu tidak ada, seperti ukuran / 2.
[Bowden] Oh, ukuran / 2, ukuran / 2. >> [Mahasiswa] Ya, dan juga dalam fungsi di atas juga.
[Bowden] Di sini? >> [Mahasiswa] Hanya ukuran. >> [Bowden] Oh. Ukuran, ukuran? >> [Mahasiswa] Ya.
[Bowden] Oke.
Biarkan aku berpikir untuk kedua.
Apakah kita mengalami masalah?
Kami selalu memperlakukan kiri sebagai 0. >> [Mahasiswa] No
Itu salah juga. Maaf. Ini harus menjadi awal. Ya.
[Bowden] Oke. Aku seperti itu lebih baik.
Dan akhir. Oke.
Jadi sekarang Anda ingin berjalan kita melalui penggabungan? >> [Mahasiswa] Oke.
Aku hanya berjalan melalui array baru yang saya buat.
Ukurannya adalah ukuran porsi array yang kita ingin diurutkan
dan mencoba untuk menemukan elemen yang saya harus dimasukkan ke dalam langkah array baru.
Jadi untuk melakukan itu, pertama aku memeriksa apakah kiri setengah dari array terus memiliki unsur lagi,
dan jika tidak, maka Anda pergi ke kondisi yang lain, yang hanya mengatakan
oke, itu harus dalam array yang tepat, dan kami akan menempatkan bahwa dalam indeks saat newArray.
>> Dan kemudian jika tidak, aku memeriksa apakah sisi kanan dari array juga selesai,
dalam hal ini saya hanya dimasukkan ke dalam sebelah kiri.
Itu tidak mungkin benar-benar diperlukan. Saya tidak yakin.
Tapi bagaimanapun, cek dua lainnya yang dari dua lebih kecil di kiri atau kanan.
Dan juga dalam setiap kasus, aku incrementing mana placeholder I kenaikan.
[Bowden] Oke.
Itu terlihat baik.
Apakah ada yang punya komentar atau masalah atau pertanyaan?
Jadi empat kasus yang kita harus membawa hal-hal menjadi hanya menjadi - atau sepertinya lima -
tapi kita harus mempertimbangkan apakah array kiri telah kehabisan hal yang kita butuhkan untuk menggabungkan,
apakah array yang benar telah kehabisan hal yang kita butuhkan untuk menggabungkan -
Saya menunjuk pada apa-apa.
Jadi apakah array kiri telah kehabisan hal-hal atau array yang benar telah kehabisan hal.
Mereka adalah dua kasus.
Kita juga perlu kasus sepele apakah hal kiri kurang dari hal yang benar.
Kemudian kita ingin memilih hal kiri.
Mereka adalah kasus.
Jadi ini benar, jadi itu yang.
Array kiri. Ini 1, 2, 3. Oke. Jadi ya, mereka adalah empat hal yang kita mungkin ingin lakukan.
Dan kami tidak akan pergi ke iteratif solusi.
Saya tidak akan merekomendasikan -
Merge sort adalah contoh dari sebuah fungsi yang bersifat tidak rekursif ekor,
itu tidak mudah untuk membuat ekor rekursif,
tetapi juga tidak sangat mudah untuk membuatnya berulang.
Ini sangat mudah.
Ini implementasi gabungan semacam,
menggabungkan, tidak peduli apa yang Anda lakukan, Anda akan membangun penggabungan.
>> Jadi menggabungkan semacam dibangun di atas merge rekursif hanya tiga baris.
Iteratif, itu lebih mengganggu dan lebih sulit untuk dipikirkan.
Tapi melihat bahwa itu bukan ekor rekursif sejak mergeSortHelp - saat itu menyebut dirinya -
masih perlu melakukan hal-hal ini kembali setelah panggilan rekursif.
Jadi ini stack frame harus terus ada bahkan setelah panggilan ini.
Dan kemudian ketika Anda menyebutnya, stack frame harus terus ada
karena bahkan setelah panggilan itu, kita masih perlu untuk menggabungkan.
Dan itu adalah trivial untuk membuat ekor ini rekursif.
Pertanyaan?
Baiklah.
Jadi akan kembali untuk memilah - oh, ada dua hal yang saya ingin menunjukkan. Oke.
Akan kembali untuk menyortir, kita akan melakukan ini dengan cepat.
Atau cari. Urutkan? Sort. Ya.
Kembali ke awal semacam.
Kami ingin menciptakan suatu algoritma yang macam array menggunakan algoritma setiap
di O n.
Jadi bagaimana ini mungkin? Apakah ada yang punya semacam -
Aku mengisyaratkan sebelumnya di -
Jika kita akan meningkatkan dari n log n untuk n O,
kami telah memperbaiki algoritma kami waktu-bijaksana,
yang berarti apa yang akan kita lakukan untuk membuat untuk itu?
[Mahasiswa] Space. >> Ya. Kita akan menggunakan lebih banyak ruang.
Dan bahkan tidak hanya lebih banyak ruang, itu ruang eksponensial lebih.
Jadi saya pikir ini jenis algoritma adalah sesuatu yang semu, pseudo polynom -
pseudo - Saya tidak ingat. Pseudo sesuatu.
Tapi itu karena kita perlu menggunakan begitu banyak ruang
bahwa hal ini dapat dicapai, tetapi tidak realistis.
>> Dan bagaimana kita mencapai hal ini?
Kita bisa mencapai hal ini jika kita menjamin bahwa setiap elemen tertentu dalam array
berada di bawah ukuran tertentu.
Jadi mari kita hanya mengatakan bahwa ukuran adalah 200,
setiap elemen dalam array di bawah ukuran 200.
Dan ini sebenarnya sangat realistis.
Anda dapat dengan mudah memiliki sebuah array yang Anda tahu segala sesuatu di dalamnya
akan menjadi kurang dari beberapa nomor.
Seperti jika Anda memiliki beberapa vektor benar-benar besar atau sesuatu
tapi kau tahu semuanya akan menjadi antara 0 dan 5,
maka itu akan secara signifikan lebih cepat untuk melakukan hal ini.
Dan terikat pada salah satu elemen adalah 5,
jadi ini terikat, yaitu berapa banyak memori yang Anda akan menggunakan.
Jadi terikat adalah 200.
Dalam teori selalu ada terikat karena integer hanya bisa sampai 4 miliar,
tapi itu tidak realistis sejak itu kita akan menggunakan ruang
pada urutan 4 miliar. Jadi itu tidak realistis.
Tapi di sini kita akan mengatakan terikat kami adalah 200.
Trik untuk melakukannya di O n adalah kita membuat array lain yang disebut jumlah ukuran TERIKAT.
Jadi sebenarnya, ini adalah jalan pintas untuk - saya benar-benar tidak tahu apakah dentang melakukan hal ini.
Tapi di GCC paling tidak - dengan asumsi dentang 'm tidak terlalu -
ini hanya akan menginisialisasi seluruh array menjadi 0s.
Jadi jika saya tidak ingin melakukan itu, maka saya secara terpisah bisa lakukan untuk (int i = 0;
i <TERIKAT, i + +) dan jumlah [i] = 0;
Jadi sekarang semuanya diinisialisasi ke 0.
Aku iterate atas array saya,
dan apa yang saya lakukan adalah saya sedang menghitung jumlah masing-masing - Mari kita turun di sini.
Kami memiliki 4, 15, 16, 50, 8, 23, 42, 108.
Yang saya menghitung adalah jumlah kejadian dari masing-masing elemen.
Mari kita benar-benar menambahkan beberapa lebih di sini dengan beberapa mengulangi.
Jadi nilai yang kita miliki di sini, nilai yang akan menjadi array [i].
Jadi val bisa 4 atau 8 atau apa pun.
Dan sekarang saya sedang menghitung berapa banyak nilai yang pernah saya lihat,
sehingga jumlah [val] + +;
Setelah ini dilakukan, jumlah ini akan terlihat seperti 0001.
Mari kita melakukan penghitungan [val] - TERIKAT + 1.
>> Nah, itu hanya untuk menjelaskan fakta bahwa kita mulai dari 0.
Jadi, jika 200 akan menjadi nomor kami terbesar,
kemudian 0 sampai 200 adalah 201 hal.
Jadi penting, itu akan terlihat seperti 00001 karena kita memiliki satu 4.
Kemudian kita akan memiliki 0001 di mana kita akan memiliki 1 dalam indeks 8 hitungan.
Kami akan memiliki 2 dalam indeks 23 hitungan.
Kami akan memiliki 2 dalam indeks ke-42 hitungan.
Jadi kita bisa menggunakan hitungan.
Jadi num_of_item = jumlah [i].
Dan jadi jika num_of_item adalah 2, itu berarti kita ingin memasukkan 2 dari nomor i
ke dalam array kami diurutkan.
Jadi kita perlu melacak seberapa jauh kita ke array.
Jadi = indeks 0.
Array - Aku hanya akan menulisnya.
Hitungan -
array [index + +] = i;
Adalah bahwa apa yang saya inginkan? Saya pikir itulah yang saya inginkan.
Ya, ini tampak bagus. Oke.
Jadi tidak semua orang mengerti apa tujuan array jumlah saya?
Hal ini menghitung jumlah kejadian dari masing-masing nomor.
Kemudian saya iterasi bahwa array penting,
dan posisi i di array jumlah
adalah jumlah i itu yang harus muncul dalam array saya diurutkan.
Itulah mengapa penting dari 4 akan menjadi 1
dan jumlah dari 8 akan menjadi 1, jumlah dari 23 akan menjadi 2.
Jadi itulah berapa banyak dari mereka saya ingin memasukkan ke dalam array saya diurutkan.
Lalu aku hanya melakukan itu.
Saya memasukkan num_of_item i s ke array saya diurutkan.
>> Pertanyaan?
Dan jadi sekali lagi, ini adalah waktu linier karena kita hanya iterasi sekali ini,
tetapi juga linier dalam apa nomor ini akan terjadi,
dan sehingga sangat tergantung pada apa yang Anda terikat.
Dengan terikat dari 200, itu tidak seburuk itu.
Jika Anda terikat akan menjadi 10.000, maka itu sedikit lebih buruk,
tetapi jika Anda terikat akan menjadi 4 miliar, itu benar-benar realistis
dan array ini akan harus ukuran 4 miliar, yang tidak realistis.
Jadi itulah yang. Pertanyaan?
[Respon siswa terdengar] >> Oke.
Aku menyadari satu hal lain ketika kita akan melalui.
Saya pikir masalahnya adalah di kawasan Lucas dan mungkin setiap satu kita lihat.
Saya benar-benar lupa.
Satu-satunya hal yang ingin saya mengomentari adalah bahwa ketika Anda sedang berhadapan dengan hal-hal seperti indeks,
Anda tidak pernah benar-benar melihat ini ketika Anda sedang menulis untuk loop,
tetapi secara teknis, setiap kali Anda sedang berhadapan dengan indeks,
Anda harus cukup banyak selalu berurusan dengan unsigned integer.
Alasan untuk ini adalah ketika Anda sedang berhadapan dengan bilangan bulat ditandatangani,
jadi jika Anda memiliki 2 bilangan bulat ditandatangani dan Anda menambahkan mereka bersama-sama
dan mereka akhirnya terlalu besar, maka Anda berakhir dengan angka negatif.
Jadi itulah integer overflow yang.
>> Jika saya tambahkan 2 miliar dan 1 miliar, saya berakhir dengan negatif 1 miliar.
Begitulah bilangan bulat bekerja pada komputer.
Jadi masalah dengan menggunakan -
Itu baik kecuali jika rendah terjadi menjadi 2 miliar dan sampai terjadi menjadi 1 miliar,
maka ini akan menjadi negatif 1 miliar dan kemudian kita akan membagi bahwa dengan 2
dan berakhir dengan negatif 500 juta.
Jadi ini hanya masalah jika Anda kebetulan akan mencari melalui array
miliaran hal.
Tapi jika + rendah sampai terjadi meluap, maka itu masalah.
Segera setelah kami membuat mereka unsigned, kemudian 2 miliar ditambah 1 miliar adalah 3 miliar.
3 miliar dibagi dengan 2 adalah 1,5 miliar.
Jadi, segera setelah mereka unsigned, semuanya sempurna.
Dan jadi itu juga masalah ketika Anda sedang menulis Anda untuk loop,
dan benar-benar, mungkin tidak secara otomatis.
Ini akan benar-benar hanya berteriak pada Anda.
Jadi jika nomor ini terlalu besar untuk menjadi hanya dalam integer tetapi akan cocok di unsigned integer,
itu akan berteriak pada Anda, jadi itulah mengapa Anda tidak pernah benar-benar mengalami masalah ini.
Anda dapat melihat bahwa indeks tidak pernah akan menjadi negatif,
dan jadi ketika Anda iterasi array,
Anda dapat hampir selalu mengatakan unsigned int i, tetapi Anda tidak benar-benar harus.
Hal-hal yang akan bekerja cukup banyak sama dengan baik.
Oke. [Berbisik] Apa waktu itu?
Hal terakhir yang saya ingin menunjukkan - dan aku hanya akan melakukannya benar-benar cepat.
Kau tahu bagaimana kita mendefinisikan # # sehingga kita dapat mendefinisikan sebagai MAX 5 atau sesuatu?
Mari kita tidak melakukan MAX. # Define TERIKAT sebagai 200. Itulah yang kami lakukan sebelumnya.
Yang mendefinisikan sebuah konstanta, yang hanya akan disalin dan disisipkan
dimanapun kita terjadi untuk menulis TERIKAT.
>> Jadi kita benar-benar bisa berbuat lebih banyak dengan # mendefinisikan.
Kita dapat mendefinisikan fungsi #.
Mereka tidak benar-benar fungsi, tapi kami akan memanggil mereka fungsi.
Sebuah contoh akan menjadi sesuatu seperti MAX (x, y) didefinisikan sebagai (x <y y:? X). Oke.
Jadi, Anda harus terbiasa dengan sintaks terner operator,
tapi x kurang dari y? Kembali y, x lain kembali.
Sehingga Anda dapat melihat Anda dapat membuat fungsi ini terpisah,
dan fungsi bisa seperti bool MAX mengambil 2 argumen, kembali ini.
Ini adalah salah satu yang paling sering saya lihat dilakukan seperti ini. Kami menyebutnya macro.
Ini adalah makro.
Ini hanya sintaks untuk itu.
Anda dapat menulis makro untuk melakukan apapun yang Anda inginkan.
Anda sering melihat macro untuk debugging printfs dan barang-barang.
Jadi jenis printf, terdapat konstanta khusus dalam C seperti menggarisbawahi GARIS garis bawah,
2 menggarisbawahi GARIS underscore,
dan ada juga saya pikir 2 menggarisbawahi FUNC. Yang mungkin itu. Sesuatu seperti itu.
Hal-hal akan diganti dengan nama fungsi
atau jumlah baris yang Anda berada di.
Sering, Anda menulis printfs debugging bahwa di sini saya kemudian bisa hanya menulis
DEBUG dan akan mencetak nomor baris dan fungsi yang saya kebetulan berada di
itu ditemui bahwa pernyataan DEBUG.
Dan Anda juga dapat mencetak hal-hal lain.
Jadi satu hal yang harus diwaspadai adalah jika saya kebetulan # define DOUBLE_MAX
sebagai sesuatu seperti 2 * y dan 2 * x.
Jadi untuk alasan apapun, Anda kebetulan melakukan itu banyak.
Jadi membuat makro.
Hal ini benar-benar rusak.
Saya akan menyebutnya dengan melakukan sesuatu seperti DOUBLE_MAX (3, 6).
Jadi apa yang harus dikembalikan?
[Mahasiswa] 12.
Ya, 12 harus dikembalikan, dan 12 dikembalikan.
3 akan diganti untuk x, 6 akan diganti untuk y, dan kita kembali 2 * 6, yaitu 12.
Sekarang bagaimana dengan ini? Apa yang harus dikembalikan?
[Mahasiswa] 14. >> Idealnya, 14.
Masalahnya adalah bahwa bagaimana hash mendefinisikan pekerjaan, ingat itu copy dan paste literal
dari segala sesuatu cukup banyak, jadi apa ini akan ditafsirkan sebagai
adalah kurang dari 3 1, ditambah 6 2 1 kali ditambah 6, 2 kali 3.
>> Jadi untuk alasan ini Anda hampir selalu membungkus semuanya dalam tanda kurung.
Setiap variabel yang hampir selalu membungkus dalam tanda kurung.
Ada kasus-kasus di mana Anda tidak perlu, seperti saya tahu bahwa saya tidak perlu melakukannya di sini
karena kurang dari cukup banyak selalu hanya akan bekerja,
meskipun itu mungkin tidak benar.
Jika ada sesuatu yang konyol seperti DOUBLE_MAX (1 == 2),
maka itu akan mendapatkan diganti dengan 3 kurang dari 1 sama sama 2,
dan sebagainya maka itu akan melakukan 3 kurang dari 1, apakah itu sama 2,
yang tidak apa yang kita inginkan.
Jadi untuk mencegah Operator masalah didahulukan,
selalu membungkus dalam tanda kurung.
Oke. Dan hanya itu, 5:30.
Jika Anda memiliki pertanyaan tentang pset tersebut, beritahu kami.
Ini harus menyenangkan, dan edisi hacker juga jauh lebih realistis
dari edisi hacker tahun lalu, jadi kami berharap bahwa banyak dari Anda mencobanya.
Tahun lalu itu sangat luar biasa.
>> [CS50.TV]