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 tiga, dan jika anda tidak mengambil kesempatan sudah, 4 00:00:19,020 --> 00:00:21,790 tahu bahawa akan ada makan tengah hari Jumaat ini seperti biasa, di mana 5 00:00:21,790 --> 00:00:25,430 anda boleh menikmati perbualan yang baik dan makanan di Bomba dan Ais 6 00:00:25,430 --> 00:00:27,980 dengan beberapa CS50 ini kakitangan dan rakan-rakan sekelas. 7 00:00:27,980 --> 00:00:30,170 Menuju ke URL ini di sini. 8 00:00:30,170 --> 00:00:33,420 >> Sekarang mana yang diketahui, atau anda tidak lama lagi boleh mengetahui, 9 00:00:33,420 --> 00:00:35,970 perkara-perkara ini di sini, yang yang diberikan pada akhir 10 00:00:35,970 --> 00:00:37,850 satu semester bagi banyak kelas. 11 00:00:37,850 --> 00:00:40,870 Yang dipanggil peperiksaan buku biru, di mana anda tulis jawapan anda untuk peperiksaan. 12 00:00:40,870 --> 00:00:44,240 Sekarang saya ada di sini 26 seperti buku biru, pada setiap daripada mereka 13 00:00:44,240 --> 00:00:47,580 ditulis nama, A melalui Z. Dan memang nama-nama yang mudah itu, A 14 00:00:47,580 --> 00:00:50,490 melalui Z. Dan salah satu matlamat di tangan hari ini 15 00:00:50,490 --> 00:00:53,910 akan menjadi untuk meneruskan apa yang kami bermula pada hari Isnin, yang tidak 16 00:00:53,910 --> 00:00:57,830 banyak melihat kod, tetapi benar-benar mencari idea dan penyelesaian masalah. 17 00:00:57,830 --> 00:01:00,170 Salah satu matlamat dan janji kursus ini 18 00:01:00,170 --> 00:01:02,985 adalah untuk mengajar anda untuk berfikir lebih berhati-hati, lebih teratur, 19 00:01:02,985 --> 00:01:05,400 dan untuk menyelesaikan masalah dengan lebih cekap. 20 00:01:05,400 --> 00:01:09,526 Dan sesungguhnya, kita boleh melakukan yang benar-benar tanpa menyentuh garis kod. 21 00:01:09,526 --> 00:01:12,150 Jadi, saya mempunyai beberapa ekor gajah di sini hari ini, oren dan biru, 22 00:01:12,150 --> 00:01:15,780 jika kita boleh mendapatkan satu sukarela, mungkin dari jauh ke belakang daripada biasa. 23 00:01:15,780 --> 00:01:18,070 Bagaimana pula di sana, datang ke atas ke bawah. 24 00:01:18,070 --> 00:01:24,180 Matlamat yang akan menjadi untuk membantu serta mentadbir peperiksaan ini di sini. 25 00:01:24,180 --> 00:01:24,935 Apa nama anda? 26 00:01:24,935 --> 00:01:25,768 >> PENONTON: 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 Biar saya mendapatkan mikrofon di sini untuk anda. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Nice untuk bertemu dengan kamu. 31 00:01:32,880 --> 00:01:34,005 >> PENONTON: Nice untuk bertemu dengan kamu. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Baiklah, jadi saya perlu di sini buku biru A melalui Z, 33 00:01:36,790 --> 00:01:41,680 dan saya akan berpura-pura bahawa Saya salah seorang pelajar, 34 00:01:41,680 --> 00:01:45,770 dan mereka datang agak rawak pada akhir peperiksaan blok tiga jam, 35 00:01:45,770 --> 00:01:49,400 supaya mereka memasuki beberapa perintah separa rawak seperti ini. 36 00:01:49,400 --> 00:01:54,510 Sekarang tugas anda hanya dalam masa yang akan untuk adalah-- ini sebenarnya cara mereka mendapatkan 37 00:01:54,510 --> 00:01:56,820 mencatatkan pada akhir kelas, kemungkinan besar. 38 00:01:56,820 --> 00:02:01,120 Pekerjaan anda sekarang akan menjadi, agak hanya, untuk menyusun buku-buku biru untuk kita 39 00:02:01,120 --> 00:02:05,220 dari A hingga Z. 40 00:02:05,220 --> 00:02:08,400 >> PENONTON: Oh, ini adalah akan mengambil selama-lamanya. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: Dan kami akan menonton seperti yang anda lakukan ini, tidak ada tekanan. 42 00:02:13,747 --> 00:02:15,330 PENONTON: Tidak, tidak tekanan atau apa-apa. 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 meletakkan pemasa. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PENONTON: seronok, menyeronokkan begitu banyak. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Saya boleh memegang mikrofon untuk anda. 49 00:02:38,574 --> 00:02:40,240 Baiklah, kita baru sahaja dua kali ganda kelajuan kita. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Jadi, dalam pada itu, biarlah saya memberikan apa yang akan menjadi soalan untuk Mary Beth 52 00:02:49,060 --> 00:02:51,540 adalah apa yang dia lakukan, bagaimana dia akan mengenai menyelesaikan ini? 53 00:02:51,540 --> 00:02:54,040 Dan sebenarnya, anda mungkin tidak mempunyai terfikir tentang sesuatu 54 00:02:54,040 --> 00:02:57,440 begitu mudah apabila anda memilih sehingga 26 buku-buku seperti ini, 55 00:02:57,440 --> 00:02:59,350 yang tidak mempunyai semula jadi memerintahkan kepada mereka. 56 00:02:59,350 --> 00:03:01,335 Apakah proses yang bahawa anda benar-benar digunakan? 57 00:03:01,335 --> 00:03:03,770 Adakah ia hanya agak rawak memilih salah satu yang pertama yang anda lihat 58 00:03:03,770 --> 00:03:05,250 dan meletakkannya di tempatnya? 59 00:03:05,250 --> 00:03:09,680 Adakah anda pertama bergerak tangan anda di sekitar mencari A kemudian mencari B? 60 00:03:09,680 --> 00:03:11,722 Adakah anda lihat pada sepasang mereka sebelah menyebelah 61 00:03:11,722 --> 00:03:14,680 dan hanya berkata, tunggu satu minit, ini tidak betul, dan kemudian menukar perintah itu? 62 00:03:14,680 --> 00:03:16,960 Kami melihat sudah pada hari Isnin bahawa ada beberapa cara 63 00:03:16,960 --> 00:03:22,140 di mana kita boleh melakukan ini, dan memang seperti yang kita berhampiran akhir di sini, 64 00:03:22,140 --> 00:03:26,360 Saya akan mengambil nota mungkin daripada apa yang Mary Beth lakukan. 65 00:03:26,360 --> 00:03:30,040 Kami mempunyai beberapa buasir ia seolah-olah, yang lebih besar, tiga yang lebih kecil. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PENONTON: Saya mengarahkan mereka apabila saya dapati dua surat 68 00:03:36,415 --> 00:03:39,540 yang saya tahu bersama-sama dalam satu urutan, Saya meletakkan mereka bersama-sama supaya saya tidak 69 00:03:39,540 --> 00:03:42,915 perlu bimbang tentang menjaga lagu satu barisan keseluruhan buku. 70 00:03:42,915 --> 00:03:45,706 Ia hanya, oh, adalah pertama, Saya telah mendapat timbunan ini di sini. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Jadi, hampir seperti satu keping teka-teki yang 72 00:03:47,580 --> 00:03:49,860 mempunyai bentuk yang betul kepada sepadan dengan satu sama lain. 73 00:03:49,860 --> 00:03:51,026 PENONTON: Pretty banyak, yeah. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, yang sangat baik. 75 00:03:55,320 --> 00:03:59,850 Dan sekarang ini setiap buasir adalah mungkin disusun? 76 00:03:59,850 --> 00:04:00,990 >> PENONTON: Yeah. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Baiklah, A melalui Z. Semua betul, tahniah, anda melakukannya. 78 00:04:09,900 --> 00:04:11,461 Anda mempunyai pilihan anda. 79 00:04:11,461 --> 00:04:11,960 Blue? 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 mencadangkan apa pendekatan beliau adalah, 82 00:04:16,679 --> 00:04:19,720 tetapi apa yang satu lagi pendekatan bagaimana anda mungkin pergi tentang menyusun perkara-perkara ini? 83 00:04:19,720 --> 00:04:21,130 Apa yang akan anda lakukan? 84 00:04:21,130 --> 00:04:24,060 Rekod untuk mengalahkan akan menjadi satu atau lebih 50 saat dan minit, 85 00:04:24,060 --> 00:04:26,039 ditambah yang saya terlupa untuk mengira. 86 00:04:26,039 --> 00:04:27,080 Apa yang akan anda lakukan? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 PENONTON: Ambil tindanan. 89 00:04:28,735 --> 00:04:29,776 Mulakan dari awal. 90 00:04:29,776 --> 00:04:32,284 Memeriksa kertas anda. 91 00:04:32,284 --> 00:04:36,586 Dan jika salah satu bahagian atas adalah lebih tinggi daripada, mungkin, mereka, 92 00:04:36,586 --> 00:04:38,980 satu bahagian bawah adalah lebih tinggi, kemudian menukar mereka. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, jadi bermula di bahagian atas dan bahagian bawah, 94 00:04:41,300 --> 00:04:43,716 dan kemudian bekerja cara anda masuk seperti itu, pertukaran mereka? 95 00:04:43,716 --> 00:04:46,580 OK, jadi yang sama sedikit dalam semangat untuk jenis gelembung, 96 00:04:46,580 --> 00:04:49,160 tetapi memilih yang keterlaluan tidak pasangan bersebelahan. 97 00:04:49,160 --> 00:04:52,080 Tetapi kekurangan itu adalah bahawa ada pasti banyak cara yang berbeza 98 00:04:52,080 --> 00:04:54,210 kita boleh melakukan ini, dan terus-terang, saya rasa anda jenis 99 00:04:54,210 --> 00:04:55,700 mengguna pakai pendekatan pasangan, bukan? 100 00:04:55,700 --> 00:05:00,567 Anda membuat semacam empat buasir disusun, dan kemudian digabungkan dengan berkesan mereka bersama-sama. 101 00:05:00,567 --> 00:05:02,650 Dan itu, berani mengatakan, satu lagi teknik sama sekali. 102 00:05:02,650 --> 00:05:06,950 Anda tidak menganggap ia sebagai satu longgokan besar, anda dibahagikan masalah itu kepada empat quads, 103 00:05:06,950 --> 00:05:09,820 jika anda akan, dan kemudian entah bagaimana digabungkan mereka pada akhirnya. 104 00:05:09,820 --> 00:05:13,410 >> Jadi mari kita mempertimbangkan, akhirnya, bagaimana lagi kita mungkin melakukan ini. 105 00:05:13,410 --> 00:05:15,860 Kami secara rasmi tanggapan gelembung semacam masa lalu, 106 00:05:15,860 --> 00:05:18,780 dan penarikan balik semacam gelembung adalah algoritma yang kita dilihat 107 00:05:18,780 --> 00:05:22,640 dengan lapan daripada rakan sekelas anda di sini, seolah-olah secara rawak disusun pada mulanya. 108 00:05:22,640 --> 00:05:26,110 Dan kita mengambil keputusan dari segi pasangan, jika dua elemen berada di luar perintah, 109 00:05:26,110 --> 00:05:26,950 hanya menukar mereka. 110 00:05:26,950 --> 00:05:28,930 Jadi empat dan dua jelas daripada perintah, 111 00:05:28,930 --> 00:05:31,080 supaya kedua-dua rakan-rakan sekelas beralih kedudukan. 112 00:05:31,080 --> 00:05:35,390 Dan kemudian kita berulang-ulang dengan empat dan enam, maka enam dan lapan, pada setiap lelaran, 113 00:05:35,390 --> 00:05:36,980 bergerak ke kanan. 114 00:05:36,980 --> 00:05:42,590 >> Jadi diberi lapan orang, berapa banyak dari segi pasangan perbandingan yang saya lakukan ketika berjalan dari 115 00:05:42,590 --> 00:05:45,220 kiri ke kanan dalam satu lelaran seperti itu? 116 00:05:45,220 --> 00:05:48,410 Berapa perbandingan? 117 00:05:48,410 --> 00:05:49,197 Tujuh, bukan? 118 00:05:49,197 --> 00:05:51,405 Kerana jika ada lapan orang tetapi anda perlu 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 mempunyai lapan perbandingan kerana anda tidak boleh membandingkan 121 00:05:56,060 --> 00:05:59,226 elemen dengan dirinya sendiri, atau ia akan hanya menjadi sia-sia, supaya anda mempunyai tujuh. 122 00:05:59,226 --> 00:06:01,290 Atau lebih umum, jika kita n orang, kami 123 00:06:01,290 --> 00:06:04,300 melakukan n tolak 1 perbandingan dengan jenis gelembung. 124 00:06:04,300 --> 00:06:08,150 >> Jadi mari kita mempertimbangkan sekarang bagaimana baik atau gelembung buruk semacam sebenarnya adalah, dan cuba 125 00:06:08,150 --> 00:06:13,570 untuk memberikan diri kita dengan perbendaharaan kata untuk algoritma kritikan seperti ini, 126 00:06:13,570 --> 00:06:14,430 dan tidak lama lagi kita sendiri. 127 00:06:14,430 --> 00:06:16,970 Jadi pas pertama menerusi semacam gelembung, kali pertama 128 00:06:16,970 --> 00:06:20,909 Saya berjalan dari kiri ke kanan di seluruh peringkat, membawa saya n tolak 1 perbandingan. 129 00:06:20,909 --> 00:06:22,950 Dan itu akan menjadi saya unit ukuran, bukan? 130 00:06:22,950 --> 00:06:26,170 Saya jenis bercakap dan berjalan, agak cepat, agak perlahan, 131 00:06:26,170 --> 00:06:29,300 jadi saya mengira bilangan saat tidak terutamanya memberitahu, 132 00:06:29,300 --> 00:06:32,260 tetapi mengira bilangan operasi yang saya lakukan pada hari Isnin, 133 00:06:32,260 --> 00:06:35,900 membandingkan dua orang, yang terasa seperti unit bagus langkah. 134 00:06:35,900 --> 00:06:40,980 >> Jadi n tolak 1 langkah kali pertama, tetapi apa yang berlaku selepas itu? 135 00:06:40,980 --> 00:06:46,610 Apa yang terbalik salah satu pas melalui senarai terisih sebaliknya? 136 00:06:46,610 --> 00:06:49,840 Apa yang anda boleh memberitahu saya tentang elemen yang adalah semua jalan di sana? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Itu adalah unsur terbesar, bukan? 139 00:06:52,870 --> 00:06:55,710 Nombor lapan, walaupun dia bermula di sini, setiap kali saya 140 00:06:55,710 --> 00:06:57,860 berbanding menentang jiran, dia terus 141 00:06:57,860 --> 00:07:00,480 menggelegak sehingga hak sebelah senarai. 142 00:07:00,480 --> 00:07:02,710 Dan sesungguhnya, itu di mana algoritma mendapat namanya. 143 00:07:02,710 --> 00:07:07,630 >> Sekarang berdasarkan logik tersebut, berapa banyak perbandingan perlu saya membuat pada kali kedua 144 00:07:07,630 --> 00:07:09,800 Saya membuat pas yang dari kiri ke kanan? 145 00:07:09,800 --> 00:07:10,730 n tolak 2, bukan? 146 00:07:10,730 --> 00:07:14,297 Ia hanya akan membuang masa saya jika saya menyimpan membandingkan lapan terhadap seseorang 147 00:07:14,297 --> 00:07:16,630 lagi kerana kita sudah tahu dia berada di tempat yang betul. 148 00:07:16,630 --> 00:07:19,760 Jadi itulah sedikit satu pengoptimuman, jadi pas seterusnya 149 00:07:19,760 --> 00:07:23,899 akan menjadi tambah n tolak dua langkah, di mana n ialah bilangan orang. 150 00:07:23,899 --> 00:07:26,940 Sekarang anda jenis boleh membuat anggaran, walaupun jika anda bukan seorang ahli sains 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 mempunyai hanya satu perbandingan kiri. 153 00:07:31,259 --> 00:07:33,800 Anda perlu jenis menetapkan bermula daripada senarai dalam kes dua 154 00:07:33,800 --> 00:07:36,540 dan satu berada di luar perintah dan harus menjadi satu dan dua, 155 00:07:36,540 --> 00:07:40,330 jadi ini selamat minum sekurang- ditambah 1 perbandingan akhir. 156 00:07:40,330 --> 00:07:44,500 >> Sekarang titik, dot, dot jenis gelombang itu tangan di beberapa butiran banyak jus, 157 00:07:44,500 --> 00:07:46,452 tetapi mari kita pergi ke depan dan memudahkan. 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 mempunyai buku matematik yang mempunyai kunci cheat sedikit 160 00:07:50,340 --> 00:07:52,550 pada kulit depan atau semula penutup yang menunjukkan anda 161 00:07:52,550 --> 00:07:56,400 apa siri penjumlahan seperti ini akhirnya menambah sehingga. 162 00:07:56,400 --> 00:07:59,600 Dalam kes umum, jika anda mempunyai pembolehubah seperti n, dan sememangnya satu ini, 163 00:07:59,600 --> 00:08:01,634 jika anda melihat anda buku matematik sekolah lama, 164 00:08:01,634 --> 00:08:04,050 anda akan melihat bahawa ini sebenarnya menambah sehingga jumlah ini di sini, 165 00:08:04,050 --> 00:08:07,970 n masa n tolak 1 semua dibahagikan dengan 2. 166 00:08:07,970 --> 00:08:11,172 Jadi buat masa ini biarlah saya menyatakan ini adalah benar, sebagainya lonjakan iman, 167 00:08:11,172 --> 00:08:12,880 itulah yang ini jumlah wang sehingga, dan kita boleh 168 00:08:12,880 --> 00:08:14,341 membuktikan bahawa dalam kes yang lebih umum. 169 00:08:14,341 --> 00:08:15,590 Tetapi sekarang mari kita berkembang ini keluar. 170 00:08:15,590 --> 00:08:19,920 Jadi mari kita membiak ini keluar, supaya n kuasa dua, tolak n, semua dibahagikan dengan 2. 171 00:08:19,920 --> 00:08:23,200 Itu benar-benar n kuasa dua, dibahagikan dengan 2, tolak n lebih 2, 172 00:08:23,200 --> 00:08:25,010 jadi itu sahaja yang bagus dan menarik. 173 00:08:25,010 --> 00:08:27,060 Tetapi apa yang berlaku jika kita kini plug-in nilai? 174 00:08:27,060 --> 00:08:29,724 Katakan saya tidak mempunyai lapan orang, tetapi mengatakan juta. 175 00:08:29,724 --> 00:08:31,890 Dan satu juta hanya kerana ia adalah satu jumlah yang cukup besar, 176 00:08:31,890 --> 00:08:34,039 mari kita pasangkan itu dan lihat apa yang berlaku. 177 00:08:34,039 --> 00:08:39,039 Jadi jika saya palam juta ke dalam formula yang Saya akan mendapatkan satu juta kuasa dua, 178 00:08:39,039 --> 00:08:42,868 dibahagikan dengan 2, tolak juta, dibahagikan dengan 2. 179 00:08:42,868 --> 00:08:44,159 Sekarang apa yang yang akan sama? 180 00:08:44,159 --> 00:08:47,354 Jadi 500 bilion, tolak 500,000. 181 00:08:47,354 --> 00:08:49,270 Dan jika saya benar-benar melakukan matematik yang keluar, cara yang 182 00:08:49,270 --> 00:08:53,920 yang menyusun satu juta orang-orang yang semacam gelembung 183 00:08:53,920 --> 00:09:01,800 mungkin mengambil masa saya 499999500000 langkah-langkah atau perbandingan pada akhirnya, 184 00:09:01,800 --> 00:09:02,900 kami hanya menentuluar. 185 00:09:02,900 --> 00:09:06,860 >> Yang terasa agak lambat, tetapi terus-terang berukuran satu input tertentu 186 00:09:06,860 --> 00:09:09,160 seperti ini, tidak semua menunjukkan yang. 187 00:09:09,160 --> 00:09:14,050 Tetapi sesungguhnya ia mencadangkan bahawa sebagai n mendapat, algoritma ini lebih besar dan lebih besar 188 00:09:14,050 --> 00:09:16,280 jenis berasa lebih teruk dan lebih teruk lagi, atau anda benar-benar 189 00:09:16,280 --> 00:09:20,450 mula berasa kesakitan yang exponentiation, n kuasa dua, 190 00:09:20,450 --> 00:09:21,770 yang menambah sehingga agak cepat. 191 00:09:21,770 --> 00:09:25,340 Dan butiran ini tidak hilang pada orang, sebenarnya 192 00:09:25,340 --> 00:09:29,640 beberapa tahun lalu, seorang senator tertentu yang merupakan berkempen, duduk untuk temuduga 193 00:09:29,640 --> 00:09:32,180 Eric dengan Google Schmidt, Ketua Pegawai Eksekutif pada masa itu, 194 00:09:32,180 --> 00:09:36,380 dan telah dicabar dengan soalan sama seperti kita meneroka hari ini. 195 00:09:36,380 --> 00:09:38,468 Mari kita lihat. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO MAIN SEMULA] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Anda di sini di Google, dan saya suka 198 00:09:48,560 --> 00:09:53,382 memikirkan jawatan presiden seperti temu duga kerja. 199 00:09:53,382 --> 00:09:56,434 Kini, ia sukar untuk mendapatkan pekerjaan sebagai presiden, 200 00:09:56,434 --> 00:09:58,100 dan anda akan melalui cabaran hebat yang diberikan sekarang. 201 00:09:58,100 --> 00:10:01,860 Ia juga sukar untuk mendapatkan pekerjaan di Google. 202 00:10:01,860 --> 00:10:05,490 Kami mempunyai soalan, dan kami meminta calon-calon soalan 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 What-- kalian fikir saya main-main, ia adalah di sini. 205 00:10:14,760 --> 00:10:17,930 Apakah cara yang paling berkesan untuk menyusun satu juta 32-bit integer? 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 >> -I'm Maaf, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Tidak, tidak, tidak. 210 00:10:27,400 --> 00:10:30,700 Saya rasa 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 >> -Ayuh, Yang memberitahu dia ini? 213 00:10:38,180 --> 00:10:40,590 Saya tidak melihat komputer sains di latar belakang anda. 214 00:10:40,590 --> 00:10:42,130 >> -We've Mendapat 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 yang berbeza soalan temuduga. 217 00:10:48,444 --> 00:10:49,300 >> [VIDEO AKHIR MAIN SEMULA] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Jadi bercakap tentang nombor tertentu walaupun, 219 00:10:52,290 --> 00:10:53,890 tidak akan menjadi apa yang berguna. 220 00:10:53,890 --> 00:10:56,810 Ia bukan satu pengajaran hidup gelembung yang jenis, diberi sejuta input, 221 00:10:56,810 --> 00:10:58,590 mungkin mengambil masa sebanyak 500 bilion langkah. 222 00:10:58,590 --> 00:11:01,120 Anda tidak boleh benar-benar umum terlalu berkesan itu 223 00:11:01,120 --> 00:11:03,560 dan membuat keputusan reka bentuk yang baik semasa menulis program. 224 00:11:03,560 --> 00:11:07,070 Jadi mari kita memberi tumpuan walaupun bagaimana kita mungkin memudahkan keputusan ini. 225 00:11:07,070 --> 00:11:11,780 >> Jadi saya telah ditonjolkan dalam kuning di sini hasil daripada kuasa dua n dibahagikan dengan 2, 226 00:11:11,780 --> 00:11:14,330 jadi kuasa dua juta dibahagikan dengan 2, dan kemudian 227 00:11:14,330 --> 00:11:16,710 Saya telah menekankan apa jawapan muktamad adalah 228 00:11:16,710 --> 00:11:20,180 sebaik sahaja kami ditolak off n dibahagi dengan 2. 229 00:11:20,180 --> 00:11:24,850 Dan tuntutan itu saya akan buat sekarang adalah, yang palang pintu yang peduli jika anda tolak off 230 00:11:24,850 --> 00:11:30,060 a n lama lebih kurang 2 apabila pertama sebahagian daripada formula ini begitu banyak lebih besar? 231 00:11:30,060 --> 00:11:33,910 Ia menguasai yang lain jangka, n kuasa dua dibahagikan dengan 2 232 00:11:33,910 --> 00:11:37,510 ini lebih besar, jelas, sebagai n menjadi besar seperti satu juta, 233 00:11:37,510 --> 00:11:41,450 yang benar-benar terdapat perbezaan yang besar di akhirnya di antara 500 bilion 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 apa yang kita akan lakukan sebagai saintis komputer 237 00:11:48,640 --> 00:11:53,270 mengabaikan terma perintah yang lebih rendah dan mengambil sesuatu seperti ini dan benar-benar 238 00:11:53,270 --> 00:11:56,050 hanya memudahkan kepada jangka yang berlaku untuk perkara itu. 239 00:11:56,050 --> 00:12:00,315 Semakin besar set data kami mendapatkan, semakin besar pangkalan data kami mendapatkan, halaman web yang lebih 240 00:12:00,315 --> 00:12:02,690 kita perlu mencari, yang lebih rakan-rakan anda di Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Sebagai n bertambah besar, kami benar-benar akan mengambil berat tentang yang terbesar 242 00:12:07,340 --> 00:12:11,560 tempoh dalam mana-mana analisis apa-apa Prestasi algoritma kami. 243 00:12:11,560 --> 00:12:16,230 Dan saya akan berkata, anda tahu apa, semacam gelembung adalah atas perintah O besar, 244 00:12:16,230 --> 00:12:18,060 atas perintah n kuasa dua. 245 00:12:18,060 --> 00:12:20,090 Ia tidak betul-betul n kuasa dua seperti yang kita lihat, 246 00:12:20,090 --> 00:12:22,060 tetapi yang benar-benar mengambil berat mengenai istilah-istilah yang lebih kecil, 247 00:12:22,060 --> 00:12:24,390 dan terus-terang, yang benar-benar peduli jika kita membahagikan oleh 2? 248 00:12:24,390 --> 00:12:25,870 Itu hanya satu faktor yang berterusan. 249 00:12:25,870 --> 00:12:29,480 Dan 500 bilion berbanding 250 bilion benar-benar masalah besar yang? 250 00:12:29,480 --> 00:12:32,190 Saya hanya boleh menunggu satu tahun, membiarkan komputer riba saya secara literal 251 00:12:32,190 --> 00:12:34,810 mendapatkan dua kali lebih cepat dalam perkakasan, dan yang jenis perbezaan 252 00:12:34,810 --> 00:12:36,650 hanya akan hilang secara semula jadi dari masa ke masa. 253 00:12:36,650 --> 00:12:39,300 >> Apa yang kita mengambil berat tentang adalah ungkapan, bahagian 254 00:12:39,300 --> 00:12:42,489 ungkapan yang berlaku untuk mengubah sebagai input kami mendapat lebih besar dan lebih besar. 255 00:12:42,489 --> 00:12:45,280 Dan memang, dalam dunia sebenar, itulah apa yang berlaku semakin 256 00:12:45,280 --> 00:12:48,330 merupakan input kepada masalah kita dan algoritma mendapat lebih besar. 257 00:12:48,330 --> 00:12:53,470 Jadi O besar akan menjadi notasi, notasi asimptot, bahawa kita hanya 258 00:12:53,470 --> 00:12:57,160 digunakan sebagai saintis komputer untuk menggambarkan prestasi, atau masa berjalan, 259 00:12:57,160 --> 00:12:58,130 satu algoritma. 260 00:12:58,130 --> 00:13:00,800 Supaya kita boleh membandingkan algoritma pada komputer yang berbeza bertulis 261 00:13:00,800 --> 00:13:04,170 oleh orang-orang yang berbeza, dengan menggunakan beberapa metrik pada asasnya serupa 262 00:13:04,170 --> 00:13:07,557 seperti bilangan perbandingan anda membuat, atau mungkin bilangan 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 kiraan adalah jumlah masa 265 00:13:11,910 --> 00:13:13,981 yang berlalu pada jam di dinding biasanya. 266 00:13:13,981 --> 00:13:16,230 Apa yang kita tidak akan bimbang tentang adalah berapa banyak memori 267 00:13:16,230 --> 00:13:17,820 anda menggunakan hari ini di kurangnya, walaupun itu 268 00:13:17,820 --> 00:13:19,370 sumber lain kita mungkin mengukur. 269 00:13:19,370 --> 00:13:23,610 Kami akan cuba untuk mendasarkan analisis kami hanya pada operasi asas, yang, 270 00:13:23,610 --> 00:13:25,930 terus terang, bahawa anda boleh melihat yang paling visual. 271 00:13:25,930 --> 00:13:30,700 Jadi dengan sesuatu seperti O besar n kuasa dua, saya mendakwa bahawa O n kuasa dua 272 00:13:30,700 --> 00:13:35,820 adalah satu atas terikat pada apa yang dikenali sebagai berjalan masa semacam gelembung. 273 00:13:35,820 --> 00:13:38,820 Dalam erti kata lain, jika anda mahu mendakwa bahawa ada 274 00:13:38,820 --> 00:13:41,370 had ini atas kepada berapa banyak langkah algoritma mungkin mengambil masa, 275 00:13:41,370 --> 00:13:46,240 ia akan berada dalam O besar n kuasa dua dalam kes ini, had atas. 276 00:13:46,240 --> 00:13:49,710 >> Bagaimana sekiranya saya bukannya menukar cerita menjadi tidak mengenai jenis gelembung, 277 00:13:49,710 --> 00:13:50,910 tetapi tentang ini had atas. 278 00:13:50,910 --> 00:13:54,030 Bolehkah anda memikirkan algoritma yang kita telah melihat sudah 279 00:13:54,030 --> 00:13:59,530 yang terikat atas, maksimum mengukur masa atau operasi, 280 00:13:59,530 --> 00:14:04,300 akan dikatakan disempadani dengan n, fungsi linear, 281 00:14:04,300 --> 00:14:07,260 bukan satu kuadratik itu melengkung? 282 00:14:07,260 --> 00:14:10,780 Apa algoritma yang sentiasa mengambil masa tidak lebih 283 00:14:10,780 --> 00:14:12,860 daripada langkah-langkah seperti n, atau Langkah 2n, atau langkah-langkah 3n? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> PENONTON: Mencari jumlah terbesar dalam senarai? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfect, mencari jumlah terbesar dalam senarai. 287 00:14:16,930 --> 00:14:18,940 Jika saya diberikan satu senarai orang misalnya, 288 00:14:18,940 --> 00:14:21,440 setiap yang memegang nombor, apa yang bilangan maksimum 289 00:14:21,440 --> 00:14:23,770 daripada langkah-langkah yang perlu mengambil saya, orang yang semunasabahnya pintar, 290 00:14:23,770 --> 00:14:27,530 untuk mencari orang yang terbesar di dalam senarai itu? 291 00:14:27,530 --> 00:14:28,100 n, bukan? 292 00:14:28,100 --> 00:14:31,320 Kerana dalam kes yang paling teruk, di mana mungkin nilai terbesar menjadi? 293 00:14:31,320 --> 00:14:32,700 Betul, semua cara di akhir. 294 00:14:32,700 --> 00:14:34,575 Jadi dalam kes yang paling teruk atas terikat, saya mungkin 295 00:14:34,575 --> 00:14:36,450 perlu pergi sepanjang jalan di sini dan menjadi seperti, 296 00:14:36,450 --> 00:14:39,170 oh, inilah nombor lapan, atau apa sahaja nilai yang. 297 00:14:39,170 --> 00:14:41,330 Sekarang ia hanya akan menjadi bodoh jika saya terus berjalan, bukan? 298 00:14:41,330 --> 00:14:43,840 Mencari lebih banyak unsur-unsur jika yang terakhir daripada mereka ada di sana? 299 00:14:43,840 --> 00:14:45,340 Jadi sudah tentu, n adalah had atas. 300 00:14:45,340 --> 00:14:47,420 Saya tidak perlu mengambil langkah yang lebih daripada itu. 301 00:14:47,420 --> 00:14:51,580 >> Jadi apa jika sebaliknya saya mencadangkan terdapat algoritma di dunia ini yang 302 00:14:51,580 --> 00:14:57,750 mempunyai masa yang berjalan itu disempadani oleh O besar log n, log n? 303 00:14:57,750 --> 00:15:00,390 Di mana telah kita lihat sebelum ini? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> PENONTON: Dalam masalah buku telefon? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Seperti masalah buku telefon. 307 00:15:04,850 --> 00:15:07,754 Apakah ukuran bagaimana banyak masa atau berapa banyak air mata itu 308 00:15:07,754 --> 00:15:10,170 mengambil masa saya untuk mencari seseorang seperti Mike Smith dalam buku telefon? 309 00:15:10,170 --> 00:15:13,212 Kita mendakwa ia adalah log n, dan walaupun tidak biasa atau ia itu 310 00:15:13,212 --> 00:15:15,170 yang kabur sedikit apa yang logaritma atau eksponen adalah, 311 00:15:15,170 --> 00:15:17,650 hanya ingat bahawa log n biasanya merujuk kepada proses, 312 00:15:17,650 --> 00:15:20,790 dalam kes ini, membahagikan sesuatu pada separuh lagi, dan sekali lagi, 313 00:15:20,790 --> 00:15:25,790 dan sekali lagi, dan sekali lagi, seperti yang ia mendapat semakin kecil seperti yang anda lakukan itu. 314 00:15:25,790 --> 00:15:28,470 >> Jadi log n merujuk, pasti, kepada contoh buku telefon, 315 00:15:28,470 --> 00:15:32,662 dengan carian binari dalam teori, apabila kita mempunyai pintu maya pada lembaga, 316 00:15:32,662 --> 00:15:34,370 atau apabila Sean adalah mencari sesuatu. 317 00:15:34,370 --> 00:15:37,374 Jika dia telah menggunakan carian binari, log n akan menjadi had atas kepada berapa banyak 318 00:15:37,374 --> 00:15:38,040 masa yang mengambil. 319 00:15:38,040 --> 00:15:44,027 Tetapi orang-algoritma yang berlari dalam Log n diandaikan apa terperinci utama? 320 00:15:44,027 --> 00:15:45,360 Bahawa senarai itu disusun, bukan? 321 00:15:45,360 --> 00:15:47,789 Algoritma anda adalah salah jika input anda tidak disusun, 322 00:15:47,789 --> 00:15:49,830 dan lagi anda menggunakan sesuatu seperti carian binari 323 00:15:49,830 --> 00:15:51,704 kerana anda mungkin boleh melompat hak ke atas elemen 324 00:15:51,704 --> 00:15:53,600 tanpa menyedari ia memang ada. 325 00:15:53,600 --> 00:15:55,600 >> Sekarang apa yang mungkin ini bermakna wahai besar satu? 326 00:15:55,600 --> 00:15:59,117 Ini tidak bermakna bahawa algoritma anda mengambil satu dan hanya satu langkah, 327 00:15:59,117 --> 00:16:01,200 ia hanya bermaksud ia mengambil bilangan berterusan langkah. 328 00:16:01,200 --> 00:16:04,060 Mungkin ia adalah 1, mungkin ia 10, mungkin ia 1,000, 329 00:16:04,060 --> 00:16:07,750 tetapi ia bebas daripada saiz masalah itu. 330 00:16:07,750 --> 00:16:10,850 Tidak kira berapa besar n adalah, algoritma masa tetap 331 00:16:10,850 --> 00:16:12,747 sentiasa mengambil jumlah yang sama langkah-langkah. 332 00:16:12,747 --> 00:16:15,080 Jadi apa yang mungkin menjadi algoritma kita bercakap tentang atau hanya 333 00:16:15,080 --> 00:16:20,418 intuitif yang datang kepada anda bahawa sentiasa berjalan dalam apa yang dikenali sebagai pemalar masa? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> PENONTON: Tambah dua nombor. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Tambah dua nombor, 2 plus 2 sama dengan 4, dilakukan. 337 00:16:25,320 --> 00:16:27,227 Jadi yang mungkin bekerja, apa lagi? 338 00:16:27,227 --> 00:16:28,560 Bagaimana tentang dunia lebih nyata, ya? 339 00:16:28,560 --> 00:16:30,686 >> PENONTON: Mencari Perkara pertama dalam senarai. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Mencari yang pertama elemen dalam senarai, pasti. 341 00:16:32,810 --> 00:16:34,540 Kami benar-benar telah bercakap mengenai tatasusunan sudah, 342 00:16:34,540 --> 00:16:36,540 bagaimana anda mendapat di Elemen pertama dalam array, 343 00:16:36,540 --> 00:16:40,465 tidak kira berapa lama array adalah dalam kod C? 344 00:16:40,465 --> 00:16:43,090 Anda hanya gunakan seperti pendakap notasi sifar, bam, anda di sana. 345 00:16:43,090 --> 00:16:46,120 Dan sesungguhnya tatasusunan, sebagai diketepikan, sokongan sesuatu yang diketahui umum 346 00:16:46,120 --> 00:16:49,240 akses rawak, akses rawak ingatan, kerana anda boleh benar-benar 347 00:16:49,240 --> 00:16:50,284 melompat ke mana-mana satu tempat. 348 00:16:50,284 --> 00:16:52,700 Kita boleh melakukan ini lebih semata-mata kita boleh putar balik untuk minggu sifar 349 00:16:52,700 --> 00:16:53,900 apabila kita lakukan Scratch. 350 00:16:53,900 --> 00:16:59,707 Berapakah masa yang diambil untuk mengatakan blok Scratch untuk melaksanakan? 351 00:16:59,707 --> 00:17:00,790 Hanya masa yang berterusan, bukan? 352 00:17:00,790 --> 00:17:03,960 Mengatakan sesuatu, katakan sesuatu, tidak kira 353 00:17:03,960 --> 00:17:07,359 bagaimana calar besar dunia adalah, ia sentiasa akan mengambil jumlah yang sama masa 354 00:17:07,359 --> 00:17:08,490 dengan hanya mengatakan sesuatu. 355 00:17:08,490 --> 00:17:11,089 >> Jadi itulah masa yang berterusan, tetapi apa yang sebelah flip? 356 00:17:11,089 --> 00:17:13,030 Jika itu adalah atas batas, bagaimana jika kita mahu 357 00:17:13,030 --> 00:17:17,089 untuk menggambarkan batas bawah algoritma kami berjalan masa? 358 00:17:17,089 --> 00:17:19,852 Hampir satu kes terbaik berpotensi, jika anda akan, 359 00:17:19,852 --> 00:17:23,060 walaupun syarat-syarat ini boleh terpakai bagi terbaik kes, kes-kes paling teruk, kes-kes purata lebih 360 00:17:23,060 --> 00:17:26,359 secara amnya, tetapi mari kita hanya tertumpu pada batas bawah amnya. 361 00:17:26,359 --> 00:17:31,920 Apa algoritma yang mempunyai yang lebih rendah terikat n langkah, 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 n langkah, itulah yang lebih rendah terikat. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> PENONTON: semacam gelembung? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: jenis Bubble mengambil anda minimum n langkah, mengapa? 367 00:17:41,610 --> 00:17:42,279 Mengapa? 368 00:17:42,279 --> 00:17:45,320 Mengapa permulaan yang akan datang kepada anda intuitif, walaupun ia bukan sahaja 369 00:17:45,320 --> 00:17:46,530 lagi? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> PENONTON: [didengar]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Tepat sekali. 374 00:17:52,360 --> 00:17:55,810 Dalam senario yang terbaik daripada semacam gelembung, dan banyak algoritma, 375 00:17:55,810 --> 00:17:58,769 jika saya menyerahkan anda lapan orang yang telah disusun, 376 00:17:58,769 --> 00:18:00,560 ia akan menjadi bodoh untuk anda, algoritma, 377 00:18:00,560 --> 00:18:02,202 untuk berulang-alik lebih daripada sekali, bukan? 378 00:18:02,202 --> 00:18:04,285 Kerana sebaik sahaja anda berjalan melalui senarai sekali, 379 00:18:04,285 --> 00:18:08,090 anda perlu sedar, oh, saya tidak membuat sebarang swap, senarai ini disusun, keluar. 380 00:18:08,090 --> 00:18:09,700 Tetapi itu akan mengambil langkah-langkah yang anda n. 381 00:18:09,700 --> 00:18:12,033 >> Dan sebaliknya, apa yang lain cara berfikir tentang perkara ini? 382 00:18:12,033 --> 00:18:15,240 Jenis Bubble adalah omega satu, boleh dikatakan, n, 383 00:18:15,240 --> 00:18:19,050 kerana jika anda melihat penggunaan di kurang dari n unsur, apa 384 00:18:19,050 --> 00:18:23,009 adalah isu asas di sana? 385 00:18:23,009 --> 00:18:24,550 Anda tidak tahu jika ia disusun, betul. 386 00:18:24,550 --> 00:18:26,800 Kita manusia kekuatan renungan lapan orang dan menjadi seperti, oh, ia disusun, 387 00:18:26,800 --> 00:18:28,430 yang tidak mengambil langkah-langkah yang saya n, tetapi melakukannya. 388 00:18:28,430 --> 00:18:30,810 Mata anda, walaupun anda jenis daripada mempunyai bidang besar penglihatan, 389 00:18:30,810 --> 00:18:33,184 anda melihat lapan elemen, anda melihat lapan orang, 390 00:18:33,184 --> 00:18:34,610 itulah lapan langkah-langkah yang berkesan. 391 00:18:34,610 --> 00:18:38,612 Dan hanya jika saya berjalan melalui seluruh Senarai saya menyedari, ya, disusun. 392 00:18:38,612 --> 00:18:41,320 Jika saya berhenti separuh jalan berfikir, semua betul, ia cantik disusun setakat ini, 393 00:18:41,320 --> 00:18:42,520 apakah kemungkinan ia tidak disusun? 394 00:18:42,520 --> 00:18:44,186 Bahawa algoritma tidak akan menjadi betul. 395 00:18:44,186 --> 00:18:46,250 Mungkin lebih cepat, tetapi tidak betul. 396 00:18:46,250 --> 00:18:48,500 >> Jadi sekarang kita mempunyai cara menggambarkan batas yang lebih rendah, 397 00:18:48,500 --> 00:18:49,710 dan bagaimana pula dengan masa yang berterusan? 398 00:18:49,710 --> 00:18:54,565 Apa algoritma yang mempunyai yang lebih rendah terikat pada masa perjalanan sebanyak satu? 399 00:18:54,565 --> 00:18:58,350 1 langkah, 2 langkah, 10 langkah, tetapi tetap, bebas daripada n, 400 00:18:58,350 --> 00:18:59,310 saiz 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 >> PENONTON: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Apakah itu? 405 00:19:06,183 --> 00:19:07,184 PENONTON: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, pasti. 408 00:19:08,400 --> 00:19:10,720 Jadi ia mengambil beberapa langkah-langkah yang tetap. 409 00:19:10,720 --> 00:19:13,170 Dan saya perlu now-- sekarang kita berbicara tentang kod C 410 00:19:13,170 --> 00:19:16,040 dan tidak Scratch, sesuatu seperti berkata, dengan printf, 411 00:19:16,040 --> 00:19:17,710 kita harus mula mendapat berhati-hati. 412 00:19:17,710 --> 00:19:21,090 Printf kerana tidak mengambil input, ia adalah rentetan, 413 00:19:21,090 --> 00:19:23,220 dan rentetan yang mempunyai panjang dari segi teknikal. 414 00:19:23,220 --> 00:19:25,530 Jadi, jika kita mahu memilih kepada anda, jika anda tidak keberatan, 415 00:19:25,530 --> 00:19:29,430 secara teknikal kita boleh berhujah bahawa printf tidak mengambil input panjang berubah-ubah, 416 00:19:29,430 --> 00:19:32,270 dan sesungguhnya ia mungkin mengambil masa lebih masa untuk mencetak rentetan yang panjang, 417 00:19:32,270 --> 00:19:33,560 daripada ini panjang. 418 00:19:33,560 --> 00:19:36,570 >> Jadi apa jika kami mengambil kira hanya menyusun dan mencari contoh? 419 00:19:36,570 --> 00:19:40,450 Bagaimana Mike Smith dalam telefon buku, atau carian binari secara umum? 420 00:19:40,450 --> 00:19:42,220 Dalam kes ini, apa yang mungkin berlaku? 421 00:19:42,220 --> 00:19:45,577 Saya membuka buku telefon dan, bam, ada beberapa Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Saya boleh memanggilnya segera. 423 00:19:46,660 --> 00:19:49,390 >> Mengambil satu langkah, mungkin dua langkah, tetapi beberapa langkah-langkah berterusan 424 00:19:49,390 --> 00:19:50,230 jika saya bernasib baik. 425 00:19:50,230 --> 00:19:52,570 Dan terus-terang, kita lihat pada Isnin rakan sekelas anda 426 00:19:52,570 --> 00:19:54,710 mendapatkan cukup bertuah dua kali berturut-turut. 427 00:19:54,710 --> 00:19:57,050 Dan itu sememangnya berterusan masa dalam batas yang lebih rendah 428 00:19:57,050 --> 00:20:01,280 algoritma yang berkenaan untuk mencari bilangan 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 diketepikan, jika anda menemui bahawa kedua-dua O besar, had atas, 431 00:20:06,400 --> 00:20:09,310 dan omega, lebih rendah terikat, adalah satu dalam yang sama, yang 432 00:20:09,310 --> 00:20:11,830 adalah formula yang sama dalam kurungan, anda juga boleh 433 00:20:11,830 --> 00:20:15,170 berkata, hanya untuk mewah, sesuatu yang di theta 434 00:20:15,170 --> 00:20:18,270 n atau theta beberapa nilai lain. 435 00:20:18,270 --> 00:20:20,661 Yang hanya bermakna apabila besar O dan omega adalah sama. 436 00:20:20,661 --> 00:20:21,910 Sekarang bagaimana pula jenis pemilihan? 437 00:20:21,910 --> 00:20:23,400 Mari kita gunakan perbendaharaan kata baru ini. 438 00:20:23,400 --> 00:20:27,407 Dalam jenis pemilihan, apakah kita melakukan sekali lagi, dan sekali lagi, dan sekali lagi? 439 00:20:27,407 --> 00:20:29,990 Saya akan berulang-alik melalui senarai, mencari siapa? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Bilangan yang paling kecil. 442 00:20:34,730 --> 00:20:37,560 >> Jadi berapa banyak langkah-langkah, bagaimana perbandingan banyak yang saya lakukan 443 00:20:37,560 --> 00:20:43,250 perlu membuat untuk memikirkan yang unsur yang paling kecil dalam senarai itu? 444 00:20:43,250 --> 00:20:44,437 n tolak 1, bukan? 445 00:20:44,437 --> 00:20:47,770 Kerana jika saya hanya bermula dengan satu yang saya diberikan dan saya mula membandingkan dia atau dia, 446 00:20:47,770 --> 00:20:49,519 kemudian dia atau dia, dia atau dia, dia atau dia, saya 447 00:20:49,519 --> 00:20:52,010 hanya boleh berpasangan elemen bersama-sama n tolak 1 kali. 448 00:20:52,010 --> 00:20:55,630 Jadi pemilihan jenis juga mengambil n tolak 1 langkah pertama kali. 449 00:20:55,630 --> 00:20:59,540 >> Berapa banyak langkah-langkah yang diperlukan saya untuk mendapati elemen kedua paling kecil? 450 00:20:59,540 --> 00:21:02,920 n tolak 2, kerana saya keadaan terpinga jika saya terus mencari orang yang sama 451 00:21:02,920 --> 00:21:06,280 sekali lagi jika saya telah dipilih beliau atau beliau dan meletakkan mereka di tempat mereka. 452 00:21:06,280 --> 00:21:09,270 Dan langkah yang ketiga, n tolak 3, maka n tolak 4. 453 00:21:09,270 --> 00:21:11,020 Kita lihat corak ini sebelum ini, dan sesungguhnya 454 00:21:11,020 --> 00:21:13,460 pemilihan jenis juga mempunyai had atas 455 00:21:13,460 --> 00:21:16,210 n kuasa dua jika kita lakukan sehingga penjumlahan itu. 456 00:21:16,210 --> 00:21:19,790 Apakah batasan bawah, pemilihan jenis ini? 457 00:21:19,790 --> 00:21:25,350 Minimum, berapa banyak masa kemestian pemilihan semacam mengambil, seperti yang kita ditakrifkan ia pada hari Isnin? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Mencadangkan dua pilihan. 460 00:21:30,490 --> 00:21:32,360 Mungkin ia n, seperti sebelum ini. 461 00:21:32,360 --> 00:21:35,040 Mungkin ia n kuasa dua, kerana ia kini sebagai had atas. 462 00:21:35,040 --> 00:21:35,874 >> PENONTON: n kuasa dua. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n kuasa dua. 464 00:21:36,664 --> 00:21:37,368 Mengapa? 465 00:21:37,368 --> 00:21:40,060 >> PENONTON: Oleh kerana anda mempunyai untuk menentukan [didengar]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Tepat sekali. 467 00:21:41,510 --> 00:21:45,077 Sekurang-kurangnya seperti yang saya ditakrifkan jenis pilihan ia agak naif, terus pergi, 468 00:21:45,077 --> 00:21:46,160 mencari elemen yang paling kecil. 469 00:21:46,160 --> 00:21:47,770 Pergi lagi, cari elemen yang paling kecil. 470 00:21:47,770 --> 00:21:49,490 Pergi lagi, cari elemen yang paling kecil. 471 00:21:49,490 --> 00:21:51,700 Tidak ada jenis pengoptimuman di sana yang 472 00:21:51,700 --> 00:21:54,350 mungkin saya akan membatalkan selepas hanya n atau lebih langkah. 473 00:21:54,350 --> 00:21:57,080 Jadi sesungguhnya, pemilihan jenis, omega n kuasa dua. 474 00:21:57,080 --> 00:22:00,667 >> Bagaimana pula dengan jenis sisipan, di mana saya telah mengambil yang saya telah diberikan, dan kemudian saya plopped dia 475 00:22:00,667 --> 00:22:01,750 atau dia di tempat yang betul? 476 00:22:01,750 --> 00:22:04,958 Kemudian saya berjalan kepada orang yang kedua, plopped dia atau dia di tempat yang betul. 477 00:22:04,958 --> 00:22:07,910 Kemudian orang yang seterusnya, plopped dia atau dia di tempat yang betul. 478 00:22:07,910 --> 00:22:10,537 Perhatikan bahawa ini adalah sangat linear, jadi untuk bercakap. 479 00:22:10,537 --> 00:22:12,620 Saya garis lurus, saya tidak akan berulang-alik, 480 00:22:12,620 --> 00:22:16,080 Saya tidak pernah benar-benar melihat ke belakang, tetapi apa yang berlaku apabila saya memasukkan dia 481 00:22:16,080 --> 00:22:20,302 atau dia ke permulaan senarai seperti yang kita lakukan pada hari Isnin? 482 00:22:20,302 --> 00:22:21,010 Apa yang berlaku? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 PENONTON: [didengar]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Ya, yang adalah tangkapan, bukan? 486 00:22:24,830 --> 00:22:26,746 Anda mungkin ingat dari rakan sekelas anda, jika mereka 487 00:22:26,746 --> 00:22:29,670 telah membuat apa-apa pergerakan dengan kaki mereka, itu adalah pembedahan. 488 00:22:29,670 --> 00:22:33,610 Jadi, jika ada tiga orang di sini dan orang yang baru milik cara di sana, 489 00:22:33,610 --> 00:22:37,360 di atas pentas yang panjang seperti ini, pasti, dia atau dia hanya boleh pergi ke akhir sangat. 490 00:22:37,360 --> 00:22:40,074 Tetapi jika kita berfikir tentang yang komputer dan pelbagai memori, 491 00:22:40,074 --> 00:22:41,990 orang-orang ini akan terpaksa shuffle lebih 492 00:22:41,990 --> 00:22:43,260 untuk memberi ruang kepada orang itu. 493 00:22:43,260 --> 00:22:46,930 Dan supaya n tolak 1 shufflings, n tolak 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 tolak 3 shufflings adalah hanya jenis berlaku di belakang saya, tidak di depan saya 495 00:22:50,660 --> 00:22:52,710 seperti sebelum ini, dalam erti kata lain. 499 00:22:52,557 --> 00:22:54,640 Sekarang sebagai diketepikan, dan sebagai anda mungkin telah melihat dalam talian 500 00:22:54,640 --> 00:22:57,699 jika anda mula poking sekitar kira-kira macam, ada begitu banyak yang berbeza 501 00:22:57,699 --> 00:22:59,490 di luar sana, sebahagian daripada mereka lebih baik daripada yang lain. 502 00:22:59,490 --> 00:23:02,200 Sesungguhnya, bogosort adalah satu itulah jenis menyeronokkan untuk melihat. 503 00:23:02,200 --> 00:23:06,650 Bogosort mengambil satu set nombor atau mengatakan dek kad, 504 00:23:06,650 --> 00:23:09,870 secara rawak Shuffle mereka, dan cek jika mereka disusun. 505 00:23:09,870 --> 00:23:12,130 Dan jika tidak, adakah sekali lagi. 506 00:23:12,130 --> 00:23:14,140 Dan jika tidak, adakah sekali lagi. 507 00:23:14,140 --> 00:23:15,440 Jika tidak, adakah sekali lagi. 508 00:23:15,440 --> 00:23:17,060 Sangat bodoh. 509 00:23:17,060 --> 00:23:19,520 >> Dan sesungguhnya, jika anda membaca seperti artikel Wikipedia, 510 00:23:19,520 --> 00:23:21,200 nama samaran adalah jenis bodoh. 511 00:23:21,200 --> 00:23:25,180 Ia akhirnya akan bekerja, mudah-mudahan, diberi masa yang cukup, 512 00:23:25,180 --> 00:23:28,240 tetapi jumlah masa boleh mengambil beberapa waktu. 513 00:23:28,240 --> 00:23:31,650 Jadi, jika saya boleh, mari kita perkara-perkara kelajuan dari contoh Mary Beth sebelum ini, 514 00:23:31,650 --> 00:23:35,150 dengan mempunyai lebih beberapa elemen, tetapi dua lagi pemproses. 515 00:23:35,150 --> 00:23:37,100 Dua orang, jika anda tidak keberatan menyertai saya. 516 00:23:37,100 --> 00:23:40,972 Bagaimana kira-kira 1 di sini, dan mari go-- tidak ada di sana? 517 00:23:40,972 --> 00:23:41,722 Tiada siapa 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 ke bawah. 520 00:23:44,190 --> 00:23:45,000 Baiklah, apa nama anda? 521 00:23:45,000 --> 00:23:45,720 >> PENONTON: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Apakah itu? 523 00:23:46,100 --> 00:23:46,766 >> PENONTON: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, baik untuk bertemu dengan kamu. 525 00:23:49,450 --> 00:23:53,670 Baiklah, kita mempunyai Peter di sini, jika anda mahu datang ke meja di sini. 526 00:23:53,670 --> 00:23:54,550 Dan apa nama anda? 527 00:23:54,550 --> 00:23:55,216 >> PENONTON: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, baik untuk bertemu dengan kamu. 530 00:23:57,030 --> 00:23:58,060 Elena memenuhi Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Dan kita perlu Andrew di sini juga, sila. 533 00:24:02,290 --> 00:24:06,107 Dan cabaran anda akan menjadi untuk menyusun dek kad. 534 00:24:06,107 --> 00:24:08,190 Dan jika tidak biasa, dek kad perlu akhirnya 535 00:24:08,190 --> 00:24:11,064 diselesaikan sesuatu yang kecil seperti ini di mana kami akan buat kelab-kelab, maka 536 00:24:11,064 --> 00:24:13,660 yang penyodok, maka hati dan berlian, dari ace sebagai satu, 537 00:24:13,660 --> 00:24:15,570 sepanjang jalan sehingga kepada raja. 538 00:24:15,570 --> 00:24:20,890 >> Kad saya akan memberikan anda akan menjadi 52 dalam kuantiti. 539 00:24:20,890 --> 00:24:23,160 Kami akan juga masa anda, dalam hanya seketika. 540 00:24:23,160 --> 00:24:26,410 Kami akan membuang Andrew pada skrin di sini, 541 00:24:26,410 --> 00:24:28,170 untuk menonton seperti yang anda lakukan ini. 542 00:24:28,170 --> 00:24:31,070 Dan supaya semua ini adalah lebih ketara, 543 00:24:31,070 --> 00:24:33,490 ini adalah kad saya di Amazon. 544 00:24:33,490 --> 00:24:42,861 Jadi mereka sudah secara rawak disusun, dan kita akan ke semasa anda. 545 00:24:42,861 --> 00:24:44,610 Dan kita akan menyimpan ia sebenar masa ini, 546 00:24:44,610 --> 00:24:47,820 jadi kita akan cuba untuk memberi tekanan kepada anda kerana jika tidak, ini akan mendapat membosankan 547 00:24:47,820 --> 00:24:48,460 dengan cepat. 548 00:24:48,460 --> 00:24:53,860 Jika anda boleh meneruskan untuk menyusun 52 unsur-unsur 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 sekali lagi, seperti yang kita menonton ini lelaki melakukan apa yang, pada akhirnya 551 00:25:07,180 --> 00:25:10,200 akan menghasilkan jelas hasil, benar-benar berfikir tentang 552 00:25:10,200 --> 00:25:12,962 bagaimana ia setiap melakukannya, bagaimana anda boleh menggambarkannya. 553 00:25:12,962 --> 00:25:15,045 Kerana 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 Tetapi anda mungkin lama mempunyai gerak hati, lama sebelum anda 556 00:25:22,349 --> 00:25:24,390 berfikir tentang mengambil sains komputer kelas anda 557 00:25:24,390 --> 00:25:27,223 mungkin mempunyai gerak hati yang dengan untuk menyelesaikan masalah seperti ini. 558 00:25:27,223 --> 00:25:29,560 Tetapi sebaik sahaja anda menyedari corak dan mula 559 00:25:29,560 --> 00:25:32,407 untuk merasmikan dengan langkah-langkah yang anda menyelesaikan masalah-masalah ini, 560 00:25:32,407 --> 00:25:35,490 anda akan mendapati bahawa anda boleh menyelesaikan banyak lebih menarik dan 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 sekurang-kurangnya satu elemen algoritma 563 00:25:42,351 --> 00:25:43,350 bahawa mereka menggunakan di sini? 564 00:25:43,350 --> 00:25:44,275 >> PENONTON: [didengar] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Apakah itu? 566 00:25:45,150 --> 00:25:47,062 PENONTON: Dengan saman. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Dengan saman. 568 00:25:47,770 --> 00:25:50,630 Oleh itu mereka berkelompok semua berlian bersama-sama 569 00:25:50,630 --> 00:25:52,560 ia seolah-olah, semua hati bersama-sama ia seolah-olah, 570 00:25:52,560 --> 00:25:56,520 dan sebagainya, tanpa berkenaan untuk nombor tersebut pada kad. 571 00:25:56,520 --> 00:26:00,900 Dan kini terdapat, misalnya, untuk menyusun mereka dengan nombor. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Sangat baik. 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 Apabila kita mempunyai empat saman disusun, apa kita perlu lakukan untuk empat buasir 576 00:26:16,950 --> 00:26:20,059 untuk mencapai satu dek disusun, cukup hanya? 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 idea menarik yang sekali lagi, berani mengatakan, adalah sangat intuitif walaupun 579 00:26:25,160 --> 00:26:28,140 jika anda mungkin tidak pernah menampar yang jenis label di atasnya. 580 00:26:28,140 --> 00:26:31,900 Ini tanggapan asas membahagikan masalah itu tidak pada separuh masa ini, 581 00:26:31,900 --> 00:26:33,410 tetapi sekurang-kurangnya kepada empat keping. 582 00:26:33,410 --> 00:26:36,810 Menyelesaikan cukup banyak masalah asas yang sama 583 00:26:36,810 --> 00:26:40,480 secara berasingan daripada satu sama lain, dan kemudian menggabungkan keputusan. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Dan, yang sangat baik, dilakukan. 586 00:26:50,140 --> 00:26:52,140 Baiklah, satu pusingan besar tepukan, jika kita boleh. 587 00:26:52,140 --> 00:26:56,480 >> [Tepuk tangan] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Saya tidak tahu apa yang anda akan lakukan dengan ini, tetapi 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 minit dan lapan saat, 591 00:27:04,660 --> 00:27:07,490 jika anda ingin mencabar rakan-rakan anda. 592 00:27:07,490 --> 00:27:12,160 Apa yang kemudian akan menjadi mengambil dari ini 593 00:27:12,160 --> 00:27:13,830 kita dapat memanfaatkan secara umum? 594 00:27:13,830 --> 00:27:16,080 Nah, berfikir kembali ke array ini nombor, 595 00:27:16,080 --> 00:27:19,060 dan berfikir kembali sekarang untuk beberapa pseudokod kita telah menulis pada masa lalu, 596 00:27:19,060 --> 00:27:22,080 dan ini adalah pseudokod untuk menyelesaikan masalah buku telefon. 597 00:27:22,080 --> 00:27:25,150 Manakala dalam pseudokod saya yang disebut satu persatu cara yang lebih teratur 598 00:27:25,150 --> 00:27:28,400 menggambarkan bagaimana saya lakukan yang sangat intuitif algoritma manusia membahagikan telefon 599 00:27:28,400 --> 00:27:31,650 buku pada separuh, ulang, ulang, ulang, sehingga saya mencari seseorang seperti Mike Smith, 600 00:27:31,650 --> 00:27:33,790 jika dia memang di dalam buku telefon. 601 00:27:33,790 --> 00:27:37,610 >> Tetapi saya jenis yang digunakan apa yang saya akan panggil pendekatan yang sangat lelaran di sini, 602 00:27:37,610 --> 00:27:42,160 dalam notis tertentu talian 8 dan talian 11. 603 00:27:42,160 --> 00:27:46,750 Mereka adalah bukti satu lelaran pendekatan, pendekatan gegelung, 604 00:27:46,750 --> 00:27:49,040 kerana itulah tingkahlaku yang mendorong. 605 00:27:49,040 --> 00:27:52,910 Mereka kedua-dua garisan mengatakan pergi ke jenis garis tiga, dan anda boleh dalam 606 00:27:52,910 --> 00:27:55,140 memikirkan bahawa anda mata minda sebagai gelung. 607 00:27:55,140 --> 00:27:59,080 Ia memberitahu anda untuk naik semula ke langkah tiga dan ulangi, sekali lagi, dan sekali lagi, 608 00:27:59,080 --> 00:28:00,010 dan lagi. 609 00:28:00,010 --> 00:28:04,410 >> Tetapi bagaimana jika kita memanfaatkan idea utama di sini bahawa yang kita lakukan bukan kali terakhir, 610 00:28:04,410 --> 00:28:10,280 dan memudahkan talian 8 dan talian 11 dan jiran-jiran mereka 611 00:28:10,280 --> 00:28:12,840 sebagai hanya ini, dalam kuning. 612 00:28:12,840 --> 00:28:16,480 Ia tidak asasnya memendekkan pseudokod yang sangat banyak, 613 00:28:16,480 --> 00:28:20,530 tetapi ia asasnya mengubah sifat algoritma saya. 614 00:28:20,530 --> 00:28:24,220 Apa yang saya kini mengatakan dalam langkah 7, dalam langkah 10, 615 00:28:24,220 --> 00:28:29,140 adalah untuk mencari Mike dengan cara yang sama yang tepat, 616 00:28:29,140 --> 00:28:31,580 tetapi hanya di sebelah kiri setengah atau separuh betul. 617 00:28:31,580 --> 00:28:33,420 >> Jadi dalam erti kata lain, jika Saya bermula dari langkah satu, 618 00:28:33,420 --> 00:28:36,150 mengambil buku telefon, terbuka ke tengah buku telefon, lihat pada nama, 619 00:28:36,150 --> 00:28:39,010 jika Smith adalah antara nama ini, hubungi Mike, lain 620 00:28:39,010 --> 00:28:44,340 jika Smith lebih awal di dalam buku, melangkah tujuh mencari Mike pada separuh kiri buku. 621 00:28:44,340 --> 00:28:47,130 Tetapi itu jenis berasa seperti ia meninggalkan saya tergantung, bukan? 622 00:28:47,130 --> 00:28:49,240 Kuning, adalah arahan, tetapi bagaimana saya 623 00:28:49,240 --> 00:28:51,870 mencari Mike di sebelah kiri separuh daripada buku telefon? 624 00:28:51,870 --> 00:28:54,210 Di mana saya mempunyai algoritma yang aku 625 00:28:54,210 --> 00:28:57,100 boleh mencari seseorang seperti Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Nah, ia merenung kita di muka. 627 00:28:58,980 --> 00:29:03,090 Saya benar-benar boleh menggunakan sama program berkesan naik ke atas 628 00:29:03,090 --> 00:29:06,490 lagi dan berlari semula garis yang sama kod. 629 00:29:06,490 --> 00:29:10,610 >> Jadi walaupun ini harus berasa seperti sedikit definisi kitaran 630 00:29:10,610 --> 00:29:13,480 mana anda hendak pergi menjawab seseorang adalah soalan dengan hanya jenis bertanya 631 00:29:13,480 --> 00:29:15,990 soalan yang sama sekali lagi, seperti mengapa, mengapa, mengapa? 632 00:29:15,990 --> 00:29:21,580 Realitinya adalah kerana kita telah keras dikodkan beberapa garis khas, langkah 4, 633 00:29:21,580 --> 00:29:25,320 yang jika, dan langkah 12, yang adalah berkesan cawangan yang lain, 634 00:29:25,320 --> 00:29:30,120 kerana kita mempunyai langkah-langkah pengganti sementara, algoritma ini akan ditamatkan jika kita 635 00:29:30,120 --> 00:29:32,050 mencari Mike, atau jika kita tidak. 636 00:29:32,050 --> 00:29:36,810 Tetapi dalam langkah 7 dan 10 sekarang, kita mempunyai apa yang kita akan memanggil algoritma rekursif. 637 00:29:36,810 --> 00:29:40,420 Dan rekursi memang idea yang kuat itulah fikiran sedikit lenturan pada mulanya, 638 00:29:40,420 --> 00:29:42,500 bahawa kita kini boleh memohon seperti berikut. 639 00:29:42,500 --> 00:29:46,600 >> Bergabung jenis akan jenis yang lepas bahawa kita melihat, sekurang-kurangnya di dalam kelas secara formal. 640 00:29:46,600 --> 00:29:50,040 Dan ia berbeza dari tiga lepas, dan sudah tentu 641 00:29:50,040 --> 00:29:52,140 separuh akhir jika kita termasuk bogosort. 642 00:29:52,140 --> 00:29:54,810 Berikut adalah pseudokod untuk jenis merge. 643 00:29:54,810 --> 00:30:00,170 Apabila input n elemen, jadi diberikan pelbagai saiz n, jika n adalah kurang daripada 2, 644 00:30:00,170 --> 00:30:01,040 kembali. 645 00:30:01,040 --> 00:30:03,610 Jadi mengapa perlu saya bahawa kewarasan cek pertama? 646 00:30:03,610 --> 00:30:09,477 Apakah implikasi sekiranya saya menyerahkan anda pelbagai yang panjang n adalah kurang daripada 2? 647 00:30:09,477 --> 00:30:11,060 Ia telah pun disusun, jelas, bukan? 648 00:30:11,060 --> 00:30:13,640 Oleh kerana senarai itu sama ada mempunyai satu elemen yang trivially 649 00:30:13,640 --> 00:30:15,180 disusun kerana ia satu-satunya perkara di sana. 650 00:30:15,180 --> 00:30:18,138 Atau, ia saiz sifar yang bermaksud tiada apa-apa untuk menyelesaikan, jadi secara semula jadi 651 00:30:18,138 --> 00:30:18,720 ia disusun. 652 00:30:18,720 --> 00:30:20,410 Hanya ada apa yang salah di sana. 653 00:30:20,410 --> 00:30:22,310 Supaya kes asas kami kononnya. 654 00:30:22,310 --> 00:30:24,440 >> Yang sama dalam semangat dengan apa yang kita lakukan dengan Mike. 655 00:30:24,440 --> 00:30:26,023 Jika Mike dalam buku telefon, memanggil dia. 656 00:30:26,023 --> 00:30:27,740 Jika dia tidak ada, menyerah. 657 00:30:27,740 --> 00:30:31,240 Ia satu kes asas yang dipanggil, 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 >> Tetapi di sini yang lompatan iman sekarang, lain, menyusun separuh kiri unsur-unsur, 660 00:30:37,890 --> 00:30:39,740 kemudian menyusun kanan separuh daripada unsur-unsur, 661 00:30:39,740 --> 00:30:41,189 dan kemudian menggabungkan bahagian disusun. 662 00:30:41,189 --> 00:30:43,230 Dan di sini di mana ia berasa seperti kita copping keluar. 663 00:30:43,230 --> 00:30:46,900 Saya meminta anda untuk menyusun n unsur-unsur, dan saya 664 00:30:46,900 --> 00:30:50,712 berkata, OK, adakah ia oleh sorting ke kiri dan sorting kanan. 665 00:30:50,712 --> 00:30:52,420 Tetapi saya katakan satu benda lain, dan ini 666 00:30:52,420 --> 00:30:55,530 adalah tema utama ia seolah-olah dalam gerak hati ini setakat ini, 667 00:30:55,530 --> 00:30:57,380 ada ini langkah ketiga bergabung. 668 00:30:57,380 --> 00:31:00,430 Yang walaupun ia seolah-olah jadi bisu dalam roh, 669 00:31:00,430 --> 00:31:02,320 seperti hanya bergabung perkara bersama-sama, ia seolah-olah 670 00:31:02,320 --> 00:31:05,380 menjadi satu langkah utama ke arah Pemasangan semula dua masalah yang 671 00:31:05,380 --> 00:31:07,330 dibahagikan akhirnya pada separuh. 672 00:31:07,330 --> 00:31:12,090 >> Jadi bergabung jenis, mari kita melakukan ini, jika anda akan jenaka saya, dengan satu demonstrasi lanjut, 673 00:31:12,090 --> 00:31:14,730 hanya supaya kita mempunyai beberapa nombor untuk bekerja dengan. 674 00:31:14,730 --> 00:31:19,470 Bolehkah saya menukar lapan tekanan bola selama lapan orang? 675 00:31:19,470 --> 00:31:29,320 Baiklah, bagaimana pula anda tiga, anda empat dalam seksyen ini, lima, enam, dan mari kita 676 00:31:29,320 --> 00:31:30,720 yang 7, 8, datang ke atas. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, yeah OK. 679 00:31:36,520 --> 00:31:38,640 Tolak 8, ada kita pergi, campur 1. 680 00:31:38,640 --> 00:31:39,150 Cemerlang. 681 00:31:39,150 --> 00:31:42,000 Semua datang betul-betul di atas, mari kita cepat memberikan anda nombor. 682 00:31:42,000 --> 00:31:50,800 Nombor dua, nombor tiga, nombor empat, nombor lima, enam, tujuh dan lapan. 683 00:31:50,800 --> 00:31:52,140 Saya lapan dengan betul kali ini. 684 00:31:52,140 --> 00:31:56,390 >> OK, jadi teruskan jika anda boleh, dan mari menyusun dalam perintah asal 685 00:31:56,390 --> 00:31:59,810 bahawa kita mempunyai semalam yang kelihatan seperti ini, jika anda tidak keberatan. 686 00:31:59,810 --> 00:32:03,620 Dan mari kita melakukannya di hadapan meja. 687 00:32:03,620 --> 00:32:06,510 Baiklah, jadi bergabung jenis. 688 00:32:06,510 --> 00:32:08,820 Ini adalah di mana ia akan untuk mendapatkan jenis yang menarik, 689 00:32:08,820 --> 00:32:12,800 kerana saya seolah-olah memberi diri saya begitu banyak maklumat hari ini kurang. 690 00:32:12,800 --> 00:32:15,149 >> Jadi bergabung jenis pertama sekali input n unsur, 691 00:32:15,149 --> 00:32:18,440 dan jelas tidak kurang daripada dua orang, ia lapan, jadi saya mempunyai beberapa kerja lagi yang perlu dilakukan. 692 00:32:18,440 --> 00:32:21,140 Jadi sekarang mental kita sebagai sebuah kelas kini di cawangan lain yang, 693 00:32:21,140 --> 00:32:22,540 yang bermaksud tiga langkah. 694 00:32:22,540 --> 00:32:25,017 Pertama, saya perlu menyusun separuh kiri unsur-unsur. 695 00:32:25,017 --> 00:32:26,350 Jadi bagaimana Aku tidak melakukan ini? 696 00:32:26,350 --> 00:32:28,950 Well, saya akan jenis mental membahagikan senarai di sini, 697 00:32:28,950 --> 00:32:30,700 anda tidak perlu fizikal bergerak, dan saya 698 00:32:30,700 --> 00:32:33,180 akan memberi tumpuan hanya pada separuh kiri unsur-unsur di sini. 699 00:32:33,180 --> 00:32:36,770 Jadi bagaimana saya pergi tentang sorting senarai kini saiz empat? 700 00:32:36,770 --> 00:32:38,730 Apa algoritma saya? 701 00:32:38,730 --> 00:32:42,580 Pertama saya menyemak adalah n kurang daripada dua, tidak, jadi saya pergi ke blok lain lagi. 702 00:32:42,580 --> 00:32:43,900 Susun meninggalkan separuh daripada unsur-unsur. 703 00:32:43,900 --> 00:32:45,608 >> Jadi sekarang lagi, mental, dan di sinilah 704 00:32:45,608 --> 00:32:49,550 anda perlu terakru banyak Sejarah mental, jika anda akan. 705 00:32:49,550 --> 00:32:51,940 Kini saya sorting kiri separuh daripada separuh kiri. 706 00:32:51,940 --> 00:32:57,000 Baiklah, jadi sekarang saya menyeru merge sama saya sorting algoritma, n adalah kurang daripada dua? 707 00:32:57,000 --> 00:33:00,590 Tidak, ia adalah dua, jadi saya perlu menyusun separuh di sebelah kiri, dan separuh yang betul. 708 00:33:00,590 --> 00:33:02,042 Jadi di sini kita pergi, menyusun separuh kiri. 709 00:33:02,042 --> 00:33:03,750 Mengapa tidak anda hanya mengambil satu langkah ke hadapan. 710 00:33:03,750 --> 00:33:04,415 Apa nama anda? 711 00:33:04,415 --> 00:33:04,860 >> PENONTON: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan telah melangkah ke hadapan. 714 00:33:06,040 --> 00:33:06,748 >> PENONTON: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, dilakukan. 716 00:33:09,000 --> 00:33:10,090 Adakah anda berkata atau Darren Dan? 717 00:33:10,090 --> 00:33:10,550 >> PENONTON: 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 ke hadapan dan dia kini disusun. 720 00:33:14,422 --> 00:33:16,130 Dan ini adalah hampir satu tuntutan bodoh, bukan? 721 00:33:16,130 --> 00:33:18,862 Saya tidak benar-benar seolah-olah mencapai apa-apa, tetapi mari kita teruskan. 722 00:33:18,862 --> 00:33:20,820 Sekarang, saya akan menyusun kanan separuh daripada unsur-unsur. 723 00:33:20,820 --> 00:33:21,200 Apa nama anda? 724 00:33:21,200 --> 00:33:21,690 >> PENONTON: Lukas. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Lukas. 726 00:33:22,273 --> 00:33:23,400 Ayuh, melangkah ke hadapan. 727 00:33:23,400 --> 00:33:25,640 Selesai, saya telah disusun Lukas. 728 00:33:25,640 --> 00:33:28,570 Separuh kiri kini disusun dan separuh yang betul kini disusun, 729 00:33:28,570 --> 00:33:30,770 tetapi sekali lagi, ada satu langkah yang penting di sini. 730 00:33:30,770 --> 00:33:32,940 Apa yang saya akan datang perlu lakukan? 731 00:33:32,940 --> 00:33:33,941 Menggabungkan bahagian disusun. 732 00:33:33,941 --> 00:33:36,648 Sekarang kita akan hanya perlu semua orang berulang-alik dengan cara ini, 733 00:33:36,648 --> 00:33:38,620 kerana saya jenis perlu beberapa ruang kosong. 734 00:33:38,620 --> 00:33:40,411 Ia hampir seperti ini lelaki adalah di atas meja, 735 00:33:40,411 --> 00:33:42,460 dan saya memerlukan bilik untuk memindahkan mereka sekitar di. 736 00:33:42,460 --> 00:33:44,170 Jadi saya akan bergabung kalian dengan melihat 737 00:33:44,170 --> 00:33:45,960 pada separuh kiri dan separuh yang betul. 738 00:33:45,960 --> 00:33:48,740 Dan yang jelas datang pertama, separuh kiri atau separuh betul? 739 00:33:48,740 --> 00:33:52,710 Jadi separuh betul, jadi mari kita bergerak Lukas lebih di sini untuk kedudukan asal Darren. 740 00:33:52,710 --> 00:33:57,640 Dan sekarang untuk bergabung separuh kiri mereka dalam, Darren yang sedang bergerak di sana. 741 00:33:57,640 --> 00:33:59,750 >> Jadi rasanya hampir kesan semacam gelembung, 742 00:33:59,750 --> 00:34:02,482 tetapi algoritma asas saya, sangat berbeza kali ini. 743 00:34:02,482 --> 00:34:04,815 Tetapi sekarang di mana perkara mendapatkan sedikit menjengkelkan kerana anda 744 00:34:04,815 --> 00:34:06,810 perlu putar balik mental di mana saya meninggalkan off. 745 00:34:06,810 --> 00:34:09,893 Saya baru sahaja bergabung di bahagian disusun, yang bermaksud saya di mana dalam algoritma saya? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Saya perlu menyusun separuh yang betul, bukan? 748 00:34:13,770 --> 00:34:15,910 >> Jika anda memutar balik, secara literal pada video, anda akan 749 00:34:15,910 --> 00:34:18,339 melihat bahawa kita mendapat ini titik Luke dan Darren 750 00:34:18,339 --> 00:34:21,370 oleh sorting kiri separuh daripada separuh kiri. 751 00:34:21,370 --> 00:34:23,430 Kemudian kami bergabung mereka bahagian disusun, yang 752 00:34:23,430 --> 00:34:27,941 bermakna langkah seterusnya adalah jenis yang bahagian kanan separuh kiri. 753 00:34:27,941 --> 00:34:29,649 Baiklah, jadi mari kita melakukan ini dengan lebih cepat. 754 00:34:29,649 --> 00:34:33,282 Baiklah, enam, saya akan menuntut anda kini disusun, datang ke hadapan. 755 00:34:33,282 --> 00:34:33,990 Apa nama anda? 756 00:34:33,990 --> 00:34:34,589 >> PENONTON: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano kini disusun. 759 00:34:36,010 --> 00:34:36,450 Dan apa nama anda? 760 00:34:36,450 --> 00:34:37,080 >> PENONTON: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex kini disusun. 762 00:34:38,379 --> 00:34:40,750 Separuh kiri, separuh betul, apa langkah terakhir? 763 00:34:40,750 --> 00:34:41,250 Bergabung. 764 00:34:41,250 --> 00:34:44,310 Pretty remeh, jadi saya akan bergabung dalam enam, 765 00:34:44,310 --> 00:34:46,930 mengambil langkah ke belakang, lapan, mengambil langkah ke belakang. 766 00:34:46,930 --> 00:34:49,530 Dan kini notis ini yang bisa dibesarkan berguna, apa yang 767 00:34:49,530 --> 00:34:53,930 kini benar tentang separuh kiri senarai, tidak kira bagaimana kita bermula? 768 00:34:53,930 --> 00:34:55,090 Ia disusun. 769 00:34:55,090 --> 00:34:57,750 >> Sekarang ia tidak disusun dalam skim besar perkara, 770 00:34:57,750 --> 00:35:00,250 tetapi ia disusun secara bebas daripada separuh yang lain. 771 00:35:00,250 --> 00:35:04,100 Sekarang apa langkah aku di jika saya terus gulung semula bagaimana kisah itu bermula? 772 00:35:04,100 --> 00:35:05,680 Sekarang saya perlu menyusun separuh betul. 773 00:35:05,680 --> 00:35:07,630 Jadi sekarang kita kembali pada cara permulaan cerita, 774 00:35:07,630 --> 00:35:08,921 dan mari kita melakukan ini dengan lebih cepat. 775 00:35:08,921 --> 00:35:11,320 Jadi saya akan menyusun bahagian kanan seluruh senarai. 776 00:35:11,320 --> 00:35:13,060 Apa langkah seterusnya? 777 00:35:13,060 --> 00:35:15,840 Menyusun separuh kiri separuh betul. 778 00:35:15,840 --> 00:35:18,715 Menyusun separuh kiri yang separuh kiri separuh betul. 779 00:35:18,715 --> 00:35:19,590 Dan apa nama anda? 780 00:35:19,590 --> 00:35:20,230 >> PENONTON: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, melangkah ke hadapan, dilakukan. 782 00:35:21,970 --> 00:35:22,860 Separuh kiri adalah disusun. 783 00:35:22,860 --> 00:35:23,330 Dan apa nama anda? 784 00:35:23,330 --> 00:35:23,820 >> PENONTON: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, mengambil langkah yang ke hadapan, anda kini disusun. 786 00:35:25,620 --> 00:35:27,010 Apakah langkah penting sekarang? 787 00:35:27,010 --> 00:35:27,510 Bergabung. 788 00:35:27,510 --> 00:35:30,509 Jadi siapa yang akan bergabung menjadi tempat di sini, jika anda boleh mengambil langkah ke belakang, 789 00:35:30,509 --> 00:35:32,930 dan tiga akan mengambil langkah ke belakang, bergabung. 790 00:35:32,930 --> 00:35:38,080 Jadi separuh kiri bahagian kanan, kini disusun. 791 00:35:38,080 --> 00:35:41,747 Terus terang, algoritma ini berasa seperti kita cara membuang lebih banyak masa berbanding sebelum ini, 792 00:35:41,747 --> 00:35:44,830 tetapi jika kita melakukan ini dalam masa sebenar, kita akan melihat apa yang bawa pulang akan menjadi. 793 00:35:44,830 --> 00:35:47,970 Sekarang di sini saya, betul separuh daripada separuh yang betul, 794 00:35:47,970 --> 00:35:50,170 biarlah saya pergi ke hadapan dan menyusun separuh kiri. 795 00:35:50,170 --> 00:35:51,482 Melangkah ke hadapan, apa nama anda? 796 00:35:51,482 --> 00:35:52,190 PENONTON: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey kini disusun. 798 00:35:53,210 --> 00:35:53,570 Apa nama anda? 799 00:35:53,570 --> 00:35:54,200 >> PENONTON: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina kini disusun sebagai juga, jika anda mengambil satu langkah ke hadapan. 801 00:35:57,033 --> 00:36:00,690 Langkah utama di sini kini bergabung, saya akan memetik dari dua senarai 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 akan datang. 804 00:36:05,150 --> 00:36:06,410 Dan sekali lagi, ini adalah disengajakan. 805 00:36:06,410 --> 00:36:08,535 Hakikat bahawa mereka mengambil langkah ke hadapan dan belakang 806 00:36:08,535 --> 00:36:12,997 bertujuan untuk menyatakan bahawa kita tidak boleh melakukan algoritma ini di tempat yang mudah 807 00:36:12,997 --> 00:36:15,830 sebagai semacam gelembung, dan jenis pemilihan, dan jenis sisipan di mana kita hanya 808 00:36:15,830 --> 00:36:16,960 disimpan pertukaran orang. 809 00:36:16,960 --> 00:36:19,940 Saya benar-benar memerlukan satu jenis kertas gores di mana 810 00:36:19,940 --> 00:36:21,827 untuk meletakkan orang ini semasa saya melakukan penggabungan itu, 811 00:36:21,827 --> 00:36:23,410 dan kemudian saya boleh meletakkan mereka kembali di tempat. 812 00:36:23,410 --> 00:36:27,260 Dan itu penting kerana saya menggunakan sumber baru, ruang, bukan sahaja masa. 813 00:36:27,260 --> 00:36:28,270 >> OK, ini luar biasa. 814 00:36:28,270 --> 00:36:32,050 Separuh kiri disusun, separuh kanan adalah disusun, sekarang bahawa kunci menggabungkan langkah. 815 00:36:32,050 --> 00:36:33,450 Bagaimana saya akan bergabung 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 Saya akan menunjukkan tangan kiri saya pada separuh kiri, tangan kanan saya 818 00:36:38,930 --> 00:36:42,680 pada separuh yang betul, dan sekarang saya perlu memutuskan langkah demi langkah yang bergabung dalam. 819 00:36:42,680 --> 00:36:44,650 Yang jelas datang pertama? 820 00:36:44,650 --> 00:36:45,150 Nombor satu. 821 00:36:45,150 --> 00:36:47,327 Jadi datang ke sini, di sini pad awal kami. 822 00:36:47,327 --> 00:36:49,910 Jadi sekarang nombor satu, dan notis apa yang saya akan lakukan dengan tangan kanan saya, 823 00:36:49,910 --> 00:36:54,152 Saya akan bergerak satu tangan kanan saya melangkah ke titik ketiga, 824 00:36:54,152 --> 00:36:55,860 dan sekarang saya perlu membuat keputusan sama. 825 00:36:55,860 --> 00:36:58,387 Dan benar-benar berdiri betul-betul di hadapan Luke di sini jika anda boleh, 826 00:36:58,387 --> 00:36:59,720 kerana ini adalah pad awal kami. 827 00:36:59,720 --> 00:37:00,610 Jadi yang datang akan datang? 828 00:37:00,610 --> 00:37:05,000 Kami mempunyai Luke dengan nombor dua atau Chris dengan nombor tiga. 829 00:37:05,000 --> 00:37:07,460 Jelas Lukas, bilangan dua, jadi anda datang ke sini. 830 00:37:07,460 --> 00:37:11,270 >> Tetapi tangan kiri saya kini akan akan incremented untuk menunjuk ke arah Darren, 831 00:37:11,270 --> 00:37:15,160 dan di sini yang utama dengan mengambil bergabung, saya akan terus melakukan ini, 832 00:37:15,160 --> 00:37:17,340 jelas, jika anda jenis daripada mengikuti logik. 833 00:37:17,340 --> 00:37:19,670 Tetapi tangan saya tidak pernah akan pergi ke belakang, 834 00:37:19,670 --> 00:37:23,861 yang bermaksud saya hanya pernah berpindah ke kiri dengan proses penggabungan saya, 835 00:37:23,861 --> 00:37:26,360 dan itu akan menjadi kunci kepada analisis kami dalam hanya seketika. 836 00:37:26,360 --> 00:37:27,859 >> Jadi sekarang mari kita selesai ini dengan pesat. 837 00:37:27,859 --> 00:37:31,650 Jadi tiga datang akan datang, kemudian empat datang akan datang, 838 00:37:31,650 --> 00:37:38,750 dan kini lima datang berikutnya, kemudian enam, dan tujuh, dan akhirnya lapan. 839 00:37:38,750 --> 00:37:42,960 Terasa seperti algoritma paling perlahan lagi, tetapi tidak jika kita benar-benar 840 00:37:42,960 --> 00:37:45,510 jalankan ia jenis yang sama kelajuan jam, jadi untuk 841 00:37:45,510 --> 00:37:48,106 bercakap, dengan yang sama berdetik jam seperti sebelum ini. 842 00:37:48,106 --> 00:37:48,605 Mengapa? 843 00:37:48,605 --> 00:37:51,100 Nah, Mari kita melihat hasil akhir. 844 00:37:51,100 --> 00:37:56,990 >> Mari kita kembali di sini, biar saya tarik demonstrasi visual 845 00:37:56,990 --> 00:37:59,030 apa yang kita lakukan. 846 00:37:59,030 --> 00:38:06,110 Zoom masuk di sini, ini Laman di sini, memberitahu Firefox 847 00:38:06,110 --> 00:38:08,200 yang kita mahu beratur di dalam kotak ini, mari kita 848 00:38:08,200 --> 00:38:11,260 mengatakan semacam gelembung, dengan yang kami kini juga biasa, 849 00:38:11,260 --> 00:38:14,130 jenis pemilihan, yang merupakan satu lagi agak satu mudah, 850 00:38:14,130 --> 00:38:18,250 dan kini semacam merge hari ini, yang akan berakhir klimaks kami. 851 00:38:18,250 --> 00:38:21,530 Sebab ia mengambil masa yang lebih lama di sini dengan manusia dan saya secara lisan adalah, 852 00:38:21,530 --> 00:38:23,480 jelas, saya menerangkan setiap langkah. 853 00:38:23,480 --> 00:38:26,920 Tetapi jika anda hanya melaksanakan ini, banyak seperti yang kami lakukan gelembung jenis dan pemilihan 854 00:38:26,920 --> 00:38:30,890 jenis bukan sahaja visual, jam tangan betapa banyak dengan lebih cekap 855 00:38:30,890 --> 00:38:33,330 memanfaatkan ini bahagian dan menakluk 856 00:38:33,330 --> 00:38:39,150 boleh apabila digunakan untuk satu set data itu tidak saiz lapan, tetapi walaupun banyak, 857 00:38:39,150 --> 00:38:39,970 lebih besar. 858 00:38:39,970 --> 00:38:44,585 Saya memberi anda bergabung jenis, sebelah- sampingan dengan ini algoritma lain. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Ini akan mendapatkan menyakitkan cepat, dan akhir yang 861 00:38:58,530 --> 00:39:00,890 tidak terlalu klimaks, mereka hanya berakhir disusun. 862 00:39:00,890 --> 00:39:05,280 Tetapi kunci mengambil ialah bagaimana kelihatan lebih cepat bergabung jenis 863 00:39:05,280 --> 00:39:08,110 adalah, melainkan jika anda fikir saya hanya jenis kerunsingan dengan anda. 864 00:39:08,110 --> 00:39:13,100 Jika kita melakukan ini sekali akhir, Mari kita menambah nilai ini, mari kita kembali 865 00:39:13,100 --> 00:39:14,960 dan memilih jenis gelembung, dan hanya untuk tendangan, 866 00:39:14,960 --> 00:39:17,330 mari kita memilih sisipan jenis, hanya sebagai langkah yang baik. 867 00:39:17,330 --> 00:39:20,020 Dan masa ini lagi, mari kita memilih jenis merge dan mari kita 868 00:39:20,020 --> 00:39:21,595 sebenarnya berjalan sebelah menyebelah ini. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Dan bukan, sebenarnya, kebetulan. 871 00:39:26,930 --> 00:39:31,140 Apa yang saya lakukan adalah berkesan saya telah dibahagikan input saya pada separuh, sekali lagi, 872 00:39:31,140 --> 00:39:32,240 dan sekali lagi, dan sekali lagi. 873 00:39:32,240 --> 00:39:35,590 Dan hanya ada banyak kali anda boleh membahagikan input anda ke bahagian, kiri 874 00:39:35,590 --> 00:39:36,240 dan kanan. 875 00:39:36,240 --> 00:39:39,425 Apakah formula yang kita terus melihat yang menggambarkan bahagian ini pada separuh 876 00:39:39,425 --> 00:39:41,050 sekali lagi, dan sekali lagi, dan sekali lagi, dan sekali lagi? 877 00:39:41,050 --> 00:39:41,890 >> PENONTON: Log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Log n. 879 00:39:42,760 --> 00:39:46,300 Tetapi kemudian ada satu langkah utama yang lain, algoritma ini tidak log n langkah. 880 00:39:46,300 --> 00:39:48,992 Jika ia hanya log n langkah, kami akan berada dalam masalah yang sama 881 00:39:48,992 --> 00:39:51,200 seperti sebelum ini di mana kita tidak boleh memastikan semuanya ini disusun. 882 00:39:51,200 --> 00:39:54,480 Anda perlu melihat secara minimum di n elemen untuk memastikan n unsur-unsur disusun, 883 00:39:54,480 --> 00:39:55,950 jika tidak ia adalah satu lonjakan iman. 884 00:39:55,950 --> 00:39:59,810 >> Jadi log minimum n langkah, tetapi apa tentang perkara ini langkah penggabungan utama 885 00:39:59,810 --> 00:40:04,370 di mana saya digabungkan separuh kiri dan kanan setengah dan berjalan di seluruh peringkat? 886 00:40:04,370 --> 00:40:06,980 Berapa banyak langkah-langkah ialah untuk bergabung? 887 00:40:06,980 --> 00:40:10,150 Ia n, tetapi saya tidak hanya bergabung masa akhir. 888 00:40:10,150 --> 00:40:15,089 Pada setiap panggilan yang bersarang, pada setiap dari orang-orang bergabung bersarang, saya masih disusun. 889 00:40:15,089 --> 00:40:18,380 Saya digabungkan kedua-dua perempuan, maka kedua-dua perempuan, maka kedua-dua lelaki dan sebagainya. 890 00:40:18,380 --> 00:40:19,955 >> Jadi saya bergabung sekali 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 membahagikan senarai dua, saya merge a. 893 00:40:23,510 --> 00:40:25,460 Bahagikan senarai pada separuh, melakukan merge a. 894 00:40:25,460 --> 00:40:28,570 Jadi jika membahagikan senarai boleh dilakukan log n kali, 895 00:40:28,570 --> 00:40:33,880 dan penggabungan yang akhirnya mengambil n langkah, apa yang mungkin sekarang atas 896 00:40:33,880 --> 00:40:37,000 terikat pada berjalan masa algoritma kami? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Dan sesungguhnya, itulah yang kami telah dicapai di sini. 899 00:40:40,560 --> 00:40:44,650 Jadi rasa yang anda lihat secara visual apabila tiga perkara yang berjalan sebelah menyebelah 900 00:40:44,650 --> 00:40:47,930 adalah n kuasa dua terhadap n kuasa dua terhadap n log n. 901 00:40:47,930 --> 00:40:51,010 Yang pada dasarnya kita akan melihat, bukan sahaja hari ini tetapi pada masa akan datang, 902 00:40:51,010 --> 00:40:52,760 jauh, jauh lebih cepat. 903 00:40:52,760 --> 00:40:56,010 Satu pusingan tepukan untuk lelaki ini, Saya akan memberi ganjaran kepada mereka dengan bola tekanan. 904 00:40:56,010 --> 00:41:00,260 Mari kita menangguhkan di sini hari ini, dan kita akan melihat anda pada hari Isnin. 905 00:41:00,260 --> 00:41:02,255