>> SPEAKER: Baiklah, ini adalah CS50.
Ini adalah akhir minggu ketiga, dan jika Anda belum mengambil keuntungan sudah,
tahu bahwa akan ada makan siang Jumat ini seperti biasa, di mana
Anda dapat menikmati percakapan yang baik dan makanan di Fire and Ice
dengan beberapa CS50 ini staf dan teman sekelas.
Kepala ke URL ini di sini.
>> Sekarang Anda mungkin ingat, atau Anda akan segera berkenalan dengan,
hal ini di sini, yang yang diberikan pada akhir
semester untuk banyak kelas.
Buku biru yang disebut ujian, di mana Anda menulis jawaban Anda untuk ujian.
Sekarang aku punya di sini 26 seperti buku biru, pada masing-masing
ditulis nama, A sampai Z. Dan memang nama-nama yang sederhana, A
melalui Z. Dan salah satu tujuan di tangan hari ini
akan menjadi untuk melanjutkan apa kami mulai pada hari Senin, yang tidak
begitu banyak melihat kode, tapi benar-benar melihat ide-ide dan pemecahan masalah.
Salah satu tujuan dan janji-janji saja ini
adalah untuk mengajarkan Anda untuk berpikir lebih hati-hati, lebih metodis,
dan untuk memecahkan masalah lebih efisien.
Dan memang, kita bisa melakukan itu benar-benar bahkan tanpa menyentuh baris kode.
Jadi saya memiliki beberapa gajah di sini hari ini, oranye dan biru,
jika kita bisa mendapatkan satu relawan, mungkin dari jauh di belakang dari biasanya.
Bagaimana di sana, datang di bawah.
Tujuan yang akan menjadi untuk membantu ditambah melaksanakan ujian ini di sini.
Siapa nama Anda?
>> AUDIENCE: Mary Beth.
SPEAKER: Mary Beth, datang ke atas.
Biarkan aku mendapatkan mikrofon di sini untuk Anda.
Senang bertemu Anda.
>> AUDIENCE: Senang bertemu Anda.
SPEAKER: Baiklah, jadi saya memiliki di sini buku biru A sampai Z,
dan aku akan berpura-pura bahwa Saya memiliki salah satu siswa,
dan mereka datang agak acak pada akhir ujian blok tiga jam,
jadi mereka berakhir di beberapa urutan semi-acak seperti ini.
Sekarang pekerjaan Anda hanya dalam beberapa saat akan untuk akan-- ini sebenarnya bagaimana mereka mendapatkan
berbalik pada akhir kelas, kemungkinan besar.
Tugas Anda sekarang akan menjadi, cukup sederhana, untuk memilah buku-buku biru untuk kita
dari A sampai Z.
>> AUDIENCE: Oh, ini adalah akan mengambil selamanya.
>> SPEAKER: Dan kita akan melihatnya setelah Anda melakukan ini, tidak ada tekanan.
AUDIENCE: Tidak, tidak ada tekanan atau apa pun.
>> SPEAKER: Dan untuk bersenang-senang, mari kita memasang timer.
>> AUDIENCE: Sangat menyenangkan, sangat menyenangkan.
>> SPEAKER: Aku bisa memegang mic untuk Anda.
Baiklah, kita baru saja dua kali lipat kecepatan kami.
Jadi sementara itu, biarkan aku berpose apa akan menjadi pertanyaan bagi Mary Beth
adalah apa yang dia lakukan, bagaimana dia akan tentang memecahkan ini?
Dan pada kenyataannya, Anda mungkin tidak memiliki pernah berpikir tentang sesuatu
begitu sederhana seperti ketika Anda memilih naik 26 buku seperti ini,
yang tidak memiliki alami memerintahkan kepada mereka.
Bagaimana prosesnya bahwa Anda benar-benar digunakan?
Apakah cukup acak hanya memilih salah satu pertama yang Anda lihat
dan memasukkannya ke dalam tempatnya?
Apakah Anda pertama kali memindahkan tangan Anda di sekitar mencari A kemudian mencari B?
Apakah anda melihat pada sepasang mereka berdampingan
dan hanya mengatakan, tunggu dulu, ini tidak benar, dan kemudian swap order?
Kami melihat sudah pada Senin bahwa ada sejumlah cara
di mana kita bisa melakukan ini, dan memang seperti yang kita mendekati akhir di sini,
Saya akan perhatikan mungkin apa Mary Beth lakukan.
Kami memiliki beberapa tumpukan tampaknya, a lebih besar, tiga yang lebih kecil.
>> AUDIENCE: Aku memerintahkan mereka ketika saya menemukan dua surat
yang saya tahu bersama-sama secara berurutan, Aku menempatkan mereka bersama-sama sehingga saya tidak
perlu khawatir tentang menjaga melacak seluruh baris buku.
Hanya saja, oh, A pertama, Aku punya setumpuk ini di sini.
SPEAKER: Jadi, hampir seperti potongan teka-teki yang
memiliki bentuk yang tepat untuk cocok dengan satu sama lain.
AUDIENCE: Cukup banyak, ya.
SPEAKER: OK, baik.
Dan sekarang masing-masing tumpukan kiranya diurutkan?
>> AUDIENCE: Ya.
>> SPEAKER: Baiklah, A sampai Z. Semua benar, selamat, Anda melakukannya.
Anda memiliki pilihan Anda.
Biru?
Baiklah, terima kasih untuk itu.
Jadi Mary Beth tidak mengusulkan apa pendekatannya adalah,
tapi apa pendekatan lain bagaimana Anda bisa pergi tentang menyortir hal-hal ini?
Apa yang akan Anda lakukan?
Rekor untuk mengalahkan pasti satu menit dan 50 detik atau lebih,
ditambah yang saya lupa untuk menghitung.
Apa yang akan Anda lakukan?
Ya?
AUDIENCE: Ambil tumpukan.
Mulai dari awal.
Periksa surat-surat Anda.
Dan jika yang paling atas adalah lebih tinggi dari, mungkin, mereka,
bagian bawah adalah lebih tinggi, kemudian beralih mereka.
>> SPEAKER: OK, jadi mulai di bagian atas dan bawah,
dan kemudian bekerja dengan cara Anda batin seperti itu, bertukar mereka?
OK, jadi sedikit mirip semangat yang bubble sort,
tetapi memilih ekstrem bukan pasangan yang berdekatan.
Tapi pendek itu adalah bahwa ada pasti banyak cara yang berbeda
kita bisa melakukan ini, dan terus terang, saya pikir Anda jenis
mengadopsi beberapa pendekatan, kan?
Anda membuat semacam empat tumpukan diurutkan, dan kemudian secara efektif bergabung bersama-sama.
Dan itu, berani bilang, lain Teknik sama sekali.
Anda tidak memperlakukannya sebagai salah satu tumpukan besar, Anda membagi masalah menjadi empat paha depan,
jika Anda mau, dan kemudian entah bagaimana bergabung mereka pada akhirnya.
>> Jadi mari kita pertimbangkan, akhirnya, bagaimana lagi kita bisa melakukan hal ini.
Kami diformalkan gagasan dari bubble sort terakhir kali,
dan bubble sort ingat adalah algoritma yang kita divisualisasikan
dengan delapan dari teman sekelas Anda di sini, tampaknya secara acak diurutkan pada awalnya.
Dan kami kemudian memutuskan berpasangan, jika dua elemen yang rusak,
hanya swap mereka.
Jadi empat dan dua jelas rusak,
sehingga kedua teman sekelas beralih posisi.
Dan kemudian kami mengulangi dengan empat dan enam, kemudian enam dan delapan, pada setiap iterasi,
bergerak ke kanan.
>> Jadi mengingat delapan orang, berapa banyak berpasangan perbandingan yang saya lakukan sambil berjalan dari
kiri ke kanan dalam satu iterasi seperti itu?
Berapa banyak perbandingan?
Seven, kan?
Karena jika ada delapan orang, tetapi Anda memiliki pasangan
mereka dan Anda terus bergerak satu hop ke kanan,
Anda tidak akan memiliki delapan perbandingan karena Anda tidak bisa membandingkan
unsur melawan dirinya sendiri, atau itu akan hanya ada gunanya, sehingga Anda memiliki tujuh.
Atau lebih umum, jika kami memiliki n orang, kita
lakukan n dikurangi 1 perbandingan dengan bubble sort.
>> Jadi mari kita pertimbangkan sekarang bagaimana baik atau gelembung buruk semacam sebenarnya, dan mencoba
untuk memberikan diri kita kosakata dengan yang cocok untuk algoritma kritik seperti ini,
dan segera kita sendiri.
Jadi lulus pertama melalui bubble sort, pertama kali
Aku berjalan dari kiri ke kanan melintasi panggung, membawa saya n dikurangi 1 perbandingan.
Dan itu akan menjadi saya satuan ukuran, kan?
Aku agak berbicara dan berjalan-jalan, agak cepat, agak lambat,
jadi menghitung jumlah saya detik tidak terutama mengatakan,
tetapi menghitung jumlah operasi yang saya lakukan pada hari Senin,
membandingkan dua orang, yang terasa seperti unit bagus ukuran.
>> Jadi n dikurangi 1 langkah pertama kalinya, tapi kemudian apa yang terjadi setelah itu?
Apa satu terbalik dari satu lulus melalui daftar jika tidak disortir?
Apa yang bisa Anda ceritakan tentang elemen yang semua cara di atas sana?
Ya?
Itu adalah elemen terbesar, kan?
Nomor delapan, meskipun dia mulai di sini, setiap kali saya
dibandingkan melawan tetangga, dia terus
menggelegak ke kanan sisi dari daftar.
Dan memang, di situlah Algoritma mendapatkan namanya.
>> Sekarang dengan logika itu, berapa banyak perbandingan perlu saya buat pada kedua kalinya
Saya membuat pass yang dari kiri ke kanan?
n minus 2, kan?
Itu hanya akan membuang-buang waktu saya jika saya terus membandingkan delapan terhadap seseorang
lain karena kita sudah tahu ia berada di tempat yang tepat.
Jadi itu sedikit optimasi, sehingga lulus berikutnya
akan menjadi ditambah n dikurangi dua langkah, dimana n adalah jumlah orang.
Sekarang Anda dapat jenis ekstrapolasi, bahkan jika Anda tidak seorang ilmuwan komputer,
bagaimana ini berakhir.
Pada akhir algoritma ini, mungkin Anda punya hanya satu perbandingan tersisa.
Anda harus jenis memperbaiki awal daftar dalam kasus dua
dan salah satu yang rusak dan harus menjadi salah satu dan dua,
jadi ini kentut di ditambah 1 perbandingan akhir.
>> Sekarang dot, dot, dot jenis gelombang itu tangan pada beberapa rincian juicier,
tapi mari kita pergi ke depan dan menyederhanakan.
Jika Anda ingat dari tinggi sekolah, terus terang, banyak Anda
memiliki buku matematika yang memiliki contekan kecil
di sampul depan atau penutup belakang yang menunjukkan Anda
penjumlahan seri apa seperti ini akhirnya ditambah hingga.
Dalam kasus umum, jika Anda memiliki variabel seperti n, dan memang yang satu ini,
jika Anda melihat Anda buku matematika sekolah tua,
Anda akan melihat bahwa sebenarnya ini menambahkan hingga jumlah ini di sini,
n kali n dikurangi 1 semua dibagi 2.
Jadi untuk saat ini saya hanya menetapkan ini benar, seterusnya lompatan iman,
itulah yang ini merangkum sampai, dan kita bisa
membuktikan bahwa dalam kasus yang lebih umum.
Tapi sekarang mari kita memperluas ini.
Jadi mari kita kalikan hal ini, jadi itu n kuadrat, dikurangi n, semua dibagi 2.
Itu benar-benar n kuadrat, dibagi 2, dikurangi n lebih dari 2,
jadi itu semua bagus dan menarik.
Tapi apa yang terjadi jika kita sekarang plug-in nilai?
Misalkan aku tidak punya delapan orang, tetapi mengatakan satu juta.
Dan satu juta hanya karena itu adalah angka yang cukup besar,
mari kita pasang di itu dan melihat apa yang terjadi.
Jadi jika saya pasang satu juta ke dalam rumus yang Aku akan mendapatkan satu juta kuadrat,
dibagi 2, minus juta, dibagi 2.
Sekarang apa yang akan sama?
Jadi 500 miliar, dikurangi 500.000.
Dan jika saya benar-benar melakukan bahwa matematika keluar, berarti bahwa
bahwa menyortir satu juta orang dengan semacam gelembung
mungkin membawa saya 499999500000 langkah-langkah atau perbandingan pada akhirnya,
kami hanya ekstrapolasi.
>> Yang terasa cukup lambat, tapi terus terang mengukur satu input tertentu
seperti ini, tidak semua jitu itu.
Tapi memang itu tidak menunjukkan bahwa sebagai n semakin besar dan lebih besar, algoritma ini
jenis rasanya lebih buruk dan buruk, atau Anda benar-benar
mulai merasakan sakit yang eksponensial, bahwa n kuadrat,
yang menambahkan sampai cukup cepat.
Dan detail ini tidak hilang pada orang, pada kenyataannya
beberapa tahun yang lalu seorang senator tertentu yang kampanye, duduk untuk wawancara
dengan Google Eric Schmidt, CEO pada saat itu,
dan ditantang dengan pertanyaan seperti kita mengeksplorasi hari ini.
Mari kita lihat.
>> [VIDEO PEMUTARAN]
>> -Senator, Kau di sini di Google, dan saya suka
memikirkan presiden sebagai wawancara kerja.
Sekarang, sulit untuk mendapatkan pekerjaan sebagai presiden,
dan Anda akan melalui kerasnya sekarang.
Hal ini juga sulit untuk mendapatkan pekerjaan di Google.
Kami memiliki pertanyaan, dan kami mengajukan pertanyaan kandidat kami,
dan ini adalah dari Larry Schwimmer.
Apa-- kalian pikir aku bercanda, itu ada di sini.
Apa cara yang paling efisien untuk mengurutkan satu juta 32-bit bilangan bulat?
>> -Well--
>> Maafkan aku, maybe--
>> Tidak, tidak, tidak.
Saya pikir semacam gelembung akan menjadi cara yang salah untuk pergi.
>> Ayo, yang mengatakan kepadanya ini?
Aku tidak melihat komputer ilmu di latar belakang Anda.
>> -Kita Punya mata-mata kita di sana.
>> -OK, Mari kita bertanya berbeda pertanyaan wawancara.
>> [END VIDEO PUTAR]
>> SPEAKER: Jadi berbicara tentang nomor tertentu meskipun,
tidak akan semua yang berguna.
Ini bukan pelajaran hidup gelembung yang semacam, diberi juta input,
mungkin mengambil sebanyak 500 miliar langkah.
Anda tidak bisa benar-benar menggeneralisasi terlalu efektif dari yang
dan membuat keputusan desain yang baik saat menulis program.
Jadi mari kita fokus meskipun pada bagaimana kita mungkin menyederhanakan hasil ini.
>> Jadi saya sudah ditandai dengan warna kuning di sini hasil n kuadrat dibagi 2,
jadi satu juta kuadrat dibagi 2, dan kemudian
Aku sudah disorot apa jawaban akhir adalah
setelah kami dikurangi off n dibagi 2.
Dan klaim saya akan buat sekarang adalah, siapa sih yang peduli jika Anda mengurangi off
n tua sedikit lebih dari 2 ketika pertama bagian dari formula ini jauh lebih besar?
Ini mendominasi yang lain istilah, n kuadrat dibagi 2
adalah jauh lebih besar, jelas, sebagai n mendapat besar seperti satu juta,
yang benar-benar ada perbedaan besar di akhir hari antara 500 miliar
dan 499999500000?
Tidak benar-benar.
Dan jadi apa kita akan lakukan sebagai ilmuwan komputer
mengabaikan orang-orang yang lebih rendah istilah ketertiban dan mengambil sesuatu seperti ini dan benar-benar
hanya menyederhanakannya ke istilah yang akan peduli.
Semakin besar set data kami dapatkan, semakin besar database kami dapatkan, halaman web yang lebih
kita harus mencari, lebih Teman-teman yang Anda miliki di Facebook.
>> Sebagai n semakin besar, kami benar-benar akan peduli tentang terbesar
Istilah dalam analisis seperti kinerja algoritma kami.
Dan aku akan mengatakan, Anda tahu apa, bubble sort adalah pada urutan O besar,
pada urutan n kuadrat.
Ini tidak benar-benar n kuadrat seperti yang kita lihat,
tapi siapa yang benar-benar peduli tentang istilah-istilah yang lebih kecil,
dan terus terang, yang benar-benar peduli jika kita membagi dengan 2?
Itu hanya faktor konstan.
Dan adalah 500 miliar dibandingkan 250 miliar benar-benar masalah besar?
Aku hanya bisa menunggu satu tahun, biarkan laptop saya benar-benar
mendapatkan dua kali lebih cepat di perangkat keras, dan hal semacam perbedaan
pergi begitu saja secara alami dari waktu ke waktu.
>> Apa yang kita pedulikan adalah ekspresi, bagian
dari ekspresi yang akan bervariasi sebagai masukan kami akan lebih besar dan lebih besar.
Dan memang, di dunia nyata, itulah yang terjadi semakin
adalah masukan untuk masalah kami dan algoritma yang semakin besar.
Jadi O besar akan menjadi notasi, notasi asimtotik, bahwa kita hanya
digunakan sebagai ilmuwan komputer untuk menggambarkan kinerja, atau waktu berjalan,
dari algoritma.
Sehingga kita dapat membandingkan algoritma pada komputer yang berbeda yang ditulis
oleh orang yang berbeda, dengan menggunakan beberapa metrik dasarnya sama
seperti jumlah perbandingan Anda membuat, atau mungkin jumlah swap
Anda membuat.
>> Apa yang kita tidak akan count adalah jumlah waktu
yang melewati pada jam di dinding biasanya.
Apa yang kita tidak akan khawatir tentang adalah berapa banyak memori
Anda menggunakan hari ini di Setidaknya, meskipun itu
sumber daya lain kita mungkin mengukur.
Kami akan mencoba untuk mendasarkan analisis kami hanya pada operasi dasar, yang,
terus terang, bahwa Anda dapat melihat sebagian visual.
Jadi dengan sesuatu seperti O besar n kuadrat, saya menyatakan bahwa O n kuadrat
merupakan batas atas pada apa yang disebut waktu berjalan dari bubble sort.
Dengan kata lain, jika Anda ingin mengklaim bahwa ada
batas atas ini pada berapa banyak langkah algoritma mungkin mengambil,
itu akan berada di O besar n kuadrat dalam kasus ini, batas atas.
>> Bagaimana jika saya bukan mengubah cerita menjadi bukan tentang bubble sort,
tetapi hal ini batas atas.
Dapatkah Anda memikirkan algoritma bahwa kita telah melihat sudah
yang batas atas, maksimum mengukur waktu atau operasi,
akan dikatakan dibatasi n, fungsi linear,
tidak satu kuadrat yang melengkung?
Apakah yang dimaksud dengan algoritma yang selalu tidak lebih
daripada seperti langkah n, atau Langkah 2n, atau langkah-langkah 3n?
Ya?
>> AUDIENCE: Menemukan jumlah terbesar dalam daftar?
>> SPEAKER Perfect, menemukan jumlah terbesar dalam daftar.
Jika aku diberi daftar orang misalnya,
masing-masing yang memegang nomor, apa jumlah maksimum
langkah itu harus membawa saya, orang cukup cerdas,
untuk menemukan orang yang terbesar dalam daftar itu?
n, kan?
Karena dalam kasus terburuk, di mana mungkin nilai terbesar itu?
Benar, semua jalan di akhir.
Jadi dalam kasus terburuk atas terikat, aku mungkin
harus pergi semua jalan di sini dan menjadi seperti,
oh, ini nomor delapan, atau apa pun nilai yang.
Sekarang itu hanya akan menjadi bodoh jika saya terus berjalan, kan?
Mencari semakin banyak unsur jika yang terakhir dari mereka ada di sana?
Jadi pasti, n adalah batas atas.
Saya tidak perlu mengambil langkah lagi dari itu.
>> Jadi bagaimana jika sebaliknya saya mengusulkan bahwa ada algoritma di dunia ini yang
memiliki waktu berjalan yang dibatasi oleh O besar log n, log n?
Di mana kita melihat ini sebelumnya?
Ya?
>> AUDIENCE: Dalam masalah buku telepon?
SPEAKER: Seperti masalah buku telepon.
Apa ukuran seberapa banyak waktu atau berapa banyak air mata itu
mengambil saya untuk menemukan seseorang seperti Mike Smith di buku telepon?
Kami mengklaim itu log n, dan bahkan jika asing atau itu
sedikit kabur apa logaritma atau eksponen itu,
hanya ingat bahwa log n umumnya mengacu pada proses,
dalam hal ini, membagi sesuatu dalam setengah lagi, dan lagi,
dan lagi, dan lagi, sedemikian rupa sehingga mendapat semakin kecil seperti yang Anda lakukan itu.
>> Jadi log n mengacu, tentu saja, untuk contoh buku telepon,
dengan pencarian biner dalam teori, ketika kita memiliki pintu virtual pada papan,
atau ketika Sean adalah mencari sesuatu.
Jika dia menggunakan pencarian biner, log n akan menjadi batas atas berapa banyak
waktu yang dibutuhkan.
Tetapi orang-algoritma yang berlari di Log n diasumsikan kunci rinci apa?
Bahwa daftar diurutkan, kan?
Algoritma Anda salah jika input tidak diurutkan,
namun Anda menggunakan sesuatu seperti pencarian biner
karena Anda mungkin melompat hak atas elemen
tanpa disadari itu memang ada.
>> Sekarang apa artinya hal ini, O besar satu?
Ini tidak berarti bahwa algoritma Anda mengambil satu dan hanya satu langkah,
itu hanya berarti dibutuhkan jumlah konstan langkah.
Mungkin 1, mungkin itu 10, mungkin itu 1.000,
tapi itu independen ukuran masalah.
Tidak peduli seberapa besar n adalah, algoritma waktu yang konstan
selalu mengambil jumlah yang sama langkah.
Jadi apa yang mungkin menjadi algoritma kita bicarakan atau hanya
intuitif yang datang kepada Anda bahwa selalu berjalan dalam apa yang disebut konstanta waktu?
Ya?
>> AUDIENCE: Tambahkan dua angka.
SPEAKER: Tambahkan dua angka, 2 ditambah 2 sama dengan 4, dilakukan.
Sehingga mungkin bekerja, apa lagi?
Bagaimana tentang dunia yang lebih nyata, ya?
>> AUDIENCE: Menemukan Hal pertama dalam daftar.
SPEAKER: Menemukan pertama elemen dalam daftar, yakin.
Kami sudah benar-benar telah berbicara tentang array sudah,
bagaimana Anda mendapatkan di elemen pertama dalam array,
tidak peduli berapa lama array dalam kode C?
Anda hanya menggunakan seperti braket notasi nol, bam, Anda berada di sana.
Dan memang array, sebagai samping, Dukungan sesuatu umumnya dikenal
sebagai akses acak, akses random memori, karena Anda benar-benar dapat
melompat ke satu tempat.
Kita dapat melakukan hal ini bahkan lebih sederhana kita bisa mundur ke minggu nol
ketika kami melakukan Scratch.
Berapa banyak waktu yang dibutuhkan untuk mengatakan blok Scratch untuk mengeksekusi?
Hanya waktu yang konstan, kan?
Katakan sesuatu, katakan sesuatu, tidak peduli
bagaimana Goresan besar dunia adalah, selalu akan mengambil jumlah waktu yang sama
hanya mengatakan sesuatu.
>> Jadi itulah waktu yang konstan, tapi apa sisi lain?
Jika itu atas batas, bagaimana jika kita ingin
untuk menggambarkan batas bawah algoritma kami waktu berjalan?
Hampir kasus terbaik berpotensi, jika Anda mau,
meskipun hal ini bisa berlaku untuk terbaik kasus, kasus-kasus terburuk, kasus rata-rata lebih
umumnya, tapi mari kita fokus pada batas bawah lebih umum.
Apakah yang dimaksud dengan algoritma yang memiliki batas bawah dari langkah n,
atau langkah-langkah 2n, atau langkah-langkah 3n?
Beberapa faktor langkah n, itu lebih rendah terikat.
Ya?
>> AUDIENCE: Bubble sort?
>> SPEAKER: Bubble sort mengambil Anda langkah minimal n, mengapa?
Mengapa demikian?
Mengapa awal bahwa untuk datang kepada Anda intuitif, bahkan jika tidak hanya
belum?
Ya?
>> AUDIENCE: [Tak terdengar].
SPEAKER: Tepat.
Dalam skenario terbaik dari bubble sort, dan banyak algoritma,
jika saya menyerahkan delapan orang yang sudah diurutkan,
akan bodoh untuk Anda, algoritma,
untuk pergi bolak-balik lebih dari sekali, kan?
Karena segera setelah Anda berjalan melalui daftar sekali,
Anda harus menyadari, oh, aku tidak membuat swap, daftar ini diurutkan, keluar.
Tapi itu akan membawa Anda n langkah.
>> Dan sebaliknya, apa yang lain cara berpikir tentang hal itu?
Bubble sort adalah omega, sehingga untuk berbicara, dari n,
karena jika Anda melihat kurang dari n elemen, apa yang
adalah masalah mendasar di sana?
Anda tidak tahu apakah itu disortir, benar.
Kami manusia kekuatan melirik delapan orang dan menjadi seperti, oh, itu diurutkan,
yang tidak membawa saya n langkah, tapi itu.
Mata Anda, meskipun Anda jenis dari memiliki lapangan besar visi,
Anda melihat delapan elemen, Anda melihat delapan orang,
itu delapan langkah efektif.
Dan hanya jika saya berjalan melalui seluruh daftar yang saya menyadari, ya, diurutkan.
Jika saya berhenti di tengah jalan berpikir, semua benar, itu cukup diurutkan sejauh ini,
apa kemungkinan itu tidak diurutkan?
Bahwa algoritma tidak akan benar.
Mungkin lebih cepat, namun tidak tepat.
>> Jadi sekarang kita memiliki cara menggambarkan batas bawah,
dan bagaimana dengan waktu yang konstan?
Apakah yang dimaksud dengan algoritma yang memiliki lebih rendah terikat pada waktu yang berjalan dari satu?
1 langkah, 2 langkah, 10 langkah, tetapi konstan, independen n,
ukuran input?
Ya, di belakang.
>> AUDIENCE: printf?
SPEAKER: Apa itu?
AUDIENCE: printf?
SPEAKER: printf.
OK, yakin.
Jadi dibutuhkan sejumlah tetap langkah.
Dan saya harus sekarang-- sekarang kita sedang berbicara tentang kode C
, bukan Scratch, sesuatu seperti mengatakan, dengan printf,
kita harus mulai untuk mendapatkan hati.
Karena printf tidak mengambil masukan, itu string,
dan string yang secara teknis memiliki panjang.
Jadi jika sekarang kita ingin memilih pada Anda, jika Anda tidak keberatan,
secara teknis kita bisa berpendapat bahwa printf tidak mengambil panjang input variabel,
dan tentunya memakan waktu waktu untuk mencetak string panjang ini,
dari ini panjang.
>> Jadi bagaimana jika kita mempertimbangkan hanya pemilahan dan pencarian contoh?
Bagaimana dengan Mike Smith di telepon buku, atau pencarian biner lebih umum?
Dalam kasus terbaik, apa yang akan terjadi?
Saya membuka buku telepon dan, bam, ada nomor Mike Smith.
Aku bisa memanggilnya segera.
>> Mengambil satu langkah, mungkin dua langkah, tetapi sejumlah konstan langkah
jika aku beruntung.
Dan terus terang, kita melihat di Anda sekelas Senin
mendapatkan cukup beruntung dua kali berturut-turut.
Dan itu memang konstan waktu di batas bawah
pada algoritma tersebut untuk mencari nomor 50 di belakang mereka ditutup
pintu.
>> Sekarang, sebagai samping, jika Anda menemukan bahwa kedua O besar, batas atas,
dan omega, yang terikat lebih rendah, adalah satu dalam sama, bahwa
adalah rumus yang sama di kurung, Anda juga dapat
mengatakan, hanya untuk menjadi mewah, sesuatu yang di theta
n atau theta dari beberapa nilai lainnya.
Itu hanya berarti ketika besar O dan omega adalah sama.
Sekarang bagaimana selection sort?
Mari kita gunakan kosakata baru ini.
Dalam selection sort, apa yang kita melakukan lagi, dan lagi, dan lagi?
Aku akan bolak-balik melalui daftar, mencari siapa?
Jumlah terkecil.
>> Jadi berapa banyak langkah, bagaimana banyak perbandingan yang saya
harus membuat untuk mencari tahu siapa elemen terkecil dalam daftar itu?
n dikurangi 1, kan?
Karena jika saya hanya mulai dengan yang saya diberikan dan saya mulai membandingkan dia,
kemudian dia, dia atau dia, dia, saya
hanya bisa memasangkan elemen bersama-sama n dikurangi 1 kali.
Jadi selection sort sama membutuhkan n dikurangi 1 langkah pertama kalinya.
>> Berapa banyak langkah yang dibutuhkan saya untuk menemukan elemen terkecil kedua?
n minus 2, karena aku menjadi bodoh jika saya tetap melihat orang yang sama
lagi jika saya sudah memilih dia atau dia dan menempatkan mereka di tempat mereka.
Dan langkah ketiga, n minus 3, maka n minus 4.
Kami telah melihat pola ini sebelumnya, dan memang
selection sort sama memiliki batas atas
n kuadrat jika kita melakukan up penjumlahan itu.
Apa itu batas bawah, selection sort nya?
Minimal, berapa banyak waktu pemilihan harus semacam ambil, seperti yang kita mendefinisikannya pada hari Senin?
Mengusulkan dua pilihan.
Mungkin itu n, seperti sebelumnya.
Mungkin itu n kuadrat, karena sekarang sebagai batas atas.
>> AUDIENCE: n kuadrat.
SPEAKER: n kuadrat.
Mengapa?
>> AUDIENCE: Karena Anda memiliki untuk menentukan [Tak terdengar].
>> SPEAKER: Tepat.
Setidaknya seperti yang saya didefinisikan selection sort itu cukup naif, terus,
menemukan elemen terkecil.
Pergi lagi, cari elemen terkecil.
Tidak ada semacam optimasi di sana yang
mungkin membiarkan saya membatalkan setelah hanya n atau lebih langkah-langkah.
Jadi memang, pilihan semacam, omega n kuadrat.
>> Bagaimana dengan insertion sort, di mana aku mengambil siapa aku diberi, dan kemudian aku menjatuhkan dia
atau dia di tempat yang tepat?
Kemudian saya melanjutkan untuk orang kedua, menjatuhkan dia di tempat yang tepat.
Kemudian orang berikutnya, menjatuhkan dia di tempat yang tepat.
Perhatikan bahwa ini sangat linear, sehingga untuk berbicara.
Aku garis lurus, aku tidak akan bolak-balik,
Aku tidak pernah melihat ke belakang benar-benar, tapi apa yang terjadi ketika saya memasukkan dia
atau dia ke awal daftar seperti yang kita lakukan pada hari Senin?
Apa yang terjadi?
Ya?
AUDIENCE: [Tak terdengar].
SPEAKER: Ya, itu adalah menangkap, kan?
Anda mungkin ingat dari teman sekelas Anda, jika mereka
sedang membuat setiap gerakan dengan kaki mereka, itu adalah sebuah operasi.
Jadi jika ada tiga orang di sini dan orang baru milik jalan di sana,
pada tahapan yang panjang seperti ini, tentu saja, dia atau dia hanya bisa pergi sampai akhir.
Tetapi jika kita berpikir tentang komputer dan sebuah array dari memori,
orang-orang ini akan harus mengocok lebih
untuk memberikan ruang bagi orang itu.
Dan sehingga n dikurangi 1 shufflings, n minus 2 shufflings, n
minus 3 shufflings hanya jenis terjadi di belakang saya, bukan di depan saya
seperti sebelumnya, dalam arti tertentu.
Sekarang sebagai samping, dan sebagai Anda mungkin telah melihat secara online
jika Anda mulai mengaduk-aduk tentang macam, ada begitu banyak yang berbeda
di luar sana, beberapa dari mereka lebih baik daripada yang lain.
Memang, Bogosort adalah salah satu itu semacam menyenangkan untuk melihat ke atas.
Bogosort mengambil satu set nomor atau mengatakan setumpuk kartu,
acak mengocok mereka, dan memeriksa apakah mereka diurutkan.
Dan jika tidak, tidak lagi.
Jika tidak, tidak lagi.
Sangat bodoh.
>> Dan memang, jika Anda membaca seperti artikel Wikipedia,
nickname adalah semacam bodoh.
Ini akhirnya akan bekerja, mudah-mudahan, dengan waktu yang cukup,
tetapi jumlah waktu bisa mengambil beberapa waktu.
Jadi jika saya bisa, mari kita kecepatan hal naik dari contoh Mary Beth sebelumnya,
dengan memiliki unsur-unsur yang lebih sedikit, tapi dua prosesor yang lebih.
Dua orang, jika Anda tidak keberatan bergabung dengan saya.
Bagaimana 1 di sini, dan mari kita go-- ada orang di sana?
Tidak ada satu di sana?
OK.
Anda dengan hitam shirt, ya, datang pada turun.
Baiklah, siapa namamu?
>> AUDIENCE: Peter.
>> SPEAKER: Apa itu?
>> AUDIENCE: Peter.
SPEAKER: Peter, David, senang bertemu dengan Anda.
Baiklah, kita memiliki Petrus di sini, jika Anda ingin datang ke meja di sini.
Dan siapa namamu?
>> AUDIENCE: Elena.
SPEAKER: Elena.
OK, senang bertemu Anda.
Elena bertemu Peter.
Peter, Elena.
Dan kita harus Andrew di sini juga, silakan.
Dan tantangan Anda akan menjadi memilah setumpuk kartu.
Dan jika asing, dek kartu harus akhirnya
diurutkan sedikit sesuatu seperti ini di mana kita akan melakukan klub, maka
para sekop, maka hati dan berlian, dari ace sebagai satu,
semua jalan sampai ke raja.
>> Kartu Aku akan memberikan akan menjadi 52 dalam kuantitas.
Kita akan sama kali, hanya dalam beberapa saat.
Kita akan membuang Andrew di layar di sini,
sehingga untuk menonton saat Anda melakukan hal ini.
Dan sehingga semua ini semua lebih terlihat,
ini adalah kartu saya dapatkan di Amazon.
Jadi mereka sudah acak diurutkan, dan kita akan ke waktu Anda.
Dan kita akan tetap real time ini,
jadi kita akan mencoba untuk menekan Anda karena jika tidak hal ini akan membosankan
cepat.
Jika Anda bisa melanjutkan untuk menyortir 52 elemen bersama-sama melalui beberapa cara, sekarang.
>> Dan lagi, seperti yang kita menonton ini orang melakukan apa, pada akhirnya
akan menghasilkan yang jelas Hasilnya, pikirkan benar-benar
bagaimana mereka masing-masing melakukannya, bagaimana Anda bisa menggambarkannya.
Karena sekali lagi, ini adalah semua proses, algoritma
yang kita ambil untuk diberikan sebagai manusia.
Tapi Anda mungkin lama memiliki intuisi, jauh sebelum Anda bahkan
berpikir tentang mengambil ilmu komputer kelas Anda
mungkin memiliki intuisi dengan yang untuk memecahkan masalah seperti ini.
Tapi setelah Anda mengenali pola dan mulai
untuk merumuskan langkah-langkah dengan mana Anda memecahkan masalah ini,
Anda akan menemukan bahwa Anda dapat memecahkan banyak lebih menarik dan jauh lebih kompleks
masalah dengan cepat.
Jadi seseorang dari penonton, apa yang setidaknya satu elemen dari algoritma
bahwa mereka menggunakan di sini?
>> AUDIENCE: [Tak terdengar]
SPEAKER: Apa itu?
AUDIENCE: Dengan setelan.
SPEAKER: Dengan setelan.
Jadi pertama mereka mengelompokkan semua berlian bersama-sama
tampaknya, semua hati bersama-sama tampaknya,
dan sebagainya, tanpa rasa hormat untuk nomor pada kartu.
Dan sekarang mereka muncul, misalnya, untuk menyortir mereka dengan nomor.
Sangat bagus.
>> Baiklah, jadi apa yang akan menjadi langkah terakhir maka di sini?
Setelah kita memiliki empat sesuai diurutkan, apa yang perlu kita lakukan untuk empat tumpukan
untuk mencapai satu diurutkan deck, cukup sederhana?
Jadi kita perlu untuk menggabungkan mereka lagi.
>> Jadi ada ide yang menarik yang lagi, berani mengatakan, sangat intuitif bahkan
jika Anda mungkin pernah ditampar semacam label di atasnya.
Gagasan mendasar ini membagi masalah tidak dalam separuh waktu ini,
tapi setidaknya menjadi empat bagian.
Pemecahan cukup banyak masalah fundamental identik
dalam isolasi dari satu sama lain, dan kemudian menggabungkan hasilnya.
Dan, sangat baik, dilakukan.
Baiklah, putaran besar tepuk tangan, jika kita bisa.
>> [Tepuk Tangan]
>> SPEAKER: Aku tidak tahu apa yang akan Anda dengan ini, tapi di sini Anda pergi.
Terima kasih banyak.
Jadi mari kita lihat, dua menit dan delapan detik,
jika Anda ingin menantang teman Anda.
Lalu apa yang akan menjadi mengambil dari ini
bahwa kita dapat memanfaatkan lebih umum?
Nah, pikirkan kembali array ini angka,
dan berpikir kembali sekarang untuk beberapa pseudocode kita sudah ditulis di masa lalu,
dan ini adalah pseudocode untuk memecahkan masalah buku telepon.
Dimana dalam pseudo I disebutkan cara yang lebih metodis
menggambarkan bagaimana saya melakukan sangat intuitif Algoritma manusia membagi telepon
buku dua, ulangi, ulangi, ulangi, sampai aku menemukan seseorang seperti Mike Smith,
jika ia memang dalam buku telepon.
>> Tapi aku agak digunakan apa yang akan saya sebut pendekatan yang sangat berulang di sini,
dalam pemberitahuan tertentu baris 8 dan baris 11.
Mereka adalah bukti adanya berulang pendekatan, pendekatan perulangan,
karena itulah perilaku mereka menginduksi.
Mereka baris kedua mengatakan pergi ke jenis garis tiga, dan Anda dapat dari
memikirkan bahwa dalam Anda mata pikiran sebagai lingkaran.
Ini memberitahu Anda untuk pergi kembali ke langkah tiga dan ulangi, lagi, dan lagi,
dan lagi.
>> Tapi bagaimana kalau kita memanfaatkan ide kunci di sini bahwa kami tidak terakhir kali,
dan menyederhanakan jalur 8 dan baris 11 dan tetangga mereka
seperti ini saja, dengan warna kuning.
Ini tidak mendasar memperpendek pseudocode sangat banyak,
tapi itu fundamental mengubah sifat algoritma saya.
Apa yang saya katakan sekarang pada langkah 7, pada langkah 10,
adalah untuk mencari Mike dengan cara yang sama persis,
tetapi hanya di sebelah kiri setengah atau setengah benar.
>> Jadi dengan kata lain, jika Saya mulai dari langkah satu,
mengambil buku telepon, terbuka untuk tengah dari buku telepon, melihat nama,
jika Smith adalah salah Nama ini, sebut Mike, lain
jika Smith adalah awal buku, langkah tujuh mencari Mike di kiri setengah dari buku.
Tapi itu jenis terasa seperti itu meninggalkan aku menggantung, kan?
Dalam kuning, adalah instruksi, tapi bagaimana saya
mencari Mike di sebelah kiri setengah dari buku telepon?
Di mana saya memiliki algoritma dengan yang saya
dapat mencari seseorang seperti Mike Smith?
Yah, itu menatap wajah kita.
Aku benar-benar dapat menggunakan yang sama persis Program efektif naik ke atas
lagi dan re-berjalan baris kode yang sama.
>> Jadi meskipun ini harus merasa seperti sedikit definisi siklus
di mana Anda menjawab seseorang yang pertanyaan dengan hanya semacam meminta
pertanyaan yang sama lagi, seperti mengapa, mengapa, mengapa?
Kenyataannya adalah karena kita telah dikodekan keras beberapa jalur khusus, langkah 4,
yang merupakan jika, dan langkah 12, yang secara efektif cabang lain,
karena kita memiliki langkah-langkah pengganti sementara, algoritma ini akan berakhir jika kita
menemukan Mike, atau jika kita tidak.
Namun pada langkah 7 dan 10 sekarang, kami memiliki apa yang akan kita sebut algoritma rekursif.
Dan rekursi memang ide yang kuat itu pikiran sedikit membungkuk pada awalnya,
bahwa kita sekarang dapat menerapkan sebagai berikut.
>> Merge sort akan menjadi semacam terakhir yang kita melihat, setidaknya di kelas formal.
Dan secara fundamental berbeda dari tiga yang terakhir, dan tentu saja
empat jika kita termasuk Bogosort.
Berikut pseudocode untuk merge sort.
Ketika masukan dari elemen n, sehingga diberikan array berukuran n, jika n kurang dari 2,
kembali.
Jadi, mengapa aku memiliki kewarasan cek dulu?
Apa implikasinya jika saya tangan Anda array yang panjangnya n kurang dari 2?
Ini sudah disortir, jelas, kan?
Karena daftar baik memiliki satu elemen, yang sepele
diurutkan karena itu satu-satunya hal di sana.
Atau, itu ukuran nol yang berarti tidak ada untuk menyortir, sehingga oleh alam
itu disortir.
Hanya ada ada yang salah di sana.
Jadi itulah yang disebut kasus dasar kami.
>> Yang mirip dalam roh dengan apa yang kita lakukan dengan Mike.
Jika Mike dalam buku telepon, memanggilnya.
Jika dia tidak ada, menyerah.
Ini adalah kasus dasar yang disebut, untuk memastikan algoritma ini pada akhir hari
akan berhenti dalam keadaan tertentu.
>> Tapi di sini adalah lompatan iman sekarang, yang lain, mengurutkan kiri setengah dari unsur-unsur,
kemudian mengurutkan kanan setengah dari unsur-unsur,
dan kemudian menggabungkan bagian diurutkan.
Dan di sinilah rasanya seperti kita copping keluar.
Aku sudah meminta Anda untuk mengurut n elemen, dan aku
mengatakan, OK, lakukan dengan menyortir kiri dan menyortir kanan.
Tapi saya katakan satu Hal lain, dan ini
adalah tema kunci tampaknya di intuisi sejauh ini,
ada langkah ketiga ini penggabungan.
Yang meskipun tampak begitu bodoh dalam roh,
seperti hanya menggabungkan hal-hal bersama-sama, tampaknya
menjadi langkah kunci menuju reassembly dari dua masalah yang
dibagi akhirnya dua.
>> Jadi menggabungkan semacam, mari kita lakukan ini, jika Anda akan humor saya, dengan satu demonstrasi lagi,
hanya agar kita memiliki beberapa nomor untuk bekerja dengan.
Dapatkah saya menukar delapan stres bola untuk delapan orang?
Baiklah, bagaimana dengan Anda tiga, Anda empat dalam bagian ini, lima, enam, dan mari kita
jangan 7, 8, ayolah up.
OK, ya OK.
Minus 8, di sana kita pergi, ditambah 1.
Sangat baik.
Baiklah ayo, ayo cepat memberikan nomor.
Nomor dua, nomor tiga, nomor empat, nomor lima, enam, tujuh, dan delapan.
Saya melakukan delapan dengan benar saat ini.
>> OK, jadi pergi ke depan jika Anda bisa, dan mari kita mengurutkan dalam urutan asli
bahwa kami memiliki kemarin yang tampak seperti ini, jika Anda tidak keberatan.
Dan mari kita melakukannya di depan meja.
Baiklah, jadi menggabungkan semacam.
Ini adalah di mana itu akan untuk mendapatkan jenis yang menarik,
karena saya tampaknya memberi diriku begitu banyak informasi yang kurang hari ini.
>> Jadi menggabungkan semacam pertama-tama masukan dari elemen n,
dan jelas tidak kurang dari dua, itu delapan, jadi saya memiliki beberapa pekerjaan yang harus dilakukan.
Jadi sekarang mental kita sebagai kelas sekarang berada di cabang lain,
yang berarti tiga langkah.
Pertama, saya harus mengurutkan kiri setengah dari unsur-unsur.
Jadi bagaimana aku pergi tentang melakukan ini?
Yah, aku akan jenis mental membagi daftar di sini,
Anda tidak perlu secara fisik bergerak, dan aku
akan hanya fokus pada kiri setengah dari unsur-unsur di sini.
Jadi bagaimana aku pergi tentang menyortir daftar sekarang ukuran empat?
Apa algoritma saya?
Pertama saya memeriksa adalah n kurang dari dua, tidak, jadi saya melanjutkan ke lain blok lagi.
Urut meninggalkan setengah dari elemen.
>> Jadi sekarang lagi, mental, dan ini adalah di mana
Anda harus bertambah banyak sejarah mental, jika Anda mau.
Sekarang aku menyortir kiri setengah dari kiri setengah.
Baiklah, jadi sekarang saya sebut merge sama saya algoritma sorting, adalah n kurang dari dua?
Tidak, itu adalah dua, jadi aku harus memilah kiri setengah, dan bagian kanan.
Jadi di sini kita pergi, mengurutkan setengah kiri.
Mengapa Anda tidak hanya mengambil satu langkah maju.
Siapa nama Anda?
>> AUDIENCE: Darren.
>> SPEAKER: Dan.
Dan telah melangkah maju.
>> AUDIENCE: Darren.
SPEAKER: Darren, dilakukan.
Apakah Anda mengatakan Darren atau Dan?
>> AUDIENCE: Darren.
>> SPEAKER: Darren.
OK, Darren telah melangkah maju dan dia sekarang diurutkan.
Dan ini hampir klaim konyol, kan?
Aku tidak benar-benar tampaknya mencapai apa-apa, tapi mari kita lanjutkan.
Sekarang biarkan aku memilah hak setengah dari elemen.
Siapa nama Anda?
>> AUDIENCE: Lukas.
>> SPEAKER: Lukas.
Ayo, maju.
Selesai, saya telah diurutkan Luke.
Setengah kiri sekarang diurutkan dan bagian kanan sekarang diurutkan,
tapi sekali lagi, ada langkah kunci di sini.
Apa yang harus saya selanjutnya perlu dilakukan?
Menggabungkan bagian diurutkan.
Sekarang kita akan hanya memiliki semua orang bolak-balik dengan cara ini,
karena saya jenis kebutuhan beberapa ruang awal.
Ini hampir seperti ini orang ini di atas meja,
dan aku butuh kamar untuk memindahkan mereka sekitar pada.
Jadi aku akan menggabungkan kalian dengan melihat
di bagian kiri dan bagian kanan.
Dan yang jelas datang pertama, setengah kiri atau bagian kanan?
Jadi setengah benar, jadi mari kita lanjutkan Lukas lebih sini ke posisi semula Darren.
Dan sekarang untuk menggabungkan kiri setengah mereka, Darren akan bergerak di sana.
>> Jadi terasa seperti hampir efek bubble sort,
tapi algoritma dasar saya, sangat berbeda kali ini.
Tapi sekarang di mana hal-hal mendapatkan sedikit mengganggu karena Anda
harus mundur mental di mana aku meninggalkan dari.
Saya baru saja bergabung dengan bagian diurutkan, yang berarti aku mana dalam algoritma saya?
Saya harus memilah bagian kanan, kan?
>> Jika Anda mundur, secara harfiah pada video, Anda akan
melihat bahwa kita harus ini titik Lukas dan Darren
dengan menyortir kiri setengah dari kiri setengah.
Kemudian kami bergabung mereka bagian diurutkan, yang
berarti langkah selanjutnya adalah mengurutkan bagian kanan kiri setengah.
Baiklah, jadi mari kita melakukan hal ini lebih cepat.
Baiklah, enam, aku akan mengklaim Anda sekarang disortir, ayolah maju.
Siapa nama Anda?
>> AUDIENCE: Adriano.
>> SPEAKER: Adriano.
Adriano kini diurutkan.
Dan siapa namamu?
>> AUDIENCE: Alex.
>> SPEAKER: Alex sekarang diurutkan.
Setengah kiri, kanan setengah, apa langkah terakhir?
Merge.
Cukup sepele, jadi aku akan bergabung dalam enam,
mengambil langkah mundur, delapan, mengambil langkah mundur.
Dan sekarang melihat ini adalah takeaway berguna, apa
sekarang benar tentang setengah kiri daftar, terlepas dari bagaimana kita mulai?
Hal ini diurutkan.
>> Sekarang itu tidak diurutkan dalam skema besar hal,
tetapi diurutkan secara independen dari setengah lainnya.
Sekarang apa langkah aku pada jika aku terus memutar bagaimana cerita dimulai?
Sekarang aku harus mengurutkan bagian kanan.
Jadi sekarang kita jalan kembali pada awal cerita,
dan mari kita lakukan ini lebih cepat.
Jadi aku akan mengurutkan bagian kanan seluruh daftar.
Apa langkah selanjutnya?
Urutkan setengah kiri kanan setengah.
Urutkan setengah kiri kiri setengah dari bagian kanan.
Dan siapa namamu?
>> AUDIENCE: Omar.
>> SPEAKER: Omar, langkah maju, dilakukan.
Kiri setengah diurutkan.
Dan siapa namamu?
>> AUDIENCE: Chris.
>> SPEAKER: Chris, mengambil langkah ke depan, Anda sekarang disortir.
Apa langkah kunci sekarang?
Merge.
Jadi salah satu akan bergabung menjadi tempat di sini, jika Anda bisa mengambil langkah mundur,
dan tiga akan mengambil langkah mundur, bergabung.
Jadi setengah kiri setengah benar, sekarang diurutkan.
Terus terang, algoritma ini terasa seperti kita membuang-buang waktu cara yang lebih dari sebelumnya,
tetapi jika kita melakukan ini secara real time, kita akan melihat apa takeaways akan.
Sekarang saya di sini, tepat setengah dari bagian kanan,
biarkan aku pergi ke depan dan memilah kiri setengah.
Langkah ke depan, siapa namamu?
AUDIENCE: Ramsey.
SPEAKER: Ramsey sekarang diurutkan.
Siapa nama Anda?
>> AUDIENCE: Marina.
>> SPEAKER: Marina sekarang diurutkan sebagai baik, jika Anda mengambil satu langkah maju.
Langkah kunci di sini sekarang bergabung, aku akan memetik dari dua daftar saya,
kiri dan kanan.
Lima akan datang pertama, dan tujuh akan datang berikutnya.
Dan lagi, ini adalah disengaja.
Fakta bahwa mereka mengambil langkah ke depan dan belakang
dimaksudkan untuk menyatakan bahwa kita tidak bisa melakukan algoritma ini di tempat yang mudah
sebagai bubble sort, dan selection sort, dan insertion sort mana kita hanya
terus swapping orang.
Aku benar-benar butuh semacam sebuah kertas awal di mana
untuk menempatkan orang-orang ini sementara aku melakukan penggabungan,
dan kemudian saya bisa menempatkan mereka kembali di tempat.
Dan itulah kuncinya karena saya menggunakan sumber daya baru, ruang, bukan hanya waktu.
>> OK, ini luar biasa.
Setengah kiri diurutkan, bagian kanan adalah diurutkan, sekarang bahwa kunci penggabungan langkah.
Bagaimana aku bisa menggabungkan ini?
Jadi, jika Anda akan mengikuti saya tangan kiri dan tangan kanan,
Aku akan menunjukkan tangan kiriku di kiri setengah, tangan kananku
di bagian kanan, dan sekarang aku harus memutuskan langkah demi langkah yang bergabung dalam.
Yang jelas-jelas lebih dulu?
Nomor satu.
Jadi datang ke sini, inilah pad awal kami.
Jadi sekarang nomor satu, dan pemberitahuan apa yang akan saya lakukan dengan tangan kanan saya,
Aku akan memindahkan satu tangan kananku langkah di atas untuk menunjukkan nomor tiga,
dan sekarang saya harus membuat keputusan yang sama.
Dan benar-benar berdiri tepat di depan Lukas di sini jika Anda bisa,
karena ini adalah pad awal kami.
Jadi yang datang berikutnya?
Kami memiliki Lukas dengan nomor dua atau Chris dengan nomor tiga.
Jelas Lukas, jumlah dua, sehingga Anda datang ke sini.
>> Tapi tangan kiri saya sekarang akan bertambah untuk menunjuk Darren,
dan inilah kunci mengambil dengan penggabungan, aku akan terus melakukan hal ini,
jelas, jika Anda jenis dari mengikuti logika.
Tapi tangan saya tidak pernah akan pergi ke belakang,
yang berarti aku hanya pernah pindah ke kiri dengan proses penggabungan saya,
dan itu akan menjadi kunci untuk analisis kami hanya dalam beberapa saat.
>> Jadi sekarang mari kita selesaikan ini dengan cepat.
Jadi tiga datang berikutnya, kemudian empat datang berikutnya,
dan sekarang lima datang berikutnya, kemudian enam, dan tujuh, dan akhirnya delapan.
Terasa seperti algoritma paling lambat , tapi tidak jika kita benar-benar
menjalankannya pada jenis yang sama clock speed, sehingga untuk
berbicara, dengan sama berdetak jam seperti sebelumnya.
Mengapa?
Nah, Mari kita melihat hasil akhirnya.
>> Mari kita kembali ke sini, biarkan aku menarik demonstrasi visual
dari apa yang baru saja kita lakukan.
Memperbesar sini, hal ini Halaman di sini, mengatakan Firefox
bahwa kita ingin antrian di kotak ini, mari kita
mengatakan bubble sort, dengan yang kita sekarang baik akrab,
selection sort, yang lain cukup mudah satu,
dan sekarang semacam merge hari ini, yang akan berakhir klimaks kami.
Alasan butuh waktu lebih lama di sini dengan manusia dan saya secara lisan adalah,
jelas, aku menjelaskan setiap langkah.
Tapi jika Anda hanya menjalankan ini, banyak seperti yang kita lakukan bubble sort dan seleksi
semacam tidak hanya secara visual, menonton berapa banyak lebih efisien
leveraging ini divisi dan menaklukkan
dapat bila diterapkan pada kumpulan data yang bahkan ukuran delapan, tapi bahkan banyak,
jauh lebih besar.
Saya memberi Anda menggabungkan semacam, side by sisi dengan ini algoritma lainnya.
Ini akan mendapatkan menyakitkan cepat, dan mengakhiri
tidak terlalu klimaks, mereka hanya berakhir diurutkan.
Tetapi kuncinya mengambil adalah bahwa terlihat betapa cepat menggabungkan semacam
adalah, kecuali jika Anda pikir aku hanya jenis bermain-main dengan Anda.
Jika kita melakukan ini terakhir kali, mari ulang ini, mari kita kembali
dan memilih bubble sort, dan hanya untuk iseng,
mari kita memilih penyisipan semacam, hanya untuk mengukur baik.
Dan kali ini lagi, mari kita memilih merge sort dan mari kita
benar-benar menjalankan sisi ini berdampingan.
>> Dan itu tidak, pada kenyataannya, kebetulan.
Apa yang saya lakukan secara efektif adalah saya sudah dibagi masukan saya di setengah, sekali lagi,
dan lagi, dan lagi.
Dan hanya ada begitu banyak kali Anda bisa membagi masukan Anda menjadi dua bagian, kiri
dan kanan.
Apa formula yang kita terus melihat yang menggambarkan divisi dua
lagi, dan lagi, dan lagi, dan lagi?
>> AUDIENCE: Log n.
>> SPEAKER: Log n.
Tapi kemudian ada satu langkah penting lainnya, algoritma ini tidak log n langkah.
Jika hanya log n langkah, kami akan berada di masalah yang sama
seperti sebelumnya di mana kita tidak bisa yakin semuanya beres.
Anda harus minimal melihat elemen n untuk memastikan n elemen diurutkan,
jika itu adalah lompatan iman.
>> Jadi log n langkah minimal, tetapi bagaimana langkah penggabungan kunci
di mana saya bergabung setengah kiri dan kanan setengah dan berjalan melintasi panggung?
Berapa banyak langkah adalah bahwa untuk bergabung?
Ini n, tapi aku tidak hanya menggabungkan kalinya.
Pada masing-masing panggilan bersarang, pada masing-masing mereka gabungan bersarang, aku masih disortir.
Saya bergabung dua orang, maka kedua guys, maka dua orang dan sebagainya.
>> Jadi aku penggabungan lagi, dan lagi.
Berapa kali?
Jadi setiap kali saya membagi daftar di setengah, saya melakukan gabungan.
Bagilah daftar menjadi dua, melakukan penggabungan.
Jadi jika membagi daftar bisa dilakukan log n kali,
dan penggabungan akhirnya mengambil n langkah, apa yang mungkin sekarang atas
terikat pada running waktu algoritma kita?
n log n.
>> Dan memang, itulah yang kami raih di sini.
Jadi merasa bahwa Anda lihat secara visual ketika ketiga hal berjalan berdampingan
adalah n kuadrat terhadap n kuadrat terhadap n log n.
Yang pada dasarnya kita akan melihat, tidak hanya hari ini, tapi di masa depan,
jauh, jauh lebih cepat.
Sebuah tepuk tangan untuk orang-orang, Aku akan membalas mereka dengan bola stres.
Mari kita menunda sini hari ini, dan kita akan melihat Anda pada hari Senin.