>> [MUSIC PLAYING]
>> DAVID J. Malan: Ini adalah CS50.
Dan ini adalah awal minggu ketiga.
Jadi kita punya banyak menarik hal untuk menutupi hari ini.
Banyak peluang bagi relawan di atas panggung.
Dan akhirnya, hari ini adalah bukan tentang kode sama sekali.
Tapi itu tentang ide-ide, dan ini tentang algoritma,
dan benar-benar membawa kembali beberapa pelajaran dari seminggu nol,
dimana recall, kami diperkenalkan monstrositas ini.
Dan inspirasi pinjaman itu, untuk memulai
untuk memecahkan yang lebih canggih masalah algoritmik.
Tapi pertama, beberapa pengumuman.
Jadi satu, jika Anda ingin bergabung Staf CS50 dan teman sekelas saat makan siang
Jumat ini, baik di sini dan di Cambridge, dan di New Haven,
silahkan kunjungi saja ini website, di mana URL dapat ditemukan.
Kuliah Rabu ini akan tidak berada di sini di Sanders.
Ini akan online saja, jadi tune in di website CS50 ini,
apakah di sini di Cambridge atau New Haven juga.
>> Dan kemudian menetapkan dua masalah sudah di tangan Anda.
Jika Anda belum menyelam di belum, izinkan saya untuk menawarkan saran sangat bernada
itu, terutama sekarang, sebagai masalah set muka,
Anda benar-benar ingin memulai sekarang, jika tidak mencoba-coba sedikit di akhir pekan atau sebelum
ketika mereka pertama kali pergi keluar pada Jumat, karena Anda akan
menemukan bahwa mereka tidak selalu semakin panjang atau lebih menantang per
se.
Saya pikir Anda akan menemukan bahwa, di umum, mereka cenderung untuk mengambil sekitar
sekitar jumlah waktu yang sama.
Tapi itu tentu tergantung pada siswa, dan
tergantung pada pola pikir yang Anda mendekatinya.
Tapi selalu, Anda akan untuk menjalankan melawan beberapa dinding,
dan Anda akan memukul beberapa bug, dan Anda hanya
tidak akan mampu mendapatkan lebih dari itu di beberapa titik.
Dan itu sangat berharga untuk dapat untuk menjauh, kembali keesokan harinya,
pergi ke kantor jam, posting di CS50 Diskusikan atau sejenisnya, untuk benar-benar mendapatkan diblokir.
Jadi ingatlah bahwa dalam pikiran.
Mulai awal mungkin adalah hal terbaik yang dapat Anda lakukan.
Jadi di sinilah kita mulai kelas, lebih dalam seminggu nol.
Dan kita bisa mendapatkan sukarelawan di sini untuk membantu saya menemukan mic?
OKE.
Berdiri sudah.
Ayo up.
Rasa itu adalah bagaimana itu akan bekerja.
Siapa namamu?
ALAN ESTRADA: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Ayo up.
Senang berjumpa dengan mu.
ALAN ESTRADA: Senang bertemu Anda.
DAVID J. Malan: Dan kau ada di sini dengan kami dalam minggu nol, tentu saja.
ALAN ESTRADA: Saya.
Aku.
>> DAVID J. Malan: Jadi bisa Anda pergi depan dan menemukan untuk kita Mike Smith,
secepat yang Anda bisa?
Secepat Anda bisa.
Secara harfiah merobek masalah dalam setengah yang Anda butuhkan untuk.
>> ALAN ESTRADA: Um.
DAVID J. Malan: Secara harfiah merobek masalah di setengah.
>> ALAN ESTRADA: Oh.
Mm.
Sangat bagus.
>> DAVID J. Malan: OK.
Baik.
Terima kasih.
ALAN ESTRADA: Sangat baik.
OKE.
>> DAVID J. Malan: Dan sekarang, Anda telah dipangkas bawah
untuk setengah ukuran dari masalah.
Sekarang, kami turun ke seperempat.
Apakah Anda memperhatikan sisi mana kita menjaga?
>> [Tertawa]
>> ALAN ESTRADA: Ya, saya think--
>> DAVID J. Malan: Apa bagian kita di?
ALAN ESTRADA: muffler, jadi.
>> DAVID J. Malan: OK.
Tapi Mike Smith akan menjadi setelah muffler.
So--
>> [Tertawa]
>> Baiklah.
ALAN ESTRADA: Ke mana kita mencari?
DAVID J. Malan: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Malan: Sekarang, kita berada di bedah.
Sekarang, dokter.
Sekarang--
>> ALAN ESTRADA: Ayo- mari kita pergi dengan nyata.
Nyata.
>> DAVID J. Malan: Nyata.
OKE.
Jika Anda perlu nyata.
Sekarang, cara yang Mike Smith?
>> ALAN ESTRADA: cara ini.
>> DAVID J. Malan: cara mana?
ALAN ESTRADA: Tunggu.
M is-- tepat?
Kami mulai with--
>> DAVID J. Malan: Ya.
Mereka meninggalkan.
Kanan Anda.
>> ALAN ESTRADA: Ya.
>> DAVID J. Malan: Jadi Mike di sini.
ALAN ESTRADA: Apa?
>> [Tertawa]
>> Bad contoh, orang-orang.
Maaf.
DAVID J. Malan: ini akan mengajarkan Anda untuk melompat keluar dari kursi Anda.
>> ALAN ESTRADA: Oh.
Oh.
Aku mendapatkanmu.
Oh.
Ini is-- OK, saya punya Anda.
Smith di sini?
>> DAVID J. Malan: Smith, terima kasih.
Jadi saya akan terus mencari sampai Smith?
>> ALAN ESTRADA: Oh, ya.
Tidak tidak tidak.
Oh tidak.
Ini adalah milikku.
>> DAVID J. Malan: Oh, Anda punya Smith.
OKE.
>> ALAN ESTRADA: Ya, saya mendapat Smith di sini.
Maaf, guys.
Saya pikir kami Michael-- cari Michael.
Maaf.
>> DAVID J. Malan: Ini OK.
Baiklah, sekarang kita ke Paccini dan Sons.
>> ALAN ESTRADA: Paccini dan anak.
DAVID J. Malan: Hanya Anda dan aku berada di atas ini.
OKE.
Temukan kami Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. Malan: Smith.
Kami berada di R untuk sampah.
ALAN ESTRADA: Sampah.
Oh.
Ini akan memakan waktu cukup lama.
>> [Tertawa]
DAVID J. Malan: Sepatu.
Kami berada di sepatu.
>> ALAN ESTRADA: Sekarang kita gonna--
>> DAVID J. Malan: Nice.
ALAN ESTRADA: Which--
[Tertawa]
Oh, ini sangat bagus.
[Tertawa]
>> DAVID J. Malan: Ini OK.
>> ALAN ESTRADA: Oh, ini baik.
Saya tidak berpikir saya akan memiliki teman PSAT setelah ini.
DAVID J. Malan: Baik.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. Malan: OK.
Jadi mari kita merobek ini di setengah.
Tidak apa-apa.
Ini berakhir buruk pula, karena Mike Smith tidak akan di halaman kuning.
>> ALAN ESTRADA: Aw.
>> DAVID J. Malan: Tidak, itu OK.
Tapi mari kita berpura-pura seperti dia di halaman ini.
Jadi sekarang, Anda sudah dipangkas masalah turun untuk satu halaman, dan kami menemukan Mike Smith.
>> [Bersorak]
Ok Terima kasih.
OKE.
Itu luar biasa.
Tapi itu masih lebih cepat dari pencarian linear,
dimana kita mulai di mulai dari buku,
dan kita bergerak perjalanan dari kiri ke kanan, akhirnya mencari Mike Smith.
Dan, jika buku telepon telah mungkin 1.000 halaman,
mungkin itu akan diambil kita 10 atau lebih air mata halaman.
>> Tapi Anda mungkin telah memanfaatkan menyentuh asumsi
selama semua itu, yang mengatakan bahwa buku telepon di muka adalah apa?
AUDIENCE: Diurutkan.
DAVID J. Malan: Ini diurutkan.
Benar?
Ini diurutkan sesuai abjad, sehingga bahwa semua nama-nama dan nomor
diurutkan dari A ke Z, dan abjad di antara.
Tapi hari ini, kami sekarang bertanya pertanyaan, baik,
bagaimana melakukan Verizon atau telepon perusahaan mendapatkan ke negara itu?
>> Karena itu salah satu hal untuk meningkatkan asumsi itu, dan oleh karena itu,
memecahkan masalah dengan algoritma yang lebih efisien.
Tapi kita pernah benar-benar tanya minggu nol, baik,
berapa harganya Verizon atau orang lain
untuk mendapatkan buku telepon dalam rangka diurutkan?
>> Benar?
Tidak peduli jika mencari Mike Smith
super cepat, jika dibutuhkan Anda tahun untuk mengurutkan halaman awalnya.
Benar?
Anda mungkin juga hanya menyaring melalui buku telepon secara acak,
jika itu akan menjadi super mahal untuk mengatasinya.
Jadi jika kita dapat memiliki relawan lain.
Mari kita lihat di sini di bagaimana kita might-- datang pada up-- bagaimana
kita bisa pergi tentang pemilahan ini.
>> Dan jika Jordan benar-benar bisa bergabung dengan kami di sini di atas panggung.
Ayo up untuk sesaat.
Siapa namamu?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, datang ke atas.
Dan Anda akan bergabung oleh saya dan Yordania di sini.
Caroline, terima kasih.
Baiklah.
Jadi apa yang kita miliki di sini untuk Caroline adalah 26 buku biru
yang FAS menggunakan untuk mengelola ujian akhir tertentu.
Ini semakin sulit untuk menemukan, tapi apa yang kami lakukan di muka
adalah bahwa kami telah membuat nama seseorang di depan masing-masing,
tapi kami sudah terus itu sederhana oleh kemudian memadamkan nama lengkap.
Jadi kita akan menempatkan orang dengan nama L, D, J, B, semua jalan A sampai Z,
tapi mereka secara acak.
Dan jadi jika Anda akan, berbicara Anda jalan melalui masalah karena Anda
melakukannya, Anda dapat pergi ke depan dan memilah ini bagi kita, dari A sampai Z.
>> AUDIENCE: OK, jadi L adalah seperti, tengah.
C mulai.
B. J sebelum L. B, T.
>> DAVID J. Malan: Tahan yang berpikir untuk satu detik.
Karena jika tidak, ini hanya menarik untuk Anda, saya, dan Yordania.
Di sana kami pergi.
AUDIENCE: [tidak terdengar].
R.
DAVID J. Malan: OK.
Apa yang kamu lakukan?
>> CAROLINE: M datang setelah O.
>> DAVID J. Malan: OK.
>> CAROLINE: O.
DAVID J. Malan: O, baik.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Ya.
>> CAROLINE: T, U, V.
>> DAVID J. Malan: V, T, U, V. Jadi Sepertinya Anda making-- terus.
Sepertinya Anda membuat tumpukan besar di sini,
dan jenis tumpukan besar di sana.
Jadi paruh pertama dari alfabet, paruh kedua dari alfabet.
OKE.
Baik.
Jenis membelah masalah dalam dua.
M, N, X. Ya.
CAROLINE: K.
DAVID J. Malan: OK.
K. Jadi Anda memilih jenis mereka satu demi satu,
memasukkannya kiri atau kanan, atau Z akan di lantai.
OKE.
>> CAROLINE: Z akan di lantai.
>> DAVID J. Malan: OK.
Y akan di lantai.
Sekarang kita dapat menempatkan X.
>> CAROLINE: G.
DAVID J. Malan: G ke kiri.
S akan benar.
Baiklah, A akan semua jalan kiri.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Sekarang, baik.
Kami punya A, B, C. W akan ke sana.
Baiklah, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Baik.
CAROLINE: Di tengah, aku gonna--
DAVID J. Malan: OK.
Jadi sekarang, kita akan jenis dari menggabungkan berbagai tumpukan.
Jadi A sampai C, maka saya lihat A, dan E, dan F, dan G, dan H, dan I. bagus.
J, K. Dan kemudian, tumpukan ini terbalik, tapi itu OK.
Tentu.
Kita dapat memotong beberapa sudut.
OKE.
Dan kemudian kita perlu W, X, Y, Z.
>> CAROLINE: Ya.
>> DAVID J. Malan: Excellent.
Jadi terima kasih besar untuk Caroline untuk menyortir ini.
>> [Bersorak]
>> Terima kasih.
Terima kasih banyak.
Jadi sekarang mari kita mempertimbangkan sejenak bagaimana Caroline pergi tentang melakukan hal itu,
dan apa yang sebenarnya kita mampu to-- bagaimana kita
mampu memecahkan masalah ketika kami hanya
diberikan sejumlah besar input acak.
>> Nah, sepertinya ada adalah sedikit sistem sana?
Benar.
Jadi huruf sebelumnya dalam alfabet, ia
adalah menempatkan ke kiri, dan huruf kemudian dalam alfabet,
dia menempatkan ke kanan.
Dan segera setelah ia menemukan beberapa surat proksimal, yang
yang pergi tepat di samping satu sama lain, ia akan menempatkan orang-orang dalam rangka.
Dan jadi kami memiliki jenis ini kecil tumpukan input diurutkan terjadi.
>> Dan jadi itu cukup seperti apa kebanyakan dari kita manusia akan melakukan.
Kami akan semacam menyaring itu, dan kami akan jenis memiliki mekanisme.
Tapi mungkin akan sulit untuk menulis itu di formula per se.
Rasanya sedikit lebih organik dari itu.
Jadi mari kita lihat apakah kita sekarang dapat terikat masalah dengan input yang lebih sedikit.
>> Alih-alih 26, mari kita melakukan sesuatu jauh lebih sedikit
dengan hanya mengatakan, tujuh, di belakang pintu-pintu ini, sehingga untuk berbicara.
Apakah ada hanya tujuh angka?
Dan jika tujuan sekarang di tangan adalah untuk menemukan nilai,
mari kita lihat seberapa efisien kita bisa pergi untuk melakukan ini.
Dan mari kita lihat apakah sekarang kita bisa mulai menerapkan beberapa nomor,
atau beberapa rumus yang dapat digunakan untuk menggambarkan efisiensi buku telepon kami
algoritma, algoritma buku ujian kami, dan lebih umum, mencari informasi.
>> Jadi untuk ini, biarkan aku pergi ke depan, dan pada layar sentuh di sini,
memasang web browser yang memiliki persis tujuh pintu.
Dan jika kita bisa mendapatkan satu lainnya relawan untuk datang ke sini,
Aku telah menempatkan pintu-pintu yang sama di sini.
Relawan cepat.
>> Ini satu-- demo akan untuk lebih cepat dan lebih cepat sekarang.
Ayo turun.
Siapa namamu?
Trevor: Trevor.
>> DAVID J. Malan: Trevor?
Baiklah, Trevor, datang di bawah.
Jadi Trevor telah sukarela di sini untuk melakukan masalah yang sama, tapi satu yang
sempit dalam lingkup, dan itu akan untuk memungkinkan kita untuk mencoba untuk meresmikan sekarang
proses untuk menyortir angka-angka ini.
>> Jadi Trevor, senang bertemu Anda.
Jadi di sini adalah sebuah array, sehingga untuk berbicara, daftar tujuh pintu.
Pergi ke depan dan menemukan kami nomor 50.
Dan kemudian setelah fakta, memberitahu kami bagaimana Anda menemukannya.
Harus be---baik saja.
Ya, ini adalah satu di sini?
Uh oh.
OKE.
Anda mengklik satu itu.
Baik.
>> Dan baik.
Sekarang Anda mengklik satu itu.
Dan biarkan aku memberikan mikrofon, sehingga Anda memilikinya hanya dalam beberapa saat.
Pergi ke depan dan klik sebelah yang Anda berniat.
Ya baik.
Trevor: Dapatkah saya unclick pintu?
DAVID J. Malan: Tidak, Anda tidak bisa unclick.
Trevor: OK.
Yang ini.
DAVID J. Malan: Di mana Anda ingin pergi?
Pilih satu?
>> Trevor: Yang satu.
>> DAVID J. Malan: No.
>> Trevor: OK.
Yang ini.
>> DAVID J. Malan: Ya.
Itu bagus.
Baiklah.
Jadi apa yang algoritma atau Prosedur untuk melakukan hal ini, Trevor?
>> Trevor: Aku hanya pergi melalui pintu sampai aku menemukan 50.
DAVID J. Malan: OK.
Algoritma yang sangat baik.
Jadi itu bagus.
Karena pada kenyataannya, jika saya mengungkapkan apa yang balik dua pintu ini lain, apa
kita akan menemukan di sini adalah bahwa kita hanya memiliki input acak.
Jadi itu benar-benar sebagai baik karena Anda bisa mendapatkan.
Dan pada kenyataannya, Anda punya lebih baik dari mendalam mencari seluruh array,
karena telah benar-benar beruntung jika Anda telah memukul nomor
50 di pintu terakhir.
Tapi bagaimana kalau kita bukan memberi Anda sebuah asumsi.
Misalkan saya semacam semua pintu-pintu ini sekitar,
sehingga Anda memiliki nomor diurutkan saat ini,
tapi kali ini benar-benar sebuah different-- saat ini,
itu benar-benar diurutkan untuk Anda.
Dan sekarang tujuan di tangan adalah untuk memukul nomor 50.
>> Trevor: OK.
>> DAVID J. Malan: Apa algoritma Anda akan?
>> Trevor: Nah, jika itu diurutkan, itu baik akan
untuk be-- jika terbesar untuk terbesar, turun, itu akan menjadi yang pertama,
atau jika itu sebaliknya, itu akan menjadi yang terakhir.
Jadi saya hanya akan tekan pintu ini, dan kemudian hanya tekan pintu terakhir.
DAVID J. Malan: Excellent.
Baiklah.
Jadi kami menemukan nomor 50.
Jadi, segera setelah Anda tahu mereka diurutkan, kami
mampu memanfaatkan asumsi ini.
Jadi mereka terlalu banyak seperti contoh buku telepon.
Segera setelah Anda miliki, bahkan dengan masalah kecil seperti ini,
masukan Anda pra-disortir, kita bisa benar-benar menemukan nilai dibilang
lebih efisien.
>> Dan aku tidak memberitahu Anda jika itu diurutkan kecil ke besar, atau besar ke kecil,
dan itu sangat wajar untuk memulai di salah satu ujung atau yang lain
untuk benar-benar menemukan bahwa nilai target.
Jadi terima kasih kepada Trevor juga.
Dan aku akan propose-- baik dilakukan.
Kami memiliki klip kecil, sebenarnya, yang adalah salah momen favorit kami di CS50,
dimana kadang-kadang demo ini tidak cukup berjalan sesuai rencana.
Dan memang sekarang, saya menarik antarmuka yang salah
dengan yang menggunakan layar sentuh.
Jadi itu adalah kesalahan saya ada.
>> Jadi ini akan membuat klip tahun depan sebagai
mengapa saya mengklik layar saya sendiri.
Tapi mari kita lihat apa yang terjadi tahun lalu
dengan Jay, yang datang, banyak seperti Trevor sini, sukarela,
dan di klip pendek ini, Anda akan melihat bagaimana demo yang sama tidak cukup
mengungkapkan pelajaran yang sama belajar.
[VIDEO PLAYBACK]
-Semua Aku ingin kau lakukan sekarang adalah untuk menemukan bagi saya, dan bagi kita,
benar-benar, nomor 50 satu langkah pada satu waktu.
>> -The Nomor 50?
>> -The Nomor 50.
Dan Anda dapat mengungkapkan apa yang di balik setiap pintu ini
hanya dengan menyentuhnya dengan jari.
Kurang ajar.
>> [Tertawa]
>> [END PLAYBACK]
DAVID J. Malan: Jadi yang berjalan sangat baik.
Mereka adalah pintu disortir.
Dan Jay, tentu saja, menemukan itu semua terlalu cepat.
Trevor melakukan pekerjaan yang jauh lebih baik dalam hal saat mendidik,
sehingga untuk berbicara, tahun ini di waktu lebih lama untuk menemukannya.
Tentu saja, maka kita memberi Jay kesempatan kedua,
dimana kita diurutkan pintu, seperti yang kita lakukan untuk Trevor,
dan Trevor melakukan super baik kali ini.
Tapi Jay melakukannya setengah cepat.
[VIDEO PLAYBACK]
Tujuan -The sekarang adalah untuk juga menemukan kami nomor 50,
tapi melakukannya algorithmically, dan memberitahu kami bagaimana Anda akan hal itu.
>> -OKE.
>> -dan Jika Anda menemukannya, Anda tetap film.
Jika Anda tidak menemukannya, Anda memberikannya kembali.
>> -Man.
>> Oh!
>> - [Tak terdengar] OK.
Jadi aku akan memeriksa ujung pertama untuk menentukan apakah there's-- Oh.
>> [Tepuk Tangan]
>> [END PLAYBACK]
DAVID J. Malan: OK.
Jadi menyortir pintu jelas menyebabkan efisiensi yang lebih besar.
Dan, dua kali lebih cepat adalah apa yang saya berarti ada.
Dan Jay beruntung kedua kali.
Dan dia juga mendapat beruntung bahwa lalu tahun, saya memesan beberapa disk Blu-ray
untuk benar-benar memberikan.
Maaf tahun ini, kami tidak memiliki sama, Trevor.
Tapi lebih baik masih beberapa tahun yang lalu.
Dan beberapa dari Anda mungkin tahu ini sesama, Sean, yang ketika ia berada di CS50,
ditantang dengan tepat masalah yang sama, meskipun dalam SD,
Anda akan segera melihat, kembali pada hari.
Dan Anda akan menemukan bahwa tidak hanya ia mengambil sedikit lebih lama dari Jay,
sedikit lebih lama dari Trevor, itu sebenarnya kesempatan bagus ini
untuk terlibat hampir semua orang di kerumunan la Harga yang Tepat, mendorong
dia untuk menemukan nomor yang kita cari.
Mari. mengambil cepat.
>> [VIDEO PLAYBACK]
>> -OKE.
Jadi tugas Anda di sini, Sean, adalah sebagai berikut.
Saya telah tersembunyi di balik ini pintu nomor tujuh.
Tapi terselip di beberapa pintu ini serta yang angka negatif lainnya.
Dan tujuan Anda adalah untuk berpikir dari baris atas ini angka
hanya sebagai sebuah array, atau hanya urutan lembar kertas
dengan angka di belakang mereka.
Dan tujuan Anda adalah, hanya menggunakan bagian atas Array sini, saya menemukan nomor tujuh.
Dan kita kemudian akan mengkritik bagaimana Anda pergi tentang melakukannya.
-Baiklah.
-Cari Kami nomor tujuh, silakan.
Tidak.
Lima, 19, 13.
>> [Tertawa]
>> Ini bukan pertanyaan jebakan.
Satu.
>> [Tertawa]
Pada titik ini, skor Anda tidak sangat baik, sehingga Anda mungkin juga terus berjalan.
Tiga.
>> [Tertawa]
>> Pergi.
Terus terang, saya tidak bisa tidak bertanya-tanya apa yang Anda bahkan berpikir tentang, so--
>> [Tertawa]
Hanya baris atas, sehingga Anda punya tiga kiri.
Jadi menemukan saya tujuh.
>> [Tertawa]
17.
Tujuh.
>> [Tepuk Tangan]
>> Baiklah.
>> [END PLAYBACK]
>> DAVID J. Malan: Jadi kita bisa menonton ini sepanjang hari.
Dan tentu saja, beberapa demo tahun ini mungkin
sekarang akan berakhir di depan Video tahun juga.
Jadi sekarang mari kita sebenarnya fokus pada algoritma
di sini, dan melihat apakah kita tidak bisa sekarang mulai untuk meresmikan
bagaimana kita bisa pergi tentang mendapatkan data kami ke negara ini bahwa itu diurutkan,
sehingga pada akhirnya, kita dapat benar-benar mencari lebih efisien.
Dan meskipun kita akan menggunakan data set yang cukup kecil,
seperti delapan nomor kami miliki di sini di papan,
akhirnya ide-ide yang sama bisa berlaku 1.000 input, satu juta masukan,
4 miliar masukan, karena algoritma akan menjadi dasarnya sama.
>> Dan jadi ini adalah kami terakhir kesempatan bagi relawan hari ini,
tapi mungkin yang paling terlibat satu, yang kami butuhkan delapan relawan
untuk datang dan berjalan kita melalui Proses pemilahan apa yang akan segera
berada di musik ini berdiri di sini.
Mari saya mulai kembali ke sini.
>> Jadi satu di hijau turquoise-- itu?
Apakah Anda melakukan?
Dua.
Ayo turun.
OKE.
Tiga.
Empat.
Biarkan me-- OK, lima.
Anda sedang dicalonkan oleh teman Anda.
Enam, tujuh, dan delapan.
Ayo up.
Baiklah.
Terima kasih banyak.
Ayo up.
>> Baiklah.
Jadi apa yang kita miliki di sini-dan ini adalah di antara yang lebih canggung,
karena ini akan mengharuskan Anda humor saya hanya sedikit waktu.
Anda harus menjadi nomor satu.
Siapa namamu?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
David.
Siapa namamu?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, Anda nomor dua.
>> SERENA: Serena, nomor tiga.
Stefan, nomor empat.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, nomor lima.
[Tidak terdengar]
DAVID J. Malan: [tidak terdengar].
David, nomor enam.
MATT: Matt.
DAVID J. Malan: Matt nomor tujuh.
Dan?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, nomor delapan.
Baiklah.
Jika Anda could-- whoops.
Jika Anda semua, sebagai Anda Tantangan pertama, ada
delapan berdiri musik di sini menghadap penonton.
Jika Anda dapat menempatkan Anda pada nomor musik ini berdiri sedemikian rupa
bahwa mereka berbaris dengan nomor yang sama di papan tulis.
Sehingga membuat dirimu terlihat seperti itu oleh menempatkan nomor Anda pada musik ini
berdiri di sini.
Sangat baik sejauh ini.
>> Sangat baik.
OKE.
Jadi sekarang, kita akan meminta pertanyaan dalam beberapa cara yang berbeda.
Bagaimana kita bisa pergi tentang pemilahan orang-orang ini di sini?
Karena kami memiliki beberapa pendekatan sebelumnya, dimana kami
jenis membuat dua ember yang berbeda.
Dan kemudian kami umumnya piecing sesuatu bersama-sama.
Segera setelah kami melihat dua angka milik bersama,
kita menempatkan mereka bersama-sama.
Dua surat yang dimiliki bersama-sama.
>> Tapi mari kita lihat apakah kita tidak dapat memformalkan ini,
sehingga kita akhirnya memiliki beberapa pseudo-kode Anda akan,
dengan mana Anda dapat memecahkan masalah ini.
Jadi sekarang, aku melihat keluar di nomor ini di sini.
Dan saya melihat sejumlah besar kesalahan.
Pada akhirnya, saya ingin satu di kiri dan delapan di sebelah kanan.
>> Dan jadi saya sedang melihat dua, empat dan dua.
Dan apa masalahnya, jelas?
Ya.
So.
Dua jelas datang sebelum empat, sehingga Anda tahu apa?
Mari saya pertama mengambil pendekatan serakah, jika Anda mau, banyak masalah seperti
mengatur satu-- jika Anda ingat dari Standard Edition Masalah Set Satu,
di mana saya hanya secara lokal memecahkan masalah itu di sini, di depan saya
dan melihat di mana itu mengarah padaku.
>> OKE.
Jadi dua dan empat, biarkan aku pergi depan dan hanya swap kalian berdua.
Jika Anda secara fisik dapat bergerak dirimu dan kertas Anda,
Saya tampaknya telah mendapat daftar dalam keadaan yang lebih baik.
>> Sekarang, mereka baik.
Aku akan pindah, empat dan enam, terlihat baik.
Bukan masalah.
Enam dan delapan, OK.
Delapan dan satu, masalah lain.
Karena apa yang benar sekitar delapan dan satu?
Satu datang sebelum delapan, dan jadi apa yang harus kita lakukan?
Mari kita swap dua ini.
Satu dan delapan.
Dan sekarang, aku akan terus berjalan.
Aku akan terus melihat ke depan.
Dan mari kita lihat apa yang terjadi.
Delapan dan tiga, dari Tentu saja, rusak.
Mari kita swap.
Delapan dan tujuh, tentu saja.
Habis.
Mari kita swap.
Delapan dan lima, tentu saja, mari kita swap.
Baiklah.
Daftar diurutkan.
iya nih?
>> OK, jelas tidak.
Tapi itu sedikit lebih baik, kan?
Karena pemberitahuan apa yang terjadi.
Setiap kali kita melakukan swap, lebih kecil jumlah jenis saring seperti itu,
dan sejumlah besar saring dengan cara ini, atau kita akan
mulai pepatah menggelegak ke kiri atau menggelegak ke kanan.
>> Sekarang, itu tidak cukup, karena yang terbaik nomor mungkin
telah pindah satu tempat maju, atau paling buruk,
nomor mungkin memiliki pindah satu tempat lebih lanjut.
Sehingga Anda tahu apa, jenis dari bekerja cukup baik sejauh ini.
Saya hanya mencoba lagi.
Dua dan empat, mereka OK.
Empat dan enam, mereka OK.
Enam dan satu, rusak.
Jadi mari kita bertukar kalian berdua.
Dan sekarang, melihat masalah ini mulai mendapatkan sedikit lebih baik lagi.
Enam dan tiga, rusak.
Mari kita bertukar Anda dua.
Enam dan tujuh, Anda baik.
Tujuh dan lima, tentu saja, rusak.
Tujuh dan delapan, dalam rangka.
Dan sekarang, aku mungkin perlu melakukan hal ini beberapa kali.
Dan pada kenyataannya, berpikir untuk diri sendiri mungkin berapa kali maksimal
mungkin saya harus berjalan bolak-balik?
>> Kami akan kembali ke itu.
Jadi dua dan empat masih OK.
Empat dan satu, nggak.
Jadi, mari kita swap.
Dan lagi, melihat secara visual satu jenis gelembung
ke kiri, di mana seharusnya.
Empat dan tiga swap.
Empat dan enam.
Enam dan lima swap.
Enam dan tujuh.
Tujuh dan delapan adalah baik.
>> Baik.
Kami mendapatkan lebih baik.
Jadi mari kita lihat.
Sekarang, kita memiliki dua dan satu.
Tentu saja, menukar.
Dua dan tiga, tiga dan empat, empat dan lima, enam dan tujuh, tujuh dan delapan.
Baik.
Dan kau tahu apa?
Karena saya membuat satu perubahan di sana, biarkan aku melakukan satu kewarasan cek.
Biarkan aku pergi semua jalan kembali ke awal.
OKE.
Satu, two-- yup, lihat?
Ada sesuatu yang salah.
Tiga, empat, lima, enam, tujuh, delapan.
Dan di lulus terakhir ini, adalah Anda nyaman dengan sekarang saya
mengklaim itu diurutkan?
OKE.
Visual, itu benar-benar benar.
Tapi fungsional, apa tidak juga hanya terjadi
dalam lulus terakhir yang memungkinkan Anda mengkonfirmasi bahwa daftar ini memang
diurutkan?
>> Apa yang saya lakukan atau tidak lakukan lulus terakhir ini?
AUDIENCE: Tidak ada perubahan.
DAVID J. Malan: Maaf?
AUDIENCE: Tidak ada perubahan.
DAVID J. Malan: Tidak ada perubahan.
Sehingga akan bodoh saya untuk melakukannya algoritma yang sama lagi
jika saya tidak melakukan perubahan pertama kalinya.
Dan negara tidak berubah.
Tentunya, saya tidak akan membuat setiap perubahan kedua kalinya.
Dan, itu aman sekarang mengatakan, daftar diurutkan.
>> Dan memang, ini sekarang sesuatu yang kita akan umumnya
panggilan bubble sort, dimana berpasangan, Anda memperbaiki kesalahan lagi,
dan lagi, dan lagi, dan Anda terus bolak-balik,
dan bolak-balik, sampai Anda tidak membuat swap tersebut, di mana titik
Anda dapat yakin, yeah, aku selesai memperbaiki semua kesalahan.
Mari kita ulang dan mencoba pendekatan lain.
Jika kalian bisa kembali ke pesanan Anda saat yang lalu,
yang tampak seperti ini.
Sekarang, mari kita mengambil pendekatan yang sedikit lebih seperti buku ujian,
dimana kami terus-menerus memilih huruf alfabet
bahwa kita seperti ingin untuk menangani berikutnya.
Mungkin itu surat tinggi, seperti A, atau surat Z. rendah
>> Jadi semua orang kembali urutan ini.
Dan sekarang biarkan aku melakukan ini.
Mari kita lihat saya tahu saya harus delapan angka di sini.
Aku akan pergi ke depan dan hanya sengaja pilih
elemen terkecil.
Benar?
Hal ini tampaknya intuitif juga.
Mengapa saya tidak menemukan terkecil elemen, meletakkannya di tempatnya,
kemudian mendapatkan elemen terkecil berikutnya, menempatkan itu tempatnya, dan hanya mengulang.
>> Karena secara intuitif, yang harus bekerja juga.
Jadi empat, itu jumlah yang cukup kecil.
Aku akan mengingat di mana ini.
Tunggu sebentar.
Dua lebih kecil.
Sekarang saya ingat di mana dua adalah, dan melupakan empat.
Kami akan berurusan dengan itu nanti.
Enam, aku tidak tertarik.
Delapan, aku tidak tertarik.
Salah satunya adalah sejumlah kecil baru saya.
Jadi aku akan ingat di mana satu.
Tiga, tidak tertarik.
Tujuh, tidak tertarik.
Lima, tidak tertarik.
>> Jadi tanpa jatuh tahap tahun ini,
Aku akan ambil nomor satu-- dan apa nama Anda lagi?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Dan jika Anda bisa bergabung dengan saya di awal daftar,
mari kita menempatkan Anda di mana Anda berada.
Unfortunately-- siapa namamu?
>> STEFAN: Stefan.
>> DAVID J. Malan: Stefan adalah di jalan.
Jadi sebelum Stefan memecahkan ini masalah, apa yang harus kita lakukan?
Apa yang kita lakukan dengan Stefan?
>> AUDIENCE: [tidak terdengar].
DAVID J. Malan: OK.
Jadi kita bisa melakukan itu.
Kita bisa semacam mengambil Stefan dan nya empat, dan hanya menaruhnya dalam variabel
dan berpegang pada itu untuk beberapa jumlah waktu,
sehingga membuat ruang untuk nomor satu.
Dan itu tidak buruk.
Saya bisa menyarankan, mengapa tidak melakukan kita hanya menempatkan Stefan di sini?
Mengapa ini mungkin melanggar satu dari ide-ide kami mulai
berbicara tentang terakhir kali, minggu lalu?
Ya?
>> AUDIENCE: [tidak terdengar].
>> DAVID J. Malan: Tidak ada indeks untuk itu.
Jika Anda berpikir tentang hal ini, memang, sebagai array, ini seperti satu negatif,
jadi tidak ada memori sebenarnya sini jika ini memang sebuah array,
seperti kita menyatakan pekan lalu dalam kuliah.
Jadi kita tidak harus melakukan ini.
Kita mungkin menyimpannya dalam variabel.
>> Atau Anda tahu apa?
Aku mendengar orang lain menyarankan itu.
Apa lagi yang bisa kita lakukan dengan Stefan?
Mengapa kita tidak hanya mengusir dia dan menempatkan dia lebih di mana nomor satu adalah.
Jadi jika Anda ingin pergi ke sana.
Dan memang, ini adalah solusi yang cukup baik.
Sekarang di satu sisi, saya sudah baik dari membuat masalah lebih buruk.
Empat sekarang lebih jauh dari mana seharusnya.
Itu harus menuju setengah ini.
>> Tapi kau tahu apa?
Yang bisa saja nasib buruk.
Mungkin nomor delapan di sini.
Dan, mungkin kita akan mendapatkan beruntung,
dan mendorong delapan mendekati akhir.
Jadi pada akhir hari, itu jenis semua rata-rata keluar.
Kami tidak perlu peduli empat.
Semua saya peduli sekarang adalah memilih elemen terkecil.
>> Dan sekarang, apa yang akan saya lakukan adalah melupakan nomor satu
permanen, karena saya tahu Daftar di belakang saya sekarang diurutkan.
Jadi daftar saya sebelumnya ukuran delapan.
Sekarang, itu ukuran tujuh.
Jadi masalah saya adalah mendapatkan lebih kecil, meskipun secara linear.
Jadi sekarang, aku akan memilih elemen terkecil saat ini, dua.
Enam, delapan, empat, tiga, tujuh, lima.
Itu adalah elemen terkecil.
Jadi apa yang harus saya lakukan with-- apa nama Anda lagi?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph?
Kita akan meninggalkan Yusuf di tempat.
Sekarang, aku akan berpura-pura bahwa orang-orang are-- baik,
Saya tahu bahwa kedua sudah diurutkan.
Sekarang mari kita fokus pada sisa daftar.
Enam adalah yang terkecil saat ini.
Delapan lebih besar.
Empat sekarang terkecil saat ini.
Tiga sekarang terkecil saat ini.
Dan sekarang, aku akan memilih tiga, yang is-- apa nama Anda lagi?
SERENA: Serena.
DAVID J. Malan: Serena, jika Anda bisa ambil nomor Anda dan pertukaran with--
Kalsang: Kalsang.
DAVID J. Malan: Kalsang.
Ayo kembali, dan kami akan menukar dua.
Dan sekarang, mari kita menempatkan ini autopilot.
Aku akan pergi dan meninggalkannya untuk kalian untuk memilih elemen terkecil berikutnya.
Dun, dun, dun, dun.
Nomor empat, apa yang harus Anda lakukan?
Sangat baik.
Sekarang, aku akan membuat lulus lain.
Dun, dun, dun, dun.
Saya melihat lima adalah yang terkecil berikutnya.
Sekarang, aku akan mengambil lulus lain.
Dun, dun, dun, dun.
Enam adalah yang terkecil.
Baik.
Tujuh adalah yang terkecil.
Tidak ada perubahan.
Delapan adalah yang terkecil.
Dilakukan.
>> Jadi apa yang baru saja kita lakukan dengan iteratif memilih salah satu elemen demi satu
adalah melaksanakan sesuatu yang kita akan meresmikan sebagai semacam seleksi.
Dan itu bahkan mungkin sederhana untuk menjelaskan,
di yang benar-benar semua yang Anda ingin lakukan adalah terus
akan bolak-balik melalui daftar memilih, elemen terkecil berikutnya,
sampai selesai.
>> Jadi itu lebih sederhana, mungkin intuitif, dari terakhir.
Mari kita coba satu yang terakhir.
Jika kalian bisa me-reset sendiri dalam posisi sebagai berikut
satu waktu akhir, mari kita lihat apakah kita tidak bisa sekarang meresmikan satu pendekatan lainnya.
Bahkan, akan seseorang di luar sana ingin mengusulkan
bagaimana lagi kita bisa pergi untuk melakukan ini?
Tanpa melemparkan keluar istilah-istilah atau semacam dari jawaban yang sudah dikenal,
hanya intuitif, apa yang bisa kita lakukan?
>> AUDIENCE: [tidak terdengar].
DAVID J. Malan: Ya.
Jadi ada beberapa intuisi yang besar di sana.
Hal-hal baik tampaknya terjadi sejauh dalam ilmu komputer ketika kita membagi
dan menaklukkan masalah membagi dalam setengah dan setengah setengah.
Dan memang, kita bisa mulai untuk melakukan itu.
Dan pada kenyataannya, itu akan menjadi, kami akan melihat, salah satu solusi terbaik kita belum.
Tapi mari kita kembali ke yang lama.
Bahkan, kami akan melakukan yang sedikit akhir pekan ini.
Apa lagi yang bisa kita lakukan untuk mengatasi ini?
Jadi semua orang di sini di Agar acak.
Kamu tahu apa?
Daripada bolak-balik, bolak-balik, bolak-balik
setiap kali, ini terasa seperti Aku melakukan banyak berjalan.
Kenapa tidak aku hanya mulai dari awal daftar,
dan hanya menempatkan empat tempatnya?
Jadi biarkan aku berasumsi untuk saat ini yang daftar saya hanya elemen pertama ini.
Apakah empat diurutkan pada saat ini dalam waktu, jika semua yang saya pedulikan adalah segala sesuatu di sini?
Ini adalah semacam sepele benar, kan?
Seperti daftar yang berisi satu nomor, dan yang nomor empat jelas diurutkan.
>> Jadi saya hanya menetapkan bahwa daftar ini diurutkan.
Tapi sekarang aku punya sisa daftar ini.
Jadi sekarang, saya menemukan dua.
Mana dua jelas milik sehubungan dengan empat?
Sebelum empat.
Jadi apa yang bisa saya lakukan di sini?
Apa nama Anda lagi?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, jika Anda bisa melangkah mundur
hanya sejenak dengan nomor Anda.
Dan sekarang apa yang harus Stefan lakukan di sini?
Mari kita bergeser Stefan di sini.
Dan sekarang, biarkan Joseph datang ke sini.
Dan sekarang, biarkan saya menyatakan bahwa semuanya di sini diurutkan.
Jadi, hasil yang serupa, tetapi Pendekatan yang berbeda secara fundamental.
Aku bahkan tidak melihat apa yang ada di bawah sana.
Aku hanya terus mengambil unsur-unsur karena mereka diserahkan kepada saya,
dan berurusan dengan mereka.
>> Jadi sekarang, saya melihat nomor enam.
Di mana nomor enam milik?
Kami memiliki dua, empat, enam.
Persis di mana dia sekarang.
Jadi mari kita tinggalkan itu saja, dan sekarang mengklaim bahwa ini bagian dari daftar
sekarang diurutkan.
Dan, ini terasa fundamental berbeda dalam bahwa aku hanya
bergerak melalui daftar di sini linear, dan aku tidak pernah dua kali lipat kembali.
Iya nih.
Baiklah.
Jadi delapan, di mana Anda berada?
Disini.
Sempurna.
Jadi sekarang, satu.
Uh oh.
Ini terasa seperti itu akan menjadi mahal.
Sekarang, dalam algoritma sebelumnya, Aku hanya bertukar orang.
Jadi saya mungkin menempatkan dia semua jalan di awalnya, tetapi kemudian pindah Joseph.
Tetapi jika saya pindah Joseph, sekarang apa yang akan menjadi salah?
>> Sekarang, saya sudah semacam undone-- saya sudah mengambil satu langkah maju dan kemudian
satu langkah mundur, karena sekarang Joseph akan rusak.
Jadi mari kita lakukan ini.
Jika Anda bisa mengambil nomor satu dan melangkah mundur untuk sesaat.
Bagaimana kita bisa put-- apa adalah nama Anda lagi?
>> Annan: Annan.
>> DAVID J. Malan: Annan di tempat?
Apa yang harus terjadi dengan hormat dua, empat, enam, dan delapan?
Mereka semua perlu menggeser.
Jadi jika delapan ingin menggeser pertama, kemudian enam, lalu empat, lalu dua.
Dan kemudian Annan, jika Anda akan ingin datang ke sini, baik.
Tapi di sini, kita baru saja jenis membayar harga
pada titik yang berbeda dalam algoritma.
Sedangkan terakhir kali dengan pilihan macam, dan bahkan bubble sort,
Aku berjalan kembali dan balik, bolak-balik,
yang tentunya menambahkan waktu-bijaksana, dan secara harfiah bertahap.
>> Insertion sort, pada awalnya Sekilas, tampak seperti itu
Super cerdas, bahwa aku hanya membuat lambat, kemajuan bertahap,
tapi aku tidak akan ini bolak-balik.
Tetapi jika seseorang memang rusak, pemberitahuan
semua pekerjaan saya hanya harus melakukan.
Aku harus bergerak setengah dari daftar hanya untuk membuat ruang untuk nomor satu.
Jadi jumlah yang sama kerja sejauh itu
terasa, hanya berbagai jenis pekerjaan.
>> Ayo lanjutkan.
Jadi sekarang kita tahu bahwa setiap orang antara satu dan delapan diurutkan.
Di sini, saya punya nomor tiga.
Jika Anda ingin mengambil nomor tiga, mundur satu.
Dan apa yang harus kalian lakukan?
Yep.
Jadi itu satu sama lain, dua, tiga langkah.
Tiga unit waktu yang hanya biaya saya, sehingga tiga bisa sekarang cocok.
Akhirnya, tujuh.
>> Mari kita pergi ke depan dan memiliki Anda mengambil langkah mundur.
Ini hanya akan biaya kami satu satuan waktu, tapi itu OK.
Dan sekarang, lima yang akan menjadi sedikit lebih mahal.
Jika Anda ingin mundur.
Kita perlu bergerak delapan, dan tujuh, dan enam.
Dan kemudian semua orang sekarang diurutkan.
Jadi andil besar untuk relawan kami di sini.
Terima kasih banyak.
>> [Tepuk Tangan]
>> Terima kasih semua.
Terima kasih semua.
Jadi mari kita lihat sekarang betapa mahal semua itu.
Mari kita pertimbangkan mungkin sederhana ini, bubble sort.
Dan saya katakan sederhana, hanya karena Anda bisa mengatasinya dengan hanya rakus
memperbaiki masalah berpasangan sini.
Memperbaiki masalah berpasangan di sini, lagi dan lagi
dan lagi, mengulang sebanyak kali Anda benar-benar perlu.
>> Jadi ternyata bahwa dengan semacam gelembung, baik,
berapa banyak langkah yang harus saya mengambil lulus pertama dari algoritma itu?
Aku mungkin take-- mari see-- satu, dua, tiga, empat, lima, enam, tujuh.
Dan ada delapan elemen di sini.
Jadi seperti n minus 1 langkah untuk dapatkan dari awal daftar
ke akhir daftar.
>> Tapi dengan pilihan semacam, ingat bahwa aku memilih elemen lagi dan lagi
dan lagi itu terkecil, Aku meletakkan di tempat,
tapi kemudian aku tidak melihat ke belakang lagi.
Jadi saya pikir itu sedikit lebih jelas maka yang pertama kali, aku mungkin
harus mengambil semua n minus 1 langkah untuk menemukan elemen terkecil.
Kemudian saya menempatkan mereka di tempat, dan saya mengusir siapa pun yang ada di sini sebelumnya.
>> Tapi kemudian saya tidak perlu terus melihat elemen ini,
karena saya tahu itu sudah terkecil.
Jadi sekarang, saya dapat melihat hanya tujuh elemen, kemudian enam elemen,
kemudian lima elemen, maka empat elemen.
Dan matematis, jika n adalah jumlah elemen atau nomor
yang kami mulai dengan, Anda bisa membayangkan bahwa ini adalah sama dengan n minus 1,
ditambah n minus 2 langkah, ditambah n minus 3 langkah,
ditambah n minus 4 langkah, semua cara turun ke hanya satu langkah.
Dan aku di orang terakhir saya.
>> Dan jika Anda ingat bahwa banyak dari statistik buku atau buku matematika
memiliki orang-orang formula pada hardcover belakang atau depan mereka,
ternyata bahwa seri ini dapat dinyatakan lebih sederhana
n kali n minus 1 lebih dari 2.
Dan itu baik-baik saja jika itu tidak di garis depan pikiran Anda.
Tapi ini memang benar.
Itu hanya cara sederhana menulis itu.
Dan kemudian jika Anda berpikir kembali ke sekolah dasar,
ketika Anda hanya mulai mengalikan hal-hal, ini tentu saja,
hanya n kuadrat dikurangi n dibagi 2.
Semua yang saya lakukan adalah memperluas ekspresi ada.
Dan jadi mari kita menulis ulang ini sedikit berbeda.
Itu n kuadrat dibagi 2 dikurangi n / 2.
>> Jadi sekali lagi, aku hanya jenis menerapkan beberapa aritmatika aturan di sana.
Tapi perhatikan sekarang bahwa istilah terbesar dalam ekspresi ini, sehingga untuk berbicara,
adalah bahwa n kuadrat.
Jadi ya, itu n kuadrat dibagi 2, dikurangi n / 2.
>> Namun umumnya, jika n adalah akan menjadi nilai besar,
Aku akan mengklaim bahwa n kuadrat akan menjadi faktor dominan.
Ini hanya akan menjadi kontributor besar
untuk jumlah langkah dari n / 2.
Jadi apa yang saya maksudkan dengan ini?
Mari kita coba contoh sederhana, bahkan meskipun matematika mendapat sedikit besar.
>> Jadi misalkan kita memiliki 1 juta orang di atas panggung, atau 1 juta hal
bahwa kita ingin mengurutkan.
Mari kita pasang satu juta menjadi formula yang tepat
untuk melihat berapa banyak langkah yang diperlukan Total untuk menyortir satu juta elemen menggunakan katakanlah,
semacam seleksi.
>> Jadi kita akan memiliki rumus yang sama seperti sebelumnya.
Saya akan pasang satu juta, sehingga saya mendapatkan satu juta kuadrat dibagi 2,
minus juta dibagi 2.
Jika saya melakukan matematika yang di muka di sini, kita memiliki 500 miliar
dikurangi 500.000, yang memberi kita 499999500000,
yang pretty darn besar.
>> Bahkan, jika Anda membandingkan sekarang 499000000000, 999000000,
500.000 terhadap nilai asli kami, 500 miliar, itu begitu sialan dekat.
Benar? n kuadrat dibagi 2 memberikan us-- atau lebih tepatnya, n kuadrat dibagi 2
memberi kami 500 miliar.
Itu cukup darn dekat untuk 499999500000,
yang berarti mengurangi off 500.000, atau lebih umum, mengurangi off
n kuadrat, tidak benar-benar masalah besar.
N kuadrat membuat ini nomor tumbuh sangat cepat.
>> Sekarang, ini penting hanya sejauh seperti yang kita, sebagai ilmuwan komputer,
umumnya tidak akan peduli begitu banyak tentang nuansa formula ini
dan apa yang jawaban yang tepat adalah.
Kami peduli hanya itu, Anda tahu apa?
Pada akhir hari, formula ini adalah di urutan n kuadrat.
>> Ya, kita membaginya dengan 2 di sana.
Ya, kita mengurangkan off n minus 2.
Tetapi pada akhir hari, istilah yang benar-benar menyakitkan kita dan biaya kita
banyak langkah-langkah adalah bahwa istilah persegi.
Dan jadi apa seorang ilmuwan komputer akan umumnya melakukan
adalah mengabaikan semua orang hal agar lebih kecil,
dan hanya melihat satu yang kontribusi yang paling untuk biaya.
>> Dan ini bagus, karena kita bisa sekarang berbicara di umum jauh lebih besar
tentang algoritma, dan dapat membandingkan mereka.
Dan fakta bahwa aku menggunakan O ini disengaja.
Ketika saya mengatakan pada urutan dari, saya secara khusus
mengacu pada sesuatu disebut besar O. Dan besar O
adalah notasi yang komputer ilmuwan menggunakan untuk menggambarkan
sebuah atas terikat pada sesuatu.
>> Jadi, jika Anda mengatakan bahwa algoritma adalah O besar n kuadrat,
karena saya mengusulkan hanya saat yang lalu, berarti bahwa
bahwa dalam hal yang berjalan waktu atau efisiensi,
dibutuhkan pada urutan n kuadrat langkah.
Mungkin lebih, mungkin kurang.
Tapi itu atas perintah n kuadrat.
Dan itulah batas atas.
Ini tidak akan menjadi lebih menyakitkan dari itu.
Ini tidak akan menjadi n potong dadu, atau 2 dengan n, atau sesuatu yang jauh lebih besar.
Ini adalah batas atas pada apa pun biaya yang.
Jadi mengingat bahwa, mari kita pertimbangkan hanya beberapa contoh.
Dan ini hanyalah sebuah daftar terbatas dari sangat umum kali berjalan
untuk algoritma yang dimaksudkan untuk menjadi ilustrasi dari beberapa hal yang kita sudah
terlihat sudah.
>> Jadi misalnya, dalam kasus semacam seleksi, apa yang saya mengklaim disini
adalah menjalankan bahwa seleksi semacam ini waktu di urutan n kuadrat.
Dalam kasus terburuk, aku akan memiliki sejumlah nomor acak di sini.
Dan seperti yang kita lihat matematis, jika saya terus berjalan
melalui daftar, melalui daftar, memilih terkecil berikutnya
Unsur lagi dan lagi, jika saya sebenarnya menuliskan semua langkah
Aku mengambil seperti yang saya diusulkan dirumuskan secara sebelumnya, itu atas perintah n kuadrat
langkah-langkah yang saya mengambil.
>> Dan ternyata gelembung yang mengurutkan dan insertion sort
hanya sebagai lambat dalam kasus terburuk.
Perhatikan, misalnya, insertion sort, algoritma yang terakhir kita berurusan dengan,
yang telah kita lihat elemen, dan kemudian masukkan tempatnya.
Dan kemudian kami melihat elemen berikutnya, dan memasukkannya tempatnya.
>> Jadi pertimbangkan skenario terbaik.
Misalkan saya telah relawan saya berbaris harfiah seperti ini, satu sampai delapan,
sudah diurutkan.
Berapa banyak langkah adalah insertion sort akan mengambil memilah delapan orang,
jika mereka tiba di atas panggung tampak seperti ini?
>> Delapan orang sudah diurutkan.
Dan saya menggunakan insertion sort.
Yang terakhir dari algoritma.
Nah, mari kita menghidupkan kembali cepat nyata.
Jadi jika saya mulai di sini, saya melihat satu.
Di mana salah satu milik?
Ini milik di sini.
Saya melihat dua.
Di mana dua milik?
Disini.
Saya melihat tiga.
Di mana tiga milik?
Disini.
>> Saya melihat empat.
Disini.
Lima, enam, tujuh, delapan.
Tidak ada alasan untuk mengulang sendiri.
Dan, berapa banyak langkah adalah bahwa dalam hal n?
Ini pada urutan n langkah, kan? n minus 1.
Tapi aku mengambil sejumlah linear langkah-langkah, dan sekarang aku sudah selesai.
Jadi itulah kasus terbaik, meskipun.
Bagaimana dengan kasus terburuk?
Apa delapan yang di sana, dan tujuh berada di sana,
dan satu dan dua yang di sini, jadi bahwa daftar yang benar-benar terbalik?
>> Nah, apa yang terjadi memang jika ini adalah nomor?
Dan kami akan melakukan hanya beberapa contoh.
Bagaimana jika, memang, nomor delapan di sini, dan whoops number--.
Jadi bagaimana jika, memang, nomor delapan adalah semua jalan di sini,
dan aku menggunakan insertion sort?
>> OKE.
Aku mengklaim pada saat itu di tempat.
Tapi sekarang, seven-- mana tujuh pergi?
Tentu saja, ia pergi ke sini.
Jadi saya harus pindah delapan lebih satu tempat.
Sekarang enam, di mana ia pergi?
Nah, baiklah.
Sekarang, saya harus pindah delapan lebih tempat, dan tujuh lebih tempat,
dan kemudian aku celepuk enam.
>> Jadi pertama kalinya, itu biaya saya satu langkah untuk memperbaiki keadaan,
maka harganya dua langkah untuk memperbaiki hal-hal.
Berapa banyak langkah itu akan mengambil untuk memperbaiki
hal menempatkan lima di tempat yang tepat?
Tiga.
Karena sekarang aku harus memindahkan satu, dua, tiga.
Berapa banyak langkah itu akan mengambil untuk menempatkan empat di tempat yang tepat?
4 ditambah 5, ditambah 6, ditambah 7.
>> Dan jadi matematis identik dengan apa yang kita dijelaskan untuk seleksi semacam.
Kami memiliki seri ini yang hanya meningkat.
1 ditambah 2 ditambah 3 ditambah 4, atau sebaliknya, 7 ditambah 6
ditambah 5 ditambah 4 menambahkan untuk saat ini tujuan untuk pada urutan n kuadrat.
>> Jadi biarkan aku menetapkan juga bahwa bubble sort juga di n kuadrat.
Karena dengan bubble sort, masing-masing waktu aku pergi melalui daftar,
Aku mengambil kira-kira berapa banyak langkah?
Setiap kali saya benar-benar berjalan kaki dari sana ke sana?
Kasar n langkah.
Tapi berapa kali mungkin aku perlu melalui daftar?
>> Nah, kira-kira n waktu.
Mungkin n minus 1, tapi kira-kira n kali.
Nah, kenapa begitu?
Nah, dengan bubble sort, jika kita mulai dengan bubble sort,
dengan daftar di terburuk situasi, yang lagi benar-benar
mundur, apa yang akan terjadi?
Aku pergi melalui daftar, dan nomor satu milik semua jalan di sana.
>> Tapi dengan bubble sort, seberapa jauh satu beralih lulus pertama saya melalui daftar?
Berapa banyak tempat yang dia dapatkan lebih dekat ke tempat yang benar?
Hanya satu.
Jadi jika Anda jenis alasan melalui ini, setiap kali melalui algoritma ini,
Mengambil kira-kira n langkah Daud.
Tapi berapa banyak melewati melalui daftar itu
akan mengambil satu gelembung ke kiri tempatnya?
>> Dia harus bergerak seperti, ruang n cara ini.
Jadi hanya untuk melakukan sortasi dari daftar, Saya harus berjalan bolak-balik n kali.
Dan setiap kali, aku melihat n elemen.
Jadi lakukan n hal n kali pada urutan n kuadrat.
>> Sekarang, kita akan melihat dalam beberapa dari celana pendek yang
tertanam dalam masalah berikutnya CS50 ini mengatur, pendekatan lain di ini,
tapi untuk saat ini, mari kita hanya mempertimbangkan beberapa kali berjalan lainnya,
terutama jika yang menyortir mengambil sedikit waktu untuk meresap.
Apa algoritma yang telah kita lihat sudah yang mengambil di urutan langkah n?
>> Apa yang harus mengambil sejumlah linear dari langkah yang telah kita lihat sejauh ini?
Apa itu?
Pencarian direktori telepon.
Algoritma pertama.
Benar?
Di mana kami linear mencari Mike Smith?
Memang.
Dari minggu nol, ketika saya mulai mengubah satu halaman pada satu waktu,
dan saya bahkan mengatakan bahwa itu adalah jenis dari algoritma linear perasaan,
dan kami memiliki gambar itu pada papan dengan garis merah langsung
dan lurus kuning line, mereka memang
algoritma yang di O besar n.
>> Karena untuk menemukan Mike Smith di telepon buku halaman n, dalam kasus terburuk,
mungkin membawa saya n langkah.
Bagaimana mengambil kehadiran?
Satu dua tiga empat lima enam.
Apa waktu berjalan ini algoritma untuk mengambil kehadiran?
O besar dari n, karena dalam teori saya harus menunjukkan semua orang di ruangan.
>> Sekarang sebagai samping, bagaimana dengan optimasi lain dari seminggu nol?
Dua, empat, enam, delapan, 10, 12.
Seorang ilmuwan komputer akan menyadari, tunggu sebentar,
yang ada di urutan n dibagi dengan dua langkah.
Benar?
Karena saya lakukan dua orang pada satu waktu.
Tapi kami akan mengabaikan istilah-istilah urutan yang lebih rendah,
dan kami hanya akan membuang membagi dengan 2,
dan hanya mengatakan, O besar n untuk algoritma itu juga.
>> Bagaimana ini?
Kami akan melewatkan beberapa, tapi apa adalah sebuah algoritma yang log n?
Yang mengambil kira-kira log langkah n?
Membagi dan menaklukkan.
Tepat.
Seperti contoh buku telepon di Minggu nol dan sebelumnya hari ini,
di mana kami membagi masalah lagi dan lagi dan lagi.
Kami menarik di papan di minggu nol sebagai jalur hijau melengkung,
dan kami mengatakan bahwa itu adalah hari algoritma logaritmik.
>> Dan memang, jumlah langkah itu dibutuhkan untuk melakukan membagi dan menaklukkan,
atau pencarian biner seperti yang kita akan mulai menyebutnya, seperti dalam buku telepon,
adalah di urutan log dan langkah-langkah.
Dan ini adalah sedikit dari salah satu yang aneh.
>> Apa yang terjadi satu langkah, atau lebih khusus
sejumlah konstan langkah?
Mungkin dua, mungkin itu tiga, tapi seorang ilmuwan komputer hanya
menyederhanakan sebagai O besar 1, beberapa nomor konstan langkah.
Apa sesuatu yang bisa melakukan itu mengambil sejumlah langkah konstan?
>> Apa waktu berjalan dari bertepuk tangan?
Waktu yang konstan.
Benar?
Seperti, apa waktu berjalan dari melakukan apa pun yang diperlukan hanya satu
operasi, seperti mencetak F Hello World.
Yang mungkin dikatakan waktu yang konstan, kecuali kurang sudut halnya dengan cetak F,
apa mungkin waktu berjalan cetak F sebenarnya?
Dan mengapa?
Apa n pengukuran dalam kasus itu?
>> AUDIENCE: [tidak terdengar].
DAVID J. Malan: Tepat.
Jumlah karakter kami ingin mencetak.
Sehingga sangat peka konteks.
Hari ini, kami telah memfokuskan banyak pada huruf dan angka di sini di papan tulis.
Tetapi juga mungkin karakter dalam string yang sebenarnya.
Jadi ternyata ada lagi ukuran yang akan mulai peduli tentang,
dan itu berlawanan O besar, sehingga untuk berbicara.
>> Itu notasi omega.
Sedangkan O besar berarti apa, yang atas terikat pada waktu Anda berjalan?
Maksimal, berapa banyak waktu mungkin sesuatu mengambil?
Omega-- maaf ini terus datang up-- adalah kebalikan dari itu,
dimana itu adalah batas bawah pada jumlah waktu sesuatu mungkin mengambil.
>> So. misalnya, apa algoritma yang mengambil langkah selalu n kuadrat?
Nah, salah satu algoritma yang telah kita lihat hari ini, pada kenyataannya, mungkin itu juga.
Seleksi semacam.
Seleksi semacam cukup bodoh.
Bahkan jika algorithm-- maaf, bahkan jika array sudah disortir,
Temukan semacam ini akan terus berjalan melalui daftar
untuk memastikan itu memiliki terkecil Unsur lagi dan lagi dan lagi.
Dan meskipun Anda manusia di penonton tahu bahwa, tunggu sebentar,
Anda sudah lulus elemen terkecil, komputer
tidak tahu bahwa sampai terlihat semua jalan melalui daftar.
Demikian pula, batas bawah yang mungkin juga diperhitungkan
mungkin waktu linier.
>> Berapa banyak waktu yang dibutuhkan untuk elemen semacam n di terbaik
kasus menggunakan sesuatu seperti bubble sort?
Misalkan daftar Anda sudah diurutkan.
Kami mengatakan bubble sort mengambil urutan n kuadrat langkah.
Tapi bagaimana jika itu sudah diurutkan?
Bagaimana jika Anda menyadari setelah satu lulus melalui array
bahwa Anda telah membuat tidak ada swap?
Apakah Anda perlu untuk terus membuat melewati lebih?
>> Tidak.
Jadi batas bawah pada bubble sort mungkin dikatakan linear.
Omega dari n.
Dan kita dapat melihat lain dari ini juga.
Jadi mari kita lihat di hanya visualisasi disini
untuk melihat bagaimana membedakan diri.
Aku akan pergi ke sini ke ini Halaman yang tersedia di website C50 ini,
tetapi akan menjadi sakit untuk mendapatkan kerja, karena menggunakan teknologi yang disebut
Applet Java, yang merupakan sebagian besar tidak didukung hari ini,
setidaknya oleh Chrome dan lain-lain tertentu.
>> Dan biarkan aku pergi ke depan dan mempercepat ini dan menjelaskan apa yang terjadi.
Ini adalah demonstrasi gelembung semacam, algoritma pertama kita melihat.
Dan itu adalah visualisasi dalam setiap dari bar ini merupakan nomor.
Semakin besar bar, semakin besar nomor tersebut.
Semakin kecil bar, semakin kecil jumlahnya.
Dan apa yang Anda dapat melihat secara visual, bahkan meskipun ini akan super cepat,
adalah bahwa bar merah seperti saya, berjalan bolak-balik memperbaiki masalah.
Anda dapat melihat bahwa unsur-unsur yang lebih besar memang menggelegak ke kanan,
dan unsur-unsur yang lebih kecil yang menggelegak ke kiri.
Dan di sini, jika kita sebenarnya melihat lebih dekat,
kita benar-benar dapat menghitung jumlah perbandingan dan swap
yang sedang dilakukan.
>> Tapi sebaliknya, mari kita lihat di kedua algoritma
kami melihat sebelumnya dengan kami relawan, seleksi semacam.
Visual, ia memiliki efek yang sangat berbeda.
Tapi itu, sekali lagi, sangat intuitif, di bahwa kita tetap memilih terkecil berikutnya
elemen, dan kami mendapat sedikit keberuntungan.
Yang merasa fundamental lebih cepat.
Tetapi jika kita berlari ini lagi dan lagi dan lagi dengan banyak input,
kita akan melihat bahwa itu memang masih di O besar n kuadrat.
>> Mari kita melakukan satu terakhir di sini, insertion sort,
yang merupakan algoritma ketiga kita melihat, dan ingat
yang satu ini berhubungan dengan elemen seperti pertemuan mereka,
tetapi kemudian mungkin pergeseran hal lebih untuk membuat ruang,
memasukkan unsur-unsur di mana mereka berada.
>> Dan ini juga berakhir memberikan hasil akhir. Sekarang semua tiga dari mereka
merasa cukup cepat.
Dan memang, aku berlari mereka di klip yang cukup bagus.
Tapi pada dasarnya, mereka semua cukup mengerikan, jujur.
Semua algoritma ini sejauh yang berjalan di O besar n kuadrat
mengambil sedikit waktu untuk menjalankan pada akhirnya.
>> Dan memang, kita bisa melihat dan merasa ini terakhir
jika saya menarik demo ketiga dan terakhir ini.
Ini adalah satu lagi visualisasi yang akan
untuk menunjukkan semacam gelembung di sebelah kiri, Temukan semacam di tengah,
dan sesuatu, sebagai salah satu dari kami tangan menimbulkan sebelumnya menyarankan,
menggabungkan semacam di sebelah kanan.
Sebuah membagi dan menaklukkan strategi di sebelah kanan.
Dan itu, pada kenyataannya, apa yang kita akan melihat pada hari Rabu.
Tapi mari kita waktu ini untuk berjalan secara paralel.
Ini kira-kira jumlah yang sama elemen, semua berjalan pada waktu yang sama.
Bubble sort vs pilihan semacam vs merge sort.
>> Sekarang, mereka semua berjalan dalam teori pada waktu yang sama.
CPU berjalan pada kecepatan yang sama, tetapi Anda
dapat merasakan bagaimana membosankan ini sangat cepat akan menjadi,
dan hanya seberapa cepat ketika kita menyuntikkan sedikit seminggu
algoritma nol ini dapat kami mempercepat pekerjaan.
>> Dan sekarang mari kita bandingkan ini dalam satu bentuk terakhir.
Aku akan pergi ke depan ke website CS50, di mana
kami memiliki link akhir ini untuk hari ini, di mana seseorang di internet
silakan mengumpulkan video yang menangkap apa pemilahan yang berbeda
algoritma terdengar seperti.
Ini adalah insertion sort.
>> [Bip]
>> Dimana Anda menerapkan frekuensi berdasarkan ketinggian bar bar.
Ini adalah semacam gelembung.
>> [Warped Bip]
>> Datang berikutnya is-- datang di samping pilihan semacam is--,
di mana lagi, kita memilih elemen terkecil berikutnya,
dan kita bisa melihatnya tumbuh dari kiri ke kanan.
>> Menggabungkan semacam, pemenang kami sejauh ini.
Perhatikan bagaimana hal itu membagi hal-hal ke [tidak terdengar] setengah dan tempat.
Semacam Gnome, yang kita belum berbicara tentang, dan menciptakan visual
dan audally sedikit bentuk yang berbeda dan suara.
Akan kembali dan sebagainya, membersihkan segalanya.
Juga memeriksa heapsort di website orang ini.
>> Dan hanya itu.
Kita akan melihat Anda waktu berikutnya.
>> [Mendesing DAN MUSIK]