>> [MUSIC PLAYING]
>> DAVID J. Malan: Baiklah.
Jadi selamat datang kembali.
Ini adalah CS50, dan adalah akhir minggu ketiga.
>> Jadi ingat dalam beberapa minggu terakhir, kita telah menghabiskan cukup banyak
waktu di C, pada pemrograman, pada sintaks.
Dan itu cukup normal, jika Anda masih berjuang dengan masalah Set 2, menjadi
membenturkan kepala ke dinding.
Ini pesan kesalahan yang rumit yang tampak dan bug yang Anda
tak bisa mengejar.
Karena, yakinlah, bahwa hanya dalam waktu beberapa minggu Anda akan melihat kembali
hal-hal seperti Caesar, dan [? V-genair,?] bahkan mungkin Crack, dan
menyadari betapa jauh Anda telah datang dalam waktu singkat.
Jadi kalau itu bisa menghibur, bertahan di sana untuk saat ini.
>> Hari ini, meskipun, kita mulai transisi untuk hal-hal tingkat yang lebih tinggi.
Dan kita mulai untuk mengambil begitu saja bahwa kalian tahu bagaimana program, atau
paling awal dari bahwa tingkat kenyamanan.
Dan kita akan mulai untuk mempertimbangkan bagaimana kita bisa pergi tentang merancang program yang lebih
efektif.
Bagaimana kita bisa pergi tentang optimalisasi efisiensi algoritma kami, dan
umumnya memecahkan lebih masalah yang menarik.
Dan mulai mengambil begitu saja bahwa, jika kita ingin, kita bisa kode apa pun
contoh yang kita miliki dalam pikiran.
Jadi hari ini, kita tidak menyentuh keyboard untuk segala bentuk kode.
Ini akan menjadi tingkat yang lebih tinggi, dan akhirnya, sekitar pemecahan masalah.
>> Jadi untuk sampai ke titik itu, saya mengusulkan bahwa tujuh berikut
persegi panjang mewakili tujuh pintu, di belakang yang merupakan sejumlah besar
nomor, di antaranya adalah nomor 50.
Biarkan aku memproyeksikan ini tentang hal ini layar di sini juga.
Dan mengusulkan bahwa kita membutuhkan sukarelawan untuk membantu menemukan saya nomor di depan
internet di sini untuk melihat.
Ayo up, di pink.
Baik.
Siapa nama Anda?
>> JENNIFER: [Tak terdengar]
>> DAVID J. Malan: Maaf?
>> JENNIFER: Jennifer.
>> DAVID J. Malan: Jennifer.
Baiklah, Jennifer.
Senang bertemu Anda.
Ayo up.
Jadi ini di sini adalah tujuh pintu, dan apa Saya ingin Anda lakukan bagi kita di sini,
di depan semua teman-teman sekelas Anda, adalah menemukan kami nomor, 50.
Untuk menemukan nomor, Anda bisa mengintip di balik salah satu pintu ini dengan hanya menekan
pada salah satu pintu, dan akan mengungkapkan jumlahnya.
Dan mari kita lihat seberapa cepat Anda dapat menemukan kami nomor, 50.
>> 15.
16.
50.
Baik dilakukan.
Baik.
Tepuk tangan untuk Jennifer.
>> [Tepuk Tangan]
>> Baik.
Jadi apa strategi Anda untuk menemukan nomor tersebut, 50?
>> JENNIFER: Um, saya pikir mungkin jika -
[Tak terdengar]
>> DAVID J. Malan: Oh.
Berikan satu detik.
Jadi itu strategi Anda untuk menemukan nomor tersebut, 50?
>> JENNIFER: Jadi aku hanya mulai di mulai melihat apa nomor pertama
adalah, dan kemudian aku berpikir, mungkin jika mereka diurutkan, aku hanya akan terus
menekan lebih tinggi?
>> DAVID J. Malan: OK.
Dan kita tampaknya telah menemukan bahwa untuk menjadi kasus.
Meskipun, mari kita mengupas lapisan-lapisan hanya sedikit, dan Anda ingin pergi
depan dan mengungkapkan pintu lain Anda bisa memilih?
>> JENNIFER: Oh, sayang.
>> DAVID J. Malan: Ah.
>> JENNIFER: Jadi saya hanya beruntung.
>> DAVID J. Malan: Jadi Anda beruntung.
Baik.
Jadi tidak buruk.
Tapi itu menarik wawasan, kan?
Jika Anda diasumsikan, dan Anda tidak mendapatkan, memang, sedikit beruntung ada.
Tetapi jika Anda berasumsi bahwa jumlahnya diurutkan, Anda bisa lebih tepat
seperti bagaimana yang mempengaruhi perilaku Anda?
>> JENNIFER: Jadi, jika mereka diurutkan, saya pikir mungkin terkecil hingga terbesar.
>> DAVID J. Malan: OK.
>> JENNIFER: Atau jika ini akhirnya menjadi benar-benar besar, maka terbesar ke terkecil.
>> DAVID J. Malan: OK.
Jadi terbesar ke terkecil, atau terkecil hingga terbesar.
Tapi biarkan aku mengusulkan, misalkan Anda memiliki mendapat sial, dan menganggap bahwa mereka
tidak, pada kenyataannya, diurutkan, berapa banyak pintu-pintu yang mungkin Anda harus mengintip
belakang dalam kasus terburuk?
>> JENNIFER: Semua dari mereka.
>> DAVID J. Malan: Semua dari mereka.
Jadi mari kita generalisasi bahwa sebagai n.
Kebetulan ada 7, tapi mari lebih umumnya mengatakan ada pintu n pada
layar di sini.
Jadi dalam kasus terburuk, Anda harus untuk melihat ke belakang 7 pintu, atau n pintu.
Dan jadi ini benar-benar, itu sedikit beruntung hari ini, tetapi itu benar-benar linier
Algoritma macam, meskipun Anda adalah jenis melompat-lompat.
Apakah itu adil?
>> JENNIFER: Ya.
>> DAVID J. Malan: Nah, biarkan aku melihat apakah Anda Perubahan strategi jika saya memindahkan kita ke
Contoh kedua kami di sini dengan 7 pintu yang berbeda.
Angka yang sama, tapi ini saat mereka diurutkan.
Apa strategi Anda di sini akan menjadi, mencoba untuk memadamkan pikiran Anda apa yang
nomor lain -
>> JENNIFER: OK.
>> DAVID J. Malan: - sebelumnya?
>> JENNIFER: Mari kita mulai dengan yang pertama.
>> DAVID J. Malan: Baiklah.
Mulailah dengan yang pertama.
4.
Sekarang di mana Anda akan pergi, dan mengapa?
>> JENNIFER: 4 benar-benar kecil.
Jadi jika mereka pun mungkin terkecil sampai terbesar, seharusnya
menjadi dua kali lipat, dan -.
>> DAVID J. Malan: OK.
Mari kita lihat, yang menurut Anda?
>> JENNIFER: Coba yang terakhir.
Nice.
>> DAVID J. Malan: Sangat baik dilakukan.
Baik.
>> [Tepuk Tangan]
>> DAVID J. Malan: OK.
Jadi Anda benar-benar melakukan hal ini mengerikan, karena kau
melakukannya dengan sangat baik.
Yang membuat kita mampu membuat titik-titik tertentu.
Jadi mari kita coba untuk memutar kembali di sini.
>> JENNIFER: OK.
>> DAVID J. Malan: Sangat baik dilakukan, namun.
Jadi Anda mulai dari awal, Anda melihat bahwa itu adalah 4, maka Anda
pindah ke akhir.
Tapi bagaimana kalau Anda tidak beruntung ada, dan anggaplah 50
berada di tempat lain.
Apa langkah ketiga Anda telah?
>> JENNIFER: Kembali ke awal.
>> DAVID J. Malan: Kembali ke awal.
OK, jadi Anda pasti sudah menyentuh pintu ini, yang 8.
Baik.
Jadi itu bukan 50.
Di mana Anda akan tampak selanjutnya?
>> JENNIFER: Jika saya tidak tahu mereka beres.
>> DAVID J. Malan: Benar.
Nah, jika Anda tidak tahu mereka diurutkan -
>> JENNIFER: Oh, memang tahu, ya.
>> DAVID J. Malan: - tetapi Anda tidak tahu di mana 50 adalah belum?
>> JENNIFER: Hanya terus.
>> DAVID J. Malan: Baiklah.
OK.
Terus.
OK, saya bisa bekerja dengan.
>> JENNIFER: OK.
>> DAVID J. Malan: Sekarang, jika Anda hanya akan terus, apa yang Anda
algoritma devolving mundur ke.
>> JENNIFER: The linier -.
>> DAVID J. Malan: Ini adalah jenis linier.
Tapi biarkan aku mengusulkan, biarkan saya ditempatkan pada pusatnya.
Biarkan aku refresh halaman.
nomor yang sama, pengaturan yang sama, pintu yang sama.
Tetapi berpikir kembali ke hari pertama dalam kelas ketika kita merobek buku telepon di
setengah, semacam, dan apa yang Strategi kami di sana?
>> JENNIFER: Mulai tengah.
>> DAVID J. Malan: OK.
Jadi mulai dari tengah.
Jadi mari kita pergi ke depan dan mensimulasikan itu.
Mulai dari tengah oleh mengungkapkan pintu itu.
Jadi jumlah 16.
Jadi apa yang akan orang yang kuat telah dilakukan, yang merobek buku telepon dalam setengah,
untuk sampai ke menebak berikutnya?
>> JENNIFER: Pergi dalam setengah ini.
>> DAVID J. Malan: Dan mengapa ke kanan?
>> JENNIFER: Jika mereka semacam terkecil sampai terbesar, kemudian 50 harus
pada akhir itu.
>> DAVID J. Malan: Baik.
Benar-benar masuk akal.
Jadi seperti buku telepon, Anda pergi ke tepat sebagai lawan ke kiri, tapi di sini
adalah takeaway kunci.
Sekarang Anda dapat membuang, atau merobek, setengah dari masalah ini, meninggalkan Anda tidak
dengan 7 pintu, tapi benar-benar hanya 3.
Yang kira-kira setengah dari ukuran masalah.
Baik.
Jadi sekarang apa yang akan Anda miliki dilakukan setelah Anda pergi kan?
>> JENNIFER: Jadi 16 masih cukup kecil, relatif terhadap 50, jadi mungkin aku akan mencoba,
seperti, yang satu ini.
>> DAVID J. Malan: Baiklah.
42.
Baiklah, jadi sekarang apa yang Anda naluri memberitahu Anda?
>> JENNIFER: Saya dapat membuang ini dan kemudian hanya -
>> DAVID J. Malan: OK.
Baik, Anda dapat membuang kiri setengah sana.
>> JENNIFER: - memilih satu ini.
>> DAVID J. Malan: Dan kanan.
>> JENNIFER: Ya.
>> DAVID J. Malan: Jadi meskipun sulit untuk melihat mungkin, ketika hanya ada
7 pintu, pikirkan, sekarang, konsistensi dari
Algoritma Anda hanya diterapkan.
Dalam kasus sebelumnya, Anda lakukan beruntung, yang besar.
Tapi Anda tidak menggunakan heuristik, Aku akan mengatakan.
Anda menggunakan semacam naluri Anda, dan mengetahui disortir, jika itu cukup
kecil di awal, jelas, kami sudah harus pergi lebih ke kanan.
Tapi dalam beberapa hal, Anda beruntung, karena mungkin ini adalah nomor 100,
dan mungkin 50 lebih di tengah.
Mungkin 50 bahkan di sini.
>> Tapi apa yang Anda lakukan sedikit berbeda kali ini adalah, Anda melakukan hal yang sama
lagi dan lagi.
Dan saya berpendapat bahwa apa yang baru saja tidak, meskipun dipengaruhi oleh telepon
buku misalnya, adalah sesuatu yang jauh lebih algoritmik, dan masih banyak
kurang istimewa cased.
Banyak kurang naluriah.
Jadi pada akhir hari, bagaimana Anda menggambarkan efisiensi
algoritma pertama, di mana Anda pergi kiri ke kanan, versus
algoritma kedua di sini?
>> JENNIFER: Yang satu ini harus, seperti, mungkin membagi waktu, atau bahkan lebih, ya.
>> DAVID J. Malan: OK, bahkan mungkin lebih.
Mari kita menekan sedikit lebih keras pada itu.
Apa benar-benar, jika kita melanjutkan terapi ini logika, kita pasti dibelah dua
waktu berjalan dengan algoritma kedua ini dengan membuang setengah dari
angka, tapi apa yang kita lakukan pada berikutnya iterasi, ketika Jennifer mengungkapkan
angka kedua?
>> Kami dibelah dua jumlah pintu lagi.
Lalu apa yang kita lakukan setelah itu, jika ada pintu lagi untuk bermain dengan?
Kami akan membagi mereka, dan sekali lagi, dan lagi, dan lagi.
Dan ini hanya seperti kalian semua berdiri pada minggu pertama
kelas, setengah dari Anda duduk, setengah Anda duduk, setengah dari Anda
duduk, sampai satu satunya jiwa berdiri.
Dan kita mengatakan bahwa waktu berjalan itu, jumlah langkah yang dibutuhkan adalah
pada urutan apa?
>> SPEAKER 1: [Tak terdengar]
>> DAVID J. Malan: Jadi log basis 2 dari n, atau hanya lebih sederhana, log n.
Jadi sesuatu yang logaritmik.
Dan grafik itu bukan garis lurus yang baru saja lebih buruk dan lebih buruk, itu
kurva ini menarik yang tidak begitu buruk dari waktu ke waktu.
Jadi mari kita berpegang pada ide ini.
Mari kita terima Jennifer.
Terima kasih banyak untuk datang ke atas.
Dan, satu detik.
Tidak ada lampu meja hari ini, tapi kami punya CS50 bola stres.
>> JENNIFER: Yay.
>> DAVID J. Malan: Baiklah, di sini.
Terima kasih untuk menimbulkan stres di sini.
Baik.
Jadi mari kita lihat apakah kita tidak bisa sekarang memformalkan ini sedikit lebih.
Jadi sekali lagi, apa yang kita lakukan adalah dasarnya hal yang sama seperti yang kita lakukan
dalam minggu pertama.
Namun, bukannya akhir hanya dengan linear algoritma, yang kita digambarkan
sebelumnya sebagai garis lurus ini, dimana, jika kita menempatkan satu pintu lebih
layar, maka Jennifer akan harus melihat, berpotensi,
di belakang salah satu pintu lagi.
Jika kita menempatkan dua pintu lagi, dia mungkin untuk melihat ke belakang dua pintu lagi.
>> Dan, ada ini linier hubungan antara ukuran
masalah pada, katakanlah, sumbu x, dan jumlah waktu yang dibutuhkan untuk
memecahkan on y tersebut.
Tapi gambar saya menyinggung sebelumnya adalah jalur hijau.
Hijau sengaja, karena itu hanya merasa lebih baik.
Secara teori, algoritma, ketika kita melakukannya dengan buku telepon, ketika kita melakukannya
dengan kalian menghitung sama lain, dan dalam kasus kedua, ketika Jennifer hanya
melakukannya di sini, itu semacam dari fundamental baik.
Karena itu bukan hanya dua kali lebih cepat.
Itu tidak bahkan empat kali lebih cepat.
Itu sepenuhnya tergantung pada apa yang ukuran masukan itu, untuk berapa banyak
langkah akhirnya mengambil.
>> Dan jadi ide sederhana ini bahwa kita semua mengambil untuk diberikan dengan buku telepon,
sama dapat diterapkan untuk sesuatu seperti ini.
Dan ini mungkin akan lebih santai dikenal sebagai, seperti yang mungkin Anda
bayangkan, membagi dan menaklukkan.
Tidak seperti apa yang kita lakukan, tentu saja, dengan buku telepon.
>> Tapi pseudocode, ingat, adalah ini.
Jadi kita tidak akan melakukan ini lagi, tapi ingat bahwa minggu pertama, kita semua berdiri
dan kemudian setengah dari Anda duduk, setengah dari Anda duduk, setengah dari Anda duduk.
Algoritma yang diterapkan dalam sedikit cara curang, dalam itu,
tidak hanya satu saya menghitung, fundamental, lebih efisien.
Dalam hal ini, saya memanfaatkan sumber daya sekunder.
Begitulah, beberapa CPU, beberapa otak, beberapa orang pintar di
Ruangan yang membantu saya mendapatkan dari sesuatu linier untuk sesuatu
logaritmik, dari sesuatu merah untuk sesuatu yang hijau.
>> Tapi dalam kasus ini, Jennifer sendiri bisa mendasar meningkatkan atas
kinerja algoritma pertama oleh, lagi, hanya berpikir sedikit lebih keras.
Dan sekarang, ketika tiba saatnya untuk melaksanakan hal-hal ini, mencari tahu
apa baris kode Anda dapat menulis seperti bahwa Anda dapat mengulangi lagi, dan
lagi, dan lagi, semacam dengan cara perulangan.
Karena Anda tidak akan memiliki mewah, seperti Jennifer lakukan pada awalnya, untuk
hanya memiliki sejumlah besar seandainya dan berkata, hmm, jika nomor ini pertama adalah 4,
biarkan aku melompat semua jalan sampai akhir.
Ooh, jika nomor yang terlalu besar, membiarkan saya pindah kembali sewenang-wenang
untuk elemen kedua.
Anda akan menemukan bahwa itu akan menjadi jauh lebih sulit untuk memformalkan apa yang kita manusia
mengambil untuk diberikan sebagai sangat wajar heuristik, tetapi komputer hanya
akan melakukan apa yang Anda katakan untuk dilakukan.
>> Sekarang ini memiliki sangat menarik implikasi.
Grafik ini semacam dimaksudkan untuk semacam membanjiri visual, tapi perhatikan, di mana
adalah garis lurus dalam grafik ini?
Dimana grafik linear yang kita sebut n?
Yah, itu semacam arah bawah gambar ini, kan?
Jadi yang kita lakukan adalah kita sudah semacam diperbesar keluar untuk sumbu x dan
y-axis untuk mencoba untuk mendapatkan rasa apa jenis lain dari kurva terlihat seperti.
>> Dan spesifik dari matematika ekspresi saat ini tidak akan begitu penting
banyak, tapi melihat bahwa ada banyak algoritma yang jauh lebih buruk daripada
sesuatu yang linear.
Memang, n potong dadu terlihat sangat buruk.
2 sampai n terlihat sangat buruk. n kuadrat terlihat sangat buruk.
Dan kita akan melihat apa yang beberapa dari mereka mungkin dalam realitas hari ini.
Dan log n tidak merasa buruk, tapi lebih baik dari n adalah log basis 2 dari n.
Tapi kau tahu, itu akan menjadi lebih lebih menakjubkan jika Jennifer, atau jika kita,
bahwa minggu pertama, telah datang dengan sesuatu yang log log n.
>> Jadi dengan kata lain, ada ini seluruh berbagai solusi yang mungkin untuk
masalah, tetapi bahkan di sini, pemberitahuan apa yang akan terjadi.
Ketika saya zoom out, yang kurva ini akan terbukti menjadi mutlak
terburuk dari orang-orang di layar sekarang?
Jadi n potong dadu terlihat cantik buruk saat ini.
Tetapi jika kita zoom out dan melihat lebih banyak x dan sumbu y, siapa yang akan
mendominasi pada akhirnya?
Jadi itu benar-benar ternyata bahwa 2 ke n, dan Anda dapat mengetahui ini hanya dengan
mencolokkan beberapa semakin besar angka, dan Anda akan melihat bahwa 2 ke
n, memang, akan lebih besar jauh lebih cepat.
Jika kita benar-benar zoom out, 2 ke algoritma n benar-benar menyebalkan.
Maksud saya ini akan mengambil sedikit waktu untuk
komputer untuk churn melalui.
>> Tapi Anda akan melihat dari waktu ke waktu, terutama masalah set masa depan dan bahkan
proyek akhir, adalah data Anda set mendapat besar, oke?
Bahkan dalam versi pertama dari Facebook, sebagai jumlah teman, dan
jumlah pengguna terdaftar mendapat besar, Anda bisa menyortir telepon dalam dan
melaksanakan sesuatu dengan pencarian linear, atau penyortiran sangat sederhana
algoritma, seperti yang akan kita lihat saat ini.
Anda harus mulai berpikir keras dan keras tentang masalah ini.
Dan jenis masalah tempat-tempat seperti Facebook, dan Google, dan Microsoft,
dan lain-lain bekerja pada adalah persis ini semacam semacam data yang besar pertanyaan
semakin hari ini.
>> Baik.
Jadi keberhasilan Jennifer dalam kedua algoritma, terus terang, dia luar biasa
juga pertama kalinya, tapi mari kita menuliskannya sebagai keberuntungan sehingga kita
dapat membuat hal ini.
Dalam kasus kedua, ia memanfaatkan suatu algoritma yang diulang lagi dan
lagi, tapi ia mengambil untuk diberikan asumsi tertentu yang kita diperbolehkan
, tapi dia dieksploitasi beberapa detail kedua kalinya bahwa dia tidak memiliki
pertama kalinya.
Yang adalah apa?
>> Bahwa daftar diurutkan.
Jadi, segera setelah daftar itu diurutkan, kita mengklaim bahwa Jennifer mampu melakukan
fundamental yang lebih baik.
7 pintu, ya, tidak menarik, tapi rasa itu kami 7 juta pintu.
Log n pasti akan untuk melakukan banyak, banyak
lebih cepat dalam jangka panjang.
Tapi dia harus memiliki pintu diurutkan untuknya.
Sekarang, saya mengambil kebebasan melakukan itu di muka pada layar komputer
di sini, tapi anggaplah bahwa Jennifer harus melakukan itu sendiri?
Misalkan bahwa pintu tersebut Data direpresentasikan dalam database, atau
teman terdaftar untuk Facebook, atau setiap halaman web di internet yang
berbagai situs mungkin perlu indeks atau cari berakhir.
>> Misalkan Anda hanya memiliki data mentah menetapkan dan itu diserahkan kepada Anda, atau
Jennifer untuk melakukan pemilahan itu?
Artinya, bukan, mengharuskan kita menjawab pertanyaan, baik, berapa banyak waktu
akan mengambil Jennifer, atau bahkan me, untuk mengurutkan angka-angka di muka jadi
bahwa dia bisa mengambil keuntungan dari itu?
Benar?
Karena implikasinya, tentu saja, adalah jika dibutuhkan saya cukup lama untuk memilah
angka, siapa sih yang peduli bahwa Anda dapat menemukan nomor seperti 50 begitu cepat,
seperti dalam kasus Jennifer, jika kita lebih dari kewalahan jumlah total waktu
butuh dengan memilah hal-hal di muka?
>> Jadi mari kita lihat jika kita tidak bisa dengan cat gambar di sini.
Saya memiliki seluruh banyak lebih banyak stres bola, jika yang membantu
memecahkan es di sini.
Dan jika Anda tidak keberatan, kami membutuhkan tujuh relawan -
pada, OK.
Wow.
Jadi kita tidak harus menghabiskan pada lampu meja, tampaknya.
Baik.
Jadi bagaimana dengan Anda dua di depan.
Bagaimana Anda dua orang di belakang.
Jadi itu empat.
Bagaimana dengan Anda di depan lima, enam dan tujuh.
Disana.
Teman Anda yang menunjuk Anda keluar, sehingga Anda mendapatkan hadiah.
>> Baik.
Ayo up.
Dan kenapa tidak kita miliki Anda orang datang ke sini.
Aku akan memberikan masing-masing nomor.
Dan pergi ke depan dan mengatur diri identik dengan apa yang
digambarkan di layar.
>> [Interposing SUARA]
>> DAVID J. Malan: Oop, maaf.
Bug.
Baik.
Nah, di sini kita pergi.
Nomor lima.
Nomor enam.
Satu, dua, tiga, empat, lima, enam, tujuh.
Oh, ini canggung.
>> SPEAKER 2: Saya hanya akan mendapatkan -.
>> DAVID J. Malan: Good deal.
Baik.
Terima kasih atas partisipasinya.
>> [Tepuk Tangan]
>> OK.
Baik.
Jadi kita memiliki empat, dua, enam, satu, tiga, tujuh, lima.
Sempurna sehingga kita memiliki tujuh sukarelawan di sini yang sama lebar dengan
array kita bermain dengan sebelumnya.
Dan saya memilih tujuh alasan yang akan hanya
nyaman dalam sedikit.
Dan aku akan mengusulkan yang pertama kita mengurutkan tujuh relawan.
Jika Anda ingin, pertama, untuk menyapa sekalipun.
Karena ini akan menjadi canggung beberapa menit.
Memperkenalkan diri.
>> GRACE: Hi, aku Grace.
Saya seorang mahasiswa di Leverett House.
>> BRANSON: Hi.
Aku Branson.
Saya seorang mahasiswa di Weld.
>> Gabe: Hi.
Aku Gabe.
Saya junior di Cabot.
>> NEIL: Aku Neil.
Saya seorang mahasiswa di Matthews.
>> JASON: Saya Jason.
Saya seorang mahasiswa di Greenough.
>> MIKE: Aku Mike.
Saya seorang mahasiswa di Grays.
>> JESS: Aku Jess.
Saya seorang mahasiswa di Leverett.
>> DAVID J. Malan: Excellent.
Baik.
Nah, terima kasih kepada semua kami relawan di sini sejauh ini.
Dan tantangan di tangan sekarang akan untuk memilah orang-orang ini, tapi kemudian
kita akan harus berpikir sedikit keras tentang seberapa efisien kita benar-benar
mengurutkannya.
Jadi mari kita coba pertama ini.
Kalian dapat melihat nomor masing-masing hanya dengan menempatkan sekitar sudut.
Pergi ke depan dan mengambil beberapa detik, dan semacam dirimu dari terkecil di
kiri ke terbesar di sebelah kanan.
Go.
>> OK.
Baik.
Itu benar-benar sangat cepat.
Sekarang seseorang di sini, apa algoritma bahwa orang-orang yang diterapkan?
>> SPEAKER 1: Sedikitnya untuk terbesar.
>> DAVID J. Malan: OK.
Setidaknya untuk terbesar benar-benar semacam ini obyektif, tapi aku tidak yakin itu
benar-benar sebuah algoritma.
Setidaknya untuk terbesar tidak memberitahu saya langkah-demi-langkah apa yang harus dilakukan.
Ya?
>> SPEAKER 1: [Tak terdengar]
>> DAVID J. Malan: OK.
Jadi jika Anda melihat seseorang lebih kecil dari nomor, kemudian pindah ke
hak dari mereka.
Jadi yang sekarang semakin ekspresif, lebih seperti sebuah algoritma, karena Anda
bisa mengatakan, jika hal ini, maka itu.
Jadi kita memiliki semacam membangun bersyarat.
Dan orang-orang ini tampaknya melakukan itu beberapa kali, karena beberapa dari Anda pindah sedikit
dari kejauhan.
Jadi ada mungkin semacam looping terjadi dalam pikiran mereka.
>> Tapi mari kita coba untuk meresmikan itu.
Jika kalian bisa me-reset kembali untuk pengaturan ini.
Mari kita lihat apakah kita tidak dapat memformalkan ini bit, dan kemudian mengajukan pertanyaan, hanya
seberapa efisien ini?
Tentu saja, ketika kita melakukan ini lebih lambat, itu akan merasa lebih baik dari
algoritma, tapi mari kita lihat apakah kita bisa memasukkan jari kita pada langkah-langkah yang tepat.
>> Jadi Anda dua orang empat dan dua.
Atau Anda urutan yang benar atau salah?
Jelas tidak benar.
Jadi kita bertukar.
Sekarang aku akan minggir di sini dan berkata, 4-6.
Apakah Anda benar atau salah?
>> Gabe: Benar.
>> DAVID J. Malan: Benar.
Enam dan satu?
Tidak.
Swap.
Jadi itulah dua swap.
Enam dan tiga?
Tidak.
Swap.
Enam dan tujuh?
Terlihat bagus.
Tujuh dan lima?
>> JESS: [Tak terdengar]
>> DAVID J. Malan: OK, swap.
Dan diurutkan.
Baik.
Jadi jelas tidak, kan?
Jadi ada yang lebih terjadi.
Tapi, memang, orang-orang, bahkan hanya naluriah.
terus bergerak.
Mereka tidak berhenti begitu saja, setelah mereka dikoreksi satu masalah.
Jadi.
Memang, aku akan memiliki untuk melakukan hal yang sama.
Aku akan harus semacam mundur kembali ke awal masalah ini,
atau awal dari array ini orang, mari kita mulai memanggil mereka.
>> Dan sekarang apa yang harus saya algoritma di kedua pass menjadi?
>> SPEAKER 1: Sama saja.
>> DAVID J. Malan: Sama saja.
Dan ini, aku mulai suka, kan?
Segera setelah Anda dapat menemukan diri Anda melakukan hal yang sama lagi dan lagi, itu
menjadi lebih seperti sebuah algoritma, dan kurang naluri manusia.
>> Jadi sekarang, di sini kita pergi lagi.
Dua dan empat?
Tidak.
Empat dan satu?
Ah, memang ada beberapa bekerja masih harus dilakukan.
Untuk dan tiga?
Baik.
Empat dan enam?
Enam dan lima?
Enam dan tujuh?
OK, sekarang, dilakukan.
OK, tidak ada.
Aku harus kembali.
>> Jadi sekarang, sekali lagi, kita melakukan ini sedikit lebih sengaja.
Dan sekarang, hanya ada satu otak eksekusi algoritma ini.
Satu CPU, jika Anda mau.
Dan terus terang, itulah satu-satunya sumber daya kita akan memiliki akses ke.
Dan sekali kita kembali ke keyboard dan memiliki sesuatu seperti C pada kami
pembuangan, kita hanya menulis program yang dapat melakukan satu hal pada suatu waktu.
Padahal, orang-orang ini beberapa saat yang lalu, kami leveraged kekuatan otak kolektif mereka
seperti kalian lakukan di minggu nol.
Jadi mari kita terus melakukan hal ini.
>> Dua dan satu.
Dua dan tiga.
Tiga dan empat.
Empat dan lima.
Lima dan enam.
Enam dan tujuh.
Selesai?
Jadi saya, tapi biarkan aku bermain advokat setan.
Apakah saya, jenis komputer yang hanya membuat lulus melalui array ini
orang, tahu bahwa aku sudah selesai?
>> SPEAKER 1: No
>> DAVID J. Malan: Jadi mengapa?
Apa yang harus saya lakukan untuk menyimpulkan tegas bahwa saya lakukan?
Mungkin satu lulus lagi.
Benar?
Karena semua saya tahu dari yang sebelumnya lulus adalah bahwa saya dikoreksi kesalahan.
Dan itu berarti, mungkin ada masih kesalahan lain
yang saya butuhkan untuk memperbaiki.
Jadi saya hanya bisa yakin dengan memutar, dan kemudian memeriksa, 1-2, dua
tiga, tiga dan empat, empat dan lima, lima dan enam, enam dan tujuh.
OK, sekarang saya tidak melakukan pekerjaan.
>> Aku pasti ingat bahwa saya tidak melakukan bekerja dengan sesuatu seperti variabel,
seperti int.
Sebut saja swap, dan jika swap adalah 0 setelah saya sampai di sini, dan itu dimulai pada 0, maka
Aku hanya akan menjadi bodoh untuk terus bolak-balik, memeriksa lagi, dan
lagi, dan lagi, kan?
Karena Anda terjebak di beberapa jenis loop tak terbatas.
Jadi, segera setelah ada 0 swap, kita dapat mengklaim bahwa ini
Algoritma ini memang lengkap.
>> Sekarang, mari kita menempatkan nama ini.
Algoritma yang saya usulkan kita hanya diimplementasikan adalah sesuatu yang disebut gelembung
semacam, yang dikenal sebagai tersebut dalam arti bahwa angka-angka yang agak lebih besar
gelembung jalan mereka ke atas, atau naik ke akhir array angka.
Tapi bagaimana efisien adalah algoritma ini?
Berapa banyak langkah aku secara fisik harus mengambil, misalnya, untuk memilah ini
tujuh manusia?
>> Empat sampai lima?
OK, terlalu banyak pada akhirnya akan menjadi jawabannya.
Tetapi bahkan kemudian, jumlah tertentu tidak begitu menarik.
Mari kita generalisasi sebagai n.
Jadi jika aku n orang di sini, dan mereka itu, semacam, dalam urutan acak di
dimulai, dalam urutan asli.
Nah, berapa banyak langkah yang saya punya untuk mengambil pada lulus pertama?
Itu salah satu, dua, tiga, empat, lima, enam, dan mereka tujuh orang, sehingga
itu adalah tujuh, enam -, sehingga n minus one langkah pertama kalinya.
>> Sekarang, berapa banyak langkah yang saya punya untuk mengambil ketika saya memutar ulang?
Nah, sebenarnya kita bisa dua kali lipat jika kita benar-benar ingin, tetapi untuk sekarang, aku
hanya akan mengatakan, oke, lain n dikurangi 1.
Jadi n dikurangi 1 akan mendapatkan menjengkelkan untuk melacak, jadi mari kita
hanya mengumpulkan sedikit.
Jadi 2n langkah.
Jadi 14 langkah, memberi atau mengambil.
>> Berapa kali saya ambil langkah waktu berikutnya?
Nah, itu 3n.
benar-benar.
Dan sekarang, dalam kasus terburuk, untuk Misalnya, berapa kali akan saya
pergi bolak-balik, bolak-balik, eksekusi algoritma ini, swapping
orang pada setiap lulus, kira-kira?
Ini sebenarnya n kuadrat, kan?
>> Karena dalam kasus terburuk, Anda dapat jenis dari berpikir tentang hal ini secara intuitif,
meskipun mungkin mengambil sedikit sedikit waktu untuk meresap
Dalam kasus terburuk, apa yang akan ini tujuh orang telah tampak seperti, di
syarat dari perjanjian jumlah mereka?
Benar-benar mundur, kan?
Dan hanya untuk mensimulasikan itu, siapa nama Anda lagi?
>> MIKE: Mike.
>> DAVID J. Malan: Mike?
OK, Mike, bisakah kau bergabung dengan saya di atas di sini untuk hanya satu detik?
Sebenarnya, tidak.
Maaf Mike, mari kita mundur.
Apa nama Anda lagi?
>> NEIL: Neil.
>> DAVID J. Malan: Neil.
OK, Neil, Anda datang dengan saya, jika Anda tidak keberatan.
Jadi aku akan mengusulkan, hanya untuk kesederhanaan, bahwa Neil sekarang dalam bukunya
mungkin kasus terburuk.
Tapi mengingat bagaimana saya menerapkan algoritma saya.
Saya membandingkan, membandingkan, membandingkan, membandingkan, membandingkan, oh.
Sekarang orang-orang ini keluar ketertiban, jadi aku memperbaikinya.
Jadi kalian bertukar.
Tapi mempertimbangkan sekarang, seberapa jauh lagi Neil tidak harus pergi?
Ini kira-kira n.
Kau tahu, itu tidak benar-benar n.
Ini seperti, n dikurangi 1, tapi aku mendapatkan melacak kesal kecil
nomor, jadi mari kita sebut saja n.
>> Jadi jika Neil bergerak satu langkah maksimal masing-masing waktu, dan untuk memindahkan Neil satu langkah,
Saya harus membuat ini benar-benar membosankan lulus bolak-balik, ini kira-kira
melakukan hal ini, n langkah, total n kali, karena itu akan membawa saya
bahwa banyak langkah untuk mendapatkan Neil semua cara untuk mana ia berada.
Jangankan orang lain jika kalian semua mis-memerintahkan juga.
>> Jadi mari kita sebut bubble sort n kuadrat.
Waktu berjalan dari algoritma ini, kinerja algoritma ini,
efisiensi algoritma ini, kami hanya akan menjelaskan lebih
umumnya sebagai n kuadrat.
Yang bagus, karena saya bisa melakukan Contoh yang sama dengan delapan orang, sembilan
orang, satu juta orang, dan bahwa Jawabannya tidak akan berubah.
>> Jadi jika kalian tidak keberatan, mari kita ulang Anda ke tempat Anda memulai.
Dan mari kita coba dua pendekatan lain dan melihat apakah kita tidak bisa melakukan fundamental
lebih baik dari ini.
Jadi, kali ini, saya akan mengusulkan semacam algoritma yang berbeda.
Itu sangat pintar dari kita terakhir kali, dan kalian benar memiliki
naluri kanan hanya jenis swapping berpasangan.
Tapi kalau aku benar-benar ingin untuk pendekatan ini sederhana, dan tujuan saya adalah untuk memindahkan
semua nomor kecil dengan cara ini, dan mendorong semua nomor besar yang
way, kenapa tidak saya hanya melakukan itu di paling naif cara yang mungkin dan melihat apakah saya
bisa lebih baik dari apa yang merupakan cukup algoritma yang kompleks?
>> Jadi mari kita lihat.
Empat adalah angka yang cukup kecil, jadi aku akan meninggalkan Anda di sana saat.
Ooh, nomor dua adalah lebih baik.
Jadi bisa Anda hanya melangkah maju sebentar?
Ini adalah saat saya bernomor terkecil kandidat, dan aku akan ingat
bahwa dengan, seperti, variabel.
Tapi aku akan tetap memeriksa.
Apakah ada seseorang yang nomor lebih kecil?
Enam, no.
Oh, ada Neil lagi.
>> Jadi saya akan mendorong Anda kembali semacam konseptual.
Neil akan datang ke depan.
Dan sekarang, variabel yang saya gunakan untuk melacak yang memiliki terkecil
Jumlah diperbarui mengandung Lokasi Neil.
Nah, mari kita lihat.
Tiga, tujuh, lima.
Oke, aku tahu Neil adalah yang terkecil.
Apa hal yang paling sederhana untuk saya lakukan sekarang?
Aku tidak akan membuang-buang waktu saya dengan hanya menggelegak Neil satu tempat ke kiri.
Mengapa saya tidak hanya menempatkan Neil mana ia milik, yang tentu saja di mana?
>> Sepanjang perjalanan di awal.
Jadi Neil, ikut aku.
Dan apa nama Anda lagi?
>> GRACE: Grace.
>> DAVID J. Malan: Grace.
OK.
Jadi Grace, sayangnya, Anda jenis di jalan.
Jadi bagaimana kita mengatasi masalah ini?
Benar?
Jika ini adalah sebuah array, ada hanya tujuh lokasi.
Ingat bahwa, dengan Rob, kita berbicara tentang menyatakan usia, dan kami hanya memiliki
jumlah terbatas usia?
Ide yang sama di sini.
Kami hanya memiliki jumlah terbatas ints.
Rahmat adalah jenis di kami cara, jadi bagaimana kita memperbaikinya?
>> Cara termudah adalah seperti, Grace, maaf.
Anda akan harus pergi ke ada sehingga kita bisa membuat ruang.
Sekarang, jika Anda berpikir tentang hal ini, mungkin kami hanya membuat masalah lebih buruk.
Dan mungkin kita lakukan, karena bagaimana jika Rahmat berada di tempat yang tepat?
Tapi kita tahu dia tidak, karena jika tidak, ia akan menjadi
berdiri ke depan bukannya Neil saat ini, kan?
Kami sudah memeriksa nomor keluar.
>> Baik.
Jadi sekarang, Neil ada di tempat yang tepat, dan Aku bisa melakukan optimasi sedikit.
Untuk menit berikutnya, aku akan mengabaikan Neil semua bersama-sama, agar tidak
membuang-buang waktu, atau tanpa sengaja menukar dia ke tempat yang salah.
Jadi sekarang, bagaimana saya menemukan berikutnya elemen yang terkecil?
Dua.
Itu angka yang cukup baik, jika Anda ingin melangkah maju dan
Aku akan mengingat Anda.
Enam, tidak baik.
Empat, tiga, tujuh, lima, tidak baik.
Jadi biarkan aku memindahkan Anda ke tempat yang tepat Anda.
Dan kita hanya beruntung saat ini.
>> Sekarang, aku akan mengabaikan dua orang, dan sekarang melakukan satu lagi
melewati ini.
Enam, bahwa sejumlah cukup kecil.
Ayo maju.
Oh, maaf.
Nomor Grace lebih baik, sehingga langkah di depan.
Empat.
Maaf, Grace.
Kembali lagi.
Nomor tiga adalah lebih baik.
Tujuh.
Lima.
Dan sekarang apa nama Anda lagi?
>> JASON: Jason.
>> DAVID J. Malan: Jason.
Jadi Jason kini terkecil Unsur Aku telah memilih.
Mana dia akan pergi?
Jadi di mana enam adalah.
Dan nama Anda lagi?
>> Gabe: Gabe.
>> DAVID J. Malan: Gabe.
Gabe ada di jalan.
Apa hal termudah untuk melakukannya?
Swap dua orang dan melanjutkan.
Jadi sekarang mari kita lihat.
Siapa yang terkecil?
Empat.
Biarkan aku hanya jenis cheat.
Lima akan menjadi yang terkecil.
Saya menemukan berikutnya, jika, Anda ingin melangkah ke depan, apa yang harus saya lakukan dengan
orang-orang ini, dengan Gabe?
Swap lagi.
Jadi sekarang, masih sedikit rusak.
Saya menemukan Gabe menjadi yang terkecil, sehingga Aku pop dia, memindahkan kalian atas.
Dan dilakukan.
>> Jadi jawabannya adalah sama.
Hasil akhirnya adalah sama.
Manakah dari kedua algoritma lebih baik?
Yang kedua, saya mendengar.
Kenapa?
>> SPEAKER 3: Ini langkah n [Tak terdengar].
>> DAVID J. Malan: Ini langkah n paling banyak.
Menarik.
Jadi, apakah itu meskipun?
Jadi, bagaimana saya menemukan unsur terkecil?
Berapa banyak langkah yang harus saya ambil yang menemukan elemen terkecil?
Saya punya terlihat sepanjang jalan di akhir, kan?
Karena dalam kasus terburuk, apa jika Neil di sini?
Jadi hanya menemukan elemen terkecil membawaku n langkah, atau n dikurangi 1.
Tapi, OK.
Jadi memperbaiki Neil.
Ingat bahwa, satu menit atau lebih yang lalu.
>> Tapi bagaimana saya menemukan berikutnya unsur terkecil?
Ini n dikurangi 1, atau n minus 2 benar-benar, dari sejumlah langkah.
Jadi OK.
Jadi aku n minus 2.
Baik.
Sehingga terasa sedikit lebih baik.
Baik.
Berapa banyak langkah waktu berikutnya untuk menemukan nomor tiga?
Jadi n minus 4.
Jadi itu menurun, satu lebih sedikit langkah pada setiap iterasi.
Jadi ini tidak merasa lebih baik, kan?
Jika terakhir kali itu kira-kira n kali n, kali ini n dikurangi 1, ditambah n dikurangi
2, ditambah n dikurangi 3, ditambah n minus 4, titik, titik, titik.
Tetapi jika Anda ingat dari sekolah tinggi Anda buku teks, cheat kecil
lembar di bagian belakang yang memiliki formula, jika Anda menambahkan rangkaian angka,
berapakah jumlah total langkah akan saya ambil di sini?
>> Ini adalah salah satu dari mereka, seperti, n dikurangi 1, kali n, dibagi 2.
Jadi biarkan aku melihat apakah saya bisa menarik up ini untuk sesaat.
Dan lagi, aku agak pembulatan beberapa angka hanya untuk menjaga hidup kita sederhana,
tapi seingat saya, itu adalah sesuatu seperti jika Saya lakukan n dikurangi 1 hal, maka n dikurangi
2, maka n minus 3, itu kira-kira sesuatu seperti ini lebih dari 2, dan jika saya
kalikan hal ini, itu sebenarnya n persegi.
Itu tidak merasa terlalu baik. n dikurangi n lebih dari 2.
>> Tapi ada satu hal.
Dalam ilmu komputer, ketika masalah mulai mendapatkan menarik adalah ketika n
akan benar-benar besar.
Dan ketika n jadi sangat besar, yang dari nilai-nilai ini akan mendominasi semua
dari yang lain?
Ini semacam n kuadrat, kan?
Ya, membaginya dengan 2 cukup bagus.
Tetapi jika Anda sedang berbicara tentang miliaran dari bagian data, atau triliunan
bagian data, OK, jadi Anda dua kali lebih cepat.
Tapi siapa yang benar-benar peduli jika itu angka yang besar, jika faktor ini adalah apa yang
besar dan lebih besar.
Dan tentunya, itu membuat lebih dari perbedaan dari orang ini.
Jadi meskipun kalian benar, algoritma kedua, kita akan menyebutnya
selection sort, adalah, dalam dunia nyata, bit lebih cepat berpotensi, karena saya
mengambil sedikit dan lebih sedikit langkah setiap kali.
>> Ini tidak benar-benar fundamental lebih cepat.
Karena jika kita benar-benar bermain ini untuk nilai-nilai n yang besar, pada akhir
hari, untuk cukup besar n, itu masih akan merasa cukup lambat.
Nah, biarkan aku mengambil satu lulus terakhir pada saat itu.
Itulah apa yang saya sebut selection sort.
Bisakah kalian ulang dirimu untuk terakhir kalinya?
Dan dalam kasus terakhir ini, aku akan untuk mengusulkan sesuatu
disebut insertion sort.
Insertion sort ini, secara konseptual, sedikit berbeda.
>> Daripada pergi bolak-balik dan memilih elemen terkecil, aku
hanya akan berurusan dengan masing-masing orang seperti saya bertemu dengan mereka, dan masukkan
mereka ke tempat yang benar.
Jadi aku hanya akan mulai dengan Grace, dan saya melihat bahwa dia nomor empat.
Di mana nomor empat milik?
Aku belum mulai memilah apa-apa, sehingga Rahmat mendapat untuk tinggal di sana.
Dan sekarang aku akan mengklaim, jika Anda bisa mengambil langkah ke kanan, ini
daftar diurutkan, ini adalah saya Daftar tersisa disortir.
Jadi sekarang aku akan melanjutkan berikutnya, dan apa nama Anda lagi?
>> BRANSON: Branson.
>> DAVID J. Malan: Branson.
Jadi Branson adalah nomor dua.
Jadi aku akan membawa Anda keluar sejenak.
Dan sekarang, di mana Anda berada dalam array ini?
Jadi di sebelah kanan Grace.
Jadi sekali lagi, kita semacam membuat Rahmat melakukan banyak pekerjaan di sini.
Di mana kita menempatkan Anda?
Jadi kita akan geser Anda ke kiri, dan masukkan Branson sana.
Tapi sekarang saya menyatakan bahwa kalian selesai.
Tapi perhatikan, aku tidak menggunakan ruang ekstra.
Ini masih 2 elemen di sini, di sini 5.
Jumlah ukuran array adalah 7, jadi saya tidak curang, oke?
>> Jadi sekarang kita miliki, dengan Gabe sini, para nomor enam, di mana Anda berada?
Anda beruntung lagi.
Jadi Anda bisa tinggal di sana.
Hanya mengambil langkah sedikit ke kanan hanya untuk membuat jelas bahwa Anda diurutkan.
Dan sekarang kami memiliki Neil lagi, nomor satu, ke mana Anda pergi?
Dan sekarang adalah di mana kita akan mulai melihat bahwa algoritma ini, meskipun pada pertama
sekilas, terasa cukup pintar, menonton apa yang akan terjadi.
Jika Anda bisa melangkah maju.
>> Di mana kita ingin menempatkan Neil?
Jadi jelas di sini, jadi bagaimana kita mendapatkan Neil sana?
Mari kita lakukan ini langkah-demi-langkah.
Gabe, di mana Anda harus pergi?
Yap, jadi mengambil satu langkah besar, atau dua setengah-langkah untuk membuat
satu langkah di sana.
Grace, di mana Anda pergi?
Baik.
Jadi langkah lain.
Dan akhirnya, Branson?
Langkah lain.
Dan sekarang kita dapat menempatkan Neil ke tempatnya.
>> Jadi sekarang, lanjutkan logika ini.
Meskipun kita tidak bergeser Neil lebih, dan lebih, dan lebih, untuk menempatkan dia
mana ia pergi, dalam kasus terburuk, nomor berikutnya mungkin kita hadapi bisa
menjadi nomor, mengatakan, ada sejumlah nol, maka kita akan menggeser semua
orang-orang ini.
Misalkan ada sejumlah, negatif satu, maka kita harus bergeser
semua orang-orang ini.
Jadi kami benar-benar hanya semacam membalik masalah sekitar, sehingga kita
mentransfer beban dari proses seleksi sehingga penyisipan
proses, sehingga kalian hanya punya untuk bergerak kira-kira n dikurangi sesuatu
sejumlah langkah.
Dan bahwa sejumlah langkah hanya akan meningkat karena saya memilih nomor lainnya,
jika saya harus terus mendorong kalian kembali, dan kembali, dan kembali.
>> Jadi hal yang menyedihkan sekarang adalah semua ini algoritma n kuadrat.
Mari kita pergi ke depan dan berkat ini guys, dan memvisualisasikan sedikit
berbeda.
Sangat baik dilakukan.
>> [Tepuk Tangan]
>> Baik.
Di sana Anda pergi.
Terima kasih untuk -
>> BRANSON: [Tak terdengar] menjaga angka.
>> DAVID J. Malan: Tidak, Anda mungkin menjaga angka juga.
Baik.
Baik dilakukan.
Baik.
Jadi mari kita lihat apakah kita tidak bisa sekarang meringkas lebih cepat, dan lebih visual,
apa yang baru saja terjadi di sini sebagai berikut.
Aku akan pergi ke depan dan menarik Firefox.
Kami akan menghubungkan demonstrasi ini di website kursus itu.
Java adalah sedikit mengganggu untuk mendapatkan kerja di beberapa browser hari ini.
Jadi jika Anda bermain dengan ini di rumah, menyadari bahwa Anda mungkin perlu menggunakan Firefox
untuk mendapatkannya bekerja.
Dan apa yang akan saya lakukan dengan ini demonstrasi adalah sebagai berikut.
>> Di bagian bawah, saya memiliki sejumlah besar pilihan menu, termasuk start dan
tombol berhenti.
Juga, sebagai samping, tampaknya ada sebuah bug dalam program ini, dimana Anda
tidak bisa benar-benar melihat awal atau menghentikan tombol kecuali Anda memegang Command atau Alt
plus dan zoom in, yang anehnya menunjukkan lebih banyak tombol.
FYI Jadi jika Anda bermain dengan ini di rumah.
Sekarang aku akan klik Start hanya dalam saat, setelah menentukan penundaan,
seperti, 200 milidetik di sini, hanya sehingga kita bisa melihat apa yang terjadi.
>> Jadi saya mengklaim bahwa ini adalah visualisasi dari algoritma pertama
orang-orang itu, bubble sort, dimana kami bertukar orang berpasangan.
Wawasan kunci visualisasi ini adalah bahwa tinggi bar
merupakan ukuran nomor.
Jadi lebih tinggi bar, besar angkanya.
Shorter bar, lebih kecil jumlahnya.
Dan jika Anda perhatikan, kita akan melalui iterasi pertama algoritma ini,
swapping jumlah besar dan kecil, sehingga sejumlah kecil datang pertama dan
jumlah yang besar pergi ke kanan.
>> Dan segera setelah kami mendapatkan akhir array banyak lebih dari tujuh nomor, kami
akan kembali ke awal.
Dan mengantisipasi ini.
Di paling kiri, bahwa si kecil akan untuk swap ke samping, dan ini
Proses berulang.
Sekarang visualisasi ini dengan cepat mendapat membosankan, jadi biarkan aku pergi ke depan dan berhenti
, ubah delay sesuatu yang jauh cepat hanya untuk mendapatkan sekarang, merasakan
algoritma ini.
>> Jadi meskipun aku sudah melesat itu, ini adalah seperti upgrade prosesor saya, membeli
komputer baru.
Saya belum berubah secara mendasar saya algoritma, tapi Anda memang bisa melihat lebih banyak
jelas daripada dengan manusia, bahwa besar nomor menggelegak ke atas,
dan jumlah kecil menggelegak turun ke bawah.
Dan sekarang hal ini di sini diurutkan.
Dan sebagai samping, dalam kotak, ada hanya beberapa pembukuan sana untuk
membantu Anda menghitung berapa banyak perbandingan, atau berapa banyak swap memiliki
sebenarnya sudah dilakukan.
>> Nah, mari kita mencoba salah satu yang lain kita melihat.
Mari saya klik pada bubble sort sini, dan membiarkan saya memilih, dan ini halaman web secara keseluruhan
adalah sedikit buggy.
Mari kita menerima risiko dan jalankan lagi.
Di sana kami pergi.
Jadi mari kita melakukan semacam seleksi.
Aku tidak tahu mengapa menu muncul di sana.
Mari kita zoom in untuk memperbaikinya bug, mengubahnya ke 50.
Ah, mari kita benar-benar melakukan yang jauh lebih cepat.
Lima milidetik atau lebih, dan Start.
>> Jadi ini adalah semacam seleksi.
Jadi sekali lagi, berpikir tentang apa yang kita lakukan dengan manusia di sini.
Kami pergi melalui array dan dipilih elemen terkecil lagi,
dan lagi, dan lagi.
Sekarang saya menyatakan bahwa masih sangat buruk.
Itu masih n kuadrat, memberi atau mengambil, tapi itu, di dunia nyata, sedikit
lebih cepat, karena saya memang mengambil sedikit lebih sedikit langkah setiap waktu.
Tapi kita hanya berbicara apa?
Mungkin 40 atau jadi bar di sini?
Kita tidak berbicara 40 juta.
Jadi itu tidak benar-benar jelas bagi saya bahwa memang keuntungan yang signifikan.
>> Sekarang saya kembali dan mengubah kami algoritma ketiga, yang pilih
insertion sort.
Dan sekarang itu benar-benar kereta karena Menu benar-benar tidak harus di sana.
Jadi sekarang kita akan gulir kembali ke sini dan mulai algoritma ini.
Whoop, mulai dan berhenti.
Jadi ini satu jenis memiliki pola yang cukup untuk itu, dimana kita lagi
memasukkan manusia, atau kasus ini, bar menjadi
lokasi yang sesuai mereka.
Dan itu sudah dilakukan sebelum Aku berbalik.
Tapi yang satu ini juga, secara teori, masih n kuadrat.
>> Jadi mari kita lihat jika kita tidak bisa meringkas tersebut sebagai berikut.
Aku akan pergi ke depan dan hanya untuk memberikan kita semacam cara umum berbicara
tentang hal ini, izinkan saya memperkenalkan hanya sedikit notasi sini.
Kau akan melihat sesuatu yang disebut besar O, karena secara harfiah besar
O. Dan ini adalah cara yang komputer ilmuwan atau ahli matematika bahkan menggunakan
untuk menggambarkan waktu berjalan dari beberapa algoritma.
Berapa banyak langkah apakah itu benar-benar mengambil?
>> Sekarang aku akan mempermalukan diri sendiri dengan tulisan tangan saya di sini hanya dalam beberapa saat.
Tapi biarkan aku pergi ke depan dan mengatakan bahwa ini akan menjadi O besar di sini.
Dan biarkan saya memperkenalkan satu lagi simbol, omega modal.
Omega akan menjadi sebaliknya, dasarnya, dari big O. Sedangkan O besar
berarti, dalam kasus terburuk, berapa banyak waktu mungkin beberapa algoritma ambil, di
hal n, omega akan menjadi berapa banyak waktu mungkin itu
mengambil dalam kasus terbaik.
Dan kita akan melihat apa yang kita maksud dengan kasus terbaik hanya dalam beberapa saat.
>> Jadi mari kita mulai sesuatu yang sederhana.
Mari saya mulai dengan pencarian linear.
Jadi tidak penyortiran.
Kita akan menyebutnya pencarian linear.
Dan sekarang, membuat sedikit tabel keluar dari ini.
Dan sekarang, dalam kasus pencarian linear, dalam kasus terburuk, berapa banyak langkah yang
itu akan membawa saya untuk menemukan jumlah pilihan sewenang-wenang?
Dan ada jumlah pintu n atau n jumlah total.
Kasus terburuk.
Berapa banyak langkah yang akan saya harus ambil untuk mencari nomor 50 dalam array
n pintu?
Dan mengapa?
Karena mungkin semua cara di atas ke akhir.
Begitu banyak seperti Jennifer dihadapi, nomor 50 itu semua cara di atas, sehingga dalam
kasus terburuk pencarian linear adalah O besar n, kita akan mengatakan.
>> Bagaimana dengan kasus terbaik, jika Anda benar-benar beruntung?
Ini hanya akan mengambil satu langkah, atau sejumlah konstan langkah.
Jadi kami akan menjelaskan bahwa sebagai 1.
Jadi ini cukup baik.
Sekarang bagaimana jika kita melakukan sesuatu seperti pencarian biner?
Jadi pencarian biner, yang terburuk kasus, mengambil berapa banyak waktu?
>> [Interposing SUARA]
>> DAVID J. Malan: Jadi sebenarnya, saya mendengarnya di beberapa tempat.
Jadi itu benar-benar log n, memberi atau mengambil, karena seperti yang kita membagi daftar dalam setengah
lagi, dan lagi, dan lagi, kami dapat untuk menemukan, pada akhirnya, nilai,
jika itu ada, tapi ada menangkap.
Apa asumsi bahwa kita harus mengambil untuk diberikan untuk pencarian biner?
Itu harus diurutkan.
Ini tidak diurutkan, Anda dapat membagi hal dalam setengah lagi dan lagi, dan Anda
bisa ke kiri, dan Anda dapat pergi ke kanan, dan Anda dapat pergi kiri dan kanan, tapi kau
tidak akan menemukan elemen jika Daftar ini tidak diurutkan, karena
Anda mungkin kehilangan itu.
Karena heuristik Anda, untuk pergi kiri atau kanan yang akan cacat jika
memang tidak diurutkan.
Jadi ada semacam biaya tersembunyi menggunakan sesuatu seperti ini.
>> Sekarang, mari kita pergi ke pemilahan kami algoritma tidak mencari -
oh, benar-benar membiarkan kita masuk kosong.
Pencarian biner dalam kasus terbaik?
Ini juga 1 jika itu hanya kebetulan di bagian paling tengah dari array, atau
tengah buku telepon.
Sekarang mari kita lakukan bubble sort.
Jadi sekali lagi, sekarang kita memasuki macam, bukan pencarian.
>> Dalam kasus terburuk, berapa banyak langkah yang kita klaim bubble sort akan mengambil?
n kuadrat.
Jadi aku akan menggambar itu.
Ooh, tulisan tangan saya terlihat lebih buruk ketika itu diproyeksikan sebesar itu.
Baik.
Jadi itu n kuadrat.
Dan dalam kasus terbaik dari bubble sort, berapa banyak langkah itu akan berlangsung?
1, aku mendengar.
>> SPEAKER 1: n.
>> DAVID J. Malan: n, aku mendengar.
>> SPEAKER 1: 2.
>> DAVID J. Malan: 2, saya mendengar.
Apakah saya mendengar 3?
Baik.
Begitulah yang saya dengar 1, n, 2, tetapi mari kita memilih terpisah setidaknya pertama mereka
saran, 1.
Ini bukan naluri buruk, karena itu jenis mengikuti pola di sini.
Tapi jika hanya membutuhkan 1 langkah, bagaimana dalam dunia bisa saya mengklaim bahwa daftar
diurutkan, karena jika saya hanya diperbolehkan untuk mengambil 1 langkah, berapa banyak elemen
Aku benar-benar bisa memeriksa untuk memastikan?
Yah, hanya 1, yang berarti ada n dikurangi 1 elemen yang bisa keluar dari
ketertiban, dan aku hanya akan pada iman setelah melihat 1 elemen yang
hal yang diurutkan.
Jadi 1 yang tidak benar di sini.
Jadi minimal, berapa banyak aku harus melihat?
>> [Interposing SUARA]
>> DAVID J. Malan: n dikurangi 1, atau benar-benar, n, karena saya perlu melihat setiap
Unsur memastikan bahwa itu tidak rusak.
Tapi sekali lagi, kita akan mengurutkan gelombang kami tangan di angka yang lebih kecil dan
berasumsi bahwa, sebagai n mendapat besar, mereka menarik pula.
Jadi itulah bubble sort.
Dan sekarang, mari kita lakukan ini dua terakhir.
Selection sort, dan kemudian kita akan melakukan insertion sort.
Dan kemudian kita akan meniup Anda pikiran dengan sesuatu yang jauh
lebih baik dari semua ini.
Baik.
>> Apa kasus terburuk berjalan waktu selection sort?
>> SPEAKER 4: n kuadrat.
>> DAVID J. Malan: n persegi, kudengar.
Tapi mengapa n kuadrat, intuitif?
>> SPEAKER 4: Karena kami hanya melakukannya.
>> DAVID J. Malan: Karena kami hanya melakukannya.
OK.
Jawaban yang bagus.
Tapi intuitif, mengapa pemilihan semacam n kuadrat?
Apa yang harus kita lakukan lagi dan lagi?
Kita harus menjaga pemindaian melalui, adalah Anda yang terkecil, adalah Anda
terkecil, kau yang terkecil.
Dan memang, kita mampu mengambil n langkah, maka n dikurangi 1, maka n minus 2.
Tetapi jika Anda jenis menambahkan mereka semuanya, atau mengambil pada iman bahwa saya telah menambahkan
mereka di muka, kita mendapatkan kira-kira n kuadrat minus beberapa nomor lebih kecil.
Jadi aku akan menelepon n kuadrat ini.
Tetapi dengan semacam seleksi yang terbaik kasus, berapa banyak langkah itu
akan membawa saya?
>> SPEAKER 5: [Tak terdengar]
>> DAVID J. Malan: Ini sayangnya masih n kuadrat, kan?
Karena jika aku memilih terkecil elemen, dan kami memiliki tujuh orang di sini,
Aku hanya tahu, setelah saya sampai ke sangat end, bahwa saya telah menemukan terkecil
nomor, di mana pun ia atau ia mungkin telah.
Tapi bagaimana saya menemukan berikutnya nomor terkecil?
Aku harus melakukan lulus lain.
Jadi dalam kasus terbaik, apa input ke selection sort?
Ini adalah daftar semacam sudah, nomor satu, nomor dua, nomor tiga, nomor empat.
Tapi aku komputer.
Saya hanya dapat melihat satu hal pada suatu waktu.
Aku tidak bisa semacam mengambil langkah kembali seperti manusia dan berkata,
ooh, ini terlihat benar.
>> Aku hanya bisa mengadili ketepatan dalam Pilihan semacam dengan memilih
nomor terkecil.
Tetapi bahkan jika saya menemukan nomor satu pertama, jika saya tidak tahu apa-apa lagi tentang
nomor lain, yang tidak saya lakukan, semua yang saya tahu bahwa saya telah menyerahkan sebuah array
atau satu set pintu belakang yang angka, satu-satunya cara saya tahu bahwa salah satu
adalah yang terkecil?
Jika saya mendapatkan semua jalan di sini dan menyadari, sialan, salah satu memang yang terkecil.
>> Tapi bagaimana saya kemudian menentukan bahwa keduanya adalah terkecil berikutnya?
Dengan melakukan inefisiensi yang sama lagi dan lagi.
Jadi akhirnya, dengan insertion sort, bagaimana, dalam kasus terburuk,
Apakah kita mengatakan itu melakukan?
Ini juga adalah n kuadrat.
Dan bagaimana dengan kasus terbaik?
Kami akan meninggalkan bahwa sebagai Cliffhanger.
Kita akan mengisi yang kosong waktu berikutnya, tapi pertama-tama saya mengusulkan agar kita
dasarnya melakukan lebih baik dari semua ini, oke?
>> Jadi pikirkan sendiri apa penyisipan semacam akan menjadi.
Nah, yang tidak sangat dramatis, karena aku satu-satunya
yang melihat perubahan.
Wow.
OK.
Jadi di sini kita memiliki sedikit Demonstrasi yang berbeda.
Jika saya memperbesar sini, Anda akan melihat bahwa pada kiri kita memiliki bubble sort, dalam
tengah kita memiliki semacam seleksi, dan paling kanan, kita memiliki sesuatu yang kita
belum melihat belum disebut menggabungkan semacam.
Tapi mempertimbangkan apa yang telah kita lakukan di sini sejauh ini.
Ketika Jennifer pertama kali muncul di atas panggung, kami pergi melalui array angka
lagi, dan lagi, dengan pencarian linear, dan kami punya waktu berjalan linear, O besar
n, sehingga untuk berbicara.
>> Ketika kita sekarang mempertimbangkan minggu pertama kelas, ketika kami telah membagi dan menaklukkan,
dan kami telah merobek buku telepon, dan Jennifer, dan kita secara kolektif
leveraged bahwa wawasan kunci, yang adalah ulangi sendiri lagi dan lagi oleh
entah bagaimana membuang, membuang, membuang, setengah dari masalah, atau
umumnya, membagi masalah dalam setengah, dan kemudian mengobati bagian yang lebih kecil dari
masalah sebagai konseptual setara yang lain, kami entah bagaimana melakukan
fundamental yang lebih baik.
Tetapi dengan bubble sort, dengan seleksi semacam, dengan insertion sort, kita sudah dapat
ada wawasan sehingga Jennifer lakukan.
Kami cukup banyak hanya berjalan kembali dan sebagainya sejumlah besar kali, dan kami
hal tweak sedikit, swapping dalam urutan ini, mungkin
memasukkan atau memilih.
Tetapi pada akhir hari, saya melakukan banyak canggung berjalan kembali dan sebagainya.
Kami tidak benar-benar memanfaatkan sesuatu pintar seperti Jennifer lakukan seperti membagi
dan menaklukkan.
>> Jadi menggabungkan semacam, sebaliknya, yang kita tidak akan melihat sampai minggu depan, itu akan
untuk memanfaatkan ide kunci dengan membagi input, dan kemudian mengurangi separuh, dan kemudian
mengurangi separuh, dan kemudian membagi dua.
Dan pada setiap iterasi dari loop itu, menyortir kiri setengah, dan hak
setengah, maka kiri setengah dari setengah kiri, dan bagian kanan kiri, kemudian
kiri setengah dari bagian kanan, dan bagian kanan bagian kanan.
Dan mengulangi lagi dan lagi.
>> Jadi, Anda akan melihat ini secara visual, tapi ini adalah apa yang menanti kita minggu depan.
Dan secara umum, ketika kita berpikir sedikit sedikit lebih keras pada masalah tersebut.
Kami memiliki n kuadrat di sebelah kiri, n kuadrat di tengah, dan n
log n di sebelah kanan.
Jadi ada cliffhanger sesungguhnya.
Kita akan melihat Anda pada hari Senin.
>> [Tepuk Tangan]