>> [MUSIC PLAYING]
DAVID Malan: Baiklah.
Baiklah, selamat datang kembali.
Jadi ini Minggu 4, awal daripadanya, sudah.
Dan Anda akan ingat bahwa minggu lalu, kami menempatkan kode disisihkan untuk hanya sedikit
dan kami mulai berbicara lebih sedikit tingkat tinggi, hal-hal seperti
pencarian dan menyortir, yang meskipun ide yang agak sederhana, yang
perwakilan dari kelas masalah Anda akan mulai untuk memecahkan khususnya
setelah Anda mulai berpikir tentang akhir proyek dan solusi yang menarik Anda
mungkin harus masalah di dunia nyata.
Sekarang bubble sort adalah salah satu yang paling sederhana algoritma tersebut, dan
bekerja dengan memiliki angka-angka kecil dalam daftar atau dalam bentuk array
gelembung jalan mereka ke atas, dan jumlah besar bergerak dengan cara mereka ke
akhir daftar itu.
>> Dan ingat bahwa kita bisa membayangkan bubble sort sedikit
sesuatu seperti ini.
Jadi biarkan aku pergi ke depan dan klik Start.
Aku sudah dipilih sebelumnya bubble sort.
Dan jika Anda ingat bahwa tinggi biru garis mewakili angka yang besar, kecil
garis biru mewakili angka kecil, seperti kita melalui ini lagi dan lagi dan
lagi, membandingkan dua bar sebelah setiap lainnya dalam warna merah, kita akan menukar
terbesar dan terkecil jika mereka rusak.
>> Jadi ini akan terus dan terus dan pergi , dan Anda akan melihat bahwa semakin besar
elemen yang membuat jalan mereka ke kanan, dan unsur-unsur yang lebih kecil
membuat jalan mereka ke kiri.
Tapi kita mulai mengukur efisiensi, yang
kualitas algoritma ini.
Dan kita mengatakan bahwa yang terburuk kasus, algoritma ini mengambil
kira-kira berapa banyak langkah?
>> Jadi n kuadrat.
Dan apa n?
>> AUDIENCE: Jumlah elemen.
>> DAVID Malan: Jadi n adalah jumlah elemen.
Dan jadi kita akan melakukan hal ini sering.
Setiap kali kita ingin berbicara tentang ukuran dari masalah atau ukuran
masukan, atau jumlah waktu yang dibutuhkan untuk menghasilkan output, kita akan hanya
umum apapun input adalah sebagai n.
Jadi kembali pada Minggu 0, halaman nomor dalam buku telepon adalah n.
Jumlah mahasiswa di ruang n.
Jadi di sini, juga, kita mengikuti pola.
>> Sekarang n kuadrat tidak terlalu cepat, jadi kami mencoba untuk berbuat lebih baik.
Dan jadi kita melihat beberapa algoritma lain, di antaranya
adalah semacam seleksi.
Jadi semacam seleksi sedikit berbeda.
Itu hampir sederhana, saya berani mengatakan, dimana saya mulai pada awal
daftar relawan kami dan aku hanya lagi dan lagi dan lagi pergi melalui
daftar, mencabut terkecil elemen pada suatu waktu dan menempatkan dia atau
nya di awal daftar.
>> Tapi ini juga, sekali kita mulai berpikir melalui matematika dan lebih besar
gambar, berpikir tentang berapa kali Aku akan bolak-balik dan kembali
dan sebagainya, kami mengatakan dalam kasus terburuk, selection sort, juga, adalah apa?
n kuadrat.
Sekarang di dunia nyata, itu mungkin benar-benar menjadi sedikit lebih cepat.
Karena sekali lagi, saya tidak harus menjaga backtracking setelah saya telah mengurutkan
terkecil unsur.
Tetapi jika kita berpikir tentang n sangat besar, dan jika Anda melakukan semacam keluar matematika sebagai
Saya lakukan pada papan, dengan n kuadrat dikurangi sesuatu, segala sesuatu yang lain
selain n kuadrat, setelah n akan benar-benar besar, tidak
benar-benar peduli sebanyak.
Jadi sebagai ilmuwan komputer, kita semacam menutup mata untuk yang lebih kecil
faktor dan fokus hanya pada faktor dalam ekspresi yang akan membuat
perbedaan terbesar.
>> Nah, terakhir, kita melihat pada insertion sort.
Dan ini adalah serupa dalam roh, tetapi daripada pergi melalui iteratif dan
pilih elemen terkecil pada waktu, saya malah mengambil tangan saya
ditangani, dan saya memutuskan, semua benar, Anda berada di sini.
Kemudian saya pindah ke elemen berikutnya dan memutuskan bahwa ia atau
dia berada di sini.
Dan kemudian aku pindah dan terus.
Dan saya mungkin untuk, sepanjang jalan, menggeser orang-orang untuk
membuat ruang bagi mereka.
Jadi itu semacam pembalikan jiwa semacam seleksi yang kita
disebut insertion sort.
>> Jadi topik ini terjadi di dunia nyata.
Hanya beberapa tahun yang lalu, ketika tertentu senator mencalonkan diri sebagai presiden,
Eric Schmidt, pada saat CEO Google, benar-benar memiliki kesempatan
mewawancarainya.
Dan kami pikir kami akan berbagi YouTube ini klip untuk Anda di sini, jika kita bisa muncul
volume.
>> [VIDEO PEMUTARAN]
>> -Sekarang, Senator, kau di sini di Google, dan saya suka berpikir tentang presiden
sebagai wawancara kerja.
>> [Tertawa]
>> -Sekarang sulit untuk mendapatkan pekerjaan sebagai presiden.
Dan Anda akan melalui kerasnya sekarang.
Ini juga sulit untuk mendapatkan pekerjaan di Google.
Kami memiliki pertanyaan dan kami meminta kami pertanyaan kandidat.
Dan yang satu ini dari Larry Schwimmer.
>> [Tertawa]
-Kalian pikir aku bercanda?
Ada di sini.
Apa cara yang paling efisien untuk mengurutkan bilangan bulat dua juta-bit?
>> [Tertawa]
>> -Well, uh -
>> -Maafkan aku.
Mungkin kita harus -
>> -Tidak, tidak, tidak, tidak, tidak.
>> -Itu bukan -
OK.
>> -Saya pikir semacam gelembung akan menjadi cara yang salah untuk pergi.
>> [Tertawa]
>> [Bersorak DAN Tepuk Tangan]
>> -Ayolah, yang mengatakan kepadanya ini?
OK.
>> [END VIDEO PEMUTARAN]
>> DAVID Malan: Jadi di sana Anda memilikinya.
Jadi kita mulai untuk mengukur ini berjalan kali, sehingga untuk berbicara, dengan sesuatu
disebut notasi asimtotik, yang hanya mengacu semacam kami untuk mengubah
mata terhadap faktor-faktor yang lebih kecil dan hanya melihat pada saat berjalan,
kinerja algoritma ini, sebagai n jadi sangat besar dari waktu ke waktu.
Dan jadi kami memperkenalkan big O. Dan O besar mewakili sesuatu yang kita pikir
sebagai batas atas.
Dan sebenarnya, Barry, bisa kita menurunkan dari mic sedikit?
>> Kami pikir ini adalah batas atas.
O begitu besar dari n berarti kuadrat bahwa dalam kasus terburuk, sesuatu seperti
selection sort akan mengambil n langkah kuadrat.
Atau sesuatu seperti insertion sort akan n langkah kuadrat.
Sekarang untuk sesuatu seperti penyisipan semacam, apa kasus terburuk?
Mengingat sebuah array, apa hal terburuk skenario yang mungkin bahwa Anda mungkin menemukan
diri Anda dihadapkan dengan?
>> Ini benar-benar mundur, kan?
Karena jika itu benar-benar mundur, Anda harus melakukan banyak pekerjaan.
Karena jika Anda benar-benar mundur, Anda akan menemukan
elemen terbesar di sini, meskipun itu milik sana.
Jadi Anda akan mengatakan, oke, pada saat ini dalam waktu, Anda berada di sini,
sehingga Anda biarkan saja.
>> Lalu Anda menyadari, oh, sialan, aku harus memindahkan elemen sedikit lebih kecil untuk
di sebelah kiri Anda.
Lalu aku harus melakukannya lagi dan lagi dan lagi.
Dan jika aku berjalan bolak-balik, Anda akan semacam merasa kinerja
algoritma itu, karena terus aku menyeret orang lain ke dalam
array untuk membuat ruang untuk itu.
Jadi itulah kasus terburuk.
>> Sebaliknya -
dan ini adalah Cliffhanger terakhir kali -
kita mengatakan bahwa insertion sort adalah omega apa?
Apa menjalankan kasus terbaik waktu insertion sort?
Jadi itu benar-benar n.
Itu adalah kosong yang kami meninggalkan di papan terakhir kali.
>> Dan itu omega n karena mengapa?
Nah, dalam kasus terbaik, apa insertion sort akan diserahkan?
Nah, daftar yang benar-benar diurutkan sudah, pekerjaan minimal yang dapat dilakukan.
Tapi apa yang rapi tentang insertion sort adalah bahwa karena itu dimulai di sini dan
memutuskan, oh, Anda adalah nomor satu, Anda berada di sini.
Oh, apa keberuntungan.
>> Kau nomor dua.
Anda juga termasuk di sini.
Nomor tiga, bahkan lebih baik, Anda berada di sini.
Begitu sampai ke ujung pseudocode daftar, per insertion sort ini
bahwa kami berjalan melalui lisan terakhir kali, hal itu dilakukan.
Tapi semacam seleksi, sebaliknya, terus melakukan apa?
>> Terus melalui daftar lagi dan lagi dan lagi.
Karena wawasan kunci hanya ada setelah Anda telah melihat semua jalan ke
akhir daftar Anda bisa yakin bahwa elemen yang Anda pilih adalah
memang elemen terkecil saat ini.
Jadi ini berbeda mental yang model akhir sampai menghasilkan beberapa dunia nyata sangat
perbedaan bagi kami, serta ini teoritis perbedaan asimtotik.
>> Jadi hanya untuk rekap, maka, O besar n kuadrat, kami telah melihat beberapa seperti
algoritma sejauh ini.
Big O n?
Apakah yang dimaksud dengan algoritma yang bisa dikatakan O besar n?
Dalam kasus terburuk, dibutuhkan sejumlah linear langkah.
>> OK, pencarian linear.
Dan dalam kasus terburuk, di mana elemen yang Anda cari ketika
menerapkan pencarian linear?
>> OK, dalam kasus terburuk, itu bahkan tidak ada.
Atau dalam kasus terburuk kedua, itu sepanjang jalan pada akhirnya, yang
plus atau minus perbedaan satu langkah.
Jadi pada akhir hari, kita dapat mengatakan itu linear.
Big O n akan pencarian linear, karena dalam kasus terburuk,
elemen bahkan tidak ada atau itu semua jalan di ujung.
>> Nah, O besar log n.
Kami tidak berbicara dengan sangat rinci tentang ini, tapi kami sudah melihat ini sebelumnya.
Apa yang berjalan dalam apa yang disebut logaritmik waktu, dalam kasus terburuk?
>> Ya, pencarian agar biner.
Dan pencarian biner dalam kasus terburuk mungkin memiliki elemen di suatu tempat di
tengah, atau di suatu tempat dalam array.
Tapi Anda hanya menemukannya sekali Anda membagi daftar dua, di
setengah, setengah, setengah.
Dan kemudian voila, itu ada.
Atau lagi, kasus terburuk, itu bahkan tidak ada.
Tapi Anda tidak tahu bahwa itu tidak ada sampai Anda mencapai semacam yang lalu
paling bawah elemen dengan mengurangi separuh dan mengurangi separuh dan pemangkasan.
>> Big O dari 1.
Jadi kita bisa O besar 2, O besar dari 3.
Setiap kali Anda ingin hanya nomor konstan, kita hanya semacam hanya menyederhanakan
bahwa O besar 1.
Meskipun jika realistis, dibutuhkan 2 atau bahkan 100 langkah, jika itu adalah
jumlah konstan langkah, kita hanya mengatakan O besar 1.
Apakah yang dimaksud dengan algoritma yang di O besar dari 1?
>> AUDIENCE: Menemukan panjang dari variabel.
>> DAVID Malan: Menemukan panjang variabel?
>> AUDIENCE: Tidak, panjang jika sudah diurutkan.
>> DAVID Malan: Baik.
OK, sehingga menemukan sesuatu yang panjang jika panjang sesuatu yang, seperti
array, disimpan dalam beberapa variabel.
Karena Anda hanya dapat membaca variabel, atau mencetak variabel, atau
umumnya hanya mengakses variabel tersebut.
Dan voila, yang membutuhkan waktu konstan.
>> Sebaliknya, pikirkan kembali untuk menggaruk.
Pikirkan kembali ke minggu pertama C, menelepon hanya printf dan pencetakan
sesuatu di layar ini bisa dibilang waktu yang konstan, karena hanya membutuhkan
beberapa jumlah siklus CPU untuk menunjukkan bahwa teks pada layar.
Atau menunggu - apakah itu?
Bagaimana lagi kita mungkin model kinerja printf?
Apakah seseorang ingin setuju, bahwa mungkin itu bukan waktu yang sangat konstan?
Dalam arti mungkin printf yang berjalan waktu, benar-benar mencetak string pada
layar, menjadi sesuatu selain konstan.
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Ya.
Jadi itu tergantung pada perspektif kita.
Jika kita benar-benar berpikir dari input ke printf sebagai string, dan
karena itu kami mengukur ukuran yang input dengan panjang - jadi mari kita sebut
bahwa panjang n juga -
bisa dibilang, printf itu sendiri O besar n karena itu akan membawa Anda langkah n
untuk mencetak masing-masing n karakter, yang paling mungkin.
Setidaknya sejauh yang kita asumsikan bahwa mungkin itu menggunakan untuk loop
bawah tenda.
>> Tapi kita harus lihat itu kode untuk memahami dengan lebih baik.
Dan memang, setelah kalian mulai menganalisis algoritma Anda sendiri, Anda akan
harfiah melakukan hal itu.
Urutkan bola mata kode Anda dan berpikir tentang - baik-baik saja, saya punya lingkaran ini
sini atau saya memiliki loop bersarang di sini, yang akan melakukan hal-hal n n kali,
dan Anda dapat semacam alasan cara Anda melalui kode, bahkan jika itu
pseudocode dan bukan kode yang sebenarnya.
>> Jadi apa tentang omega kuadrat dari n?
Apa algoritma yang dalam terbaik kasus, masih mengambil langkah n kuadrat?
Ya?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Jadi pemilihan jenis.
Karena dalam masalah yang benar-benar berkurang dengan fakta itu lagi, saya tidak tahu
Saya telah menemukan terkecil saat ini sampai Aku sudah memeriksa semua elemen sialan.
Jadi omega, katakanlah, n, kita hanya datang dengan satu.
Insertion sort.
Jika daftar kebetulan diurutkan sudah, dalam kasus terbaik kita hanya
untuk membuat satu lulus melalui itu, di mana titik kami yakin.
Dan kemudian yang bisa dikatakan harus linier, pasti.
>> Bagaimana omega dari 1?
Apa, dalam kasus terbaik, mungkin mengambil sejumlah konstan langkah?
Jadi pencarian linear, jika Anda hanya beruntung dan unsur yang Anda cari
tepat di awal daftar, kalau itu di mana Anda memulai Anda
linear traversal dari daftar itu.
>> Dan ini benar dari beberapa hal.
Sebagai contoh, bahkan biner pencarian omega dari 1.
Karena apa jika Anda mendapatkan benar-benar sangat beruntung dan memukul-oleskan di tengah
array adalah nomor Anda sedang mencari?
Jadi Anda bisa mendapatkan beruntung di sana, juga.
>> Yang satu ini, terakhir, omega n log n.
Jadi n log n, kita tidak benar-benar berbicara tentang, tapi -
>> AUDIENCE: Merge sort?
>> DAVID Malan: Merge sort.
Itu cliffhanger dari terakhir kali, di mana kita mengusulkan, dan kami menunjukkan
visual, bahwa ada algoritma.
Dan menggabungkan semacam hanya satu seperti algoritma yang secara fundamental lebih cepat
dari beberapa orang-orang lainnya.
Bahkan, menggabungkan pendek tidak hanya di kasus terbaik n log n, di terburuk
kasus n log n.
Dan ketika Anda memiliki kebetulan ini omega dan O besar menjadi hal yang sama?
Kami benar-benar bisa menggambarkan bahwa apa yang disebut theta, meskipun itu adalah
sedikit kurang umum.
Tapi itu hanya berarti dua batas, dalam hal ini, adalah sama.
>> Jadi menggabungkan semacam, apa ini benar-benar mendidih ke bagi kita?
Nah, mengingat motivasi.
Biarkan aku menarik animasi lain yang kita tidak melihat terakhir kali.
Yang satu ini, ide yang sama, tetapi itu sedikit lebih besar.
Dan aku akan pergi ke depan dan menunjukkan pertama - kami memiliki insertion sort pada
kiri atas, maka pemilihan semacam, bubble sort, beberapa jenis lain -
shell dan cepat - bahwa kita belum bicara tentang, dan tumpukan dan menggabungkan semacam.
>> Jadi setidaknya mencoba untuk fokus mata Anda pada tiga di sebelah kiri dan kemudian
menggabungkan semacam ketika saya klik ini panah hijau.
Tapi aku akan membiarkan semua dari mereka menjalankan, hanya untuk memberikan rasa keragaman
algoritma yang ada di dunia.
Aku akan membiarkan menjalankan ini hanya beberapa detik.
Dan jika Anda fokus mata Anda - memilih sebuah algoritma, fokus pada itu untuk hanya
detik - Anda akan mulai melihat pola yang itu menerapkan.
>> Merge sort, pemberitahuan, dilakukan.
Heap sort, quick sort, shell -
jadi sepertinya kami memperkenalkan tiga algoritma terburuk pekan lalu.
Tapi itu baik bahwa kita di sini hari ini untuk melihat merge sort, yang merupakan salah satu
yang lebih mudah adalah dengan melihat, bahkan meskipun mungkin akan menekuk pikiran Anda
hanya sedikit.
Di sini kita bisa melihat betapa selection sort menyebalkan.
>> Tapi di sisi lain, itu sangat mudah untuk menerapkan.
Dan mungkin untuk P Set 3, itulah salah satu algoritma Anda memilih untuk mengimplementasikan
untuk edisi standar.
Baik-baik saja, sempurna benar.
>> Tapi sekali lagi, seperti n mendapat besar, jika Anda memilih untuk menerapkan algoritma yang lebih cepat
seperti menggabungkan semacam, kemungkinan besar dalam yang lebih besar dan input yang lebih besar, kode Anda hanya
akan berjalan lebih cepat.
Website Anda akan bekerja lebih baik.
Pengguna Anda akan lebih bahagia.
Dan jadi ada efek ini untuk benar-benar memberikan
kami beberapa berpikir lebih dalam.
>> Jadi mari kita lihat apa yang menggabungkan semacam sebenarnya semua tentang.
Yang keren adalah bahwa menggabungkan semacam ini hanya ini.
Ini, sekali lagi, apa yang telah kita disebut pseudocode, makhluk pseudocode
Inggris-seperti sintaks.
Dan kesederhanaan adalah semacam menarik.
>> Jadi pada masukan dari n elemen - sehingga hanya berarti, inilah sebuah array.
Itu punya hal-hal n di dalamnya.
Itu semua kita mengatakan ada.
>> Jika n kurang dari 2, kembali.
Jadi itu hanya kasus sepele.
Jika n kurang dari 2, maka jelas itu 1 atau 0, dalam hal hal
sudah diurutkan atau tidak ada, jadi hanya kembali.
Tidak ada yang dapat dilakukan.
Jadi itu kasus sederhana untuk merobek.
>> Lain, kita memiliki tiga langkah.
Urutkan kiri setengah dari elemen, semacam bagian kanan elemen,
dan kemudian menggabungkan bagian diurutkan.
Apa yang menarik di sini adalah bahwa Aku agak punting, kan?
Ada semacam definisi melingkar algoritma ini.
Dalam arti apakah algoritma ini melingkar definisi?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Ya, algoritma sorting saya, dua langkah perusahaan adalah "semacam
sesuatu. "Dan sehingga menimbulkan pertanyaan, baik, apa yang akan saya gunakan
untuk menyortir kiri setengah dan bagian kanan?
Dan keindahan di sini adalah bahwa meskipun lagi, ini adalah pikiran-lipatan
Bagian berpotensi, Anda dapat menggunakan yang sama algoritma untuk mengurutkan kiri setengah.
>> Tapi tunggu sebentar.
Ketika Anda diminta untuk mengurutkan kiri setengah, apa dua
langkah akan selanjutnya?
Kita akan mengurutkan kiri setengah dari setengah kiri dan kanan
setengah dari kiri setengah.
Sialan, bagaimana cara saya mengurutkan dua bagian, atau tempat, sekarang?
>> Tapi itu OK.
Kami memiliki algoritma sorting sini.
Dan meskipun Anda mungkin khawatir pada pertama ini adalah jenis tak terbatas
lingkaran, itu adalah siklus yang tidak pernah akan berakhir - itu akan
berakhir setelah apa yang terjadi?
Setelah n kurang dari 2.
Yang akhirnya akan terjadi, karena jika Anda terus mengurangi separuh dan
mengurangi separuh mengurangi separuh bagian ini, pasti akhirnya Anda akan berakhir
dengan hanya 1 atau 0 elemen.
Pada saat itu, algoritma ini mengatakan Anda sudah selesai.
>> Jadi sihir yang nyata dalam hal ini algoritma tampaknya berada di
langkah terakhir, penggabungan.
Itu ide yang sederhana hanya penggabungan dua hal, itulah yang akhirnya akan
untuk memungkinkan kita untuk mengurutkan array, katakanlah, delapan elemen.
Jadi saya memiliki delapan bola stres lebih up di sini, delapan lembar kertas, dan satu
Google Kaca -
yang saya bisa tetap.
>> [Tertawa]
>> DAVID Malan: Jika kita bisa mengambil delapan relawan, dan mari kita lihat apakah kita bisa
memainkan permainan ini keluar, jadi.
Wow, OK.
Ilmu komputer semakin menyenangkan.
Baik.
Jadi bagaimana dengan Anda tiga, tangan terbesar di sana.
Empat di belakang.
Dan bagaimana kita akan melakukannya Anda tiga berturut-turut ini?
Dan empat di depan.
Jadi Anda delapan, datang ke atas.
>> [Tertawa]
>> DAVID Malan: Aku sebenarnya tidak yakin apa itu.
Apakah bola stres?
Lampu meja?
Materi?
Internet?
>> OK.
Jadi datang ke atas.
Siapa yang mau -
terus datang.
Mari kita lihat.
Dan ini menempatkan Anda di lokasi -
Anda berada di satu lokasi.
Uh-oh, tunggu dulu.
1, 2, 3, 4, 5, 6, 7 - oh, baik.
Baiklah, kita baik.
Baiklah, sehingga semua orang memiliki kursi, tapi tidak pada Google Glass.
Biarkan aku mengantri tersebut.
Siapa nama Anda?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Baiklah, Anda bisa terlihat seperti geek, kalau itu OK.
Yah, saya lakukan juga, saya kira, untuk sesaat.
Baiklah, standby.
Kami sudah mencoba untuk datang dengan menggunakan kasus untuk Google Glass, dan kami
pikir akan menyenangkan untuk hanya melakukan ini ketika orang-orang di atas panggung.
Kami akan merekam dunia dari sudut pandang mereka.
Baik.
Tidak mungkin apa yang dimaksudkan Google.
Baiklah, jika Anda tidak keberatan memakai ini untuk menit berikutnya canggung,
itu akan menjadi indah.
>> Baiklah, sehingga kita memiliki sebuah array elemen, dan bahwa array, sesuai dengan
potongan kertas di orang-orang ini ' tangan, saat ini dipilah.
>> MICHELLE: Oh, itu kan aneh.
>> DAVID Malan: Ini cukup banyak acak.
Dan hanya dalam beberapa saat, kita akan mencoba untuk melaksanakan menggabungkan semacam bersama-sama
dan melihat mana yang Patut diketahui.
Dan trik di sini dengan merge sort adalah sesuatu yang kita belum dianggap belum.
Kami benar-benar membutuhkan beberapa ruang tambahan.
Jadi apa yang akan menjadi sangat menarik tentang ini adalah bahwa
orang ini akan bergerak di sekitar sedikit bit, karena aku akan berasumsi bahwa
ada sebuah array tambahan ruang, mengatakan, tepat di belakang mereka.
>> Jadi, jika mereka berada di belakang kursi mereka, itu array sekunder.
Jika mereka duduk di sini, itu array primer.
Tapi ini adalah sumber daya yang kita miliki tidak memanfaatkan sejauh ini dengan gelembung
semacam, dengan semacam seleksi, dengan insertion sort.
Ingat minggu lalu, semua orang hanya jenis beringsut di tempat.
Mereka tidak menggunakan memori tambahan.
Kami membuat ruang untuk orang-orang dengan memindahkan orang.
>> Jadi ini adalah wawasan kunci, terlalu.
Ada trade-off ini, secara umum dalam ilmu komputer, sumber daya.
Jika Anda ingin mempercepat sesuatu seperti waktu, Anda akan
harus membayar harga.
Dan salah satu harga tersebut sangat sering ruang, jumlah memori atau hard
ruang disk yang Anda gunakan.
Atau, terus terang, jumlah waktu programmer.
Berapa banyak waktu yang diperlukan, manusia, untuk benar-benar menerapkan lagi
algoritma rumit.
Tapi untuk hari ini, trade-off adalah waktu dan ruang.
>> Jadi, jika kalian hanya bisa menahan Anda angka sehingga kita dapat melihat bahwa Anda
memang pencocokan 4, 2, 6, 1, 3, 7, 8.
Luar biasa.
Jadi aku akan mencoba untuk mengatur hal, jika kalian bisa hanya
mengikuti langkah saya di sini.
>> Jadi saya akan mengimplementasikan, pertama, Langkah pertama pseudocode, yang merupakan
pada masukan dari n elemen, jika n kurang dari 2, kemudian kembali.
Jelas, yang tidak berlaku, jadi kami pindah.
Jadi mengurutkan kiri setengah dari elemen.
Jadi itu berarti aku akan fokus saya perhatian untuk hanya sejenak di ini
empat orang di sini.
Baiklah, apa yang harus saya lakukan selanjutnya?
>> AUDIENCE: Urutkan kiri setengah.
>> DAVID Malan: Jadi sekarang saya harus mengurutkan kiri setengah dari orang-orang ini.
Karena sekali lagi, berasumsi untuk diri sendiri Tujuannya adalah untuk memilah kiri setengah.
Bagaimana Anda melakukannya?
Cukup ikuti petunjuk, bahkan meskipun kita melakukannya lagi.
Jadi mengurutkan kiri setengah.
Sekarang aku menyortir dua orang.
Apa yang terjadi selanjutnya?
>> AUDIENCE: Urutkan kiri setengah.
>> DAVID Malan: Urutkan kiri setengah.
Jadi sekarang ini, kursi ini di sini, adalah daftar ukuran 1.
Dan siapa namamu lagi?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID Malan: Princess Daisy di sini.
Dan jadi dia sudah disortir, karena daftar adalah ukuran 1.
Apa yang harus saya lakukan selanjutnya?
OK, kembali, karena daftar itu adalah ukuran 1, yaitu kurang dari 2.
Lalu apa langkah selanjutnya?
Dan sekarang Anda harus jenis mundur dalam pikiran Anda.
>> Urutkan bagian kanan, yang -
siapa namamu?
>> LINDA: Linda.
>> DAVID Malan: Linda.
Dan apa yang kita lakukan sekarang kami memiliki daftar ukuran 1?
>> AUDIENCE: Kembali.
>> DAVID Malan: Hati-hati.
Kita kembali dulu, dan sekarang ketiga langkah - dan jika aku agak menggambarkan dengan
merangkul dua kursi sekarang, sekarang saya harus menggabungkan kedua elemen.
Jadi sekarang sayangnya, elemen yang rusak.
Tapi di situlah proses penggabungan mulai mendapatkan menarik.
>> Jadi, jika kalian bisa berdiri untuk hanya Sesaat, aku akan membutuhkan Anda, dalam
saat, untuk melangkah di belakang kursi Anda.
Dan jika Linda, karena 2 adalah lebih kecil dari 4, kenapa tidak
Anda datang sekitar pertama?
Tinggal di sana.
Jadi Linda, Anda datang sekitar pertama.
>> Sekarang pada kenyataannya jika itu hanya sebuah array kita hanya bisa memindahkannya secara real time
dari kursi ini ke tempat ini.
Jadi bayangkan jika mengambil beberapa konstanta jumlah langkah 1.
Dan sekarang -
tetapi kita perlu menempatkan Anda dalam lokasi pertama di sini.
>> Dan sekarang jika Anda bisa datang, juga, kita akan
berada di lokasi dua.
Dan meskipun ini terasa seperti itu mengambil beberapa saat, apa yang bagus saat ini adalah
bahwa kiri setengah dari kiri setengah sekarang diurutkan.
Jadi apa langkah berikutnya, jika kita sekarang mundur lebih jauh dalam cerita itu?
>> AUDIENCE: setengah Kanan.
>> DAVID Malan: Urutkan kanan setengah.
Jadi kalian harus melakukan ini, juga.
Jadi, jika Anda bisa berdiri untuk sesaat?
Dan siapa namamu?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, jadi Jess sekarang kiri setengah dari setengah benar.
Dan jadi dia daftar ukuran 1.
Dia jelas diurutkan.
Dan nama Anda lagi?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle jelas daftar ukuran 1.
Dia sudah diurutkan.
Jadi sekarang keajaiban terjadi, proses penggabungan.
Jadi siapa yang akan datang pertama?
Jelas Michelle.
Jadi, jika Anda bisa datang sekitar kembali.
Ruang yang kita miliki untuk sekarang tepat di belakang kursi ini di sini.
Dan sekarang jika Anda bisa kembali juga, kita sekarang memiliki, harus jelas, dua
bagian, masing-masing ukuran 2 -
dan hanya untuk kepentingan penggambaran itu, jika Anda bisa membuat sedikit ruang -
satu kiri setengah di sini, satu setengah di sini.
>> Rewind lanjut dalam cerita.
Apa langkah selanjutnya?
>> AUDIENCE: Gabung.
>> DAVID Malan: Jadi sekarang kita harus bergabung.
Jadi OK, jadi sekarang, untungnya, kami hanya membebaskan empat kursi.
Jadi kita telah menggunakan dua kali lebih banyak memori, tetapi kami dapat memberikan flip-menjatuhkan diri antara
dua array.
Jadi nomor yang akan datang pertama?
Jadi Michelle, jelas.
Jadi datang dan mengambil duduk di sini.
Dan kemudian nomor 2 jelas selanjutnya, sehingga Anda datang ke sini.
Nomor 4, nomor 6.
Dan lagi, meskipun ada sedikit berjalan terlibat,
benar-benar, ini bisa terjadi secara instan, dengan memindahkan satu -
OK, baik dimainkan.
>> [Tertawa]
>> DAVID Malan: Dan sekarang kita dalam kondisi yang cukup baik.
Kiri setengah dari seluruh masukan sekarang telah diurutkan.
Baiklah, jadi orang-orang ini memiliki keuntungan dari saya -
bagaimana itu berakhir semua gadis di kiri dan semua anak laki-laki di sebelah kanan?
>> OK, jadi orang-orang 'berbalik sekarang.
Jadi saya tidak akan memandu Anda melalui langkah-langkah ini.
Kita akan melihat apakah kita dapat mengajukan permohonan kembali pseudocode yang sama.
Jika Anda ingin untuk terus maju dan berdiri, dan kalian, biarlah saya memberikan mic.
Lihat jika Anda tidak bisa meniru apa yang kita hanya lakukan di sini pada
ujung daftar.
Siapa yang perlu berbicara pertama, berdasarkan algoritma?
Jadi menjelaskan apa yang Anda lakukan sebelum Anda membuat gerakan kaki.
>> SPEAKER 1: Baiklah, jadi karena Saya kiri setengah dari
kiri setengah, aku kembali.
Benar?
>> DAVID Malan: Baik.
>> SPEAKER 1: Dan kemudian -
>> DAVID Malan: Siapa yang mic pergi ke depan?
>> SPEAKER 1: nomor berikutnya.
>> SPEAKER 2: Jadi saya bagian kanan dari kiri setengah dari
kiri setengah, dan aku kembali.
>> DAVID Malan: Baik.
Anda kembali.
Jadi sekarang apa di samping untuk kalian berdua?
>> SPEAKER 2: Kami ingin melihat siapa yang lebih kecil.
>> DAVID Malan: Tepat.
Kami ingin menggabungkan.
Ruang kita akan gunakan untuk menggabungkan Anda ke dalam, meskipun mereka
jelas diurutkan sudah, kita akan untuk mengikuti algoritma yang sama.
Jadi yang pergi di belakang pertama?
Jadi 3, dan kemudian 7.
Dan sekarang mic berjalan orang-orang ini, OK?
>> SPEAKER 3: Jadi aku setengah kanan kiri setengah, dan n saya kurang dari
1, jadi aku hanya akan lulus -
>> DAVID Malan: Baik.
>> SPEAKER 4: Aku kanan setengah dari bagian kanan bagian kanan, dan aku
juga salah satu orang, jadi aku akan kembali.
Jadi sekarang kita menggabungkan.
>> SPEAKER 3: Jadi kita kembali.
>> DAVID Malan: Jadi Anda pergi ke belakang.
Jadi 5 pergi dulu, kemudian 8.
Dan sekarang penonton, yang merupakan langkah kita harus mundur sekarang
kembali ke dalam pikiran kita?
>> AUDIENCE: Gabung.
>> DAVID Malan: Penggabungan setengah kiri dan kanan setengah dari kiri setengah asli.
Jadi sekarang -
dan hanya untuk membuat ini jelas, membuat sedikit ruang
antara Anda dua orang.
Jadi sekarang itu dua daftar, kiri dan kanan.
Jadi bagaimana kita sekarang menggabungkan kalian ke barisan depan kursi lagi?
>> 3 pergi dulu.
Kemudian 5, jelas.
Kemudian 7, dan sekarang 8.
OK, dan sekarang kita?
>> AUDIENCE: Tidak dilakukan.
>> DAVID Malan: Tidak dilakukan, karena jelas, ada satu langkah yang tersisa.
Tapi sekali lagi, alasan saya menggunakan ini jargon seperti "mundur dalam pikiran Anda,"
itu karena itu benar-benar apa yang terjadi.
Kita akan melalui semua langkah ini, tapi kami semacam berhenti untuk
saat, menyelam lebih dalam algoritma, berhenti sejenak,
menyelam lebih dalam algoritma, dan sekarang kita harus semacam mundur dalam kami
pikiran dan membatalkan semua lapisan ini bahwa kita sudah semacam ditahan.
>> Jadi sekarang kita memiliki dua daftar ukuran 4.
Jika kalian bisa berdiri untuk terakhir kalinya dan membuat sedikit ruang di sini untuk
membuat jelas bahwa ini adalah kiri setengah dari aslinya,
kanan setengah dari aslinya.
Siapa angka pertama yang kita perlu untuk menarik ke belakang?
Michelle, tentu saja.
>> Jadi kita menempatkan Michelle sini.
Dan siapa yang memiliki nomor 2?
Nomor 2 datang pada kembali juga.
Nomor 3?
Luar biasa.
Angka 4, angka 5, angka 6, nomor 7, dan nomor 8.
>> OK, jadi rasanya seperti banyak langkah-langkah, pasti.
Tapi sekarang mari kita lihat apakah kita tidak dapat mengkonfirmasi semacam intuitif bahwa ini
algoritma fundamental, terutama karena n jadi sangat besar, seperti yang kita lihat
dengan animasi, adalah fundamental lebih cepat.
Jadi saya mengklaim algoritma ini, yang terburuk kasus dan bahkan dalam kasus terbaik,
adalah O besar n kali log n.
Artinya, ada beberapa aspek ini algoritma yang mengambil n langkah, tetapi
ada aspek lain di suatu tempat di bahwa iterasi, perulangan itu, yang
mengambil log n langkah.
Dapatkah kita menempatkan jari kita pada apa yang mereka dua nomor maksud?
Nah, di mana -
mana 'd mic pergi?
>> SPEAKER 1: Apakah log n menjadi melanggar kita menjadi dua -
membaginya dengan dua, pada dasarnya.
>> DAVID Malan: Tepat.
Setiap kali kita melihat dalam algoritma sehingga Sejauh ini, sudah ada pola
membagi, membagi, membagi.
Dan itu biasanya berkurang untuk sesuatu yang
logaritmik, log basis 2.
Tapi itu benar-benar bisa menjadi apa pun, tapi log basis 2.
>> Sekarang bagaimana dengan n?
Saya dapat melihat bahwa kami jenis dibagi Anda guys - Anda dibagi, dibagi Anda,
Anda dibagi, dibagi Anda.
Dimana akhirnya datang?
>> Jadi penggabungan.
Karena berpikir tentang hal ini.
Ketika Anda menggabungkan delapan orang bersama-sama, dimana setengah dari mereka adalah satu set dari empat
dan setengah lainnya adalah lain set empat, bagaimana Anda pergi
tentang melakukan penggabungan?
Nah, kalian melakukannya cukup intuitif.
>> Tapi kalau aku malah melakukannya sedikit lebih metodis, aku mungkin telah menunjuk
orang paling kiri pertama dengan kiri saya tangan, menunjuk orang paling kiri
itu setengah dengan tangan kanan saya, dan hanya kemudian berjalan melalui
Daftar, menunjuk elemen terkecil setiap kali, menggerakkan jari saya di atas dan
lebih sesuai kebutuhan seluruh daftar.
Tapi apa kunci tentang penggabungan ini proses saya membandingkan pasangan ini
elemen.
Dari paruh kanan dan dari kiri setengah, aku tidak pernah backtracking.
>> Jadi penggabungan itu sendiri adalah mengambil tidak lebih dari n langkah.
Dan berapa kali aku memiliki untuk melakukan itu penggabungan?
Yah, tidak lebih dari n, dan kami hanya melihat bahwa dengan penggabungan akhir.
Dan jadi jika Anda melakukan sesuatu yang memerlukan log n langkah n kali, atau sebaliknya,
itu akan memberi kita n kali log n.
>> Dan mengapa ini lebih baik?
Nah, jika kita sudah tahu bahwa log n lebih baik daripada n - benar?
Kita telah melihat dalam pencarian biner, buku telepon Misalnya, log n pasti
lebih baik daripada linear.
Jadi itu berarti n kali log n adalah jelas lebih baik daripada yang lain n kali
n, AKA n kuadrat.
Dan itulah yang akhirnya kita rasakan.
>> Begitu besar putaran tepuk tangan, jika kita bisa, untuk orang-orang.
>> [Tepuk Tangan]
>> DAVID Malan: Dan hadiah perpisahan Anda - Anda dapat menyimpan nomor,
jika Anda ingin.
Dan hadiah perpisahan Anda, seperti biasa.
Oh, dan kami akan mengirimkan rekaman, Michelle.
Terima kasih.
Baik.
Membantu diri Anda sendiri untuk bola stres.
>> Dan biarkan aku berhenti, sementara itu, teman kita Rob Bowden untuk menawarkan
perspektif yang agak berbeda tentang hal ini, karena Anda dapat berpikir tentang ini
langkah-langkah yang terjadi dalam agak cara yang berbeda.
Bahkan, set-up untuk apa Rob tentang untuk menunjukkan kepada kita mengasumsikan bahwa kita sudah
sudah dilakukan sampai membagi dari daftar besar menjadi delapan daftar kecil,
masing-masing ukuran 1.
>> Jadi kami mengubah pseudocode a sedikit hanya untuk semacam mendapatkannya di
Ide inti cara kerja penggabungan.
Tapi waktu berjalan apa dia akan lakukan adalah masih
akan menjadi sama.
Dan lagi, set-up di sini adalah bahwa dia dimulai dengan delapan daftar ukuran 1.
Jadi, Anda telah melewatkan bagian di mana dia benar-benar melakukan log n, n log, log n
membagi input.
>> [VIDEO PEMUTARAN]
>> -Itu saja untuk langkah pertama.
Untuk langkah kedua, berulang kali menggabungkan pasang daftar.
>> DAVID Malan: Hm.
Hanya audio akan datang dari komputer saya.
Mari kita coba lagi.
>> -Hanya sewenang-wenang memilih mana - sekarang kita memiliki empat daftar.
Pelajari sebelumnya.
>> DAVID Malan: Di sana kami pergi.
>> Menggabung-108 dan 15, kita akhirnya dengan daftar 15, 108.
Menggabung 50 dan 4, kita berakhir dengan 4, 50.
Penggabungan 8 dan 42, kami berakhir dengan 8, 42.
Dan penggabungan 23 dan 16, kami berakhir dengan 16, 23.
>> Sekarang semua daftar kami adalah ukuran 2.
Perhatikan bahwa masing-masing empat daftar diurutkan.
Jadi kita bisa mulai menggabungkan pasang daftar lagi.
Menggabung 15 dan 108 dan 4 dan 50, kami pertama kita 4, maka 15, maka
50, maka 108.
Penggabungan 8, 42 dan 16, 23, pertama kita mengambil 8, maka 16, maka 23,
maka 42.
>> Jadi sekarang kita hanya memiliki dua daftar ukuran 4, masing-masing yang diurutkan.
Jadi sekarang kita menggabungkan kedua daftar.
Pertama, kita mengambil 4, maka kita mengambil 8, maka kita mengambil 15, kemudian 16, kemudian
23, kemudian 42, kemudian 50, kemudian 108.
>> [END VIDEO PEMUTARAN]
>> DAVID Malan: Sekali lagi, pemberitahuan, ia tidak pernah menyentuh secangkir diberikan lebih dari satu kali
setelah maju di luar itu.
Jadi dia tidak pernah mengulangi.
Jadi dia selalu bergerak ke samping, dan di situlah kami mendapat n kami.
>> Mengapa tidak membiarkan saya menarik satu animasi yang kita lihat sebelumnya, tapi kali ini
fokus hanya pada merge sort.
Biarkan aku pergi ke depan dan tampilannya dalam hal ini di sini.
Pertama biarkan saya memilih input acak, memperbesar ini, dan Anda dapat semacam melihat
apa yang kita mengambil untuk diberikan, sebelumnya, menggabungkan semacam benar-benar melakukan.
>> Jadi perhatikan bahwa Anda mendapatkan bagian ini atau ini atau kuartal ini perdelapan
Masalah yang tiba-tiba mulai mengambil bentuk yang baik.
Dan akhirnya, Anda lihat di akhir yang bam,
semuanya digabungkan.
>> Jadi ini hanya tiga yang berbeda mengambil ide yang sama.
Tapi wawasan kunci, seperti membagi dan menaklukkan di kelas pertama,
adalah bahwa kami memutuskan untuk entah bagaimana membagi masalah menjadi sesuatu yang besar, menjadi
sesuatu semacam identik dalam roh, tetapi lebih kecil dan lebih kecil dan lebih kecil
dan lebih kecil.
>> Sekarang lagi menyenangkan cara untuk semacam berpikir tentang ini, meskipun itu tidak
akan memberikan intuitif yang sama pemahaman, adalah
animasi berikut.
Jadi, ini adalah video seseorang menempatkan bersama-sama yang terkait berbeda
suara dengan berbagai operasi untuk insertion sort, untuk menggabungkan menyortir, dan
untuk beberapa orang lain.
Jadi suatu saat, aku akan memukul Play.
Ini sekitar satu menit yang panjang.
Dan meskipun Anda masih dapat melihat pola terjadi, kali ini Anda bisa
juga mendengar bagaimana algoritma ini tampil berbeda dan dengan
pola agak berbeda.
>> Ini adalah insertion sort.
>> [NADA BERMAIN]
>> DAVID Malan: Ini lagi mencoba untuk menyisipkan setiap elemen
ke tempatnya.
Ini adalah bubble sort.
>> [NADA BERMAIN]
>> DAVID Malan: Dan Anda dapat semacam merasa bagaimana relatif sedikit bekerja itu melakukan
pada setiap langkah.
Ini adalah apa yang terdengar seperti tediousness.
>> [NADA BERMAIN]
>> DAVID Malan: Ini adalah semacam seleksi, di mana kita memilih elemen yang kita inginkan dengan
akan melalui lagi dan lagi dan lagi dan meletakkannya di awal.
>> [NADA BERMAIN]
>> DAVID Malan: Ini adalah menggabungkan semacam, yang Anda benar-benar bisa mulai merasakan.
>> [NADA BERMAIN]
>> [Tertawa]
>> DAVID Malan: Sesuatu yang disebut gnome semacam, yang kita belum melihat.
>> [NADA BERMAIN]
>> DAVID Malan: Jadi biarkan aku lihat, sekarang, terganggu karena Anda mudah-mudahan adalah dengan
musik, jika aku bisa menyelipkan sedikit sedikit matematika di sini.
Jadi ada cara keempat yang kita bisa berpikir tentang apa artinya ini
fungsi menjadi lebih cepat dari yang yang pernah kita lihat sebelumnya.
Dan jika Anda datang di kursus dari latar belakang matematika, Anda
benar-benar tahu mungkin sudah Anda dapat menampar istilah di teknik ini -
yaitu rekursi, fungsi yang entah bagaimana menyebut dirinya.
>> Dan lagi, ingat bahwa merge sort pseudocode adalah rekursif dalam arti
bahwa salah satu langkah merge semacam ini adalah untuk memanggil sort -
yaitu, sendiri.
Tapi untungnya, karena kami terus memanggil macam, atau menggabungkan semacam,
khusus, pada kecil dan lebih kecil dan daftar yang lebih kecil, kita akhirnya
dipercaya keluar berkat apa yang akan kita sebut kasus dasar, kasus keras-kode yang
mengatakan jika daftar kecil, kurang dari 2 dalam kasus itu, hanya kembali segera.
Jika kita tidak memiliki kasus khusus, algoritma akan pernah keluar bawah,
dan Anda memang akan masuk ke sebuah infinite loop benar-benar selamanya.
>> Tapi misalkan kita ingin sekarang menempatkan beberapa nomor ini, sekali lagi, menggunakan n
sebagai ukuran input.
Dan saya ingin bertanya, apa total waktu yang terlibat dalam
menjalankan merge sort?
Atau lebih umum, apa biaya itu dalam waktu?
>> Yah itu cukup mudah untuk mengukur itu.
Jika n kurang dari 2, waktu yang terlibat dalam memilah n elemen,
dimana n adalah 2, adalah 0.
Karena kami hanya kembali.
Tidak ada pekerjaan yang harus dilakukan.
Sekarang bisa dibilang, mungkin itu salah satu langkah atau dua langkah-langkah untuk mengetahui jumlah
bekerja, tapi itu cukup dekat untuk 0 yang Aku hanya akan mengatakan tidak kerja
diperlukan jika daftar sangat kecil akan menarik.
>> Tapi kasus ini menarik.
Rekursif kasus ini adalah cabang dari pseudocode yang mengatakan lain, semacam
kiri setengah, mengurutkan kanan setengah, menggabungkan dua bagian.
Sekarang mengapa ungkapan ini merupakan biaya itu?
Nah, T n hanya berarti waktu untuk memilah elemen n.
Dan kemudian di sisi kanan dari tanda sama dengan di sana, T n dibagi
oleh 2 ini mengacu pada biaya apa?
Sorting kiri setengah.
T lain dari n dibagi 2 yaitu mungkin mengacu pada biaya
mengurutkan bagian kanan.
>> Dan kemudian ditambah n?
Adalah penggabungan.
Karena jika Anda memiliki dua daftar, satu dari berukuran n lebih dari 2 dan satu lagi berukuran n
lebih dari 2, Anda harus menyentuh dasarnya masing-masing elemen, seperti Rob
menyentuh setiap cangkir, dan hanya seperti kita menunjuk masing-masing
relawan di atas panggung.
Jadi n adalah biaya penggabungan.
>> Sekarang sayangnya, formula ini juga sendiri rekursif.
Jadi jika mengajukan pertanyaan, jika n adalah, katakanlah, 16, jika ada 16 orang di atas panggung
atau 16 cangkir dalam video, berapa banyak jumlah langkah yang diperlukan untuk mengurutkan mereka
dengan merge sort?
Ini sebenarnya bukan jawaban yang jelas, karena sekarang Anda harus semacam
rekursif menjawab formula ini.
>> Tapi itu OK, karena biar mengusulkan bahwa kita melakukan hal berikut.
Waktu yang terlibat untuk mengurutkan 16 orang atau 16 cangkir akan diwakili
umumnya sebagai T dari 16.
Tapi itu sama, menurut kami rumus sebelumnya, 2 kali jumlah
waktu yang diperlukan untuk menyortir 8 cangkir ditambah 16.
Dan lagi, ditambah 16 adalah waktu untuk bergabung, dan dua kali T dari 8 adalah
waktu untuk memilah kiri setengah dan setengah benar.
>> Tapi sekali lagi, ini tidak cukup.
Kita harus menyelam lebih dalam.
Ini berarti kita harus menjawab Pertanyaannya, apakah T dari 8?
Nah T dari 8 hanya 2 kali T dari 4 ditambah 8.
Nah, apa T dari 4?
T dari 4 hanya 2 kali dari T 2 ditambah 4.
Nah, apa T dari 2?
T 2 adalah hanya 2 kali dari T 1 ditambah 2.
>> Dan sekali lagi, kami tidak mendapatkan jenis terjebak dalam siklus ini.
Tapi itu akan memukul bahwa disebut kasus dasar.
Karena apa T dari 1, apakah kita mengklaim?
0.
Jadi sekarang akhirnya kita bisa bekerja mundur.
>> Jika T 1 adalah 0, sekarang saya bisa kembali naik satu berbaris dengan orang ini di sini, dan saya bisa
plug in 0 untuk T dari 1.
Jadi itu berarti itu sama dengan 2 kali nol, atau dikenal sebagai 0, ditambah 2.
Dan sehingga ekspresi keseluruhan adalah 2.
>> Sekarang jika saya mengambil T 2, yang jawabannya adalah 2, hubungkan ke garis tengah, T
4, yang memberi saya 2 kali 2 ditambah 4, jadi 8.
Jika saya kemudian pasang di 8 dengan sebelumnya line, yang memberikan saya 2 kali 8, 16.
Dan jika kita kemudian melanjutkan bahwa dengan 24, menambahkan dalam 16, akhirnya kami mendapatkan
nilai 64.
>> Sekarang bahwa dalam dan dari dirinya sendiri semacam berbicara ada notasi n, yang
big O, omega bahwa kita sudah telah berbicara tentang.
Tapi ternyata bahwa 64 memang 16, ukuran input,
log basis 2 dari 16.
Dan jika ini sedikit asing, hanya berpikir kembali, dan itu akan kembali
Anda akhirnya.
Jika ini adalah log basis 2, itu seperti 2 diangkat ke apa yang memberi Anda 16?
Oh, itu 4, jadi 16 kali 4.
>> Dan sekali lagi, ini bukan masalah besar jika hal ini adalah semacam memori kabur sekarang.
Tetapi untuk sekarang, mengambil iman bahwa 16 log 16 adalah 64.
Dan memang, dengan kewarasan sederhana memeriksa, kami telah dikonfirmasi -
tetapi tidak terbukti secara formal -
bahwa waktu berjalan dari merge semacam ini memang n log n.
>> Jadi tidak buruk.
Ini jelas lebih baik daripada algoritma yang telah kita lihat sejauh ini, dan
itu karena kami telah mempengaruhi, satu, teknik yang disebut rekursi.
Tapi yang lebih menarik dari itu, bahwa gagasan membagi dan menaklukkan.
Sekali lagi, benar-benar minggu 0 hal-hal yang bahkan sekarang berulang dalam
cara yang lebih menarik.
>> Sekarang sedikit latihan menyenangkan, jika Anda sudah pernah melakukan ini - dan Anda mungkin
tidak akan, karena semacam normal orang tidak berpikir untuk melakukan hal ini.
Tetapi jika aku pergi ke google.com dan jika Saya ingin belajar sesuatu tentang
rekursi, Enter.
>> [Tertawa]
[Tertawa MORE]
DAVID Malan: Bad joke perlahan-lahan menyebar.
[Tertawa]
DAVID Malan: Hanya dalam kasus, itu ada.
Aku tidak mengejanya salah, dan ada lelucon.
Baik.
Jelaskan kepada orang-orang di sebelah Anda jika belum cukup diklik dulu.
Tapi rekursi, lebih umum, mengacu dengan proses fungsi panggilan
sendiri, atau lebih umum, membagi masalah menjadi sesuatu yang dapat
dipecahkan sedikit demi sedikit dengan memecahkan identik masalah perwakilan.
>> Nah, mari kita ubah gigi untuk sesaat.
Kami ingin berakhir pada cliffhangers tertentu, jadi mari kita mulai untuk mengatur
panggung, selama beberapa menit, pada ide yang sangat sederhana -
bahwa swapping dua elemen, kan?
Semua algoritma ini kita sudah berbicara tentang masa lalu beberapa
kuliah melibatkan beberapa semacam swapping.
Hari itu divisualisasikan oleh mereka mendapatkan keluar dari kursi mereka dan
berjalan-jalan, tapi dalam kode, kita akan hanya mengambil sebuah elemen dari satu array
dan celepuk menjadi lain.
>> Jadi bagaimana kita pergi tentang melakukan ini?
Nah, biarkan aku pergi ke depan dan menulis program cepat di sini.
Aku akan pergi ke depan dan melakukan ini sebagai berikut.
Mari kita sebut ini -
apa yang kita ingin memanggil satu ini?
>> Sebenarnya, tidak.
Mari saya mundur.
Saya tidak ingin melakukan itu Belum cliffhanger.
Ini akan merusak kesenangan.
Mari kita lakukan ini sebagai gantinya.
>> Misalkan saya ingin menulis sedikit Program dan bahwa kini merangkul ini
gagasan rekursi.
Aku agak mendapat depan sendiri ada.
Aku akan melakukan hal berikut.
>> Pertama, cepat meliputi standar io.h, serta termasuk dari cs50.h.
Dan kemudian aku akan pergi ke depan dan menyatakan void main int
dengan cara yang biasa.
Aku sadar bahwa aku sudah misnamed file, sehingga biarkan aku hanya menambahkan ekstensi c. sini jadi
bahwa kita dapat mengkompilasi dengan benar.
Mulai fungsi ini.
>> Dan fungsi saya ingin menulis, cukup sederhana, adalah salah satu yang meminta
pengguna untuk nomor dan kemudian menambahkan sampai semua angka antara itu
jumlah dan, katakanlah, 0.
Jadi pertama aku akan pergi ke depan dan menyatakan int n.
Lalu aku menyalin beberapa kode yang kami telah digunakan untuk sementara waktu.
Sementara ada sesuatu yang benar.
Aku akan datang kembali ke dalam sekejap.
>> Apa yang ingin saya lakukan?
Saya ingin mengatakan printf positif silahkan integer.
Dan kemudian aku akan mengatakan n mendapat mendapatkan int.
Jadi sekali lagi, beberapa kode boilerplate bahwa kami telah digunakan sebelumnya.
Dan aku akan melakukan hal ini sedangkan n kurang dari 1.
Jadi, ini akan memastikan bahwa pengguna memberi saya bilangan bulat positif.
>> Dan sekarang aku akan melakukan hal berikut.
Saya ingin menambahkan semua nomor antara 1 dan dan n, atau 0 dan n,
ekuivalen, untuk mendapatkan jumlah total.
Jadi simbol sigma besar Anda mungkin ingat.
Jadi aku akan melakukan ini dengan panggilan pertama fungsi yang disebut sigma,
lewat di n, dan kemudian aku akan printf mengatakan, jawabannya ada di sana.
>> Jadi singkatnya, saya mendapatkan dan int dari pengguna.
Saya memastikan itu positif.
Saya menyatakan yang disebut jawaban variabel tipe int dan toko di dalamnya pengembalian
nilai sigma, lewat di n sebagai masukan.
Dan kemudian saya mencetak jawaban itu.
>> Sayangnya, meskipun sigma terdengar seperti sesuatu yang mungkin dalam
file math.h, deklarasi, itu sebenarnya tidak.
Jadi itu OK.
Saya bisa menerapkan ini sendiri.
Aku akan melaksanakan fungsi yang disebut sigma, dan itu akan mengambil
Parameter -
mari kita sebut saja m, hanya jadi berbeda.
Dan kemudian di sini, aku akan mengatakan, baik, jika m adalah kurang dari 1 - ini adalah
sangat menarik Program.
Jadi aku akan pergi ke depan dan segera mengembalikan 0.
Itu hanya tidak masuk akal untuk menambahkan semua angka antara 1 dan m jika m
itu sendiri 0 atau negatif.
>> Dan kemudian aku akan pergi ke depan dan melakukan hal ini sangat iteratif.
Aku akan melakukan hal semacam ini tua-sekolah, dan aku akan pergi ke depan
dan mengatakan bahwa aku akan menyatakan jumlah untuk menjadi 0.
Lalu aku akan memiliki untuk loop int -
dan biarkan aku melakukannya untuk mencocokkan kami kode distribusi, sehingga Anda memiliki salinan
di rumah. int i mendapat 1 pada hingga i adalah kurang dari atau sama dengan m.
i plus plus.
Dan kemudian dalam hal ini untuk loop -
kita hampir sampai -
sum sum mendapat ditambah 1.
Dan kemudian aku akan kembali jumlah tersebut.
>> Jadi saya melakukan ini dengan cepat, cukup diakui.
Tapi sekali lagi, fungsi utama cukup langsung, berbasis pada kode kita sudah
ditulis sejauh ini.
Menggunakan dual loop untuk mendapatkan positif int dari pengguna.
Saya kemudian lulus int bahwa untuk fungsi baru disebut sigma, menyebutnya, sekali lagi, n.
Dan saya menyimpan nilai kembali, jawabannya dari kotak hitam saat ini
dikenal sebagai sigma, dalam variabel disebut jawaban.
Lalu aku mencetaknya.
>> Jika sekarang kita melanjutkan cerita, bagaimana sigma dilaksanakan?
Saya mengusulkan untuk menerapkan sebagai berikut.
Pertama, sedikit pemeriksaan kesalahan memastikan bahwa pengguna tidak
bermain-main dengan saya dan lewat di beberapa negatif atau nilai 0.
Kemudian saya mendeklarasikan variabel disebut jumlah dan set ke 0.
>> Dan sekarang aku mulai bergerak dari i sama 1 sepanjang jalan sampai dengan dan termasuk m,
karena saya ingin memasukkan semua nomor dari satu melalui m, inklusif.
Dan dalam hal ini untuk loop, saya hanya melakukan sum mendapatkan apapun sekarang, ditambah
nilai i.
Ditambah nilai i.
>> Sebagai samping, jika Anda sudah tidak melihat ini sebelumnya, ada beberapa gula sintaksis
untuk baris ini.
Saya bisa menulis ulang ini sebagai ditambah sama dengan i, hanya untuk menyelamatkan diri beberapa keystrokes
dan untuk melihat sedikit lebih dingin.
Tapi itu semua.
Ini fungsional hal yang sama.
>> Sayangnya, kode ini tidak akan mengkompilasi belum.
Jika saya jalankan make sigma 0, bagaimana am Aku akan dimarahi?
Apa itu akan tidak suka?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Ya, saya tidak menyatakan fungsi di bagian atas, kan?
C adalah jenis bodoh, dalam hal ini hanya melakukan apa yang Anda kirim ke lakukan, dan Anda
harus melakukannya dalam urutan itu.
Dan jadi jika saya tekan Enter di sini, aku akan mendapatkan peringatan tentang sigma implisit
deklarasi.
>> Oh, tidak masalah.
Aku bisa naik ke atas, dan saya bisa mengatakan, baiklah, tunggu sebentar.
Sigma adalah fungsi yang mengembalikan int dan mereka mengharapkan
int sebagai masukan, koma.
Atau aku bisa menempatkan seluruh fungsi atas utama, tapi secara umum, aku akan
merekomendasikan melawan itu, karena itu bagus untuk selalu memiliki utama di bagian atas sehingga
Anda bisa menyelam kanan dan tahu apa Program lakukan dengan membaca utama pertama.
>> Jadi sekarang biarkan aku membersihkan layar.
Remake sigma 0.
Semua tampaknya untuk memeriksa.
Biarkan aku menjalankan sigma 0.
Inter positif.
Aku akan memberikan nomor 3 untuk tetap sederhana.
Jadi yang harus memberi saya 3 ditambah 2 ditambah 1, jadi 6.
Masukkan, dan memang saya mendapatkan 6.
>> Aku bisa melakukan sesuatu yang lebih besar -
50, 12, 75.
Sama seperti tangen, aku akan melakukan sesuatu yang konyol seperti benar-benar besar
nomor, Oh, yang benar-benar bekerja -
eh, saya tidak berpikir itu benar.
Mari kita lihat.
Mari kita benar-benar berantakan dengan itu.
>> Itulah masalah.
Apa yang terjadi?
Kode tidak seburuk itu.
Ini masih linier.
Bersiul adalah efek yang baik, meskipun.
Apa yang terjadi?
>> Tidak yakin apakah aku mendengarnya.
Jadi ternyata - dan ini sebagai samping.
Ini bukan inti untuk gagasan rekursi.
Ternyata, karena saya sedang mencoba untuk mewakili seperti sejumlah besar, kebanyakan
kemungkinan itu sedang disalahtafsirkan oleh C sebagai angka tidak positif,
tapi angka negatif.
>> Kami belum membicarakan hal ini, tetapi ternyata ada angka negatif
di dunia di samping ke nomor positif.
Dan cara-cara yang dapat Anda mewakili angka negatif
dasarnya adalah, Anda menggunakan salah satu bit khusus untuk menunjukkan
positif atas negatif.
Ini sedikit lebih kompleks dari itu, tapi itu ide dasar.
>> Saking sayangnya, jika C membingungkan satu dari bit dengan benar-benar berarti,
oh, ini adalah angka negatif, loop saya di sini, misalnya, sebenarnya tidak pernah
akan mengakhiri.
Jadi jika saya benar-benar mencetak sesuatu lagi dan lagi, kita akan
melihat jauh.
Tapi sekali lagi, ini adalah selain titik.
Ini benar-benar hanya semacam keingintahuan intelektual yang kita akan datang
kembali ke akhirnya.
Tetapi untuk sekarang, ini adalah yang benar pelaksanaan jika kita asumsikan bahwa
pengguna akan memberikan ints yang cocok dalam ints.
>> Tapi saya mengklaim bahwa kode ini, terus terang, bisa dilakukan jauh lebih sederhana.
Jika tujuan di tangan adalah untuk mengambil nomor seperti m dan menjumlahkan semua
angka antara 1 dan, atau sebaliknya antara 1 dan, saya menyatakan
bahwa saya dapat meminjam ide ini yang menggabungkan semacam punya, yang mengambil masalah
ini ukuran dan membaginya menjadi sesuatu yang lebih kecil.
Mungkin bukan setengah, tetapi lebih kecil, tapi representatif sama.
Ide yang sama, tapi masalah kecil.
>> Aku sebenarnya - biarkan aku menyimpan file ini dengan nomor versi yang berbeda.
Kami akan memanggil versi ini 1 bukan 0.
Dan saya menyatakan bahwa saya benar-benar dapat reimplement ini semacam ini
pikiran-lipatan jalan.
>> Aku akan meninggalkan bagian dari itu sendiri.
Aku akan mengatakan jika m kurang dari atau bahkan sama dengan 0 -
Aku hanya akan menjadi sedikit lebih anal saat ini
dengan kesalahan saya memeriksa -
Aku akan pergi ke depan dan kembali 0.
Ini adalah sewenang-wenang.
Saya hanya hanya memutuskan jika pengguna memberi saya angka negatif, aku
kembali 0, dan mereka harus membaca dokumentasi lebih dekat.
>> Lain -
perhatikan apa yang akan saya lakukan.
Lain saya akan kembali m ditambah -
apa yang sigma m?
Nah, sigma m + m dikurangi 1, ditambah m minus 2, ditambah m dikurangi 3.
Saya tidak ingin menulis semua yang keluar.
Mengapa tidak aku hanya tendangan?
Secara rekursif menyebut diriku dengan sedikit masalah kecil, titik koma,
dan menyebutnya sehari?
>> Benar?
Sekarang di sini, juga, Anda mungkin merasa khawatir atau bahwa ini adalah infinite loop bahwa aku
merangsang, dimana saya menerapkan sigma dengan menghubungi sigma.
Tapi itu sangat OK, karena saya berpikir ke depan sebuah menambahkan baris mana?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: 23 sampai dengan 26, yang jika kondisi saya.
Karena apa yang bagus tentang pengurangan di sini, karena saya terus
menyerahkan masalah kecil sigma, lebih kecil masalah, lebih kecil - itu tidak
setengah ukuran.
Ini hanya langkah kecil yang lebih kecil, tapi itu OK.
Karena pada akhirnya, kami akan bekerja perjalanan ke 1 atau 0.
Dan setelah kita memukul 0, sigma tidak akan menyebut dirinya lagi.
Ini akan segera mengembalikan 0.
>> Jadi efeknya, jika Anda semacam angin ini dalam pikiran Anda, adalah dengan menambahkan m ditambah
m dikurangi 1, ditambah m minus 2, ditambah m dikurangi 3, ditambah titik, titik, titik, m dikurangi
m, akhirnya memberikan Anda 0, dan Efek akhirnya menambahkan semua
hal-hal ini bersama-sama.
Jadi kita tidak, dengan rekursi, memecahkan masalah yang kita
tidak bisa memecahkan sebelumnya.
Memang, versi 0 ini, dan setiap Masalahnya sampai saat ini, telah dipecahkan
dengan hanya menggunakan untuk loop atau saat loop atau konstruksi serupa.
>> Tapi rekursi, aku yakin, memberi kita cara berpikir yang berbeda tentang
masalah, dimana jika kita bisa mengambil Masalahnya, membaginya dari sesuatu
agak besar menjadi sesuatu yang agak kecil, saya menyatakan bahwa kita bisa mengatasinya
mungkin sedikit lebih elegan dalam hal dari desain, dengan kode kurang,
dan bahkan mungkin memecahkan masalah yang akan lebih sulit, karena kita akhirnya akan
lihat, memecahkan murni iteratif.
>> Tapi cliffhanger yang saya lakukan ingin meninggalkan kita pada adalah ini.
Biarkan aku pergi ke depan dan membuka up file dari -
sebenarnya, biarkan aku pergi dan lakukan sangat cepat ini.
Biarkan aku pergi ke depan dan mengusulkan berikut.
Diantara kode hari ini adalah file ini di sini.
Yang ini, NOSWAP.
>> Jadi ini adalah sebuah program kecil yang bodoh Aku melecut bahwa klaim untuk melakukan
berikut.
Dalam utama, pertama menyatakan sebuah int disebut x dan memberikannya
nilai 1.
Kemudian menyatakan sebuah y int dan memberikannya nilai 2.
Kemudian ia akan mencetak apa x dan y adalah.
Lalu ia berkata, swapping, dot dot dot.
>> Kemudian mengaku memanggil fungsi disebut swap, lewat di x dan
y, ide yang merupakan yang diharapkan x dan y akan datang kembali
berbeda, sebaliknya.
Kemudian mengklaim bertukar!
dengan tanda seru.
Kemudian mencetak x dan y.
>> Tapi ternyata bahwa ini sangat demonstrasi sederhana turun
di sini sebenarnya kereta.
Meskipun saya menyatakan sementara variabel dan untuk sementara menempatkan di
itu, maka aku pemindahan a nilai b -
yang terasa wajar, karena saya sudah menyimpan salinan di temp.
Kemudian saya update b untuk sama apa pun yang ada di temp.
Ini semacam permainan cangkang bergerak ke b dan b menjadi dengan menggunakan
tengah-manusia yang disebut suhu terasa sangat masuk akal.
>> Tapi saya mengklaim bahwa ketika saya menjalankan ini kode, seperti yang akan saya lakukan sekarang -
biarkan aku pergi ke depan dan paste di sini.
Aku akan menelepon noswap.c ini.
Dan seperti namanya, ini bukan akan menjadi program yang benar.
Membuat NOSWAP. / Tanpa swap.
x 1, y adalah 2, swapping, bertukar.
x 1, y adalah 2.
Ini adalah fundamental salah, bahkan meskipun ini tampaknya sempurna
masuk akal untuk saya.
Dan ada alasan, tapi kami tidak akan mengungkapkan alasannya dulu.
>> Untuk saat ini Cliffhanger kedua saya ingin untuk meninggalkan Anda dengan adalah ini,
pengumuman macam pada kode kupon.
Inovasi kami dengan hari-hari akhir tahun ini telah menimbulkan sejumlah non-sepele
pertanyaan, yang bukan maksud kami.
Tujuan dari kode kupon, dimana jika Anda melakukan bagian dari masalah
ditetapkan di awal, sehingga mendapatkan satu hari ekstra, benar-benar untuk membantu kalian membantu
sendiri mulai awal, semacam dari incentivizing dengan Anda.
Membantu kita mendistribusikan beban di jam kantor lebih baik sehingga
itu semacam menang-menang.
>> Sayangnya, saya pikir instruksi saya belum, sampai saat ini, sangat jelas, sehingga
Aku kembali akhir pekan ini dan diperbarui spec di besar, teks lebih berani untuk
menjelaskan peluru seperti ini.
Dan hanya untuk mengatakan lebih terbuka, dengan default, masalah set disebabkan Kamis
pada siang hari, per silabus.
Jika Anda mulai awal, menyelesaikan bagian dari permasalahan yang disampaikan oleh Rabu pukul 12:00
PM, bagian yang berhubungan dengan kupon kode, idenya adalah bahwa Anda dapat memperpanjang
batas waktu Anda untuk P mengatur sampai Jumat.
Artinya, sedikit dari bagian kecil dari P mengatur relatif terhadap apa yang biasanya adalah
masalah yang lebih besar, dan Anda membeli diri satu hari ekstra.
Sekali lagi, itu membuat Anda berpikir tentang sejumlah masalah, membawa Anda ke
jam kantor lebih cepat.
Tapi masalah kode kupon masih diperlukan, bahkan jika Anda tidak mengirimkannya.
>> Tapi yang lebih compellingly adalah ini.
(STAGE WHISPER) Dan orang-orang itu meninggalkan dini akan menyesal.
Sebagaimana orang-orang di balkon.
Saya mohon maaf sebelumnya kepada orang-orang di balkon untuk alasan-alasan yang akan
jelas hanya dalam beberapa saat.
>> Jadi kita beruntung untuk memiliki salah satu Mantan rekan pengajar kepala CS50 yang di
sebuah perusahaan bernama dropbox.com.
Mereka telah sangat bermurah hati menyumbangkan kode kupon di sini selama ini banyak ruang,
yang naik dari biasanya 2 gigabyte.
Jadi apa yang saya pikir kami akan melakukan hal ini catatan akhir adalah melakukan sedikit giveaway,
dimana hanya dalam beberapa saat, kami akan mengungkapkan pemenang dan yang memiliki kupon
kode yang Anda dapat pergi ke mereka website, ketik dalam, dan voila, mendapatkan
lebih jauh Dropbox ruang untuk Anda alat dan untuk file pribadi Anda.
>> Dan pertama-tama, yang ingin berpartisipasi dalam gambar ini?
OK, sekarang yang membuatnya bahkan lebih menyenangkan.
Orang yang menerima ini 25-gigabyte kode kupon - yang jauh
lebih menarik daripada akhir hari sekarang, mungkin -
adalah orang yang duduk di atas bantalan kursi di bawahnya ada
kode kupon.
Sekarang Anda dapat melihat di bawah bantalan kursi Anda.
>> [VIDEO PEMUTARAN]
>> -Satu, dua, tiga.
>> [BERTERIAK]
>> -Anda mendapatkan mobil!
Anda mendapatkan mobil!
>> DAVID Malan: Kita akan melihat Anda Rabu.
>> -Anda mendapatkan mobil!
Anda mendapatkan mobil!
>> DAVID Malan: Balcony orang, datang di sini ke depan,
di mana kita memiliki ekstra.
>> -Semua orang mendapat mobil!
Semua orang mendapat mobil!
>> [END VIDEO PEMUTARAN]
>> Narator: Pada CS50 berikutnya -
>> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [Ukelele drama]