1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Baiklah, ini adalah CS50. 3 00:00:14,910 --> 00:00:19,020 Ini adalah akhir minggu ketiga, dan jika Anda belum mengambil keuntungan sudah, 4 00:00:19,020 --> 00:00:21,790 tahu bahwa akan ada makan siang Jumat ini seperti biasa, di mana 5 00:00:21,790 --> 00:00:25,430 Anda dapat menikmati percakapan yang baik dan makanan di Fire and Ice 6 00:00:25,430 --> 00:00:27,980 dengan beberapa CS50 ini staf dan teman sekelas. 7 00:00:27,980 --> 00:00:30,170 Kepala ke URL ini di sini. 8 00:00:30,170 --> 00:00:33,420 >> Sekarang Anda mungkin ingat, atau Anda akan segera berkenalan dengan, 9 00:00:33,420 --> 00:00:35,970 hal ini di sini, yang yang diberikan pada akhir 10 00:00:35,970 --> 00:00:37,850 semester untuk banyak kelas. 11 00:00:37,850 --> 00:00:40,870 Buku biru yang disebut ujian, di mana Anda menulis jawaban Anda untuk ujian. 12 00:00:40,870 --> 00:00:44,240 Sekarang aku punya di sini 26 seperti buku biru, pada masing-masing 13 00:00:44,240 --> 00:00:47,580 ditulis nama, A sampai Z. Dan memang nama-nama yang sederhana, A 14 00:00:47,580 --> 00:00:50,490 melalui Z. Dan salah satu tujuan di tangan hari ini 15 00:00:50,490 --> 00:00:53,910 akan menjadi untuk melanjutkan apa kami mulai pada hari Senin, yang tidak 16 00:00:53,910 --> 00:00:57,830 begitu banyak melihat kode, tapi benar-benar melihat ide-ide dan pemecahan masalah. 17 00:00:57,830 --> 00:01:00,170 Salah satu tujuan dan janji-janji saja ini 18 00:01:00,170 --> 00:01:02,985 adalah untuk mengajarkan Anda untuk berpikir lebih hati-hati, lebih metodis, 19 00:01:02,985 --> 00:01:05,400 dan untuk memecahkan masalah lebih efisien. 20 00:01:05,400 --> 00:01:09,526 Dan memang, kita bisa melakukan itu benar-benar bahkan tanpa menyentuh baris kode. 21 00:01:09,526 --> 00:01:12,150 Jadi saya memiliki beberapa gajah di sini hari ini, oranye dan biru, 22 00:01:12,150 --> 00:01:15,780 jika kita bisa mendapatkan satu relawan, mungkin dari jauh di belakang dari biasanya. 23 00:01:15,780 --> 00:01:18,070 Bagaimana di sana, datang di bawah. 24 00:01:18,070 --> 00:01:24,180 Tujuan yang akan menjadi untuk membantu ditambah melaksanakan ujian ini di sini. 25 00:01:24,180 --> 00:01:24,935 Siapa nama Anda? 26 00:01:24,935 --> 00:01:25,768 >> AUDIENCE: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, datang ke atas. 28 00:01:27,560 --> 00:01:29,560 Biarkan aku mendapatkan mikrofon di sini untuk Anda. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Senang bertemu Anda. 31 00:01:32,880 --> 00:01:34,005 >> AUDIENCE: Senang bertemu Anda. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Baiklah, jadi saya memiliki di sini buku biru A sampai Z, 33 00:01:36,790 --> 00:01:41,680 dan aku akan berpura-pura bahwa Saya memiliki salah satu siswa, 34 00:01:41,680 --> 00:01:45,770 dan mereka datang agak acak pada akhir ujian blok tiga jam, 35 00:01:45,770 --> 00:01:49,400 jadi mereka berakhir di beberapa urutan semi-acak seperti ini. 36 00:01:49,400 --> 00:01:54,510 Sekarang pekerjaan Anda hanya dalam beberapa saat akan untuk akan-- ini sebenarnya bagaimana mereka mendapatkan 37 00:01:54,510 --> 00:01:56,820 berbalik pada akhir kelas, kemungkinan besar. 38 00:01:56,820 --> 00:02:01,120 Tugas Anda sekarang akan menjadi, cukup sederhana, untuk memilah buku-buku biru untuk kita 39 00:02:01,120 --> 00:02:05,220 dari A sampai Z. 40 00:02:05,220 --> 00:02:08,400 >> AUDIENCE: Oh, ini adalah akan mengambil selamanya. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: Dan kita akan melihatnya setelah Anda melakukan ini, tidak ada tekanan. 42 00:02:13,747 --> 00:02:15,330 AUDIENCE: Tidak, tidak ada tekanan atau apa pun. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: Dan untuk bersenang-senang, mari kita memasang timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> AUDIENCE: Sangat menyenangkan, sangat menyenangkan. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Aku bisa memegang mic untuk Anda. 49 00:02:38,574 --> 00:02:40,240 Baiklah, kita baru saja dua kali lipat kecepatan kami. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Jadi sementara itu, biarkan aku berpose apa akan menjadi pertanyaan bagi Mary Beth 52 00:02:49,060 --> 00:02:51,540 adalah apa yang dia lakukan, bagaimana dia akan tentang memecahkan ini? 53 00:02:51,540 --> 00:02:54,040 Dan pada kenyataannya, Anda mungkin tidak memiliki pernah berpikir tentang sesuatu 54 00:02:54,040 --> 00:02:57,440 begitu sederhana seperti ketika Anda memilih naik 26 buku seperti ini, 55 00:02:57,440 --> 00:02:59,350 yang tidak memiliki alami memerintahkan kepada mereka. 56 00:02:59,350 --> 00:03:01,335 Bagaimana prosesnya bahwa Anda benar-benar digunakan? 57 00:03:01,335 --> 00:03:03,770 Apakah cukup acak hanya memilih salah satu pertama yang Anda lihat 58 00:03:03,770 --> 00:03:05,250 dan memasukkannya ke dalam tempatnya? 59 00:03:05,250 --> 00:03:09,680 Apakah Anda pertama kali memindahkan tangan Anda di sekitar mencari A kemudian mencari B? 60 00:03:09,680 --> 00:03:11,722 Apakah anda melihat pada sepasang mereka berdampingan 61 00:03:11,722 --> 00:03:14,680 dan hanya mengatakan, tunggu dulu, ini tidak benar, dan kemudian swap order? 62 00:03:14,680 --> 00:03:16,960 Kami melihat sudah pada Senin bahwa ada sejumlah cara 63 00:03:16,960 --> 00:03:22,140 di mana kita bisa melakukan ini, dan memang seperti yang kita mendekati akhir di sini, 64 00:03:22,140 --> 00:03:26,360 Saya akan perhatikan mungkin apa Mary Beth lakukan. 65 00:03:26,360 --> 00:03:30,040 Kami memiliki beberapa tumpukan tampaknya, a lebih besar, tiga yang lebih kecil. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> AUDIENCE: Aku memerintahkan mereka ketika saya menemukan dua surat 68 00:03:36,415 --> 00:03:39,540 yang saya tahu bersama-sama secara berurutan, Aku menempatkan mereka bersama-sama sehingga saya tidak 69 00:03:39,540 --> 00:03:42,915 perlu khawatir tentang menjaga melacak seluruh baris buku. 70 00:03:42,915 --> 00:03:45,706 Hanya saja, oh, A pertama, Aku punya setumpuk ini di sini. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Jadi, hampir seperti potongan teka-teki yang 72 00:03:47,580 --> 00:03:49,860 memiliki bentuk yang tepat untuk cocok dengan satu sama lain. 73 00:03:49,860 --> 00:03:51,026 AUDIENCE: Cukup banyak, ya. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, baik. 75 00:03:55,320 --> 00:03:59,850 Dan sekarang masing-masing tumpukan kiranya diurutkan? 76 00:03:59,850 --> 00:04:00,990 >> AUDIENCE: Ya. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Baiklah, A sampai Z. Semua benar, selamat, Anda melakukannya. 78 00:04:09,900 --> 00:04:11,461 Anda memiliki pilihan Anda. 79 00:04:11,461 --> 00:04:11,960 Biru? 80 00:04:11,960 --> 00:04:13,530 Baiklah, terima kasih untuk itu. 81 00:04:13,530 --> 00:04:16,679 Jadi Mary Beth tidak mengusulkan apa pendekatannya adalah, 82 00:04:16,679 --> 00:04:19,720 tapi apa pendekatan lain bagaimana Anda bisa pergi tentang menyortir hal-hal ini? 83 00:04:19,720 --> 00:04:21,130 Apa yang akan Anda lakukan? 84 00:04:21,130 --> 00:04:24,060 Rekor untuk mengalahkan pasti satu menit dan 50 detik atau lebih, 85 00:04:24,060 --> 00:04:26,039 ditambah yang saya lupa untuk menghitung. 86 00:04:26,039 --> 00:04:27,080 Apa yang akan Anda lakukan? 87 00:04:27,080 --> 00:04:27,579 Ya? 88 00:04:27,579 --> 00:04:28,735 AUDIENCE: Ambil tumpukan. 89 00:04:28,735 --> 00:04:29,776 Mulai dari awal. 90 00:04:29,776 --> 00:04:32,284 Periksa surat-surat Anda. 91 00:04:32,284 --> 00:04:36,586 Dan jika yang paling atas adalah lebih tinggi dari, mungkin, mereka, 92 00:04:36,586 --> 00:04:38,980 bagian bawah adalah lebih tinggi, kemudian beralih mereka. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, jadi mulai di bagian atas dan bawah, 94 00:04:41,300 --> 00:04:43,716 dan kemudian bekerja dengan cara Anda batin seperti itu, bertukar mereka? 95 00:04:43,716 --> 00:04:46,580 OK, jadi sedikit mirip semangat yang bubble sort, 96 00:04:46,580 --> 00:04:49,160 tetapi memilih ekstrem bukan pasangan yang berdekatan. 97 00:04:49,160 --> 00:04:52,080 Tapi pendek itu adalah bahwa ada pasti banyak cara yang berbeda 98 00:04:52,080 --> 00:04:54,210 kita bisa melakukan ini, dan terus terang, saya pikir Anda jenis 99 00:04:54,210 --> 00:04:55,700 mengadopsi beberapa pendekatan, kan? 100 00:04:55,700 --> 00:05:00,567 Anda membuat semacam empat tumpukan diurutkan, dan kemudian secara efektif bergabung bersama-sama. 101 00:05:00,567 --> 00:05:02,650 Dan itu, berani bilang, lain Teknik sama sekali. 102 00:05:02,650 --> 00:05:06,950 Anda tidak memperlakukannya sebagai salah satu tumpukan besar, Anda membagi masalah menjadi empat paha depan, 103 00:05:06,950 --> 00:05:09,820 jika Anda mau, dan kemudian entah bagaimana bergabung mereka pada akhirnya. 104 00:05:09,820 --> 00:05:13,410 >> Jadi mari kita pertimbangkan, akhirnya, bagaimana lagi kita bisa melakukan hal ini. 105 00:05:13,410 --> 00:05:15,860 Kami diformalkan gagasan dari bubble sort terakhir kali, 106 00:05:15,860 --> 00:05:18,780 dan bubble sort ingat adalah algoritma yang kita divisualisasikan 107 00:05:18,780 --> 00:05:22,640 dengan delapan dari teman sekelas Anda di sini, tampaknya secara acak diurutkan pada awalnya. 108 00:05:22,640 --> 00:05:26,110 Dan kami kemudian memutuskan berpasangan, jika dua elemen yang rusak, 109 00:05:26,110 --> 00:05:26,950 hanya swap mereka. 110 00:05:26,950 --> 00:05:28,930 Jadi empat dan dua jelas rusak, 111 00:05:28,930 --> 00:05:31,080 sehingga kedua teman sekelas beralih posisi. 112 00:05:31,080 --> 00:05:35,390 Dan kemudian kami mengulangi dengan empat dan enam, kemudian enam dan delapan, pada setiap iterasi, 113 00:05:35,390 --> 00:05:36,980 bergerak ke kanan. 114 00:05:36,980 --> 00:05:42,590 >> Jadi mengingat delapan orang, berapa banyak berpasangan perbandingan yang saya lakukan sambil berjalan dari 115 00:05:42,590 --> 00:05:45,220 kiri ke kanan dalam satu iterasi seperti itu? 116 00:05:45,220 --> 00:05:48,410 Berapa banyak perbandingan? 117 00:05:48,410 --> 00:05:49,197 Seven, kan? 118 00:05:49,197 --> 00:05:51,405 Karena jika ada delapan orang, tetapi Anda memiliki pasangan 119 00:05:51,405 --> 00:05:53,880 mereka dan Anda terus bergerak satu hop ke kanan, 120 00:05:53,880 --> 00:05:56,060 Anda tidak akan memiliki delapan perbandingan karena Anda tidak bisa membandingkan 121 00:05:56,060 --> 00:05:59,226 unsur melawan dirinya sendiri, atau itu akan hanya ada gunanya, sehingga Anda memiliki tujuh. 122 00:05:59,226 --> 00:06:01,290 Atau lebih umum, jika kami memiliki n orang, kita 123 00:06:01,290 --> 00:06:04,300 lakukan n dikurangi 1 perbandingan dengan bubble sort. 124 00:06:04,300 --> 00:06:08,150 >> Jadi mari kita pertimbangkan sekarang bagaimana baik atau gelembung buruk semacam sebenarnya, dan mencoba 125 00:06:08,150 --> 00:06:13,570 untuk memberikan diri kita kosakata dengan yang cocok untuk algoritma kritik seperti ini, 126 00:06:13,570 --> 00:06:14,430 dan segera kita sendiri. 127 00:06:14,430 --> 00:06:16,970 Jadi lulus pertama melalui bubble sort, pertama kali 128 00:06:16,970 --> 00:06:20,909 Aku berjalan dari kiri ke kanan melintasi panggung, membawa saya n dikurangi 1 perbandingan. 129 00:06:20,909 --> 00:06:22,950 Dan itu akan menjadi saya satuan ukuran, kan? 130 00:06:22,950 --> 00:06:26,170 Aku agak berbicara dan berjalan-jalan, agak cepat, agak lambat, 131 00:06:26,170 --> 00:06:29,300 jadi menghitung jumlah saya detik tidak terutama mengatakan, 132 00:06:29,300 --> 00:06:32,260 tetapi menghitung jumlah operasi yang saya lakukan pada hari Senin, 133 00:06:32,260 --> 00:06:35,900 membandingkan dua orang, yang terasa seperti unit bagus ukuran. 134 00:06:35,900 --> 00:06:40,980 >> Jadi n dikurangi 1 langkah pertama kalinya, tapi kemudian apa yang terjadi setelah itu? 135 00:06:40,980 --> 00:06:46,610 Apa satu terbalik dari satu lulus melalui daftar jika tidak disortir? 136 00:06:46,610 --> 00:06:49,840 Apa yang bisa Anda ceritakan tentang elemen yang semua cara di atas sana? 137 00:06:49,840 --> 00:06:51,300 Ya? 138 00:06:51,300 --> 00:06:52,870 Itu adalah elemen terbesar, kan? 139 00:06:52,870 --> 00:06:55,710 Nomor delapan, meskipun dia mulai di sini, setiap kali saya 140 00:06:55,710 --> 00:06:57,860 dibandingkan melawan tetangga, dia terus 141 00:06:57,860 --> 00:07:00,480 menggelegak ke kanan sisi dari daftar. 142 00:07:00,480 --> 00:07:02,710 Dan memang, di situlah Algoritma mendapatkan namanya. 143 00:07:02,710 --> 00:07:07,630 >> Sekarang dengan logika itu, berapa banyak perbandingan perlu saya buat pada kedua kalinya 144 00:07:07,630 --> 00:07:09,800 Saya membuat pass yang dari kiri ke kanan? 145 00:07:09,800 --> 00:07:10,730 n minus 2, kan? 146 00:07:10,730 --> 00:07:14,297 Itu hanya akan membuang-buang waktu saya jika saya terus membandingkan delapan terhadap seseorang 147 00:07:14,297 --> 00:07:16,630 lain karena kita sudah tahu ia berada di tempat yang tepat. 148 00:07:16,630 --> 00:07:19,760 Jadi itu sedikit optimasi, sehingga lulus berikutnya 149 00:07:19,760 --> 00:07:23,899 akan menjadi ditambah n dikurangi dua langkah, dimana n adalah jumlah orang. 150 00:07:23,899 --> 00:07:26,940 Sekarang Anda dapat jenis ekstrapolasi, bahkan jika Anda tidak seorang ilmuwan komputer, 151 00:07:26,940 --> 00:07:27,680 bagaimana ini berakhir. 152 00:07:27,680 --> 00:07:31,259 Pada akhir algoritma ini, mungkin Anda punya hanya satu perbandingan tersisa. 153 00:07:31,259 --> 00:07:33,800 Anda harus jenis memperbaiki awal daftar dalam kasus dua 154 00:07:33,800 --> 00:07:36,540 dan salah satu yang rusak dan harus menjadi salah satu dan dua, 155 00:07:36,540 --> 00:07:40,330 jadi ini kentut di ditambah 1 perbandingan akhir. 156 00:07:40,330 --> 00:07:44,500 >> Sekarang dot, dot, dot jenis gelombang itu tangan pada beberapa rincian juicier, 157 00:07:44,500 --> 00:07:46,452 tapi mari kita pergi ke depan dan menyederhanakan. 158 00:07:46,452 --> 00:07:48,660 Jika Anda ingat dari tinggi sekolah, terus terang, banyak Anda 159 00:07:48,660 --> 00:07:50,340 memiliki buku matematika yang memiliki contekan kecil 160 00:07:50,340 --> 00:07:52,550 di sampul depan atau penutup belakang yang menunjukkan Anda 161 00:07:52,550 --> 00:07:56,400 penjumlahan seri apa seperti ini akhirnya ditambah hingga. 162 00:07:56,400 --> 00:07:59,600 Dalam kasus umum, jika Anda memiliki variabel seperti n, dan memang yang satu ini, 163 00:07:59,600 --> 00:08:01,634 jika Anda melihat Anda buku matematika sekolah tua, 164 00:08:01,634 --> 00:08:04,050 Anda akan melihat bahwa sebenarnya ini menambahkan hingga jumlah ini di sini, 165 00:08:04,050 --> 00:08:07,970 n kali n dikurangi 1 semua dibagi 2. 166 00:08:07,970 --> 00:08:11,172 Jadi untuk saat ini saya hanya menetapkan ini benar, seterusnya lompatan iman, 167 00:08:11,172 --> 00:08:12,880 itulah yang ini merangkum sampai, dan kita bisa 168 00:08:12,880 --> 00:08:14,341 membuktikan bahwa dalam kasus yang lebih umum. 169 00:08:14,341 --> 00:08:15,590 Tapi sekarang mari kita memperluas ini. 170 00:08:15,590 --> 00:08:19,920 Jadi mari kita kalikan hal ini, jadi itu n kuadrat, dikurangi n, semua dibagi 2. 171 00:08:19,920 --> 00:08:23,200 Itu benar-benar n kuadrat, dibagi 2, dikurangi n lebih dari 2, 172 00:08:23,200 --> 00:08:25,010 jadi itu semua bagus dan menarik. 173 00:08:25,010 --> 00:08:27,060 Tapi apa yang terjadi jika kita sekarang plug-in nilai? 174 00:08:27,060 --> 00:08:29,724 Misalkan aku tidak punya delapan orang, tetapi mengatakan satu juta. 175 00:08:29,724 --> 00:08:31,890 Dan satu juta hanya karena itu adalah angka yang cukup besar, 176 00:08:31,890 --> 00:08:34,039 mari kita pasang di itu dan melihat apa yang terjadi. 177 00:08:34,039 --> 00:08:39,039 Jadi jika saya pasang satu juta ke dalam rumus yang Aku akan mendapatkan satu juta kuadrat, 178 00:08:39,039 --> 00:08:42,868 dibagi 2, minus juta, dibagi 2. 179 00:08:42,868 --> 00:08:44,159 Sekarang apa yang akan sama? 180 00:08:44,159 --> 00:08:47,354 Jadi 500 miliar, dikurangi 500.000. 181 00:08:47,354 --> 00:08:49,270 Dan jika saya benar-benar melakukan bahwa matematika keluar, berarti bahwa 182 00:08:49,270 --> 00:08:53,920 bahwa menyortir satu juta orang dengan semacam gelembung 183 00:08:53,920 --> 00:09:01,800 mungkin membawa saya 499999500000 langkah-langkah atau perbandingan pada akhirnya, 184 00:09:01,800 --> 00:09:02,900 kami hanya ekstrapolasi. 185 00:09:02,900 --> 00:09:06,860 >> Yang terasa cukup lambat, tapi terus terang mengukur satu input tertentu 186 00:09:06,860 --> 00:09:09,160 seperti ini, tidak semua jitu itu. 187 00:09:09,160 --> 00:09:14,050 Tapi memang itu tidak menunjukkan bahwa sebagai n semakin besar dan lebih besar, algoritma ini 188 00:09:14,050 --> 00:09:16,280 jenis rasanya lebih buruk dan buruk, atau Anda benar-benar 189 00:09:16,280 --> 00:09:20,450 mulai merasakan sakit yang eksponensial, bahwa n kuadrat, 190 00:09:20,450 --> 00:09:21,770 yang menambahkan sampai cukup cepat. 191 00:09:21,770 --> 00:09:25,340 Dan detail ini tidak hilang pada orang, pada kenyataannya 192 00:09:25,340 --> 00:09:29,640 beberapa tahun yang lalu seorang senator tertentu yang kampanye, duduk untuk wawancara 193 00:09:29,640 --> 00:09:32,180 dengan Google Eric Schmidt, CEO pada saat itu, 194 00:09:32,180 --> 00:09:36,380 dan ditantang dengan pertanyaan seperti kita mengeksplorasi hari ini. 195 00:09:36,380 --> 00:09:38,468 Mari kita lihat. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO PEMUTARAN] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Kau di sini di Google, dan saya suka 198 00:09:48,560 --> 00:09:53,382 memikirkan presiden sebagai wawancara kerja. 199 00:09:53,382 --> 00:09:56,434 Sekarang, sulit untuk mendapatkan pekerjaan sebagai presiden, 200 00:09:56,434 --> 00:09:58,100 dan Anda akan melalui kerasnya sekarang. 201 00:09:58,100 --> 00:10:01,860 Hal ini juga sulit untuk mendapatkan pekerjaan di Google. 202 00:10:01,860 --> 00:10:05,490 Kami memiliki pertanyaan, dan kami mengajukan pertanyaan kandidat kami, 203 00:10:05,490 --> 00:10:09,770 dan ini adalah dari Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Apa-- kalian pikir aku bercanda, itu ada di sini. 205 00:10:14,760 --> 00:10:17,930 Apa cara yang paling efisien untuk mengurutkan satu juta 32-bit bilangan bulat? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> Maafkan aku, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Tidak, tidak, tidak. 210 00:10:27,400 --> 00:10:30,700 Saya pikir semacam gelembung akan menjadi cara yang salah untuk pergi. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Ayo, yang mengatakan kepadanya ini? 213 00:10:38,180 --> 00:10:40,590 Aku tidak melihat komputer ilmu di latar belakang Anda. 214 00:10:40,590 --> 00:10:42,130 >> -Kita Punya mata-mata kita di sana. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Mari kita bertanya berbeda pertanyaan wawancara. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PUTAR] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Jadi berbicara tentang nomor tertentu meskipun, 219 00:10:52,290 --> 00:10:53,890 tidak akan semua yang berguna. 220 00:10:53,890 --> 00:10:56,810 Ini bukan pelajaran hidup gelembung yang semacam, diberi juta input, 221 00:10:56,810 --> 00:10:58,590 mungkin mengambil sebanyak 500 miliar langkah. 222 00:10:58,590 --> 00:11:01,120 Anda tidak bisa benar-benar menggeneralisasi terlalu efektif dari yang 223 00:11:01,120 --> 00:11:03,560 dan membuat keputusan desain yang baik saat menulis program. 224 00:11:03,560 --> 00:11:07,070 Jadi mari kita fokus meskipun pada bagaimana kita mungkin menyederhanakan hasil ini. 225 00:11:07,070 --> 00:11:11,780 >> Jadi saya sudah ditandai dengan warna kuning di sini hasil n kuadrat dibagi 2, 226 00:11:11,780 --> 00:11:14,330 jadi satu juta kuadrat dibagi 2, dan kemudian 227 00:11:14,330 --> 00:11:16,710 Aku sudah disorot apa jawaban akhir adalah 228 00:11:16,710 --> 00:11:20,180 setelah kami dikurangi off n dibagi 2. 229 00:11:20,180 --> 00:11:24,850 Dan klaim saya akan buat sekarang adalah, siapa sih yang peduli jika Anda mengurangi off 230 00:11:24,850 --> 00:11:30,060 n tua sedikit lebih dari 2 ketika pertama bagian dari formula ini jauh lebih besar? 231 00:11:30,060 --> 00:11:33,910 Ini mendominasi yang lain istilah, n kuadrat dibagi 2 232 00:11:33,910 --> 00:11:37,510 adalah jauh lebih besar, jelas, sebagai n mendapat besar seperti satu juta, 233 00:11:37,510 --> 00:11:41,450 yang benar-benar ada perbedaan besar di akhir hari antara 500 miliar 234 00:11:41,450 --> 00:11:45,730 dan 499999500000? 235 00:11:45,730 --> 00:11:46,349 Tidak benar-benar. 236 00:11:46,349 --> 00:11:48,640 Dan jadi apa kita akan lakukan sebagai ilmuwan komputer 237 00:11:48,640 --> 00:11:53,270 mengabaikan orang-orang yang lebih rendah istilah ketertiban dan mengambil sesuatu seperti ini dan benar-benar 238 00:11:53,270 --> 00:11:56,050 hanya menyederhanakannya ke istilah yang akan peduli. 239 00:11:56,050 --> 00:12:00,315 Semakin besar set data kami dapatkan, semakin besar database kami dapatkan, halaman web yang lebih 240 00:12:00,315 --> 00:12:02,690 kita harus mencari, lebih Teman-teman yang Anda miliki di Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Sebagai n semakin besar, kami benar-benar akan peduli tentang terbesar 242 00:12:07,340 --> 00:12:11,560 Istilah dalam analisis seperti kinerja algoritma kami. 243 00:12:11,560 --> 00:12:16,230 Dan aku akan mengatakan, Anda tahu apa, bubble sort adalah pada urutan O besar, 244 00:12:16,230 --> 00:12:18,060 pada urutan n kuadrat. 245 00:12:18,060 --> 00:12:20,090 Ini tidak benar-benar n kuadrat seperti yang kita lihat, 246 00:12:20,090 --> 00:12:22,060 tapi siapa yang benar-benar peduli tentang istilah-istilah yang lebih kecil, 247 00:12:22,060 --> 00:12:24,390 dan terus terang, yang benar-benar peduli jika kita membagi dengan 2? 248 00:12:24,390 --> 00:12:25,870 Itu hanya faktor konstan. 249 00:12:25,870 --> 00:12:29,480 Dan adalah 500 miliar dibandingkan 250 miliar benar-benar masalah besar? 250 00:12:29,480 --> 00:12:32,190 Aku hanya bisa menunggu satu tahun, biarkan laptop saya benar-benar 251 00:12:32,190 --> 00:12:34,810 mendapatkan dua kali lebih cepat di perangkat keras, dan hal semacam perbedaan 252 00:12:34,810 --> 00:12:36,650 pergi begitu saja secara alami dari waktu ke waktu. 253 00:12:36,650 --> 00:12:39,300 >> Apa yang kita pedulikan adalah ekspresi, bagian 254 00:12:39,300 --> 00:12:42,489 dari ekspresi yang akan bervariasi sebagai masukan kami akan lebih besar dan lebih besar. 255 00:12:42,489 --> 00:12:45,280 Dan memang, di dunia nyata, itulah yang terjadi semakin 256 00:12:45,280 --> 00:12:48,330 adalah masukan untuk masalah kami dan algoritma yang semakin besar. 257 00:12:48,330 --> 00:12:53,470 Jadi O besar akan menjadi notasi, notasi asimtotik, bahwa kita hanya 258 00:12:53,470 --> 00:12:57,160 digunakan sebagai ilmuwan komputer untuk menggambarkan kinerja, atau waktu berjalan, 259 00:12:57,160 --> 00:12:58,130 dari algoritma. 260 00:12:58,130 --> 00:13:00,800 Sehingga kita dapat membandingkan algoritma pada komputer yang berbeda yang ditulis 261 00:13:00,800 --> 00:13:04,170 oleh orang yang berbeda, dengan menggunakan beberapa metrik dasarnya sama 262 00:13:04,170 --> 00:13:07,557 seperti jumlah perbandingan Anda membuat, atau mungkin jumlah swap 263 00:13:07,557 --> 00:13:08,140 Anda membuat. 264 00:13:08,140 --> 00:13:11,910 >> Apa yang kita tidak akan count adalah jumlah waktu 265 00:13:11,910 --> 00:13:13,981 yang melewati pada jam di dinding biasanya. 266 00:13:13,981 --> 00:13:16,230 Apa yang kita tidak akan khawatir tentang adalah berapa banyak memori 267 00:13:16,230 --> 00:13:17,820 Anda menggunakan hari ini di Setidaknya, meskipun itu 268 00:13:17,820 --> 00:13:19,370 sumber daya lain kita mungkin mengukur. 269 00:13:19,370 --> 00:13:23,610 Kami akan mencoba untuk mendasarkan analisis kami hanya pada operasi dasar, yang, 270 00:13:23,610 --> 00:13:25,930 terus terang, bahwa Anda dapat melihat sebagian visual. 271 00:13:25,930 --> 00:13:30,700 Jadi dengan sesuatu seperti O besar n kuadrat, saya menyatakan bahwa O n kuadrat 272 00:13:30,700 --> 00:13:35,820 merupakan batas atas pada apa yang disebut waktu berjalan dari bubble sort. 273 00:13:35,820 --> 00:13:38,820 Dengan kata lain, jika Anda ingin mengklaim bahwa ada 274 00:13:38,820 --> 00:13:41,370 batas atas ini pada berapa banyak langkah algoritma mungkin mengambil, 275 00:13:41,370 --> 00:13:46,240 itu akan berada di O besar n kuadrat dalam kasus ini, batas atas. 276 00:13:46,240 --> 00:13:49,710 >> Bagaimana jika saya bukan mengubah cerita menjadi bukan tentang bubble sort, 277 00:13:49,710 --> 00:13:50,910 tetapi hal ini batas atas. 278 00:13:50,910 --> 00:13:54,030 Dapatkah Anda memikirkan algoritma bahwa kita telah melihat sudah 279 00:13:54,030 --> 00:13:59,530 yang batas atas, maksimum mengukur waktu atau operasi, 280 00:13:59,530 --> 00:14:04,300 akan dikatakan dibatasi n, fungsi linear, 281 00:14:04,300 --> 00:14:07,260 tidak satu kuadrat yang melengkung? 282 00:14:07,260 --> 00:14:10,780 Apakah yang dimaksud dengan algoritma yang selalu tidak lebih 283 00:14:10,780 --> 00:14:12,860 daripada seperti langkah n, atau Langkah 2n, atau langkah-langkah 3n? 284 00:14:12,860 --> 00:14:13,360 Ya? 285 00:14:13,360 --> 00:14:15,030 >> AUDIENCE: Menemukan jumlah terbesar dalam daftar? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER Perfect, menemukan jumlah terbesar dalam daftar. 287 00:14:16,930 --> 00:14:18,940 Jika aku diberi daftar orang misalnya, 288 00:14:18,940 --> 00:14:21,440 masing-masing yang memegang nomor, apa jumlah maksimum 289 00:14:21,440 --> 00:14:23,770 langkah itu harus membawa saya, orang cukup cerdas, 290 00:14:23,770 --> 00:14:27,530 untuk menemukan orang yang terbesar dalam daftar itu? 291 00:14:27,530 --> 00:14:28,100 n, kan? 292 00:14:28,100 --> 00:14:31,320 Karena dalam kasus terburuk, di mana mungkin nilai terbesar itu? 293 00:14:31,320 --> 00:14:32,700 Benar, semua jalan di akhir. 294 00:14:32,700 --> 00:14:34,575 Jadi dalam kasus terburuk atas terikat, aku mungkin 295 00:14:34,575 --> 00:14:36,450 harus pergi semua jalan di sini dan menjadi seperti, 296 00:14:36,450 --> 00:14:39,170 oh, ini nomor delapan, atau apa pun nilai yang. 297 00:14:39,170 --> 00:14:41,330 Sekarang itu hanya akan menjadi bodoh jika saya terus berjalan, kan? 298 00:14:41,330 --> 00:14:43,840 Mencari semakin banyak unsur jika yang terakhir dari mereka ada di sana? 299 00:14:43,840 --> 00:14:45,340 Jadi pasti, n adalah batas atas. 300 00:14:45,340 --> 00:14:47,420 Saya tidak perlu mengambil langkah lagi dari itu. 301 00:14:47,420 --> 00:14:51,580 >> Jadi bagaimana jika sebaliknya saya mengusulkan bahwa ada algoritma di dunia ini yang 302 00:14:51,580 --> 00:14:57,750 memiliki waktu berjalan yang dibatasi oleh O besar log n, log n? 303 00:14:57,750 --> 00:15:00,390 Di mana kita melihat ini sebelumnya? 304 00:15:00,390 --> 00:15:00,890 Ya? 305 00:15:00,890 --> 00:15:03,309 >> AUDIENCE: Dalam masalah buku telepon? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Seperti masalah buku telepon. 307 00:15:04,850 --> 00:15:07,754 Apa ukuran seberapa banyak waktu atau berapa banyak air mata itu 308 00:15:07,754 --> 00:15:10,170 mengambil saya untuk menemukan seseorang seperti Mike Smith di buku telepon? 309 00:15:10,170 --> 00:15:13,212 Kami mengklaim itu log n, dan bahkan jika asing atau itu 310 00:15:13,212 --> 00:15:15,170 sedikit kabur apa logaritma atau eksponen itu, 311 00:15:15,170 --> 00:15:17,650 hanya ingat bahwa log n umumnya mengacu pada proses, 312 00:15:17,650 --> 00:15:20,790 dalam hal ini, membagi sesuatu dalam setengah lagi, dan lagi, 313 00:15:20,790 --> 00:15:25,790 dan lagi, dan lagi, sedemikian rupa sehingga mendapat semakin kecil seperti yang Anda lakukan itu. 314 00:15:25,790 --> 00:15:28,470 >> Jadi log n mengacu, tentu saja, untuk contoh buku telepon, 315 00:15:28,470 --> 00:15:32,662 dengan pencarian biner dalam teori, ketika kita memiliki pintu virtual pada papan, 316 00:15:32,662 --> 00:15:34,370 atau ketika Sean adalah mencari sesuatu. 317 00:15:34,370 --> 00:15:37,374 Jika dia menggunakan pencarian biner, log n akan menjadi batas atas berapa banyak 318 00:15:37,374 --> 00:15:38,040 waktu yang dibutuhkan. 319 00:15:38,040 --> 00:15:44,027 Tetapi orang-algoritma yang berlari di Log n diasumsikan kunci rinci apa? 320 00:15:44,027 --> 00:15:45,360 Bahwa daftar diurutkan, kan? 321 00:15:45,360 --> 00:15:47,789 Algoritma Anda salah jika input tidak diurutkan, 322 00:15:47,789 --> 00:15:49,830 namun Anda menggunakan sesuatu seperti pencarian biner 323 00:15:49,830 --> 00:15:51,704 karena Anda mungkin melompat hak atas elemen 324 00:15:51,704 --> 00:15:53,600 tanpa disadari itu memang ada. 325 00:15:53,600 --> 00:15:55,600 >> Sekarang apa artinya hal ini, O besar satu? 326 00:15:55,600 --> 00:15:59,117 Ini tidak berarti bahwa algoritma Anda mengambil satu dan hanya satu langkah, 327 00:15:59,117 --> 00:16:01,200 itu hanya berarti dibutuhkan jumlah konstan langkah. 328 00:16:01,200 --> 00:16:04,060 Mungkin 1, mungkin itu 10, mungkin itu 1.000, 329 00:16:04,060 --> 00:16:07,750 tapi itu independen ukuran masalah. 330 00:16:07,750 --> 00:16:10,850 Tidak peduli seberapa besar n adalah, algoritma waktu yang konstan 331 00:16:10,850 --> 00:16:12,747 selalu mengambil jumlah yang sama langkah. 332 00:16:12,747 --> 00:16:15,080 Jadi apa yang mungkin menjadi algoritma kita bicarakan atau hanya 333 00:16:15,080 --> 00:16:20,418 intuitif yang datang kepada Anda bahwa selalu berjalan dalam apa yang disebut konstanta waktu? 334 00:16:20,418 --> 00:16:20,918 Ya? 335 00:16:20,918 --> 00:16:22,001 >> AUDIENCE: Tambahkan dua angka. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Tambahkan dua angka, 2 ditambah 2 sama dengan 4, dilakukan. 337 00:16:25,320 --> 00:16:27,227 Sehingga mungkin bekerja, apa lagi? 338 00:16:27,227 --> 00:16:28,560 Bagaimana tentang dunia yang lebih nyata, ya? 339 00:16:28,560 --> 00:16:30,686 >> AUDIENCE: Menemukan Hal pertama dalam daftar. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Menemukan pertama elemen dalam daftar, yakin. 341 00:16:32,810 --> 00:16:34,540 Kami sudah benar-benar telah berbicara tentang array sudah, 342 00:16:34,540 --> 00:16:36,540 bagaimana Anda mendapatkan di elemen pertama dalam array, 343 00:16:36,540 --> 00:16:40,465 tidak peduli berapa lama array dalam kode C? 344 00:16:40,465 --> 00:16:43,090 Anda hanya menggunakan seperti braket notasi nol, bam, Anda berada di sana. 345 00:16:43,090 --> 00:16:46,120 Dan memang array, sebagai samping, Dukungan sesuatu umumnya dikenal 346 00:16:46,120 --> 00:16:49,240 sebagai akses acak, akses random memori, karena Anda benar-benar dapat 347 00:16:49,240 --> 00:16:50,284 melompat ke satu tempat. 348 00:16:50,284 --> 00:16:52,700 Kita dapat melakukan hal ini bahkan lebih sederhana kita bisa mundur ke minggu nol 349 00:16:52,700 --> 00:16:53,900 ketika kami melakukan Scratch. 350 00:16:53,900 --> 00:16:59,707 Berapa banyak waktu yang dibutuhkan untuk mengatakan blok Scratch untuk mengeksekusi? 351 00:16:59,707 --> 00:17:00,790 Hanya waktu yang konstan, kan? 352 00:17:00,790 --> 00:17:03,960 Katakan sesuatu, katakan sesuatu, tidak peduli 353 00:17:03,960 --> 00:17:07,359 bagaimana Goresan besar dunia adalah, selalu akan mengambil jumlah waktu yang sama 354 00:17:07,359 --> 00:17:08,490 hanya mengatakan sesuatu. 355 00:17:08,490 --> 00:17:11,089 >> Jadi itulah waktu yang konstan, tapi apa sisi lain? 356 00:17:11,089 --> 00:17:13,030 Jika itu atas batas, bagaimana jika kita ingin 357 00:17:13,030 --> 00:17:17,089 untuk menggambarkan batas bawah algoritma kami waktu berjalan? 358 00:17:17,089 --> 00:17:19,852 Hampir kasus terbaik berpotensi, jika Anda mau, 359 00:17:19,852 --> 00:17:23,060 meskipun hal ini bisa berlaku untuk terbaik kasus, kasus-kasus terburuk, kasus rata-rata lebih 360 00:17:23,060 --> 00:17:26,359 umumnya, tapi mari kita fokus pada batas bawah lebih umum. 361 00:17:26,359 --> 00:17:31,920 Apakah yang dimaksud dengan algoritma yang memiliki batas bawah dari langkah n, 362 00:17:31,920 --> 00:17:33,350 atau langkah-langkah 2n, atau langkah-langkah 3n? 363 00:17:33,350 --> 00:17:36,241 Beberapa faktor langkah n, itu lebih rendah terikat. 364 00:17:36,241 --> 00:17:36,740 Ya? 365 00:17:36,740 --> 00:17:37,910 >> AUDIENCE: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort mengambil Anda langkah minimal n, mengapa? 367 00:17:41,610 --> 00:17:42,279 Mengapa demikian? 368 00:17:42,279 --> 00:17:45,320 Mengapa awal bahwa untuk datang kepada Anda intuitif, bahkan jika tidak hanya 369 00:17:45,320 --> 00:17:46,530 belum? 370 00:17:46,530 --> 00:17:47,030 Ya? 371 00:17:47,030 --> 00:17:47,990 >> AUDIENCE: [Tak terdengar]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Tepat. 374 00:17:52,360 --> 00:17:55,810 Dalam skenario terbaik dari bubble sort, dan banyak algoritma, 375 00:17:55,810 --> 00:17:58,769 jika saya menyerahkan delapan orang yang sudah diurutkan, 376 00:17:58,769 --> 00:18:00,560 akan bodoh untuk Anda, algoritma, 377 00:18:00,560 --> 00:18:02,202 untuk pergi bolak-balik lebih dari sekali, kan? 378 00:18:02,202 --> 00:18:04,285 Karena segera setelah Anda berjalan melalui daftar sekali, 379 00:18:04,285 --> 00:18:08,090 Anda harus menyadari, oh, aku tidak membuat swap, daftar ini diurutkan, keluar. 380 00:18:08,090 --> 00:18:09,700 Tapi itu akan membawa Anda n langkah. 381 00:18:09,700 --> 00:18:12,033 >> Dan sebaliknya, apa yang lain cara berpikir tentang hal itu? 382 00:18:12,033 --> 00:18:15,240 Bubble sort adalah omega, sehingga untuk berbicara, dari n, 383 00:18:15,240 --> 00:18:19,050 karena jika Anda melihat kurang dari n elemen, apa yang 384 00:18:19,050 --> 00:18:23,009 adalah masalah mendasar di sana? 385 00:18:23,009 --> 00:18:24,550 Anda tidak tahu apakah itu disortir, benar. 386 00:18:24,550 --> 00:18:26,800 Kami manusia kekuatan melirik delapan orang dan menjadi seperti, oh, itu diurutkan, 387 00:18:26,800 --> 00:18:28,430 yang tidak membawa saya n langkah, tapi itu. 388 00:18:28,430 --> 00:18:30,810 Mata Anda, meskipun Anda jenis dari memiliki lapangan besar visi, 389 00:18:30,810 --> 00:18:33,184 Anda melihat delapan elemen, Anda melihat delapan orang, 390 00:18:33,184 --> 00:18:34,610 itu delapan langkah efektif. 391 00:18:34,610 --> 00:18:38,612 Dan hanya jika saya berjalan melalui seluruh daftar yang saya menyadari, ya, diurutkan. 392 00:18:38,612 --> 00:18:41,320 Jika saya berhenti di tengah jalan berpikir, semua benar, itu cukup diurutkan sejauh ini, 393 00:18:41,320 --> 00:18:42,520 apa kemungkinan itu tidak diurutkan? 394 00:18:42,520 --> 00:18:44,186 Bahwa algoritma tidak akan benar. 395 00:18:44,186 --> 00:18:46,250 Mungkin lebih cepat, namun tidak tepat. 396 00:18:46,250 --> 00:18:48,500 >> Jadi sekarang kita memiliki cara menggambarkan batas bawah, 397 00:18:48,500 --> 00:18:49,710 dan bagaimana dengan waktu yang konstan? 398 00:18:49,710 --> 00:18:54,565 Apakah yang dimaksud dengan algoritma yang memiliki lebih rendah terikat pada waktu yang berjalan dari satu? 399 00:18:54,565 --> 00:18:58,350 1 langkah, 2 langkah, 10 langkah, tetapi konstan, independen n, 400 00:18:58,350 --> 00:18:59,310 ukuran input? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ya, di belakang. 403 00:19:04,600 --> 00:19:05,309 >> AUDIENCE: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Apa itu? 405 00:19:06,183 --> 00:19:07,184 AUDIENCE: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, yakin. 408 00:19:08,400 --> 00:19:10,720 Jadi dibutuhkan sejumlah tetap langkah. 409 00:19:10,720 --> 00:19:13,170 Dan saya harus sekarang-- sekarang kita sedang berbicara tentang kode C 410 00:19:13,170 --> 00:19:16,040 , bukan Scratch, sesuatu seperti mengatakan, dengan printf, 411 00:19:16,040 --> 00:19:17,710 kita harus mulai untuk mendapatkan hati. 412 00:19:17,710 --> 00:19:21,090 Karena printf tidak mengambil masukan, itu string, 413 00:19:21,090 --> 00:19:23,220 dan string yang secara teknis memiliki panjang. 414 00:19:23,220 --> 00:19:25,530 Jadi jika sekarang kita ingin memilih pada Anda, jika Anda tidak keberatan, 415 00:19:25,530 --> 00:19:29,430 secara teknis kita bisa berpendapat bahwa printf tidak mengambil panjang input variabel, 416 00:19:29,430 --> 00:19:32,270 dan tentunya memakan waktu waktu untuk mencetak string panjang ini, 417 00:19:32,270 --> 00:19:33,560 dari ini panjang. 418 00:19:33,560 --> 00:19:36,570 >> Jadi bagaimana jika kita mempertimbangkan hanya pemilahan dan pencarian contoh? 419 00:19:36,570 --> 00:19:40,450 Bagaimana dengan Mike Smith di telepon buku, atau pencarian biner lebih umum? 420 00:19:40,450 --> 00:19:42,220 Dalam kasus terbaik, apa yang akan terjadi? 421 00:19:42,220 --> 00:19:45,577 Saya membuka buku telepon dan, bam, ada nomor Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Aku bisa memanggilnya segera. 423 00:19:46,660 --> 00:19:49,390 >> Mengambil satu langkah, mungkin dua langkah, tetapi sejumlah konstan langkah 424 00:19:49,390 --> 00:19:50,230 jika aku beruntung. 425 00:19:50,230 --> 00:19:52,570 Dan terus terang, kita melihat di Anda sekelas Senin 426 00:19:52,570 --> 00:19:54,710 mendapatkan cukup beruntung dua kali berturut-turut. 427 00:19:54,710 --> 00:19:57,050 Dan itu memang konstan waktu di batas bawah 428 00:19:57,050 --> 00:20:01,280 pada algoritma tersebut untuk mencari nomor 50 di belakang mereka ditutup 429 00:20:01,280 --> 00:20:01,830 pintu. 430 00:20:01,830 --> 00:20:06,400 >> Sekarang, sebagai samping, jika Anda menemukan bahwa kedua O besar, batas atas, 431 00:20:06,400 --> 00:20:09,310 dan omega, yang terikat lebih rendah, adalah satu dalam sama, bahwa 432 00:20:09,310 --> 00:20:11,830 adalah rumus yang sama di kurung, Anda juga dapat 433 00:20:11,830 --> 00:20:15,170 mengatakan, hanya untuk menjadi mewah, sesuatu yang di theta 434 00:20:15,170 --> 00:20:18,270 n atau theta dari beberapa nilai lainnya. 435 00:20:18,270 --> 00:20:20,661 Itu hanya berarti ketika besar O dan omega adalah sama. 436 00:20:20,661 --> 00:20:21,910 Sekarang bagaimana selection sort? 437 00:20:21,910 --> 00:20:23,400 Mari kita gunakan kosakata baru ini. 438 00:20:23,400 --> 00:20:27,407 Dalam selection sort, apa yang kita melakukan lagi, dan lagi, dan lagi? 439 00:20:27,407 --> 00:20:29,990 Aku akan bolak-balik melalui daftar, mencari siapa? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Jumlah terkecil. 442 00:20:34,730 --> 00:20:37,560 >> Jadi berapa banyak langkah, bagaimana banyak perbandingan yang saya 443 00:20:37,560 --> 00:20:43,250 harus membuat untuk mencari tahu siapa elemen terkecil dalam daftar itu? 444 00:20:43,250 --> 00:20:44,437 n dikurangi 1, kan? 445 00:20:44,437 --> 00:20:47,770 Karena jika saya hanya mulai dengan yang saya diberikan dan saya mulai membandingkan dia, 446 00:20:47,770 --> 00:20:49,519 kemudian dia, dia atau dia, dia, saya 447 00:20:49,519 --> 00:20:52,010 hanya bisa memasangkan elemen bersama-sama n dikurangi 1 kali. 448 00:20:52,010 --> 00:20:55,630 Jadi selection sort sama membutuhkan n dikurangi 1 langkah pertama kalinya. 449 00:20:55,630 --> 00:20:59,540 >> Berapa banyak langkah yang dibutuhkan saya untuk menemukan elemen terkecil kedua? 450 00:20:59,540 --> 00:21:02,920 n minus 2, karena aku menjadi bodoh jika saya tetap melihat orang yang sama 451 00:21:02,920 --> 00:21:06,280 lagi jika saya sudah memilih dia atau dia dan menempatkan mereka di tempat mereka. 452 00:21:06,280 --> 00:21:09,270 Dan langkah ketiga, n minus 3, maka n minus 4. 453 00:21:09,270 --> 00:21:11,020 Kami telah melihat pola ini sebelumnya, dan memang 454 00:21:11,020 --> 00:21:13,460 selection sort sama memiliki batas atas 455 00:21:13,460 --> 00:21:16,210 n kuadrat jika kita melakukan up penjumlahan itu. 456 00:21:16,210 --> 00:21:19,790 Apa itu batas bawah, selection sort nya? 457 00:21:19,790 --> 00:21:25,350 Minimal, berapa banyak waktu pemilihan harus semacam ambil, seperti yang kita mendefinisikannya pada hari Senin? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Mengusulkan dua pilihan. 460 00:21:30,490 --> 00:21:32,360 Mungkin itu n, seperti sebelumnya. 461 00:21:32,360 --> 00:21:35,040 Mungkin itu n kuadrat, karena sekarang sebagai batas atas. 462 00:21:35,040 --> 00:21:35,874 >> AUDIENCE: n kuadrat. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n kuadrat. 464 00:21:36,664 --> 00:21:37,368 Mengapa? 465 00:21:37,368 --> 00:21:40,060 >> AUDIENCE: Karena Anda memiliki untuk menentukan [Tak terdengar]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Tepat. 467 00:21:41,510 --> 00:21:45,077 Setidaknya seperti yang saya didefinisikan selection sort itu cukup naif, terus, 468 00:21:45,077 --> 00:21:46,160 menemukan elemen terkecil. 469 00:21:46,160 --> 00:21:47,770 Pergi lagi, cari elemen terkecil. 470 00:21:47,770 --> 00:21:49,490 Pergi lagi, cari elemen terkecil. 471 00:21:49,490 --> 00:21:51,700 Tidak ada semacam optimasi di sana yang 472 00:21:51,700 --> 00:21:54,350 mungkin membiarkan saya membatalkan setelah hanya n atau lebih langkah-langkah. 473 00:21:54,350 --> 00:21:57,080 Jadi memang, pilihan semacam, omega n kuadrat. 474 00:21:57,080 --> 00:22:00,667 >> Bagaimana dengan insertion sort, di mana aku mengambil siapa aku diberi, dan kemudian aku menjatuhkan dia 475 00:22:00,667 --> 00:22:01,750 atau dia di tempat yang tepat? 476 00:22:01,750 --> 00:22:04,958 Kemudian saya melanjutkan untuk orang kedua, menjatuhkan dia di tempat yang tepat. 477 00:22:04,958 --> 00:22:07,910 Kemudian orang berikutnya, menjatuhkan dia di tempat yang tepat. 478 00:22:07,910 --> 00:22:10,537 Perhatikan bahwa ini sangat linear, sehingga untuk berbicara. 479 00:22:10,537 --> 00:22:12,620 Aku garis lurus, aku tidak akan bolak-balik, 480 00:22:12,620 --> 00:22:16,080 Aku tidak pernah melihat ke belakang benar-benar, tapi apa yang terjadi ketika saya memasukkan dia 481 00:22:16,080 --> 00:22:20,302 atau dia ke awal daftar seperti yang kita lakukan pada hari Senin? 482 00:22:20,302 --> 00:22:21,010 Apa yang terjadi? 483 00:22:21,010 --> 00:22:21,510 Ya? 484 00:22:21,510 --> 00:22:23,122 AUDIENCE: [Tak terdengar]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Ya, itu adalah menangkap, kan? 486 00:22:24,830 --> 00:22:26,746 Anda mungkin ingat dari teman sekelas Anda, jika mereka 487 00:22:26,746 --> 00:22:29,670 sedang membuat setiap gerakan dengan kaki mereka, itu adalah sebuah operasi. 488 00:22:29,670 --> 00:22:33,610 Jadi jika ada tiga orang di sini dan orang baru milik jalan di sana, 489 00:22:33,610 --> 00:22:37,360 pada tahapan yang panjang seperti ini, tentu saja, dia atau dia hanya bisa pergi sampai akhir. 490 00:22:37,360 --> 00:22:40,074 Tetapi jika kita berpikir tentang komputer dan sebuah array dari memori, 491 00:22:40,074 --> 00:22:41,990 orang-orang ini akan harus mengocok lebih 492 00:22:41,990 --> 00:22:43,260 untuk memberikan ruang bagi orang itu. 493 00:22:43,260 --> 00:22:46,930 Dan sehingga n dikurangi 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings hanya jenis terjadi di belakang saya, bukan di depan saya 495 00:22:50,660 --> 00:22:52,710 seperti sebelumnya, dalam arti tertentu. 499 00:22:52,557 --> 00:22:54,640 Sekarang sebagai samping, dan sebagai Anda mungkin telah melihat secara online 500 00:22:54,640 --> 00:22:57,699 jika Anda mulai mengaduk-aduk tentang macam, ada begitu banyak yang berbeda 501 00:22:57,699 --> 00:22:59,490 di luar sana, beberapa dari mereka lebih baik daripada yang lain. 502 00:22:59,490 --> 00:23:02,200 Memang, Bogosort adalah salah satu itu semacam menyenangkan untuk melihat ke atas. 503 00:23:02,200 --> 00:23:06,650 Bogosort mengambil satu set nomor atau mengatakan setumpuk kartu, 504 00:23:06,650 --> 00:23:09,870 acak mengocok mereka, dan memeriksa apakah mereka diurutkan. 505 00:23:09,870 --> 00:23:12,130 Dan jika tidak, tidak lagi. 506 00:23:12,130 --> 00:23:14,140 Dan jika tidak, tidak lagi. 507 00:23:14,140 --> 00:23:15,440 Jika tidak, tidak lagi. 508 00:23:15,440 --> 00:23:17,060 Sangat bodoh. 509 00:23:17,060 --> 00:23:19,520 >> Dan memang, jika Anda membaca seperti artikel Wikipedia, 510 00:23:19,520 --> 00:23:21,200 nickname adalah semacam bodoh. 511 00:23:21,200 --> 00:23:25,180 Ini akhirnya akan bekerja, mudah-mudahan, dengan waktu yang cukup, 512 00:23:25,180 --> 00:23:28,240 tetapi jumlah waktu bisa mengambil beberapa waktu. 513 00:23:28,240 --> 00:23:31,650 Jadi jika saya bisa, mari kita kecepatan hal naik dari contoh Mary Beth sebelumnya, 514 00:23:31,650 --> 00:23:35,150 dengan memiliki unsur-unsur yang lebih sedikit, tapi dua prosesor yang lebih. 515 00:23:35,150 --> 00:23:37,100 Dua orang, jika Anda tidak keberatan bergabung dengan saya. 516 00:23:37,100 --> 00:23:40,972 Bagaimana 1 di sini, dan mari kita go-- ada orang di sana? 517 00:23:40,972 --> 00:23:41,722 Tidak ada satu di sana? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Anda dengan hitam shirt, ya, datang pada turun. 520 00:23:44,190 --> 00:23:45,000 Baiklah, siapa namamu? 521 00:23:45,000 --> 00:23:45,720 >> AUDIENCE: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Apa itu? 523 00:23:46,100 --> 00:23:46,766 >> AUDIENCE: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, senang bertemu dengan Anda. 525 00:23:49,450 --> 00:23:53,670 Baiklah, kita memiliki Petrus di sini, jika Anda ingin datang ke meja di sini. 526 00:23:53,670 --> 00:23:54,550 Dan siapa namamu? 527 00:23:54,550 --> 00:23:55,216 >> AUDIENCE: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, senang bertemu Anda. 530 00:23:57,030 --> 00:23:58,060 Elena bertemu Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Dan kita harus Andrew di sini juga, silakan. 533 00:24:02,290 --> 00:24:06,107 Dan tantangan Anda akan menjadi memilah setumpuk kartu. 534 00:24:06,107 --> 00:24:08,190 Dan jika asing, dek kartu harus akhirnya 535 00:24:08,190 --> 00:24:11,064 diurutkan sedikit sesuatu seperti ini di mana kita akan melakukan klub, maka 536 00:24:11,064 --> 00:24:13,660 para sekop, maka hati dan berlian, dari ace sebagai satu, 537 00:24:13,660 --> 00:24:15,570 semua jalan sampai ke raja. 538 00:24:15,570 --> 00:24:20,890 >> Kartu Aku akan memberikan akan menjadi 52 dalam kuantitas. 539 00:24:20,890 --> 00:24:23,160 Kita akan sama kali, hanya dalam beberapa saat. 540 00:24:23,160 --> 00:24:26,410 Kita akan membuang Andrew di layar di sini, 541 00:24:26,410 --> 00:24:28,170 sehingga untuk menonton saat Anda melakukan hal ini. 542 00:24:28,170 --> 00:24:31,070 Dan sehingga semua ini semua lebih terlihat, 543 00:24:31,070 --> 00:24:33,490 ini adalah kartu saya dapatkan di Amazon. 544 00:24:33,490 --> 00:24:42,861 Jadi mereka sudah acak diurutkan, dan kita akan ke waktu Anda. 545 00:24:42,861 --> 00:24:44,610 Dan kita akan tetap real time ini, 546 00:24:44,610 --> 00:24:47,820 jadi kita akan mencoba untuk menekan Anda karena jika tidak hal ini akan membosankan 547 00:24:47,820 --> 00:24:48,460 cepat. 548 00:24:48,460 --> 00:24:53,860 Jika Anda bisa melanjutkan untuk menyortir 52 elemen bersama-sama melalui beberapa cara, sekarang. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Dan lagi, seperti yang kita menonton ini orang melakukan apa, pada akhirnya 551 00:25:07,180 --> 00:25:10,200 akan menghasilkan yang jelas Hasilnya, pikirkan benar-benar 552 00:25:10,200 --> 00:25:12,962 bagaimana mereka masing-masing melakukannya, bagaimana Anda bisa menggambarkannya. 553 00:25:12,962 --> 00:25:15,045 Karena sekali lagi, ini adalah semua proses, algoritma 554 00:25:15,045 --> 00:25:17,090 yang kita ambil untuk diberikan sebagai manusia. 555 00:25:17,090 --> 00:25:22,349 Tapi Anda mungkin lama memiliki intuisi, jauh sebelum Anda bahkan 556 00:25:22,349 --> 00:25:24,390 berpikir tentang mengambil ilmu komputer kelas Anda 557 00:25:24,390 --> 00:25:27,223 mungkin memiliki intuisi dengan yang untuk memecahkan masalah seperti ini. 558 00:25:27,223 --> 00:25:29,560 Tapi setelah Anda mengenali pola dan mulai 559 00:25:29,560 --> 00:25:32,407 untuk merumuskan langkah-langkah dengan mana Anda memecahkan masalah ini, 560 00:25:32,407 --> 00:25:35,490 Anda akan menemukan bahwa Anda dapat memecahkan banyak lebih menarik dan jauh lebih kompleks 561 00:25:35,490 --> 00:25:39,190 masalah dengan cepat. 562 00:25:39,190 --> 00:25:42,351 Jadi seseorang dari penonton, apa yang setidaknya satu elemen dari algoritma 563 00:25:42,351 --> 00:25:43,350 bahwa mereka menggunakan di sini? 564 00:25:43,350 --> 00:25:44,275 >> AUDIENCE: [Tak terdengar] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Apa itu? 566 00:25:45,150 --> 00:25:47,062 AUDIENCE: Dengan setelan. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Dengan setelan. 568 00:25:47,770 --> 00:25:50,630 Jadi pertama mereka mengelompokkan semua berlian bersama-sama 569 00:25:50,630 --> 00:25:52,560 tampaknya, semua hati bersama-sama tampaknya, 570 00:25:52,560 --> 00:25:56,520 dan sebagainya, tanpa rasa hormat untuk nomor pada kartu. 571 00:25:56,520 --> 00:26:00,900 Dan sekarang mereka muncul, misalnya, untuk menyortir mereka dengan nomor. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Sangat bagus. 574 00:26:08,910 --> 00:26:12,370 >> Baiklah, jadi apa yang akan menjadi langkah terakhir maka di sini? 575 00:26:12,370 --> 00:26:16,950 Setelah kita memiliki empat sesuai diurutkan, apa yang perlu kita lakukan untuk empat tumpukan 576 00:26:16,950 --> 00:26:20,059 untuk mencapai satu diurutkan deck, cukup sederhana? 577 00:26:20,059 --> 00:26:21,350 Jadi kita perlu untuk menggabungkan mereka lagi. 578 00:26:21,350 --> 00:26:25,160 >> Jadi ada ide yang menarik yang lagi, berani mengatakan, sangat intuitif bahkan 579 00:26:25,160 --> 00:26:28,140 jika Anda mungkin pernah ditampar semacam label di atasnya. 580 00:26:28,140 --> 00:26:31,900 Gagasan mendasar ini membagi masalah tidak dalam separuh waktu ini, 581 00:26:31,900 --> 00:26:33,410 tapi setidaknya menjadi empat bagian. 582 00:26:33,410 --> 00:26:36,810 Pemecahan cukup banyak masalah fundamental identik 583 00:26:36,810 --> 00:26:40,480 dalam isolasi dari satu sama lain, dan kemudian menggabungkan hasilnya. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Dan, sangat baik, dilakukan. 586 00:26:50,140 --> 00:26:52,140 Baiklah, putaran besar tepuk tangan, jika kita bisa. 587 00:26:52,140 --> 00:26:56,480 >> [Tepuk Tangan] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Aku tidak tahu apa yang akan Anda dengan ini, tapi di sini Anda pergi. 589 00:26:59,740 --> 00:27:01,690 Terima kasih banyak. 590 00:27:01,690 --> 00:27:04,660 Jadi mari kita lihat, dua menit dan delapan detik, 591 00:27:04,660 --> 00:27:07,490 jika Anda ingin menantang teman Anda. 592 00:27:07,490 --> 00:27:12,160 Lalu apa yang akan menjadi mengambil dari ini 593 00:27:12,160 --> 00:27:13,830 bahwa kita dapat memanfaatkan lebih umum? 594 00:27:13,830 --> 00:27:16,080 Nah, pikirkan kembali array ini angka, 595 00:27:16,080 --> 00:27:19,060 dan berpikir kembali sekarang untuk beberapa pseudocode kita sudah ditulis di masa lalu, 596 00:27:19,060 --> 00:27:22,080 dan ini adalah pseudocode untuk memecahkan masalah buku telepon. 597 00:27:22,080 --> 00:27:25,150 Dimana dalam pseudo I disebutkan cara yang lebih metodis 598 00:27:25,150 --> 00:27:28,400 menggambarkan bagaimana saya melakukan sangat intuitif Algoritma manusia membagi telepon 599 00:27:28,400 --> 00:27:31,650 buku dua, ulangi, ulangi, ulangi, sampai aku menemukan seseorang seperti Mike Smith, 600 00:27:31,650 --> 00:27:33,790 jika ia memang dalam buku telepon. 601 00:27:33,790 --> 00:27:37,610 >> Tapi aku agak digunakan apa yang akan saya sebut pendekatan yang sangat berulang di sini, 602 00:27:37,610 --> 00:27:42,160 dalam pemberitahuan tertentu baris 8 dan baris 11. 603 00:27:42,160 --> 00:27:46,750 Mereka adalah bukti adanya berulang pendekatan, pendekatan perulangan, 604 00:27:46,750 --> 00:27:49,040 karena itulah perilaku mereka menginduksi. 605 00:27:49,040 --> 00:27:52,910 Mereka baris kedua mengatakan pergi ke jenis garis tiga, dan Anda dapat dari 606 00:27:52,910 --> 00:27:55,140 memikirkan bahwa dalam Anda mata pikiran sebagai lingkaran. 607 00:27:55,140 --> 00:27:59,080 Ini memberitahu Anda untuk pergi kembali ke langkah tiga dan ulangi, lagi, dan lagi, 608 00:27:59,080 --> 00:28:00,010 dan lagi. 609 00:28:00,010 --> 00:28:04,410 >> Tapi bagaimana kalau kita memanfaatkan ide kunci di sini bahwa kami tidak terakhir kali, 610 00:28:04,410 --> 00:28:10,280 dan menyederhanakan jalur 8 dan baris 11 dan tetangga mereka 611 00:28:10,280 --> 00:28:12,840 seperti ini saja, dengan warna kuning. 612 00:28:12,840 --> 00:28:16,480 Ini tidak mendasar memperpendek pseudocode sangat banyak, 613 00:28:16,480 --> 00:28:20,530 tapi itu fundamental mengubah sifat algoritma saya. 614 00:28:20,530 --> 00:28:24,220 Apa yang saya katakan sekarang pada langkah 7, pada langkah 10, 615 00:28:24,220 --> 00:28:29,140 adalah untuk mencari Mike dengan cara yang sama persis, 616 00:28:29,140 --> 00:28:31,580 tetapi hanya di sebelah kiri setengah atau setengah benar. 617 00:28:31,580 --> 00:28:33,420 >> Jadi dengan kata lain, jika Saya mulai dari langkah satu, 618 00:28:33,420 --> 00:28:36,150 mengambil buku telepon, terbuka untuk tengah dari buku telepon, melihat nama, 619 00:28:36,150 --> 00:28:39,010 jika Smith adalah salah Nama ini, sebut Mike, lain 620 00:28:39,010 --> 00:28:44,340 jika Smith adalah awal buku, langkah tujuh mencari Mike di kiri setengah dari buku. 621 00:28:44,340 --> 00:28:47,130 Tapi itu jenis terasa seperti itu meninggalkan aku menggantung, kan? 622 00:28:47,130 --> 00:28:49,240 Dalam kuning, adalah instruksi, tapi bagaimana saya 623 00:28:49,240 --> 00:28:51,870 mencari Mike di sebelah kiri setengah dari buku telepon? 624 00:28:51,870 --> 00:28:54,210 Di mana saya memiliki algoritma dengan yang saya 625 00:28:54,210 --> 00:28:57,100 dapat mencari seseorang seperti Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Yah, itu menatap wajah kita. 627 00:28:58,980 --> 00:29:03,090 Aku benar-benar dapat menggunakan yang sama persis Program efektif naik ke atas 628 00:29:03,090 --> 00:29:06,490 lagi dan re-berjalan baris kode yang sama. 629 00:29:06,490 --> 00:29:10,610 >> Jadi meskipun ini harus merasa seperti sedikit definisi siklus 630 00:29:10,610 --> 00:29:13,480 di mana Anda menjawab seseorang yang pertanyaan dengan hanya semacam meminta 631 00:29:13,480 --> 00:29:15,990 pertanyaan yang sama lagi, seperti mengapa, mengapa, mengapa? 632 00:29:15,990 --> 00:29:21,580 Kenyataannya adalah karena kita telah dikodekan keras beberapa jalur khusus, langkah 4, 633 00:29:21,580 --> 00:29:25,320 yang merupakan jika, dan langkah 12, yang secara efektif cabang lain, 634 00:29:25,320 --> 00:29:30,120 karena kita memiliki langkah-langkah pengganti sementara, algoritma ini akan berakhir jika kita 635 00:29:30,120 --> 00:29:32,050 menemukan Mike, atau jika kita tidak. 636 00:29:32,050 --> 00:29:36,810 Namun pada langkah 7 dan 10 sekarang, kami memiliki apa yang akan kita sebut algoritma rekursif. 637 00:29:36,810 --> 00:29:40,420 Dan rekursi memang ide yang kuat itu pikiran sedikit membungkuk pada awalnya, 638 00:29:40,420 --> 00:29:42,500 bahwa kita sekarang dapat menerapkan sebagai berikut. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort akan menjadi semacam terakhir yang kita melihat, setidaknya di kelas formal. 640 00:29:46,600 --> 00:29:50,040 Dan secara fundamental berbeda dari tiga yang terakhir, dan tentu saja 641 00:29:50,040 --> 00:29:52,140 empat jika kita termasuk Bogosort. 642 00:29:52,140 --> 00:29:54,810 Berikut pseudocode untuk merge sort. 643 00:29:54,810 --> 00:30:00,170 Ketika masukan dari elemen n, sehingga diberikan array berukuran n, jika n kurang dari 2, 644 00:30:00,170 --> 00:30:01,040 kembali. 645 00:30:01,040 --> 00:30:03,610 Jadi, mengapa aku memiliki kewarasan cek dulu? 646 00:30:03,610 --> 00:30:09,477 Apa implikasinya jika saya tangan Anda array yang panjangnya n kurang dari 2? 647 00:30:09,477 --> 00:30:11,060 Ini sudah disortir, jelas, kan? 648 00:30:11,060 --> 00:30:13,640 Karena daftar baik memiliki satu elemen, yang sepele 649 00:30:13,640 --> 00:30:15,180 diurutkan karena itu satu-satunya hal di sana. 650 00:30:15,180 --> 00:30:18,138 Atau, itu ukuran nol yang berarti tidak ada untuk menyortir, sehingga oleh alam 651 00:30:18,138 --> 00:30:18,720 itu disortir. 652 00:30:18,720 --> 00:30:20,410 Hanya ada ada yang salah di sana. 653 00:30:20,410 --> 00:30:22,310 Jadi itulah yang disebut kasus dasar kami. 654 00:30:22,310 --> 00:30:24,440 >> Yang mirip dalam roh dengan apa yang kita lakukan dengan Mike. 655 00:30:24,440 --> 00:30:26,023 Jika Mike dalam buku telepon, memanggilnya. 656 00:30:26,023 --> 00:30:27,740 Jika dia tidak ada, menyerah. 657 00:30:27,740 --> 00:30:31,240 Ini adalah kasus dasar yang disebut, untuk memastikan algoritma ini pada akhir hari 658 00:30:31,240 --> 00:30:33,540 akan berhenti dalam keadaan tertentu. 659 00:30:33,540 --> 00:30:37,890 >> Tapi di sini adalah lompatan iman sekarang, yang lain, mengurutkan kiri setengah dari unsur-unsur, 660 00:30:37,890 --> 00:30:39,740 kemudian mengurutkan kanan setengah dari unsur-unsur, 661 00:30:39,740 --> 00:30:41,189 dan kemudian menggabungkan bagian diurutkan. 662 00:30:41,189 --> 00:30:43,230 Dan di sinilah rasanya seperti kita copping keluar. 663 00:30:43,230 --> 00:30:46,900 Aku sudah meminta Anda untuk mengurut n elemen, dan aku 664 00:30:46,900 --> 00:30:50,712 mengatakan, OK, lakukan dengan menyortir kiri dan menyortir kanan. 665 00:30:50,712 --> 00:30:52,420 Tapi saya katakan satu Hal lain, dan ini 666 00:30:52,420 --> 00:30:55,530 adalah tema kunci tampaknya di intuisi sejauh ini, 667 00:30:55,530 --> 00:30:57,380 ada langkah ketiga ini penggabungan. 668 00:30:57,380 --> 00:31:00,430 Yang meskipun tampak begitu bodoh dalam roh, 669 00:31:00,430 --> 00:31:02,320 seperti hanya menggabungkan hal-hal bersama-sama, tampaknya 670 00:31:02,320 --> 00:31:05,380 menjadi langkah kunci menuju reassembly dari dua masalah yang 671 00:31:05,380 --> 00:31:07,330 dibagi akhirnya dua. 672 00:31:07,330 --> 00:31:12,090 >> Jadi menggabungkan semacam, mari kita lakukan ini, jika Anda akan humor saya, dengan satu demonstrasi lagi, 673 00:31:12,090 --> 00:31:14,730 hanya agar kita memiliki beberapa nomor untuk bekerja dengan. 674 00:31:14,730 --> 00:31:19,470 Dapatkah saya menukar delapan stres bola untuk delapan orang? 675 00:31:19,470 --> 00:31:29,320 Baiklah, bagaimana dengan Anda tiga, Anda empat dalam bagian ini, lima, enam, dan mari kita 676 00:31:29,320 --> 00:31:30,720 jangan 7, 8, ayolah up. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ya OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, di sana kita pergi, ditambah 1. 680 00:31:38,640 --> 00:31:39,150 Sangat baik. 681 00:31:39,150 --> 00:31:42,000 Baiklah ayo, ayo cepat memberikan nomor. 682 00:31:42,000 --> 00:31:50,800 Nomor dua, nomor tiga, nomor empat, nomor lima, enam, tujuh, dan delapan. 683 00:31:50,800 --> 00:31:52,140 Saya melakukan delapan dengan benar saat ini. 684 00:31:52,140 --> 00:31:56,390 >> OK, jadi pergi ke depan jika Anda bisa, dan mari kita mengurutkan dalam urutan asli 685 00:31:56,390 --> 00:31:59,810 bahwa kami memiliki kemarin yang tampak seperti ini, jika Anda tidak keberatan. 686 00:31:59,810 --> 00:32:03,620 Dan mari kita melakukannya di depan meja. 687 00:32:03,620 --> 00:32:06,510 Baiklah, jadi menggabungkan semacam. 688 00:32:06,510 --> 00:32:08,820 Ini adalah di mana itu akan untuk mendapatkan jenis yang menarik, 689 00:32:08,820 --> 00:32:12,800 karena saya tampaknya memberi diriku begitu banyak informasi yang kurang hari ini. 690 00:32:12,800 --> 00:32:15,149 >> Jadi menggabungkan semacam pertama-tama masukan dari elemen n, 691 00:32:15,149 --> 00:32:18,440 dan jelas tidak kurang dari dua, itu delapan, jadi saya memiliki beberapa pekerjaan yang harus dilakukan. 692 00:32:18,440 --> 00:32:21,140 Jadi sekarang mental kita sebagai kelas sekarang berada di cabang lain, 693 00:32:21,140 --> 00:32:22,540 yang berarti tiga langkah. 694 00:32:22,540 --> 00:32:25,017 Pertama, saya harus mengurutkan kiri setengah dari unsur-unsur. 695 00:32:25,017 --> 00:32:26,350 Jadi bagaimana aku pergi tentang melakukan ini? 696 00:32:26,350 --> 00:32:28,950 Yah, aku akan jenis mental membagi daftar di sini, 697 00:32:28,950 --> 00:32:30,700 Anda tidak perlu secara fisik bergerak, dan aku 698 00:32:30,700 --> 00:32:33,180 akan hanya fokus pada kiri setengah dari unsur-unsur di sini. 699 00:32:33,180 --> 00:32:36,770 Jadi bagaimana aku pergi tentang menyortir daftar sekarang ukuran empat? 700 00:32:36,770 --> 00:32:38,730 Apa algoritma saya? 701 00:32:38,730 --> 00:32:42,580 Pertama saya memeriksa adalah n kurang dari dua, tidak, jadi saya melanjutkan ke lain blok lagi. 702 00:32:42,580 --> 00:32:43,900 Urut meninggalkan setengah dari elemen. 703 00:32:43,900 --> 00:32:45,608 >> Jadi sekarang lagi, mental, dan ini adalah di mana 704 00:32:45,608 --> 00:32:49,550 Anda harus bertambah banyak sejarah mental, jika Anda mau. 705 00:32:49,550 --> 00:32:51,940 Sekarang aku menyortir kiri setengah dari kiri setengah. 706 00:32:51,940 --> 00:32:57,000 Baiklah, jadi sekarang saya sebut merge sama saya algoritma sorting, adalah n kurang dari dua? 707 00:32:57,000 --> 00:33:00,590 Tidak, itu adalah dua, jadi aku harus memilah kiri setengah, dan bagian kanan. 708 00:33:00,590 --> 00:33:02,042 Jadi di sini kita pergi, mengurutkan setengah kiri. 709 00:33:02,042 --> 00:33:03,750 Mengapa Anda tidak hanya mengambil satu langkah maju. 710 00:33:03,750 --> 00:33:04,415 Siapa nama Anda? 711 00:33:04,415 --> 00:33:04,860 >> AUDIENCE: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan telah melangkah maju. 714 00:33:06,040 --> 00:33:06,748 >> AUDIENCE: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, dilakukan. 716 00:33:09,000 --> 00:33:10,090 Apakah Anda mengatakan Darren atau Dan? 717 00:33:10,090 --> 00:33:10,550 >> AUDIENCE: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren telah melangkah maju dan dia sekarang diurutkan. 720 00:33:14,422 --> 00:33:16,130 Dan ini hampir klaim konyol, kan? 721 00:33:16,130 --> 00:33:18,862 Aku tidak benar-benar tampaknya mencapai apa-apa, tapi mari kita lanjutkan. 722 00:33:18,862 --> 00:33:20,820 Sekarang biarkan aku memilah hak setengah dari elemen. 723 00:33:20,820 --> 00:33:21,200 Siapa nama Anda? 724 00:33:21,200 --> 00:33:21,690 >> AUDIENCE: Lukas. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Lukas. 726 00:33:22,273 --> 00:33:23,400 Ayo, maju. 727 00:33:23,400 --> 00:33:25,640 Selesai, saya telah diurutkan Luke. 728 00:33:25,640 --> 00:33:28,570 Setengah kiri sekarang diurutkan dan bagian kanan sekarang diurutkan, 729 00:33:28,570 --> 00:33:30,770 tapi sekali lagi, ada langkah kunci di sini. 730 00:33:30,770 --> 00:33:32,940 Apa yang harus saya selanjutnya perlu dilakukan? 731 00:33:32,940 --> 00:33:33,941 Menggabungkan bagian diurutkan. 732 00:33:33,941 --> 00:33:36,648 Sekarang kita akan hanya memiliki semua orang bolak-balik dengan cara ini, 733 00:33:36,648 --> 00:33:38,620 karena saya jenis kebutuhan beberapa ruang awal. 734 00:33:38,620 --> 00:33:40,411 Ini hampir seperti ini orang ini di atas meja, 735 00:33:40,411 --> 00:33:42,460 dan aku butuh kamar untuk memindahkan mereka sekitar pada. 736 00:33:42,460 --> 00:33:44,170 Jadi aku akan menggabungkan kalian dengan melihat 737 00:33:44,170 --> 00:33:45,960 di bagian kiri dan bagian kanan. 738 00:33:45,960 --> 00:33:48,740 Dan yang jelas datang pertama, setengah kiri atau bagian kanan? 739 00:33:48,740 --> 00:33:52,710 Jadi setengah benar, jadi mari kita lanjutkan Lukas lebih sini ke posisi semula Darren. 740 00:33:52,710 --> 00:33:57,640 Dan sekarang untuk menggabungkan kiri setengah mereka, Darren akan bergerak di sana. 741 00:33:57,640 --> 00:33:59,750 >> Jadi terasa seperti hampir efek bubble sort, 742 00:33:59,750 --> 00:34:02,482 tapi algoritma dasar saya, sangat berbeda kali ini. 743 00:34:02,482 --> 00:34:04,815 Tapi sekarang di mana hal-hal mendapatkan sedikit mengganggu karena Anda 744 00:34:04,815 --> 00:34:06,810 harus mundur mental di mana aku meninggalkan dari. 745 00:34:06,810 --> 00:34:09,893 Saya baru saja bergabung dengan bagian diurutkan, yang berarti aku mana dalam algoritma saya? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Saya harus memilah bagian kanan, kan? 748 00:34:13,770 --> 00:34:15,910 >> Jika Anda mundur, secara harfiah pada video, Anda akan 749 00:34:15,910 --> 00:34:18,339 melihat bahwa kita harus ini titik Lukas dan Darren 750 00:34:18,339 --> 00:34:21,370 dengan menyortir kiri setengah dari kiri setengah. 751 00:34:21,370 --> 00:34:23,430 Kemudian kami bergabung mereka bagian diurutkan, yang 752 00:34:23,430 --> 00:34:27,941 berarti langkah selanjutnya adalah mengurutkan bagian kanan kiri setengah. 753 00:34:27,941 --> 00:34:29,649 Baiklah, jadi mari kita melakukan hal ini lebih cepat. 754 00:34:29,649 --> 00:34:33,282 Baiklah, enam, aku akan mengklaim Anda sekarang disortir, ayolah maju. 755 00:34:33,282 --> 00:34:33,990 Siapa nama Anda? 756 00:34:33,990 --> 00:34:34,589 >> AUDIENCE: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano kini diurutkan. 759 00:34:36,010 --> 00:34:36,450 Dan siapa namamu? 760 00:34:36,450 --> 00:34:37,080 >> AUDIENCE: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex sekarang diurutkan. 762 00:34:38,379 --> 00:34:40,750 Setengah kiri, kanan setengah, apa langkah terakhir? 763 00:34:40,750 --> 00:34:41,250 Merge. 764 00:34:41,250 --> 00:34:44,310 Cukup sepele, jadi aku akan bergabung dalam enam, 765 00:34:44,310 --> 00:34:46,930 mengambil langkah mundur, delapan, mengambil langkah mundur. 766 00:34:46,930 --> 00:34:49,530 Dan sekarang melihat ini adalah takeaway berguna, apa 767 00:34:49,530 --> 00:34:53,930 sekarang benar tentang setengah kiri daftar, terlepas dari bagaimana kita mulai? 768 00:34:53,930 --> 00:34:55,090 Hal ini diurutkan. 769 00:34:55,090 --> 00:34:57,750 >> Sekarang itu tidak diurutkan dalam skema besar hal, 770 00:34:57,750 --> 00:35:00,250 tetapi diurutkan secara independen dari setengah lainnya. 771 00:35:00,250 --> 00:35:04,100 Sekarang apa langkah aku pada jika aku terus memutar bagaimana cerita dimulai? 772 00:35:04,100 --> 00:35:05,680 Sekarang aku harus mengurutkan bagian kanan. 773 00:35:05,680 --> 00:35:07,630 Jadi sekarang kita jalan kembali pada awal cerita, 774 00:35:07,630 --> 00:35:08,921 dan mari kita lakukan ini lebih cepat. 775 00:35:08,921 --> 00:35:11,320 Jadi aku akan mengurutkan bagian kanan seluruh daftar. 776 00:35:11,320 --> 00:35:13,060 Apa langkah selanjutnya? 777 00:35:13,060 --> 00:35:15,840 Urutkan setengah kiri kanan setengah. 778 00:35:15,840 --> 00:35:18,715 Urutkan setengah kiri kiri setengah dari bagian kanan. 779 00:35:18,715 --> 00:35:19,590 Dan siapa namamu? 780 00:35:19,590 --> 00:35:20,230 >> AUDIENCE: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, langkah maju, dilakukan. 782 00:35:21,970 --> 00:35:22,860 Kiri setengah diurutkan. 783 00:35:22,860 --> 00:35:23,330 Dan siapa namamu? 784 00:35:23,330 --> 00:35:23,820 >> AUDIENCE: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, mengambil langkah ke depan, Anda sekarang disortir. 786 00:35:25,620 --> 00:35:27,010 Apa langkah kunci sekarang? 787 00:35:27,010 --> 00:35:27,510 Merge. 788 00:35:27,510 --> 00:35:30,509 Jadi salah satu akan bergabung menjadi tempat di sini, jika Anda bisa mengambil langkah mundur, 789 00:35:30,509 --> 00:35:32,930 dan tiga akan mengambil langkah mundur, bergabung. 790 00:35:32,930 --> 00:35:38,080 Jadi setengah kiri setengah benar, sekarang diurutkan. 791 00:35:38,080 --> 00:35:41,747 Terus terang, algoritma ini terasa seperti kita membuang-buang waktu cara yang lebih dari sebelumnya, 792 00:35:41,747 --> 00:35:44,830 tetapi jika kita melakukan ini secara real time, kita akan melihat apa takeaways akan. 793 00:35:44,830 --> 00:35:47,970 Sekarang saya di sini, tepat setengah dari bagian kanan, 794 00:35:47,970 --> 00:35:50,170 biarkan aku pergi ke depan dan memilah kiri setengah. 795 00:35:50,170 --> 00:35:51,482 Langkah ke depan, siapa namamu? 796 00:35:51,482 --> 00:35:52,190 AUDIENCE: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey sekarang diurutkan. 798 00:35:53,210 --> 00:35:53,570 Siapa nama Anda? 799 00:35:53,570 --> 00:35:54,200 >> AUDIENCE: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina sekarang diurutkan sebagai baik, jika Anda mengambil satu langkah maju. 801 00:35:57,033 --> 00:36:00,690 Langkah kunci di sini sekarang bergabung, aku akan memetik dari dua daftar saya, 802 00:36:00,690 --> 00:36:01,720 kiri dan kanan. 803 00:36:01,720 --> 00:36:05,150 Lima akan datang pertama, dan tujuh akan datang berikutnya. 804 00:36:05,150 --> 00:36:06,410 Dan lagi, ini adalah disengaja. 805 00:36:06,410 --> 00:36:08,535 Fakta bahwa mereka mengambil langkah ke depan dan belakang 806 00:36:08,535 --> 00:36:12,997 dimaksudkan untuk menyatakan bahwa kita tidak bisa melakukan algoritma ini di tempat yang mudah 807 00:36:12,997 --> 00:36:15,830 sebagai bubble sort, dan selection sort, dan insertion sort mana kita hanya 808 00:36:15,830 --> 00:36:16,960 terus swapping orang. 809 00:36:16,960 --> 00:36:19,940 Aku benar-benar butuh semacam sebuah kertas awal di mana 810 00:36:19,940 --> 00:36:21,827 untuk menempatkan orang-orang ini sementara aku melakukan penggabungan, 811 00:36:21,827 --> 00:36:23,410 dan kemudian saya bisa menempatkan mereka kembali di tempat. 812 00:36:23,410 --> 00:36:27,260 Dan itulah kuncinya karena saya menggunakan sumber daya baru, ruang, bukan hanya waktu. 813 00:36:27,260 --> 00:36:28,270 >> OK, ini luar biasa. 814 00:36:28,270 --> 00:36:32,050 Setengah kiri diurutkan, bagian kanan adalah diurutkan, sekarang bahwa kunci penggabungan langkah. 815 00:36:32,050 --> 00:36:33,450 Bagaimana aku bisa menggabungkan ini? 816 00:36:33,450 --> 00:36:35,470 Jadi, jika Anda akan mengikuti saya tangan kiri dan tangan kanan, 817 00:36:35,470 --> 00:36:38,930 Aku akan menunjukkan tangan kiriku di kiri setengah, tangan kananku 818 00:36:38,930 --> 00:36:42,680 di bagian kanan, dan sekarang aku harus memutuskan langkah demi langkah yang bergabung dalam. 819 00:36:42,680 --> 00:36:44,650 Yang jelas-jelas lebih dulu? 820 00:36:44,650 --> 00:36:45,150 Nomor satu. 821 00:36:45,150 --> 00:36:47,327 Jadi datang ke sini, inilah pad awal kami. 822 00:36:47,327 --> 00:36:49,910 Jadi sekarang nomor satu, dan pemberitahuan apa yang akan saya lakukan dengan tangan kanan saya, 823 00:36:49,910 --> 00:36:54,152 Aku akan memindahkan satu tangan kananku langkah di atas untuk menunjukkan nomor tiga, 824 00:36:54,152 --> 00:36:55,860 dan sekarang saya harus membuat keputusan yang sama. 825 00:36:55,860 --> 00:36:58,387 Dan benar-benar berdiri tepat di depan Lukas di sini jika Anda bisa, 826 00:36:58,387 --> 00:36:59,720 karena ini adalah pad awal kami. 827 00:36:59,720 --> 00:37:00,610 Jadi yang datang berikutnya? 828 00:37:00,610 --> 00:37:05,000 Kami memiliki Lukas dengan nomor dua atau Chris dengan nomor tiga. 829 00:37:05,000 --> 00:37:07,460 Jelas Lukas, jumlah dua, sehingga Anda datang ke sini. 830 00:37:07,460 --> 00:37:11,270 >> Tapi tangan kiri saya sekarang akan bertambah untuk menunjuk Darren, 831 00:37:11,270 --> 00:37:15,160 dan inilah kunci mengambil dengan penggabungan, aku akan terus melakukan hal ini, 832 00:37:15,160 --> 00:37:17,340 jelas, jika Anda jenis dari mengikuti logika. 833 00:37:17,340 --> 00:37:19,670 Tapi tangan saya tidak pernah akan pergi ke belakang, 834 00:37:19,670 --> 00:37:23,861 yang berarti aku hanya pernah pindah ke kiri dengan proses penggabungan saya, 835 00:37:23,861 --> 00:37:26,360 dan itu akan menjadi kunci untuk analisis kami hanya dalam beberapa saat. 836 00:37:26,360 --> 00:37:27,859 >> Jadi sekarang mari kita selesaikan ini dengan cepat. 837 00:37:27,859 --> 00:37:31,650 Jadi tiga datang berikutnya, kemudian empat datang berikutnya, 838 00:37:31,650 --> 00:37:38,750 dan sekarang lima datang berikutnya, kemudian enam, dan tujuh, dan akhirnya delapan. 839 00:37:38,750 --> 00:37:42,960 Terasa seperti algoritma paling lambat , tapi tidak jika kita benar-benar 840 00:37:42,960 --> 00:37:45,510 menjalankannya pada jenis yang sama clock speed, sehingga untuk 841 00:37:45,510 --> 00:37:48,106 berbicara, dengan sama berdetak jam seperti sebelumnya. 842 00:37:48,106 --> 00:37:48,605 Mengapa? 843 00:37:48,605 --> 00:37:51,100 Nah, Mari kita melihat hasil akhirnya. 844 00:37:51,100 --> 00:37:56,990 >> Mari kita kembali ke sini, biarkan aku menarik demonstrasi visual 845 00:37:56,990 --> 00:37:59,030 dari apa yang baru saja kita lakukan. 846 00:37:59,030 --> 00:38:06,110 Memperbesar sini, hal ini Halaman di sini, mengatakan Firefox 847 00:38:06,110 --> 00:38:08,200 bahwa kita ingin antrian di kotak ini, mari kita 848 00:38:08,200 --> 00:38:11,260 mengatakan bubble sort, dengan yang kita sekarang baik akrab, 849 00:38:11,260 --> 00:38:14,130 selection sort, yang lain cukup mudah satu, 850 00:38:14,130 --> 00:38:18,250 dan sekarang semacam merge hari ini, yang akan berakhir klimaks kami. 851 00:38:18,250 --> 00:38:21,530 Alasan butuh waktu lebih lama di sini dengan manusia dan saya secara lisan adalah, 852 00:38:21,530 --> 00:38:23,480 jelas, aku menjelaskan setiap langkah. 853 00:38:23,480 --> 00:38:26,920 Tapi jika Anda hanya menjalankan ini, banyak seperti yang kita lakukan bubble sort dan seleksi 854 00:38:26,920 --> 00:38:30,890 semacam tidak hanya secara visual, menonton berapa banyak lebih efisien 855 00:38:30,890 --> 00:38:33,330 leveraging ini divisi dan menaklukkan 856 00:38:33,330 --> 00:38:39,150 dapat bila diterapkan pada kumpulan data yang bahkan ukuran delapan, tapi bahkan banyak, 857 00:38:39,150 --> 00:38:39,970 jauh lebih besar. 858 00:38:39,970 --> 00:38:44,585 Saya memberi Anda menggabungkan semacam, side by sisi dengan ini algoritma lainnya. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Ini akan mendapatkan menyakitkan cepat, dan mengakhiri 861 00:38:58,530 --> 00:39:00,890 tidak terlalu klimaks, mereka hanya berakhir diurutkan. 862 00:39:00,890 --> 00:39:05,280 Tetapi kuncinya mengambil adalah bahwa terlihat betapa cepat menggabungkan semacam 863 00:39:05,280 --> 00:39:08,110 adalah, kecuali jika Anda pikir aku hanya jenis bermain-main dengan Anda. 864 00:39:08,110 --> 00:39:13,100 Jika kita melakukan ini terakhir kali, mari ulang ini, mari kita kembali 865 00:39:13,100 --> 00:39:14,960 dan memilih bubble sort, dan hanya untuk iseng, 866 00:39:14,960 --> 00:39:17,330 mari kita memilih penyisipan semacam, hanya untuk mengukur baik. 867 00:39:17,330 --> 00:39:20,020 Dan kali ini lagi, mari kita memilih merge sort dan mari kita 868 00:39:20,020 --> 00:39:21,595 benar-benar menjalankan sisi ini berdampingan. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Dan itu tidak, pada kenyataannya, kebetulan. 871 00:39:26,930 --> 00:39:31,140 Apa yang saya lakukan secara efektif adalah saya sudah dibagi masukan saya di setengah, sekali lagi, 872 00:39:31,140 --> 00:39:32,240 dan lagi, dan lagi. 873 00:39:32,240 --> 00:39:35,590 Dan hanya ada begitu banyak kali Anda bisa membagi masukan Anda menjadi dua bagian, kiri 874 00:39:35,590 --> 00:39:36,240 dan kanan. 875 00:39:36,240 --> 00:39:39,425 Apa formula yang kita terus melihat yang menggambarkan divisi dua 876 00:39:39,425 --> 00:39:41,050 lagi, dan lagi, dan lagi, dan lagi? 877 00:39:41,050 --> 00:39:41,890 >> AUDIENCE: Log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Log n. 879 00:39:42,760 --> 00:39:46,300 Tapi kemudian ada satu langkah penting lainnya, algoritma ini tidak log n langkah. 880 00:39:46,300 --> 00:39:48,992 Jika hanya log n langkah, kami akan berada di masalah yang sama 881 00:39:48,992 --> 00:39:51,200 seperti sebelumnya di mana kita tidak bisa yakin semuanya beres. 882 00:39:51,200 --> 00:39:54,480 Anda harus minimal melihat elemen n untuk memastikan n elemen diurutkan, 883 00:39:54,480 --> 00:39:55,950 jika itu adalah lompatan iman. 884 00:39:55,950 --> 00:39:59,810 >> Jadi log n langkah minimal, tetapi bagaimana langkah penggabungan kunci 885 00:39:59,810 --> 00:40:04,370 di mana saya bergabung setengah kiri dan kanan setengah dan berjalan melintasi panggung? 886 00:40:04,370 --> 00:40:06,980 Berapa banyak langkah adalah bahwa untuk bergabung? 887 00:40:06,980 --> 00:40:10,150 Ini n, tapi aku tidak hanya menggabungkan kalinya. 888 00:40:10,150 --> 00:40:15,089 Pada masing-masing panggilan bersarang, pada masing-masing mereka gabungan bersarang, aku masih disortir. 889 00:40:15,089 --> 00:40:18,380 Saya bergabung dua orang, maka kedua guys, maka dua orang dan sebagainya. 890 00:40:18,380 --> 00:40:19,955 >> Jadi aku penggabungan lagi, dan lagi. 891 00:40:19,955 --> 00:40:20,580 Berapa kali? 892 00:40:20,580 --> 00:40:23,510 Jadi setiap kali saya membagi daftar di setengah, saya melakukan gabungan. 893 00:40:23,510 --> 00:40:25,460 Bagilah daftar menjadi dua, melakukan penggabungan. 894 00:40:25,460 --> 00:40:28,570 Jadi jika membagi daftar bisa dilakukan log n kali, 895 00:40:28,570 --> 00:40:33,880 dan penggabungan akhirnya mengambil n langkah, apa yang mungkin sekarang atas 896 00:40:33,880 --> 00:40:37,000 terikat pada running waktu algoritma kita? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Dan memang, itulah yang kami raih di sini. 899 00:40:40,560 --> 00:40:44,650 Jadi merasa bahwa Anda lihat secara visual ketika ketiga hal berjalan berdampingan 900 00:40:44,650 --> 00:40:47,930 adalah n kuadrat terhadap n kuadrat terhadap n log n. 901 00:40:47,930 --> 00:40:51,010 Yang pada dasarnya kita akan melihat, tidak hanya hari ini, tapi di masa depan, 902 00:40:51,010 --> 00:40:52,760 jauh, jauh lebih cepat. 903 00:40:52,760 --> 00:40:56,010 Sebuah tepuk tangan untuk orang-orang, Aku akan membalas mereka dengan bola stres. 904 00:40:56,010 --> 00:41:00,260 Mari kita menunda sini hari ini, dan kita akan melihat Anda pada hari Senin. 905 00:41:00,260 --> 00:41:02,255