1 00:00:00,000 --> 00:00:11,904 >> [MUSIC PLAYING] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSOR: Baiklah. 3 00:00:12,910 --> 00:00:16,730 Ini adalah CS50 dan ini akhir minggu tiga. 4 00:00:16,730 --> 00:00:20,230 Jadi kita di sini hari ini, tidak di Sanders Teater, bukan di Weidner Perpustakaan. 5 00:00:20,230 --> 00:00:23,170 Dalam yang studio dikenal sebagai Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 atau harus kami katakan Studio H, atau akan kami say-- jika Anda menikmati lelucon itu, 7 00:00:28,310 --> 00:00:30,540 itu benar-benar dari teman sekelas, Mark, online, 8 00:00:30,540 --> 00:00:32,420 yang menyarankan sebanyak via Twitter. 9 00:00:32,420 --> 00:00:34,270 Sekarang apa yang keren tentang berada di sini di studio 10 00:00:34,270 --> 00:00:38,410 adalah bahwa saya dikelilingi oleh orang-hijau dinding, layar hijau atau chromakey, 11 00:00:38,410 --> 00:00:43,290 sehingga untuk berbicara, yang berarti bahwa CS50 ini tim produksi, tanpa sepengetahuan saya 12 00:00:43,290 --> 00:00:47,380 sekarang, bisa menempatkan saya paling mana saja di dunia, 13 00:00:47,380 --> 00:00:48,660 untuk lebih baik atau buruk. 14 00:00:48,660 --> 00:00:51,800 >> Sekarang apa yang ada di depan, masalah ditetapkan dua adalah di tangan Anda untuk minggu ini, 15 00:00:51,800 --> 00:00:53,830 tetapi dengan masalah mengatur tiga minggu mendatang, 16 00:00:53,830 --> 00:00:56,600 Anda akan ditantang dengan yang disebut permainan 15, 17 00:00:56,600 --> 00:00:58,960 sebuah nikmat partai lama yang Anda mungkin ingat menerima 18 00:00:58,960 --> 00:01:02,030 sebagai anak yang memiliki seluruh banyak angka yang bisa geser ke atas, ke bawah, 19 00:01:02,030 --> 00:01:05,790 kiri dan kanan, dan ada satu celah dalam teka-teki, di mana Anda 20 00:01:05,790 --> 00:01:07,840 benar-benar dapat geser potongan-potongan teka-teki. 21 00:01:07,840 --> 00:01:11,150 Pada akhirnya Anda menerima ini teka-teki dalam beberapa urutan setengah acak, 22 00:01:11,150 --> 00:01:12,940 dan tujuannya adalah untuk semacam itu, atas ke bawah, 23 00:01:12,940 --> 00:01:16,310 kiri ke kanan, dari satu semua jalan melalui 15. 24 00:01:16,310 --> 00:01:19,360 >> Sayangnya, pelaksanaan Anda akan memiliki di tangan 25 00:01:19,360 --> 00:01:21,590 akan menjadi perangkat lunak berdasarkan, tidak secara fisik. 26 00:01:21,590 --> 00:01:25,280 Anda benar-benar akan harus menulis kode dengan yang diterima oleh siswa atau pengguna dapat 27 00:01:25,280 --> 00:01:26,760 memainkan permainan 15. 28 00:01:26,760 --> 00:01:29,030 Dan pada kenyataannya, di hacker edisi permainan 15, 29 00:01:29,030 --> 00:01:32,155 Anda akan menjadi tantangan untuk melaksanakan, bukan hanya bermain sekolah tua ini 30 00:01:32,155 --> 00:01:35,010 permainan, melainkan pemecahan yang itu, menerapkan modus dewa, 31 00:01:35,010 --> 00:01:38,280 sehingga untuk berbicara, yang benar-benar memecahkan teka-teki bagi manusia, 32 00:01:38,280 --> 00:01:41,080 dengan menyediakan petunjuk, setelah hint, setelah sedikit. 33 00:01:41,080 --> 00:01:42,280 Jadi lebih pada minggu depan. 34 00:01:42,280 --> 00:01:43,720 Tapi itulah yang ada di depan. 35 00:01:43,720 --> 00:01:47,610 >> Untuk saat ini ingat bahwa awal pekan ini kami memiliki cliffhanger ini, jika Anda mau, 36 00:01:47,610 --> 00:01:52,560 dimana yang terbaik yang kami lakukan pengurutan bijaksana adalah batas atas dari besar o n 37 00:01:52,560 --> 00:01:53,210 kuadrat. 38 00:01:53,210 --> 00:01:56,520 Dengan kata lain, bubble sort, semacam seleksi, insertion sort, 39 00:01:56,520 --> 00:01:59,120 semua dari mereka, sementara yang berbeda dalam implementasinya, 40 00:01:59,120 --> 00:02:03,480 diserahkan ke sebuah n kuadrat berjalan waktu dalam kasus terburuk. 41 00:02:03,480 --> 00:02:06,010 Dan kita umumnya menganggap bahwa kasus yang paling buruk untuk menyortir 42 00:02:06,010 --> 00:02:08,814 adalah salah satu yang Anda masukan benar-benar mundur. 43 00:02:08,814 --> 00:02:11,980 Dan memang, butuh beberapa langkah untuk melaksanakan masing-masing algoritma. 44 00:02:11,980 --> 00:02:15,110 >> Sekarang di akhir kelas ingat, kami membandingkan bubble sort 45 00:02:15,110 --> 00:02:19,390 terhadap pilihan semacam terhadap satu lainnya bahwa kita disebut merge semacam pada saat itu, 46 00:02:19,390 --> 00:02:22,120 dan saya mengusulkan bahwa itu mengambil keuntungan dari pelajaran dari seminggu 47 00:02:22,120 --> 00:02:24,060 nol, membagi dan menaklukkan. 48 00:02:24,060 --> 00:02:28,810 Dan entah bagaimana mencapai beberapa jenis logaritmik waktu berjalan akhirnya, 49 00:02:28,810 --> 00:02:31,024 bukan sesuatu itu murni kuadrat. 50 00:02:31,024 --> 00:02:33,440 Dan itu tidak cukup logaritmik, itu sedikit lebih dari itu. 51 00:02:33,440 --> 00:02:36,520 Tetapi jika Anda ingat dari kelas, itu jauh, jauh lebih cepat. 52 00:02:36,520 --> 00:02:38,210 Mari kita lihat di mana kita tinggalkan. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble sort dibandingkan pilihan semacam vs merge sort. 55 00:02:45,370 --> 00:02:47,700 Sekarang mereka semua berjalan, di teori, pada saat yang sama. 56 00:02:47,700 --> 00:02:50,510 CPU berjalan pada kecepatan yang sama. 57 00:02:50,510 --> 00:02:54,990 Tapi Anda bisa merasakan bagaimana membosankan ini sangat cepat akan menjadi, 58 00:02:54,990 --> 00:02:58,790 dan hanya seberapa cepat, ketika kita menyuntikkan sedikit algoritma minggu nol ini, 59 00:02:58,790 --> 00:03:00,080 bisa kita mempercepat. 60 00:03:00,080 --> 00:03:01,630 >> Jadi tanda semacam tampak luar biasa. 61 00:03:01,630 --> 00:03:05,220 Bagaimana kita bisa memanfaatkan itu, dalam rangka untuk mengurutkan nomor lebih cepat. 62 00:03:05,220 --> 00:03:07,140 Nah mari kita berpikir kembali untuk bahan yang kami 63 00:03:07,140 --> 00:03:10,380 memiliki kembali minggu nol, yang dari mencari seseorang di buku telepon, 64 00:03:10,380 --> 00:03:12,380 dan ingat bahwa pseudocode yang kita diusulkan, 65 00:03:12,380 --> 00:03:14,560 melalui mana kita dapat menemukan seseorang seperti Mike Smith, 66 00:03:14,560 --> 00:03:16,310 tampak sedikit sesuatu seperti ini. 67 00:03:16,310 --> 00:03:20,820 >> Sekarang kita lihat pada khususnya pada baris 7 dan 8, dan 10 dan 11, 68 00:03:20,820 --> 00:03:25,240 yang menginduksi lingkaran itu, dimana kami terus akan kembali ke jalur 3 lagi, dan lagi, 69 00:03:25,240 --> 00:03:26,520 dan lagi. 70 00:03:26,520 --> 00:03:31,790 Tapi ternyata bahwa kita dapat melihat algoritma ini, di sini di pseudocode, 71 00:03:31,790 --> 00:03:33,620 sedikit lebih holistik. 72 00:03:33,620 --> 00:03:35,960 Bahkan, apa yang saya cari di sini di layar, 73 00:03:35,960 --> 00:03:41,180 adalah algoritma untuk mencari Mike Smith antara beberapa set halaman. 74 00:03:41,180 --> 00:03:45,520 Dan memang, kita bisa menyederhanakan ini algoritma dalam garis 7 dan 8, 75 00:03:45,520 --> 00:03:49,860 dan 10 dan 11 untuk hanya mengatakan ini, yang saya sudah disajikan di sini dalam kuning. 76 00:03:49,860 --> 00:03:52,210 Dengan kata lain, jika Mike Smith adalah awal dalam buku ini, 77 00:03:52,210 --> 00:03:55,004 kita tidak perlu menentukan langkah demi langkah sekarang bagaimana untuk pergi menemukannya. 78 00:03:55,004 --> 00:03:56,920 Kami tidak harus menentukan kembali ke jalur 3, 79 00:03:56,920 --> 00:03:58,960 kenapa tidak kita hanya sebaliknya, mengatakan, lebih umum, 80 00:03:58,960 --> 00:04:01,500 mencari Mike di kiri setengah dari buku ini. 81 00:04:01,500 --> 00:04:03,960 >> Sebaliknya, jika Mike adalah sebenarnya nanti dalam buku ini, 82 00:04:03,960 --> 00:04:07,540 kenapa tidak kita hanya mengutip pencarian tanda kutip untuk Mike di bagian kanan buku. 83 00:04:07,540 --> 00:04:11,030 Dengan kata lain, kenapa tidak kita hanya semacam menyepak bola untuk diri kita sendiri mengatakan, 84 00:04:11,030 --> 00:04:13,130 mencari Mike dalam bagian dari buku, 85 00:04:13,130 --> 00:04:16,279 dan menyerahkan kepada kami yang ada algoritma untuk memberitahu kami 86 00:04:16,279 --> 00:04:18,750 bagaimana mencari Mike di yang kiri setengah dari buku ini. 87 00:04:18,750 --> 00:04:20,750 Dengan kata lain, kami algoritma bekerja apakah itu 88 00:04:20,750 --> 00:04:24,670 buku telepon ketebalan ini, ini ketebalan, atau ketebalan apapun. 89 00:04:24,670 --> 00:04:27,826 Jadi kita bisa rekursif mendefinisikan algoritma ini. 90 00:04:27,826 --> 00:04:29,950 Dengan kata lain, pada layar di sini, adalah sebuah algoritma 91 00:04:29,950 --> 00:04:33,130 untuk mencari Mike Smith antara halaman buku telepon. 92 00:04:33,130 --> 00:04:37,410 Jadi sejalan 7 dan 10, mari kita hanya mengatakan hal itu. 93 00:04:37,410 --> 00:04:40,250 Dan saya menggunakan istilah ini sejenak lalu, dan memang, rekursi 94 00:04:40,250 --> 00:04:42,450 adalah kata kunci untuk saat ini, dan itu proses ini 95 00:04:42,450 --> 00:04:47,210 melakukan sesuatu siklus oleh entah bagaimana menggunakan kode yang sudah Anda miliki, 96 00:04:47,210 --> 00:04:49,722 dan menyebutnya lagi, dan lagi, dan lagi. 97 00:04:49,722 --> 00:04:51,930 Sekarang itu akan menjadi penting bahwa kita entah bagaimana bawah 98 00:04:51,930 --> 00:04:53,821 keluar, dan tidak melakukan itu panjang tak terhingga. 99 00:04:53,821 --> 00:04:56,070 Jika tidak kita akan memiliki memang loop tak terbatas. 100 00:04:56,070 --> 00:04:59,810 Tapi mari kita lihat apakah kita dapat meminjam ide ini rekursi, melakukan sesuatu lagi 101 00:04:59,810 --> 00:05:03,600 dan lagi dan lagi, untuk memecahkan masalah menyortir melalui penggabungan 102 00:05:03,600 --> 00:05:05,900 semacam, semua lebih efisien. 103 00:05:05,900 --> 00:05:06,970 >> Jadi saya memberikan menggabungkan semacam. 104 00:05:06,970 --> 00:05:07,920 Mari lihat. 105 00:05:07,920 --> 00:05:10,850 Jadi di sini adalah pseudocode, dengan yang kita bisa menerapkan pemilahan, 106 00:05:10,850 --> 00:05:12,640 menggunakan algoritma ini disebut merge sort. 107 00:05:12,640 --> 00:05:13,880 Dan itu cukup sederhana ini. 108 00:05:13,880 --> 00:05:15,940 Masukan dari elemen n, dengan kata lain, jika Anda 109 00:05:15,940 --> 00:05:18,830 diberikan n elemen dan angka dan surat atau apapun input, 110 00:05:18,830 --> 00:05:22,430 jika Anda diberi unsur n, jika n kurang dari 2, hanya kembali. 111 00:05:22,430 --> 00:05:22,930 Benar? 112 00:05:22,930 --> 00:05:26,430 Karena jika n kurang dari 2, yang berarti bahwa daftar elemen 113 00:05:26,430 --> 00:05:30,446 adalah salah satu dari ukuran 0 atau 1, dan dalam kedua kasus tersebut sepele, 114 00:05:30,446 --> 00:05:31,570 daftar tersebut sudah diurutkan. 115 00:05:31,570 --> 00:05:32,810 Jika tidak ada daftar, itu diurutkan. 116 00:05:32,810 --> 00:05:35,185 Dan jika ada daftar panjang 1, itu jelas diurutkan. 117 00:05:35,185 --> 00:05:38,280 Jadi algoritma hanya perlu benar-benar melakukan sesuatu yang menarik, 118 00:05:38,280 --> 00:05:40,870 jika kita memiliki dua atau lebih elemen yang diberikan kepada kita. 119 00:05:40,870 --> 00:05:42,440 Jadi mari kita lihat keajaiban kemudian. 120 00:05:42,440 --> 00:05:47,500 Lain menyortir kiri setengah dari unsur-unsur, kemudian mengurutkan kanan setengah dari elemen, 121 00:05:47,500 --> 00:05:49,640 kemudian menggabungkan bagian diurutkan. 122 00:05:49,640 --> 00:05:52,440 Dan apa jenis pikiran membungkuk di sini, adalah bahwa saya tidak benar-benar 123 00:05:52,440 --> 00:05:56,190 tampaknya telah mengatakan kepada Anda apa dulu, kan? 124 00:05:56,190 --> 00:05:59,560 Semua sudah saya katakan adalah, diberikan daftar n elemen, mengurutkan setengah kiri, 125 00:05:59,560 --> 00:06:01,800 maka setengah benar, maka menggabungkan bagian diurutkan, 126 00:06:01,800 --> 00:06:03,840 tetapi di mana adalah saus rahasia yang sebenarnya? 127 00:06:03,840 --> 00:06:05,260 Dimana algoritma? 128 00:06:05,260 --> 00:06:09,150 Nah ternyata dua baris pertama, setengah semacam meninggalkan elemen, 129 00:06:09,150 --> 00:06:13,970 dan hak semacam setengah dari elemen, panggilan rekursif, sehingga untuk berbicara. 130 00:06:13,970 --> 00:06:16,120 >> Setelah semua, ini titik waktu, saya harus 131 00:06:16,120 --> 00:06:18,950 algoritma yang dapat digunakan untuk mengurutkan sejumlah elemen? 132 00:06:18,950 --> 00:06:19,450 Iya nih. 133 00:06:19,450 --> 00:06:20,620 Ada di sini. 134 00:06:20,620 --> 00:06:25,180 Ada di sini di layar, dan jadi saya bisa menggunakan set yang sama langkah 135 00:06:25,180 --> 00:06:28,500 memilah kiri setengah, yang saya bisa kanan setengah. 136 00:06:28,500 --> 00:06:30,420 Dan memang, lagi, dan lagi. 137 00:06:30,420 --> 00:06:34,210 Jadi entah bagaimana, dan kami akan segera melihat ini, keajaiban semacam penggabungan 138 00:06:34,210 --> 00:06:37,967 tertanam dalam sangat akhir line, menggabungkan bagian diurutkan. 139 00:06:37,967 --> 00:06:39,300 Dan yang tampaknya cukup intuitif. 140 00:06:39,300 --> 00:06:41,050 Anda mengambil dua bagian, dan Anda, entah bagaimana, menggabungkan mereka bersama-sama, 141 00:06:41,050 --> 00:06:43,260 dan kami akan melihat ini konkret dalam sekejap. 142 00:06:43,260 --> 00:06:45,080 >> Tapi ini adalah algoritma lengkap. 143 00:06:45,080 --> 00:06:46,640 Dan mari kita lihat persis mengapa. 144 00:06:46,640 --> 00:06:50,912 Nah misalkan kita diberi ini sama delapan elemen di sini di layar, satu 145 00:06:50,912 --> 00:06:53,120 melalui delapan, tapi mereka dalam rangka acak. 146 00:06:53,120 --> 00:06:55,320 Dan tujuan di tangan adalah untuk mengurutkan elemen-elemen ini. 147 00:06:55,320 --> 00:06:58,280 Nah bagaimana saya bisa pergi tentang melakukannya menggunakan, lagi, 148 00:06:58,280 --> 00:07:00,407 menggabungkan semacam, sesuai pseudocode ini? 149 00:07:00,407 --> 00:07:02,740 Dan lagi, menanamkan ini di pikiran Anda, untuk sesaat. 150 00:07:02,740 --> 00:07:05,270 Kasus pertama adalah cukup sepele, jika kurang dari 2, 151 00:07:05,270 --> 00:07:07,060 hanya kembali, tidak ada pekerjaan yang harus dilakukan. 152 00:07:07,060 --> 00:07:09,290 Jadi benar-benar hanya ada tiga langkah-langkah untuk benar-benar perlu diingat. 153 00:07:09,290 --> 00:07:11,081 Lagi, dan lagi, aku akan ingin memiliki 154 00:07:11,081 --> 00:07:13,980 memilah kiri setengah, mengurutkan bagian kanan, 155 00:07:13,980 --> 00:07:15,890 dan kemudian sekali mereka dua bagian diurutkan, 156 00:07:15,890 --> 00:07:18,710 Saya ingin menggabungkan mereka bersama-sama menjadi satu daftar diurutkan. 157 00:07:18,710 --> 00:07:19,940 Jadi ingatlah bahwa dalam pikiran. 158 00:07:19,940 --> 00:07:21,310 >> Jadi, inilah daftar asli. 159 00:07:21,310 --> 00:07:23,510 Mari kita memperlakukan ini sebagai array, seperti yang kita mulai 160 00:07:23,510 --> 00:07:25,800 di minggu kedua, yang merupakan blok memori yang berdekatan. 161 00:07:25,800 --> 00:07:28,480 Dalam hal ini, berisi delapan angka, kembali ke belakang ke belakang. 162 00:07:28,480 --> 00:07:30,700 Dan mari kita sekarang berlaku merge sort. 163 00:07:30,700 --> 00:07:33,300 Jadi saya pertama kali ingin mengurutkan kiri setengah dari daftar ini, 164 00:07:33,300 --> 00:07:37,370 dan mari kita, oleh karena itu, fokus pada 4, 8, 6, dan 2. 165 00:07:37,370 --> 00:07:41,000 >> Sekarang bagaimana aku pergi tentang menyortir daftar ukuran 4? 166 00:07:41,000 --> 00:07:45,990 Yah aku harus sekarang mempertimbangkan menyortir kiri kiri setengah. 167 00:07:45,990 --> 00:07:47,720 Sekali lagi, mari kita mundur untuk sesaat. 168 00:07:47,720 --> 00:07:51,010 Jika pseudocode adalah ini, dan aku diberi delapan elemen, 169 00:07:51,010 --> 00:07:53,230 8 jelas lebih besar dari atau sama dengan 2. 170 00:07:53,230 --> 00:07:54,980 Jadi dengan kasus pertama tidak berlaku. 171 00:07:54,980 --> 00:07:58,120 Jadi untuk mengurutkan delapan elemen, saya pertama kali mengurutkan kiri setengah dari elemen, 172 00:07:58,120 --> 00:08:01,930 maka saya mengurutkan bagian kanan, maka saya menggabungkan dua bagian diurutkan, masing-masing ukuran 4. 173 00:08:01,930 --> 00:08:02,470 OKE. 174 00:08:02,470 --> 00:08:07,480 >> Tetapi jika Anda baru saja mengatakan kepada saya, mengurutkan setengah kiri, yang sekarang ukuran 4, 175 00:08:07,480 --> 00:08:09,350 bagaimana cara mengurutkan setengah kiri? 176 00:08:09,350 --> 00:08:11,430 Nah jika saya memiliki masukan dari empat elemen, 177 00:08:11,430 --> 00:08:14,590 Saya pertama kali mengurutkan kiri dua, maka dua yang benar, 178 00:08:14,590 --> 00:08:16,210 dan kemudian saya menggabungkan mereka bersama-sama. 179 00:08:16,210 --> 00:08:18,700 Jadi sekali lagi, itu menjadi sedikit dari pikiran membungkuk permainan di sini, 180 00:08:18,700 --> 00:08:21,450 karena Anda, jenis, harus ingat di mana Anda berada dalam cerita, 181 00:08:21,450 --> 00:08:23,620 tapi pada akhir hari, diberikan sejumlah elemen, 182 00:08:23,620 --> 00:08:25,620 Anda pertama kali ingin mengurutkan setengah kiri, maka bagian kanan, 183 00:08:25,620 --> 00:08:26,661 kemudian menggabungkan mereka bersama-sama. 184 00:08:26,661 --> 00:08:28,630 Mari kita mulai untuk melakukan hal itu. 185 00:08:28,630 --> 00:08:30,170 Berikut masukan dari delapan elemen. 186 00:08:30,170 --> 00:08:31,910 Sekarang kita sedang melihat kiri setengah di sini. 187 00:08:31,910 --> 00:08:33,720 Bagaimana cara memilah empat elemen? 188 00:08:33,720 --> 00:08:35,610 Yah aku pertama mengurutkan setengah kiri. 189 00:08:35,610 --> 00:08:37,720 Sekarang bagaimana cara mengurutkan setengah kiri? 190 00:08:37,720 --> 00:08:39,419 Yah aku sudah diberi dua elemen. 191 00:08:39,419 --> 00:08:41,240 Jadi mari kita mengurutkan kedua elemen ini. 192 00:08:41,240 --> 00:08:44,540 2 lebih besar dari atau sama dengan 2, tentu saja. 193 00:08:44,540 --> 00:08:46,170 Sehingga kasus pertama tidak berlaku. 194 00:08:46,170 --> 00:08:49,010 >> Jadi saya sekarang harus memilah kiri setengah dari dua elemen tersebut. 195 00:08:49,010 --> 00:08:50,870 Kiri setengah, tentu saja, hanya 4. 196 00:08:50,870 --> 00:08:54,020 Jadi bagaimana cara mengurutkan daftar satu elemen? 197 00:08:54,020 --> 00:08:57,960 Nah sekarang, bahwa kasus dasar khusus di bagian atas, sehingga untuk berbicara, berlaku. 198 00:08:57,960 --> 00:09:01,470 1 kurang dari 2, dan saya Daftar memang ukuran 1. 199 00:09:01,470 --> 00:09:02,747 Jadi aku hanya kembali. 200 00:09:02,747 --> 00:09:03,580 Saya tidak melakukan apa-apa. 201 00:09:03,580 --> 00:09:06,770 Dan memang, melihat apa yang telah saya dilakukan, 4 sudah diurutkan. 202 00:09:06,770 --> 00:09:09,220 Seperti aku sudah sebagian berhasil di sini. 203 00:09:09,220 --> 00:09:11,750 >> Sekarang tampaknya agak bodoh untuk mengklaim, tapi itu benar. 204 00:09:11,750 --> 00:09:13,700 4 adalah daftar ukuran 1. 205 00:09:13,700 --> 00:09:15,090 Ini sudah diurutkan. 206 00:09:15,090 --> 00:09:16,270 Itulah setengah kiri. 207 00:09:16,270 --> 00:09:18,010 Sekarang saya mengurutkan bagian kanan. 208 00:09:18,010 --> 00:09:22,310 Masukan saya adalah salah satu elemen, 8 sama, sudah diurutkan. 209 00:09:22,310 --> 00:09:25,170 Bodoh juga, tapi sekali lagi, Prinsip dasar ini 210 00:09:25,170 --> 00:09:28,310 akan memungkinkan kita untuk membangun sekarang di atas ini berhasil. 211 00:09:28,310 --> 00:09:32,260 4 diurutkan, 8 diurutkan, sekarang apa itu langkah terakhir? 212 00:09:32,260 --> 00:09:35,330 Jadi langkah ketiga dan terakhir, setiap waktu Anda menyortir daftar, recall, 213 00:09:35,330 --> 00:09:38,310 adalah untuk menggabungkan dua bagian, kiri dan kanan. 214 00:09:38,310 --> 00:09:39,900 Jadi mari kita melakukan hal itu. 215 00:09:39,900 --> 00:09:41,940 Setengah kiri saya, tentu saja, 4. 216 00:09:41,940 --> 00:09:43,310 Setengah kanan saya adalah 8. 217 00:09:43,310 --> 00:09:44,100 >> Jadi mari kita lakukan ini. 218 00:09:44,100 --> 00:09:46,410 Pertama aku akan mengalokasikan beberapa memori tambahan, 219 00:09:46,410 --> 00:09:48,680 bahwa saya akan mewakili di sini, hanya sebagai array sekunder, 220 00:09:48,680 --> 00:09:49,660 itu cukup besar untuk muat ini. 221 00:09:49,660 --> 00:09:52,243 Tapi Anda bisa bayangkan memperluas bahwa persegi panjang seluruh panjang, 222 00:09:52,243 --> 00:09:53,290 jika kita membutuhkan lebih banyak nanti. 223 00:09:53,290 --> 00:09:58,440 Bagaimana cara mengambil 4 dan 8, dan menggabungkan kedua daftar ukuran 1 bersama-sama? 224 00:09:58,440 --> 00:10:00,270 Di sini juga, cukup sederhana. 225 00:10:00,270 --> 00:10:03,300 4 datang pertama, kemudian datang 8. 226 00:10:03,300 --> 00:10:07,130 Karena jika saya ingin mengurutkan setengah kiri, maka bagian kanan, 227 00:10:07,130 --> 00:10:09,900 dan kemudian menggabungkan dua bagian bersama-sama, dalam rangka diurutkan, 228 00:10:09,900 --> 00:10:11,940 4 datang pertama, kemudian datang 8. 229 00:10:11,940 --> 00:10:15,810 >> Jadi kita tampaknya akan membuat kemajuan, bahkan meskipun saya tidak melakukan pekerjaan yang sebenarnya. 230 00:10:15,810 --> 00:10:17,800 Tapi ingat di mana kita berada dalam cerita. 231 00:10:17,800 --> 00:10:19,360 Kami awalnya mengambil delapan elemen. 232 00:10:19,360 --> 00:10:21,480 Kami diurutkan setengah kiri, yaitu 4. 233 00:10:21,480 --> 00:10:24,450 Kemudian kita diurutkan kiri setengah dari kiri setengah, yang 2. 234 00:10:24,450 --> 00:10:25,270 Dan di sini kita pergi. 235 00:10:25,270 --> 00:10:26,920 Kita sudah selesai dengan langkah itu. 236 00:10:26,920 --> 00:10:29,930 >> Jadi jika kita sudah diurutkan meninggalkan setengah dari 2, sekarang kita 237 00:10:29,930 --> 00:10:32,130 harus memilah kanan setengah dari 2. 238 00:10:32,130 --> 00:10:35,710 Jadi bagian kanan 2 adalah kedua nilai di sini, 6 dan 2. 239 00:10:35,710 --> 00:10:40,620 Jadi mari kita sekarang mengambil masukan dari ukuran 2, dan mengurutkan setengah kiri, dan kemudian 240 00:10:40,620 --> 00:10:42,610 bagian kanan, dan kemudian menggabungkan mereka bersama-sama. 241 00:10:42,610 --> 00:10:45,722 Nah bagaimana cara mengurutkan daftar ukuran 1, yang berisi hanya nomor 6? 242 00:10:45,722 --> 00:10:46,430 Saya sudah dilakukan. 243 00:10:46,430 --> 00:10:48,680 Daftar yang ukuran 1 diurutkan. 244 00:10:48,680 --> 00:10:52,140 >> Bagaimana cara mengurutkan daftar lain ukuran 1, yang disebut setengah benar. 245 00:10:52,140 --> 00:10:54,690 Baik itu, juga, sudah diurutkan. 246 00:10:54,690 --> 00:10:56,190 Jumlah 2 sendirian. 247 00:10:56,190 --> 00:11:00,160 Jadi sekarang aku punya dua bagian, kiri dan benar, saya perlu untuk menggabungkan mereka bersama-sama. 248 00:11:00,160 --> 00:11:01,800 Biarkan saya memberi diriku beberapa ruang tambahan. 249 00:11:01,800 --> 00:11:05,580 Dan menempatkan 2 di sana, kemudian 6 di sana, sehingga 250 00:11:05,580 --> 00:11:10,740 menyortir daftar itu, kiri dan kanan, dan penggabungan bersama-sama, akhirnya. 251 00:11:10,740 --> 00:11:12,160 Jadi aku dalam kondisi yang sedikit lebih baik. 252 00:11:12,160 --> 00:11:16,250 Aku belum selesai, karena jelas 4, 8, 2, 6 bukanlah memesan terakhir yang saya inginkan. 253 00:11:16,250 --> 00:11:20,640 Tapi saya sekarang memiliki dua daftar ukuran 2, yang memiliki keduanya, masing-masing, telah disortir. 254 00:11:20,640 --> 00:11:24,580 Jadi sekarang jika Anda mundur dalam pikiran Anda mata, mana yang meninggalkan kita? 255 00:11:24,580 --> 00:11:28,520 Saya mulai dengan delapan elemen, maka saya whittled itu ke kiri setengah dari 4, 256 00:11:28,520 --> 00:11:31,386 kemudian kiri setengah dari 2, dan kemudian kanan setengah dari 2, 257 00:11:31,386 --> 00:11:34,510 Aku selesai, oleh karena itu, penyortiran kiri setengah dari 2, dan kanan setengah dari 2, 258 00:11:34,510 --> 00:11:37,800 jadi apa langkah ketiga dan terakhir di sini? 259 00:11:37,800 --> 00:11:41,290 Saya harus bergabung bersama dua daftar ukuran 2. 260 00:11:41,290 --> 00:11:42,040 Jadi mari kita pergi ke depan. 261 00:11:42,040 --> 00:11:43,940 Dan pada layar di sini, memberikan saya beberapa memori tambahan, 262 00:11:43,940 --> 00:11:47,170 meskipun secara teknis, perhatikan bahwa saya telah mendapat sejumlah ruang kosong di bagian atas 263 00:11:47,170 --> 00:11:47,670 ada. 264 00:11:47,670 --> 00:11:50,044 Jika saya ingin menjadi terutama ruang yang efisien bijaksana, 265 00:11:50,044 --> 00:11:52,960 Aku hanya bisa mulai bergerak elemen bolak-balik, atas dan bawah. 266 00:11:52,960 --> 00:11:55,460 Tapi hanya untuk kejelasan visual, Aku akan meletakkannya di bawah ini, 267 00:11:55,460 --> 00:11:56,800 untuk menjaga hal-hal baik dan bersih. 268 00:11:56,800 --> 00:11:58,150 >> Jadi saya punya dua daftar ukuran 2. 269 00:11:58,150 --> 00:11:59,770 Daftar pertama memiliki 4 dan 8. 270 00:11:59,770 --> 00:12:01,500 Daftar kedua memiliki 2 dan 6. 271 00:12:01,500 --> 00:12:03,950 Mari kita gabungkan bersama-sama dalam rangka diurutkan. 272 00:12:03,950 --> 00:12:09,910 2, tentu saja, datang pertama, kemudian 4, kemudian 6, kemudian 8. 273 00:12:09,910 --> 00:12:12,560 Dan sekarang kita tampaknya akan mendapatkan suatu tempat yang menarik. 274 00:12:12,560 --> 00:12:15,720 Sekarang saya sudah diurutkan setengah dari daftar, dan kebetulan, itu 275 00:12:15,720 --> 00:12:18,650 semua angka bahkan, tapi itu adalah, memang, hanya kebetulan. 276 00:12:18,650 --> 00:12:22,220 Dan saya sekarang telah diurutkan kiri setengah, sehingga itu 2, 4, 6, dan 8. 277 00:12:22,220 --> 00:12:23,430 Tidak ada yang rusak. 278 00:12:23,430 --> 00:12:24,620 Yang terasa seperti kemajuan. 279 00:12:24,620 --> 00:12:26,650 >> Sekarang rasanya seperti saya sudah berbicara selamanya sekarang, 280 00:12:26,650 --> 00:12:29,850 jadi apa masih harus dilihat apakah ini algoritma, memang, lebih efisien. 281 00:12:29,850 --> 00:12:31,766 Tapi kita akan melalui super metodis. 282 00:12:31,766 --> 00:12:34,060 Sebuah komputer, tentu saja, akan melakukannya seperti itu. 283 00:12:34,060 --> 00:12:34,840 Jadi di mana kita? 284 00:12:34,840 --> 00:12:36,180 Kami mulai dengan delapan elemen. 285 00:12:36,180 --> 00:12:37,840 Saya diurutkan kiri setengah dari 4. 286 00:12:37,840 --> 00:12:39,290 Saya tampaknya dilakukan dengan itu. 287 00:12:39,290 --> 00:12:42,535 Jadi sekarang langkah berikutnya adalah untuk mengurutkan bagian kanan 4. 288 00:12:42,535 --> 00:12:44,410 Dan bagian ini kita bisa pergi melalui lebih sedikit 289 00:12:44,410 --> 00:12:47,140 cepat, meskipun Anda dipersilahkan untuk mundur atau berhenti, hanya 290 00:12:47,140 --> 00:12:49,910 memikirkan itu pada kecepatan Anda sendiri, tapi apa 291 00:12:49,910 --> 00:12:53,290 kita miliki sekarang adalah kesempatan untuk melakukan algoritma yang sama yang sebenarnya di empat 292 00:12:53,290 --> 00:12:54,380 nomor yang berbeda. 293 00:12:54,380 --> 00:12:57,740 >> Jadi mari kita pergi ke depan, dan fokus pada bagian kanan, yang kita di sini. 294 00:12:57,740 --> 00:13:01,260 Kiri setengah dari yang setengah benar, dan sekarang 295 00:13:01,260 --> 00:13:04,560 kiri setengah dari kiri setengah dari yang setengah benar, 296 00:13:04,560 --> 00:13:08,030 dan bagaimana cara mengurutkan daftar ukuran 1 hanya berisi nomor 1? 297 00:13:08,030 --> 00:13:09,030 Ini sudah dilakukan. 298 00:13:09,030 --> 00:13:11,830 Bagaimana saya melakukan hal yang sama untuk daftar ukuran 1 yang mengandung hanya 7? 299 00:13:11,830 --> 00:13:12,840 Ini sudah dilakukan. 300 00:13:12,840 --> 00:13:16,790 Langkah ketiga untuk setengah ini kemudian adalah untuk menggabungkan dua unsur ini 301 00:13:16,790 --> 00:13:20,889 dalam daftar baru ukuran 2, 1 dan 7. 302 00:13:20,889 --> 00:13:23,180 Jangan tampaknya telah melakukan semua bahwa banyak pekerjaan yang menarik. 303 00:13:23,180 --> 00:13:24,346 Mari kita lihat apa yang terjadi selanjutnya. 304 00:13:24,346 --> 00:13:29,210 Aku hanya diurutkan kiri setengah dari setengah hak masukan asli saya. 305 00:13:29,210 --> 00:13:32,360 Sekarang mari kita mengurutkan kanan setengah, yang berisi 5 dan 3. 306 00:13:32,360 --> 00:13:35,740 Mari kita kembali melihat kiri setengah, diurutkan, setengah benar, diurutkan, 307 00:13:35,740 --> 00:13:39,120 dan menggabungkan dua bersama-sama, ke beberapa ruang tambahan, 308 00:13:39,120 --> 00:13:41,670 3 datang pertama, kemudian datang 5. 309 00:13:41,670 --> 00:13:46,190 Dan sekarang, kami telah diurutkan setengah kiri kanan setengah 310 00:13:46,190 --> 00:13:49,420 dari masalah asli, dan kanan setengah dari kanan setengah 311 00:13:49,420 --> 00:13:50,800 dari masalah asli. 312 00:13:50,800 --> 00:13:52,480 Apa Langkah ketiga dan terakhir? 313 00:13:52,480 --> 00:13:54,854 Nah untuk menggabungkan dua bagian bersama-sama. 314 00:13:54,854 --> 00:13:57,020 Jadi biarkan aku mendapatkan diriku beberapa ruang ekstra, tapi, sekali lagi, saya 315 00:13:57,020 --> 00:13:58,699 bisa menggunakan ruang yang di bagian atas cadangan. 316 00:13:58,699 --> 00:14:00,490 Tapi kami akan terus sederhana visual. 317 00:14:00,490 --> 00:14:07,070 Biarkan saya bergabung dalam 1 sekarang, dan kemudian 3, dan kemudian 5, dan kemudian 7. 318 00:14:07,070 --> 00:14:10,740 Sehingga meninggalkan saya sekarang dengan kanan setengah dari masalah asli 319 00:14:10,740 --> 00:14:12,840 yang sempurna diurutkan. 320 00:14:12,840 --> 00:14:13,662 >> Jadi apa yang tersisa? 321 00:14:13,662 --> 00:14:16,120 Saya merasa seperti saya terus mengatakan hal yang sama lagi, dan lagi, 322 00:14:16,120 --> 00:14:18,700 tapi itu mencerminkan Fakta bahwa kita sedang menggunakan rekursi. 323 00:14:18,700 --> 00:14:21,050 Proses menggunakan algoritma lagi, dan lagi, 324 00:14:21,050 --> 00:14:23,940 pada subset kecil dari masalah asli. 325 00:14:23,940 --> 00:14:27,580 Jadi saya sekarang telah kiri diurutkan setengah dari masalah asli. 326 00:14:27,580 --> 00:14:30,847 Saya memiliki diurutkan setengah benar dari masalah asli. 327 00:14:30,847 --> 00:14:32,180 Apa langkah ketiga dan terakhir? 328 00:14:32,180 --> 00:14:33,590 Oh, itu penggabungan. 329 00:14:33,590 --> 00:14:34,480 Jadi mari kita lakukan itu. 330 00:14:34,480 --> 00:14:36,420 Mari kita mengalokasikan beberapa tambahan memori, tetapi Tuhan, kita 331 00:14:36,420 --> 00:14:37,503 bisa menempatkannya di mana saja sekarang. 332 00:14:37,503 --> 00:14:40,356 Kami memiliki begitu banyak ruang yang tersedia kepada kami, tapi kami akan tetap sederhana. 333 00:14:40,356 --> 00:14:42,730 Alih-alih akan kembali dan balik dengan memori asli kami, 334 00:14:42,730 --> 00:14:44,480 mari kita lakukan saja visual di sini di bawah ini, 335 00:14:44,480 --> 00:14:47,240 untuk menyelesaikan penggabungan setengah kiri dan kanan setengah. 336 00:14:47,240 --> 00:14:49,279 >> Jadi dengan menggabungkan, apa yang harus saya lakukan? 337 00:14:49,279 --> 00:14:50,820 Saya ingin mengambil unsur-unsur dalam rangka. 338 00:14:50,820 --> 00:14:53,230 Jadi melihat kiri setengah, Aku melihat nomor pertama adalah 2. 339 00:14:53,230 --> 00:14:55,230 Aku melihat bagian kanan, Saya melihat angka pertama 340 00:14:55,230 --> 00:14:58,290 adalah 1, jadi jelas yang nomor yang saya ingin mencabut, 341 00:14:58,290 --> 00:15:00,430 dan menempatkan pertama dalam daftar terakhir saya? 342 00:15:00,430 --> 00:15:01,449 Tentu saja, 1. 343 00:15:01,449 --> 00:15:02,990 Sekarang saya ingin menanyakan hal yang sama. 344 00:15:02,990 --> 00:15:05,040 Pada babak kiri, saya sudah masih punya nomor 2. 345 00:15:05,040 --> 00:15:07,490 Pada bagian kanan, Aku punya nomor 3. 346 00:15:07,490 --> 00:15:08,930 Yang mana yang ingin saya pilih? 347 00:15:08,930 --> 00:15:11,760 Tentu saja, nomor 2 dan sekarang melihat calon 348 00:15:11,760 --> 00:15:13,620 4 di sebelah kiri, 3 di sebelah kanan. 349 00:15:13,620 --> 00:15:15,020 Mari kita, tentu saja, memilih 3. 350 00:15:15,020 --> 00:15:18,020 Sekarang calon 4 di kiri, 5 di sebelah kanan. 351 00:15:18,020 --> 00:15:19,460 Kami, tentu saja, pilih 4. 352 00:15:19,460 --> 00:15:21,240 6 di sebelah kiri, 5 di sebelah kanan. 353 00:15:21,240 --> 00:15:22,730 Kami, tentu saja, memilih 5. 354 00:15:22,730 --> 00:15:25,020 6 di sebelah kiri, 7 di sebelah kanan. 355 00:15:25,020 --> 00:15:29,320 Kami memilih 6, dan kemudian kita memilih 7, dan kemudian kita memilih 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Jadi sejumlah besar kata-kata kemudian, kami telah diurutkan daftar ini delapan elemen 358 00:15:34,370 --> 00:15:38,450 dalam daftar satu sampai delapan, yang meningkat dengan setiap langkah, 359 00:15:38,450 --> 00:15:40,850 tapi berapa banyak waktu melakukan itu membawa kita untuk melakukan itu. 360 00:15:40,850 --> 00:15:43,190 Yah aku sudah sengaja hal meletakkan keluar pictorially 361 00:15:43,190 --> 00:15:46,330 di sini, sehingga kita bisa jenis melihat atau menghargai divisi 362 00:15:46,330 --> 00:15:49,060 di menaklukkan yang telah terjadi. 363 00:15:49,060 --> 00:15:52,830 >> Memang jika Anda melihat kembali bangun, Saya sudah meninggalkan semua ini garis putus-putus 364 00:15:52,830 --> 00:15:55,660 di pemegang tempat, Anda bisa, jenis, melihat, dalam urutan terbalik, 365 00:15:55,660 --> 00:15:58,800 jika Anda jenis melihat kembali sejarah sekarang, daftar asli saya 366 00:15:58,800 --> 00:16:00,250 adalah, tentu saja, dari ukuran 8. 367 00:16:00,250 --> 00:16:03,480 Dan kemudian sebelumnya, saya berurusan dengan dua daftar ukuran 4, 368 00:16:03,480 --> 00:16:08,400 dan kemudian empat daftar ukuran 2, dan kemudian delapan daftar ukuran 1. 369 00:16:08,400 --> 00:16:10,151 >> Jadi, apa ini, jenis, mengingatkan Anda tentang? 370 00:16:10,151 --> 00:16:11,858 Nah, memang, salah algoritma kami telah 371 00:16:11,858 --> 00:16:14,430 memandang sejauh mana kita membagi, dan membagi, dan membagi, 372 00:16:14,430 --> 00:16:19,500 tetap memiliki hal lagi, dan lagi, menghasilkan ide umum ini. 373 00:16:19,500 --> 00:16:23,100 Dan jadi ada sesuatu logaritmik yang terjadi di sini. 374 00:16:23,100 --> 00:16:26,790 Dan itu tidak cukup log n, tapi ada komponen logaritmik 375 00:16:26,790 --> 00:16:28,280 apa yang baru saja kita lakukan. 376 00:16:28,280 --> 00:16:31,570 >> Sekarang mari kita mempertimbangkan bagaimana yang sebenarnya. 377 00:16:31,570 --> 00:16:34,481 Jadi log n, lagi adalah waktu berjalan yang besar, 378 00:16:34,481 --> 00:16:36,980 ketika kita melakukan sesuatu seperti pencarian biner, seperti sekarang kita menyebutnya, 379 00:16:36,980 --> 00:16:40,090 membagi dan menaklukkan strategi melalui yang kami menemukan Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Sekarang teknis. 381 00:16:41,020 --> 00:16:43,640 Itu log basis 2 dari n, bahkan meskipun dalam kebanyakan kelas matematika, 382 00:16:43,640 --> 00:16:45,770 10 biasanya dasar yang Anda berasumsi. 383 00:16:45,770 --> 00:16:48,940 Tapi ilmuwan komputer hampir selalu berpikir dan berbicara dalam hal basis 2, 384 00:16:48,940 --> 00:16:52,569 jadi kita umumnya hanya mengatakan log n, bukannya log basis 2 dari n, 385 00:16:52,569 --> 00:16:55,110 tapi mereka tepat satu dan sama dalam dunia komputer 386 00:16:55,110 --> 00:16:57,234 ilmu pengetahuan, dan sebagai samping, ada faktor konstan 387 00:16:57,234 --> 00:17:01,070 Perbedaan antara keduanya, sehingga diperdebatkan pula, untuk alasan yang lebih formal. 388 00:17:01,070 --> 00:17:04,520 >> Tapi untuk saat ini, apa yang kita peduli tentang adalah contoh ini. 389 00:17:04,520 --> 00:17:08,520 Jadi mari kita tidak membuktikan dengan contoh, tetapi pada Setidaknya menggunakan contoh angka 390 00:17:08,520 --> 00:17:10,730 di tangan sebagai cek kewarasan, jika Anda mau. 391 00:17:10,730 --> 00:17:14,510 Jadi sebelumnya rumus adalah log basis 2 dari n, tapi apa n dalam kasus ini. 392 00:17:14,510 --> 00:17:18,526 Aku punya nomor n asli, atau 8 dari nomor asli khusus. 393 00:17:18,526 --> 00:17:20,359 Sekarang ini sudah sedikit sementara, tapi aku cukup 394 00:17:20,359 --> 00:17:25,300 memastikan bahwa log basis 2 dari nilai 8 adalah 3, 395 00:17:25,300 --> 00:17:29,630 dan memang, apa yang baik tentang itu adalah bahwa 3 adalah persis berapa kali 396 00:17:29,630 --> 00:17:33,320 Anda dapat membagi daftar panjang 8 lagi, dan lagi, 397 00:17:33,320 --> 00:17:36,160 dan lagi, sampai Anda meninggalkan dengan daftar hanya ukuran 1. 398 00:17:36,160 --> 00:17:36,660 Benar? 399 00:17:36,660 --> 00:17:40,790 8 pergi ke 4, pergi ke 2, pergi ke 1, dan itulah 400 00:17:40,790 --> 00:17:43,470 reflektif persis yang gambar kami memiliki beberapa saat yang lalu. 401 00:17:43,470 --> 00:17:47,160 Jadi kewarasan sedikit periksa ke mana logaritma sebenarnya terlibat. 402 00:17:47,160 --> 00:17:50,180 >> Jadi sekarang, apa lagi yang terlibat di sini? n. 403 00:17:50,180 --> 00:17:53,440 Jadi perhatikan bahwa setiap waktu aku membagi daftar, 404 00:17:53,440 --> 00:17:58,260 meskipun dalam urutan terbalik dalam sejarah di sini, saya masih melakukan hal-hal n. 405 00:17:58,260 --> 00:18:02,320 Langkah penggabungan diperlukan bahwa Aku menyentuh setiap salah satu nomor, 406 00:18:02,320 --> 00:18:05,060 untuk geser ke lokasi yang sesuai. 407 00:18:05,060 --> 00:18:10,760 Jadi meskipun ketinggian ini diagram adalah ukuran log n dari n atau 3, 408 00:18:10,760 --> 00:18:13,860 khusus, dengan kata lain, Saya melakukan tiga divisi di sini. 409 00:18:13,860 --> 00:18:18,800 Berapa banyak pekerjaan yang saya lakukan secara horizontal bersama grafik ini setiap kali? 410 00:18:18,800 --> 00:18:21,110 >> Yah, aku n langkah bekerja, karena jika saya sudah 411 00:18:21,110 --> 00:18:24,080 punya empat elemen dan empat elemen, dan saya perlu untuk menggabungkan mereka bersama-sama. 412 00:18:24,080 --> 00:18:26,040 Saya perlu melalui empat dan empat ini, 413 00:18:26,040 --> 00:18:28,123 akhirnya untuk menggabungkan mereka kembali menjadi delapan elemen. 414 00:18:28,123 --> 00:18:32,182 Jika sebaliknya aku punya delapan jari di sini, yang tidak saya lakukan, dan delapan 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Jika saya sudah mendapat empat jari di sini, 416 00:18:34,390 --> 00:18:37,380 yang saya lakukan, empat jari di sini, yang saya lakukan, 417 00:18:37,380 --> 00:18:40,590 maka itu sama Misalnya seperti sebelumnya, jika saya lakukan 418 00:18:40,590 --> 00:18:44,010 memiliki delapan jari meskipun dalam total, yang saya dapat, jenis, lakukan. 419 00:18:44,010 --> 00:18:47,950 Aku benar-benar bisa lakukan di sini, maka saya pasti bisa 420 00:18:47,950 --> 00:18:50,370 menggabungkan semua daftar ini ukuran 1 bersama-sama. 421 00:18:50,370 --> 00:18:54,050 Tapi aku pasti harus melihat di setiap elemen tepat satu kali. 422 00:18:54,050 --> 00:18:59,640 Jadi ketinggian proses ini adalah log n, lebar proses ini, sehingga untuk berbicara, 423 00:18:59,640 --> 00:19:02,490 adalah n, sehingga apa yang kita tampaknya untuk memiliki, akhirnya, adalah 424 00:19:02,490 --> 00:19:06,470 waktu berjalan dari ukuran n kali log n. 425 00:19:06,470 --> 00:19:08,977 >> Dengan kata lain, kami membagi daftar, log n kali, 426 00:19:08,977 --> 00:19:11,810 tapi setiap kali kita melakukan itu, kita memiliki menyentuh setiap salah satu elemen 427 00:19:11,810 --> 00:19:13,560 untuk menggabungkan mereka semua bersama-sama, yang 428 00:19:13,560 --> 00:19:18,120 itu n langkah, jadi kita harus n kali log n, atau sebagai seorang ilmuwan komputer akan mengatakan, 429 00:19:18,120 --> 00:19:20,380 asimtotik, yang akan menjadi kata yang besar 430 00:19:20,380 --> 00:19:22,810 untuk menggambarkan atas terikat pada waktu berjalan, 431 00:19:22,810 --> 00:19:28,010 kita berjalan di o besar log n waktu, sehingga untuk berbicara. 432 00:19:28,010 --> 00:19:31,510 >> Sekarang ini penting, karena ingat apa yang kali berjalan yang 433 00:19:31,510 --> 00:19:34,120 dengan bubble sort, dan seleksi macam, dan insertion sort, 434 00:19:34,120 --> 00:19:38,200 dan bahkan beberapa orang lain yang ada, n kuadrat adalah di mana kami berada di. 435 00:19:38,200 --> 00:19:39,990 Dan Anda dapat, jenis, lihat ini di sini. 436 00:19:39,990 --> 00:19:45,720 Jika n kuadrat jelas n kali n, tapi di sini kita memiliki n kali log n, 437 00:19:45,720 --> 00:19:48,770 dan kita sudah tahu dari seminggu nol, bahwa log n, logaritmik itu, 438 00:19:48,770 --> 00:19:50,550 lebih baik daripada sesuatu yang linear. 439 00:19:50,550 --> 00:19:52,930 Setelah semua, mengingat gambar dengan merah dan kuning 440 00:19:52,930 --> 00:19:56,500 dan garis-garis hijau yang kita menarik, yang baris logaritmik hijau jauh lebih rendah. 441 00:19:56,500 --> 00:20:00,920 Dan karena itu, jauh lebih baik dan lebih cepat dari garis kuning dan merah langsung, 442 00:20:00,920 --> 00:20:05,900 n kali log n adalah, memang, lebih baik dari n kali n, atau n kuadrat. 443 00:20:05,900 --> 00:20:09,110 >> Jadi kita tampaknya memiliki mengidentifikasi merge algoritma 444 00:20:09,110 --> 00:20:11,870 semacam yang berjalan di banyak waktu yang lebih cepat, dan memang, 445 00:20:11,870 --> 00:20:16,560 itu sebabnya, awal pekan ini, ketika kita melihat bahwa kontes antara gelembung 446 00:20:16,560 --> 00:20:20,750 sort, selection sort, dan menggabungkan semacam, menggabungkan semacam benar-benar menang. 447 00:20:20,750 --> 00:20:23,660 Dan memang, kita bahkan tidak menunggu untuk bubble sort dan seleksi semacam 448 00:20:23,660 --> 00:20:24,790 menyelesaikan. 449 00:20:24,790 --> 00:20:27,410 >> Sekarang mari kita satu lulus lainnya ini, dari sedikit lebih 450 00:20:27,410 --> 00:20:31,030 perspektif formal, hanya di kasus, ini bergema baik 451 00:20:31,030 --> 00:20:33,380 dari itu diskusi tingkat tinggi. 452 00:20:33,380 --> 00:20:34,880 Jadi, inilah algoritma lagi. 453 00:20:34,880 --> 00:20:36,770 Mari kita bertanya pada diri sendiri, apa waktu berjalan 454 00:20:36,770 --> 00:20:39,287 adalah ini algoritma berbagai langkah? 455 00:20:39,287 --> 00:20:41,620 Mari kita membaginya menjadi yang pertama kasus dan kasus kedua. 456 00:20:41,620 --> 00:20:46,280 IF dan ELSE Dalam kasus IF, JIKA n kurang dari 2, hanya kembali. 457 00:20:46,280 --> 00:20:47,580 Terasa seperti waktu yang konstan. 458 00:20:47,580 --> 00:20:50,970 Ini, jenis, seperti dua langkah, JIKA n kurang dari 2, kemudian kembali. 459 00:20:50,970 --> 00:20:54,580 Tapi seperti yang kita mengatakan pada hari Senin, waktu yang konstan, atau besar o dari 1, 460 00:20:54,580 --> 00:20:57,130 bisa dua langkah, tiga langkah, bahkan 1.000 langkah. 461 00:20:57,130 --> 00:20:59,870 Yang penting adalah bahwa hal itu sejumlah konstan langkah. 462 00:20:59,870 --> 00:21:03,240 Jadi kuning disorot pseudocode di sini berjalan di, kita akan menyebutnya, 463 00:21:03,240 --> 00:21:04,490 waktu yang konstan. 464 00:21:04,490 --> 00:21:06,780 Jadi lebih formal, dan kita akan to-- ini 465 00:21:06,780 --> 00:21:09,910 akan sejauh mana kita meresmikan hak ini sekarang-- T dari n, 466 00:21:09,910 --> 00:21:15,030 waktu berjalan dari masalah yang mengambil n somethings sebagai masukan, 467 00:21:15,030 --> 00:21:19,150 sama besar o dari satu, JIKA n kurang dari 2. 468 00:21:19,150 --> 00:21:20,640 Jadi itu tergantung pada itu. 469 00:21:20,640 --> 00:21:24,150 Jadi harus jelas, IF n kurang dari 2, kita memiliki daftar yang sangat singkat, maka 470 00:21:24,150 --> 00:21:29,151 waktu berjalan, T n, di mana n adalah 1 atau 0, dalam kasus yang sangat spesifik ini, 471 00:21:29,151 --> 00:21:30,650 itu hanya akan menjadi waktu yang konstan. 472 00:21:30,650 --> 00:21:32,691 Ini akan mengambil satu langkah, dua langkah, apa pun. 473 00:21:32,691 --> 00:21:33,950 Ini tetap jumlah langkah. 474 00:21:33,950 --> 00:21:38,840 >> Jadi bagian berair pasti harus dalam kasus lain di pseudocode. 475 00:21:38,840 --> 00:21:40,220 Kasus ELSE. 476 00:21:40,220 --> 00:21:44,870 Urutkan kiri setengah dari elemen, jenis hak setengah dari elemen, menggabungkan bagian diurutkan. 477 00:21:44,870 --> 00:21:46,800 Berapa lama masing-masing langkah mengambil? 478 00:21:46,800 --> 00:21:49,780 Nah, jika menjalankan waktu untuk memilah elemen n 479 00:21:49,780 --> 00:21:53,010 adalah, sebut saja sangat umum, T n, 480 00:21:53,010 --> 00:21:55,500 kemudian menyortir kiri setengah dari elemen 481 00:21:55,500 --> 00:21:59,720 adalah, jenis, seperti mengatakan, T dari n dibagi 2, 482 00:21:59,720 --> 00:22:03,000 dan juga memilah bagian kanan elemen adalah, jenis, seperti mengatakan, 483 00:22:03,000 --> 00:22:06,974 T dari n dibagi 2, dan kemudian penggabungan bagian diurutkan. 484 00:22:06,974 --> 00:22:08,890 Nah jika saya punya beberapa jumlah elemen di sini, 485 00:22:08,890 --> 00:22:11,230 seperti empat, dan beberapa nomor elemen di sini, seperti empat, 486 00:22:11,230 --> 00:22:14,650 dan saya harus menggabungkan masing-masing empat ini di, dan masing-masing empat di, salah satu 487 00:22:14,650 --> 00:22:17,160 setelah yang lain, sehingga akhirnya saya memiliki delapan unsur. 488 00:22:17,160 --> 00:22:20,230 Rasanya seperti itu besar o langkah n? 489 00:22:20,230 --> 00:22:23,500 Jika saya punya n jari dan masing- mereka harus bergabung ke tempat, 490 00:22:23,500 --> 00:22:25,270 itu seperti langkah n lain. 491 00:22:25,270 --> 00:22:27,360 >> Jadi memang dirumuskan secara, kita dapat mengekspresikan ini, 492 00:22:27,360 --> 00:22:29,960 meskipun scarily kecil pada awalnya Sekilas, tapi itu adalah sesuatu 493 00:22:29,960 --> 00:22:31,600 yang menangkap persis logika itu. 494 00:22:31,600 --> 00:22:35,710 Waktu berjalan, T n, IF n lebih besar dari atau sama dengan 2. 495 00:22:35,710 --> 00:22:42,500 Dalam hal ini, kasus ELSE, adalah T n dibagi 2, ditambah T N dibagi 2, 496 00:22:42,500 --> 00:22:45,320 ditambah besar o n, beberapa jumlah linear langkah, 497 00:22:45,320 --> 00:22:51,630 mungkin persis n, mungkin 2 kali n, tapi kira-kira, urutan n. 498 00:22:51,630 --> 00:22:54,060 Jadi itu juga, adalah bagaimana kita bisa mengungkapkan ini dirumuskan secara. 499 00:22:54,060 --> 00:22:56,809 Sekarang Anda tidak akan tahu ini kecuali Anda telah direkam dalam pikiran Anda, 500 00:22:56,809 --> 00:22:58,710 atau mencarinya di belakang buku teks, yang 501 00:22:58,710 --> 00:23:00,501 mungkin memiliki sedikit contekan pada akhirnya, 502 00:23:00,501 --> 00:23:03,940 tapi ini, memang, akan memberi kita besar o n log n, 503 00:23:03,940 --> 00:23:06,620 karena kekambuhan yang Anda lihat di sini di layar, 504 00:23:06,620 --> 00:23:09,550 jika Anda benar-benar melakukan itu, dengan jumlah tak terbatas contoh, 505 00:23:09,550 --> 00:23:13,000 atau Anda melakukannya dirumuskan secara, Anda akan melihat bahwa ini, karena formula ini 506 00:23:13,000 --> 00:23:17,100 sendiri adalah rekursif, dengan t n atas sesuatu di sebelah kanan, 507 00:23:17,100 --> 00:23:21,680 dan t dari n lebih di sebelah kiri, ini bisa sebenarnya dinyatakan, akhirnya, 508 00:23:21,680 --> 00:23:24,339 pergi sebagai besar dari n log n. 509 00:23:24,339 --> 00:23:26,130 Jika tidak yakin, itu baik untuk saat ini, hanya 510 00:23:26,130 --> 00:23:28,960 mengambil iman, bahwa itu, memang, apa kekambuhan yang mengarah ke, 511 00:23:28,960 --> 00:23:31,780 tapi ini hanya sedikit lebih dari Pendekatan matematis untuk mencari 512 00:23:31,780 --> 00:23:36,520 pada saat berjalan dari merge sort berdasarkan pseudocode-nya saja. 513 00:23:36,520 --> 00:23:39,030 >> Sekarang mari kita sedikit nafas dari semua itu, 514 00:23:39,030 --> 00:23:41,710 dan lihatlah sebuah mantan senator tertentu, yang 515 00:23:41,710 --> 00:23:44,260 mungkin terlihat sedikit akrab, yang duduk dengan Google Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, beberapa waktu lalu, untuk wawancara di atas panggung, di depan seluruh bunch 517 00:23:48,410 --> 00:23:53,710 orang, berbicara tentang akhirnya topik, itu cukup sekarang akrab. 518 00:23:53,710 --> 00:23:54,575 Mari lihat. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> ERIC SCHMIDT: Sekarang Senator, Anda berada di sini di Google, 521 00:24:03,890 --> 00:24:09,490 dan saya suka berpikir dari presiden sebagai wawancara kerja. 522 00:24:09,490 --> 00:24:11,712 Sekarang sulit untuk mendapatkan pekerjaan sebagai presiden. 523 00:24:11,712 --> 00:24:12,670 PRESIDEN OBAMA: Benar. 524 00:24:12,670 --> 00:24:13,940 ERIC SCHMIDT: Dan kau akan melakukan [tidak terdengar] sekarang. 525 00:24:13,940 --> 00:24:15,523 Ini juga sulit untuk mendapatkan pekerjaan di Google. 526 00:24:15,523 --> 00:24:17,700 PRESIDEN OBAMA: Benar. 527 00:24:17,700 --> 00:24:21,330 >> ERIC SCHMIDT: Kami memiliki pertanyaan, dan kami bertanya kandidat kami, 528 00:24:21,330 --> 00:24:24,310 dan yang satu ini dari Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> PRESIDEN OBAMA: OK. 530 00:24:25,890 --> 00:24:27,005 >> ERIC SCHMIDT: Apa? 531 00:24:27,005 --> 00:24:28,130 Kalian pikir aku bercanda? 532 00:24:28,130 --> 00:24:30,590 Ada di sini. 533 00:24:30,590 --> 00:24:33,490 Apa cara yang paling efisien untuk mengurutkan bilangan bulat juta 32 bit? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> PRESIDEN OBAMA: Well-- 536 00:24:38,979 --> 00:24:41,020 ERIC SCHMIDT: Kadang-kadang, mungkin aku minta maaf, maybe-- 537 00:24:41,020 --> 00:24:42,750 PRESIDEN OBAMA: Tidak, tidak, tidak, tidak, tidak, aku think-- 538 00:24:42,750 --> 00:24:43,240 ERIC SCHMIDT: Itu tidak itu-- 539 00:24:43,240 --> 00:24:45,430 PRESIDEN OBAMA: Saya berpikir, saya pikir gelembung 540 00:24:45,430 --> 00:24:46,875 semacam akan menjadi cara yang salah untuk pergi. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 ERIC SCHMIDT: Ayo. 543 00:24:50,535 --> 00:24:52,200 Yang mengatakan kepadanya ini? 544 00:24:52,200 --> 00:24:54,020 OKE. 545 00:24:54,020 --> 00:24:55,590 Saya tidak ilmu komputer on-- 546 00:24:55,590 --> 00:24:58,986 >> PRESIDEN OBAMA: Kami sudah mendapat mata-mata kita di sana. 547 00:24:58,986 --> 00:24:59,860 PROFESSOR: Baiklah. 548 00:24:59,860 --> 00:25:03,370 Mari kita tinggalkan di belakang kami sekarang dunia teoritis algoritma 549 00:25:03,370 --> 00:25:06,520 dalam analisis asimtotik daripadanya, dan kembali ke beberapa topik 550 00:25:06,520 --> 00:25:09,940 dari minggu nol dan satu, dan mulai untuk menghapus beberapa roda pelatihan, 551 00:25:09,940 --> 00:25:10,450 jika Anda mau. 552 00:25:10,450 --> 00:25:13,241 Sehingga Anda benar-benar memahami akhirnya dari bawah ke atas, apa 553 00:25:13,241 --> 00:25:16,805 terjadi di bawah tenda, ketika Anda menulis, mengkompilasi, dan menjalankan program. 554 00:25:16,805 --> 00:25:19,680 Ingat khususnya, bahwa ini adalah program C pertama kita melihat, 555 00:25:19,680 --> 00:25:22,840 kanonik, program yang sederhana macam, relatif berbicara, 556 00:25:22,840 --> 00:25:24,620 dimana, mencetak, Hello World. 557 00:25:24,620 --> 00:25:27,610 Dan ingat bahwa aku mengatakan, proses bahwa kode sumber melewati 558 00:25:27,610 --> 00:25:28,430 adalah persis ini. 559 00:25:28,430 --> 00:25:31,180 Anda mengambil kode sumber Anda, lulus melalui compiler, seperti dentang, 560 00:25:31,180 --> 00:25:34,650 dan keluar datang kode objek, yang mungkin terlihat seperti ini, nol dan satu 561 00:25:34,650 --> 00:25:37,880 bahwa CPU komputer, pusat unit pengolahan atau otak, 562 00:25:37,880 --> 00:25:39,760 akhirnya mengerti. 563 00:25:39,760 --> 00:25:42,460 >> Ternyata itu adalah sedikit terlalu menyederhanakan, 564 00:25:42,460 --> 00:25:44,480 bahwa kita sekarang dalam posisi untuk menggoda terpisah 565 00:25:44,480 --> 00:25:46,720 untuk memahami apa yang benar-benar telah terjadi di bawah tenda 566 00:25:46,720 --> 00:25:48,600 setiap kali Anda menjalankan Dentang, atau lebih umum, 567 00:25:48,600 --> 00:25:53,040 setiap kali Anda membuat sebuah program, menggunakan Membuat dan CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Secara khusus, hal-hal seperti ini pertama dihasilkan, 569 00:25:56,760 --> 00:25:58,684 ketika Anda pertama kali mengkompilasi program Anda. 570 00:25:58,684 --> 00:26:00,600 Dengan kata lain, ketika Anda mengambil kode sumber Anda 571 00:26:00,600 --> 00:26:04,390 dan kompilasi, apa yang pertama yang dikeluarkan oleh dentang 572 00:26:04,390 --> 00:26:06,370 adalah sesuatu yang dikenal sebagai kode assembly. 573 00:26:06,370 --> 00:26:08,990 Dan pada kenyataannya, tampak persis seperti ini. 574 00:26:08,990 --> 00:26:11,170 >> Aku berlari perintah di baris perintah sebelumnya. 575 00:26:11,170 --> 00:26:16,260 Hello.c dentang dasbor modal s, dan ini menciptakan sebuah file 576 00:26:16,260 --> 00:26:19,490 bagi saya disebut hello.s, dalam yang tepat 577 00:26:19,490 --> 00:26:22,290 isi ini, dan sedikit lebih di atas dan sedikit lebih bawah, 578 00:26:22,290 --> 00:26:25,080 tapi aku sudah menempatkan juiciest Informasi di sini di layar. 579 00:26:25,080 --> 00:26:29,190 Dan jika Anda melihat dekat, Anda akan melihat setidaknya beberapa kata kunci akrab. 580 00:26:29,190 --> 00:26:31,330 Kami memiliki utama di atas. 581 00:26:31,330 --> 00:26:35,140 Kami telah printf turun di tengah. 582 00:26:35,140 --> 00:26:38,670 Dan kami juga memiliki hello world backslash n dalam tanda kutip di bawah. 583 00:26:38,670 --> 00:26:42,450 >> Dan segala sesuatu yang lain di sini adalah petunjuk tingkat yang sangat rendah 584 00:26:42,450 --> 00:26:45,500 bahwa CPU komputer mengerti. 585 00:26:45,500 --> 00:26:50,090 Instruksi CPU yang bergerak memori sekitar, bahwa string beban dari memori, 586 00:26:50,090 --> 00:26:52,750 dan akhirnya, cetak hal di layar. 587 00:26:52,750 --> 00:26:56,780 Sekarang apa yang terjadi meskipun setelah kode assembly ini dihasilkan? 588 00:26:56,780 --> 00:26:59,964 Pada akhirnya, Anda lakukan, memang, masih menghasilkan kode objek. 589 00:26:59,964 --> 00:27:02,630 Tapi langkah-langkah yang harus benar-benar telah terjadi di bawah tenda 590 00:27:02,630 --> 00:27:04,180 terlihat sedikit lebih seperti ini. 591 00:27:04,180 --> 00:27:08,390 Source code menjadi kode assembly, yang kemudian menjadi kode objek, 592 00:27:08,390 --> 00:27:11,930 dan kata-kata operasi di sini adalah bahwa, ketika Anda mengkompilasi kode sumber Anda, 593 00:27:11,930 --> 00:27:16,300 keluar datang kode perakitan, dan kemudian ketika Anda merakit kode perakitan Anda, 594 00:27:16,300 --> 00:27:17,800 keluar datang kode objek. 595 00:27:17,800 --> 00:27:20,360 >> Sekarang dentang super canggih, seperti banyak kompiler, 596 00:27:20,360 --> 00:27:23,151 dan itu semua langkah ini bersama-sama, dan itu tidak selalu 597 00:27:23,151 --> 00:27:25,360 output apapun antara file yang Anda bahkan dapat melihat. 598 00:27:25,360 --> 00:27:28,400 Itu hanya mengkompilasi hal, yang merupakan istilah umum yang 599 00:27:28,400 --> 00:27:30,000 menggambarkan seluruh proses ini. 600 00:27:30,000 --> 00:27:32,000 Tetapi jika Anda benar-benar ingin menjadi tertentu, ada 601 00:27:32,000 --> 00:27:34,330 lebih banyak terjadi di sana juga. 602 00:27:34,330 --> 00:27:38,860 >> Tapi mari kita juga mempertimbangkan bahwa bahkan sekarang bahwa program super sederhana, hello.c, 603 00:27:38,860 --> 00:27:40,540 disebut fungsi. 604 00:27:40,540 --> 00:27:41,870 Ini disebut printf. 605 00:27:41,870 --> 00:27:46,900 Tapi aku tidak menulis printf, memang, yang datang dengan c, sehingga untuk berbicara. 606 00:27:46,900 --> 00:27:51,139 Ini adalah recall fungsi yang dideklarasikan di io.h standar, yang 607 00:27:51,139 --> 00:27:53,180 adalah file header, yang adalah topik kita akan benar-benar 608 00:27:53,180 --> 00:27:55,780 menyelam ke kedalaman lebih lama. 609 00:27:55,780 --> 00:27:58,000 Tapi file header biasanya disertai 610 00:27:58,000 --> 00:28:02,920 oleh file kode, berkas kode sumber, sehingga seperti terdapat io.h. standar 611 00:28:02,920 --> 00:28:05,930 >> Beberapa waktu yang lalu, seseorang, atau someones, juga menulis 612 00:28:05,930 --> 00:28:11,040 file bernama io.c standar, di yang definisi yang sebenarnya, 613 00:28:11,040 --> 00:28:15,220 atau implementasi dari printf, dan tandan fungsi lainnya, 614 00:28:15,220 --> 00:28:16,870 benar-benar ditulis. 615 00:28:16,870 --> 00:28:22,140 Jadi mengingat bahwa, jika kita mempertimbangkan memiliki di sini di sebelah kiri, hello.c, bahwa ketika 616 00:28:22,140 --> 00:28:26,250 disusun, memberi kita hello.s, bahkan jika Dentang tidak mengganggu tabungan di tempat 617 00:28:26,250 --> 00:28:31,360 kita bisa melihat itu, dan bahwa kode perakitan akan dirakit menjadi hello.o, yang 618 00:28:31,360 --> 00:28:34,630 adalah, memang, nama default diberikan setiap kali Anda mengkompilasi sumber 619 00:28:34,630 --> 00:28:39,350 kode ke dalam kode objek, tetapi tidak cukup siap untuk melaksanakannya belum, 620 00:28:39,350 --> 00:28:41,460 karena langkah lain harus terjadi, dan memiliki 621 00:28:41,460 --> 00:28:44,440 telah terjadi selama beberapa masa lalu minggu, mungkin tanpa sepengetahuan Anda. 622 00:28:44,440 --> 00:28:47,290 >> Khusus di suatu tempat di CS50 IDE, dan ini, 623 00:28:47,290 --> 00:28:49,870 juga, akan menjadi sedikit penyederhanaan sejenak, 624 00:28:49,870 --> 00:28:54,670 ada, atau ada pada waktu, file bernama io.c standar, 625 00:28:54,670 --> 00:28:58,440 bahwa seseorang dikompilasi ke io.s standar atau setara, 626 00:28:58,440 --> 00:29:02,010 bahwa seseorang kemudian dirakit ke io.o standar, 627 00:29:02,010 --> 00:29:04,600 atau ternyata menjadi File yang sedikit berbeda 628 00:29:04,600 --> 00:29:07,220 format yang dapat memiliki yang berbeda mengajukan perpanjangan sama sekali, 629 00:29:07,220 --> 00:29:11,720 tetapi dalam teori dan konseptual, tepatnya langkah-langkah harus terjadi dalam beberapa bentuk. 630 00:29:11,720 --> 00:29:14,060 Yang mengatakan, bahwa sekarang ketika saya sedang menulis sebuah program, 631 00:29:14,060 --> 00:29:17,870 hello.c, yang hanya mengatakan, halo dunia, dan aku menggunakan kode orang lain 632 00:29:17,870 --> 00:29:22,480 seperti printf, yang dulunya di atas waktu, dalam sebuah file bernama io.c standar, 633 00:29:22,480 --> 00:29:26,390 kemudian entah bagaimana aku harus mengambil saya kode objek, nol dan yang, 634 00:29:26,390 --> 00:29:29,260 dan objek orang itu kode, atau nol dan satu, 635 00:29:29,260 --> 00:29:34,970 dan entah bagaimana menghubungkan mereka bersama-sama ke satu file akhir, yang disebut halo, yang 636 00:29:34,970 --> 00:29:38,070 memiliki semua nol dan yang dari fungsi utama saya, 637 00:29:38,070 --> 00:29:40,830 dan semua nol dan orang-orang untuk printf. 638 00:29:40,830 --> 00:29:44,900 >> Dan memang, bahwa proses terakhir adalah disebut, menghubungkan kode objek. 639 00:29:44,900 --> 00:29:47,490 Output yang adalah file executable. 640 00:29:47,490 --> 00:29:49,780 Jadi dalam keadilan, di akhir hari, tidak ada 641 00:29:49,780 --> 00:29:52,660 telah berubah sejak satu minggu, ketika kita pertama mulai menyusun program. 642 00:29:52,660 --> 00:29:55,200 Memang, semua ini telah terjadi di bawah kap mesin, 643 00:29:55,200 --> 00:29:57,241 tapi sekarang kami dalam posisi di mana kita bisa benar-benar 644 00:29:57,241 --> 00:29:58,794 menggoda selain berbagai langkah. 645 00:29:58,794 --> 00:30:00,710 Dan memang, di akhir hari, kami masih 646 00:30:00,710 --> 00:30:04,480 kiri dengan nol dan satu, yang sebenarnya Shalawat besar sekarang 647 00:30:04,480 --> 00:30:08,620 dengan kemampuan lain dari C, yang kita tidak harus meningkatkan kemungkinan besar 648 00:30:08,620 --> 00:30:11,250 sampai saat ini, dikenal sebagai operator bitwise. 649 00:30:11,250 --> 00:30:15,220 Dengan kata lain, sejauh ini, kapan saja kita sudah berurusan dengan data di C atau variabel di C, 650 00:30:15,220 --> 00:30:17,660 kami sudah hal-hal seperti karakter dan mengapung dan ins 651 00:30:17,660 --> 00:30:21,990 dan rindu dan ganda dan seperti, tapi semua orang setidaknya delapan bit. 652 00:30:21,990 --> 00:30:25,550 Kami sudah pernah belum mampu memanipulasi bit individu, 653 00:30:25,550 --> 00:30:28,970 meskipun bit individu, kita tahu, bisa mewakili 0 dan 1. 654 00:30:28,970 --> 00:30:32,640 Sekarang ternyata bahwa di C, Anda bisa mendapatkan akses ke bit individu, 655 00:30:32,640 --> 00:30:35,530 jika Anda tahu sintaks, yang dapat digunakan untuk mendapatkan mereka. 656 00:30:35,530 --> 00:30:38,010 >> Jadi mari kita lihat di operator bitwise. 657 00:30:38,010 --> 00:30:41,700 Jadi digambarkan di sini adalah beberapa simbol yang kami, jenis, jenis, terlihat sebelumnya. 658 00:30:41,700 --> 00:30:45,580 Saya melihat ampersand, vertikal bar, dan beberapa orang lain juga, 659 00:30:45,580 --> 00:30:49,430 dan ingat bahwa ampersand ampersand adalah sesuatu yang telah kita lihat sebelumnya. 660 00:30:49,430 --> 00:30:54,060 Logika AND operator, di mana Anda memiliki dua dari mereka bersama-sama, atau logika OR 661 00:30:54,060 --> 00:30:56,300 operator, di mana Anda memiliki dua bar vertikal. 662 00:30:56,300 --> 00:31:00,550 Operator bitwise, yang kita akan melihat beroperasi pada bit individual, 663 00:31:00,550 --> 00:31:03,810 hanya menggunakan ampersand tunggal, tunggal vertikal, simbol tanda sisipan 664 00:31:03,810 --> 00:31:06,620 datang berikutnya, kecil tilde, dan kemudian meninggalkan 665 00:31:06,620 --> 00:31:08,990 braket kiri braket, atau braket kanan braket yang tepat. 666 00:31:08,990 --> 00:31:10,770 Masing-masing memiliki arti yang berbeda. 667 00:31:10,770 --> 00:31:11,950 >> Bahkan, mari kita lihat. 668 00:31:11,950 --> 00:31:16,560 Mari kita pergi sekolah tua hari ini, dan penggunaan layar sentuh dari masa lampau, 669 00:31:16,560 --> 00:31:18,002 dikenal sebagai papan tulis. 670 00:31:18,002 --> 00:31:19,710 Dan papan tulis ini akan memungkinkan kita 671 00:31:19,710 --> 00:31:27,360 untuk mengungkapkan beberapa simbol yang cukup sederhana, atau lebih tepatnya beberapa rumus cukup sederhana, 672 00:31:27,360 --> 00:31:29,560 yang kita dapat kemudian akhirnya leverage, dalam rangka 673 00:31:29,560 --> 00:31:33,230 untuk mengakses individu bit dalam program C. 674 00:31:33,230 --> 00:31:34,480 Dengan kata lain, mari kita lakukan ini. 675 00:31:34,480 --> 00:31:37,080 Mari kita pertama berbicara untuk sejenak tentang ampersand, 676 00:31:37,080 --> 00:31:39,560 yang merupakan bitwise DAN operator. 677 00:31:39,560 --> 00:31:42,130 Dengan kata lain, ini adalah operator yang memungkinkan 678 00:31:42,130 --> 00:31:45,930 saya memiliki variabel kiri biasanya, dan variabel kanan, 679 00:31:45,930 --> 00:31:50,640 atau nilai individu, bahwa jika kita DAN mereka bersama-sama, memberi saya hasil akhir. 680 00:31:50,640 --> 00:31:51,560 Jadi apa yang saya maksud? 681 00:31:51,560 --> 00:31:54,840 Jika dalam sebuah program, Anda memiliki variabel yang menyimpan salah satu nilai-nilai ini, 682 00:31:54,840 --> 00:31:58,000 atau mari kita tetap sederhana, dan hanya menulis nol dan satu secara individual, 683 00:31:58,000 --> 00:32:00,940 berikut adalah cara operator ampersand bekerja. 684 00:32:00,940 --> 00:32:06,400 0 ampersand 0 akan sama 0. 685 00:32:06,400 --> 00:32:07,210 Sekarang kenapa begitu? 686 00:32:07,210 --> 00:32:09,291 >> Ini sangat mirip dengan Ekspresi Boolean, 687 00:32:09,291 --> 00:32:10,540 yang telah kita bahas sejauh ini. 688 00:32:10,540 --> 00:32:15,800 Jika Anda berpikir setelah semua, 0 adalah palsu, 0 adalah palsu, palsu dan palsu 689 00:32:15,800 --> 00:32:18,720 adalah, seperti yang telah kita bahas logis, juga palsu. 690 00:32:18,720 --> 00:32:20,270 Jadi kita mendapatkan 0 sini juga. 691 00:32:20,270 --> 00:32:24,390 Jika Anda mengambil 0 ampersand 1, baik itu juga, 692 00:32:24,390 --> 00:32:29,890 akan menjadi 0, karena untuk ini ekspresi kiri untuk menjadi kenyataan atau 1, 693 00:32:29,890 --> 00:32:32,360 itu akan perlu untuk menjadi kenyataan dan benar. 694 00:32:32,360 --> 00:32:36,320 Tapi di sini kita memiliki palsu dan benar, atau 0 dan 1. 695 00:32:36,320 --> 00:32:42,000 Sekarang lagi, jika kita memiliki 1 ampersand 0, itu juga, akan menjadi 0, 696 00:32:42,000 --> 00:32:47,240 dan jika kita memiliki 1 ampersand 1, akhirnya kita memiliki 1 bit. 697 00:32:47,240 --> 00:32:50,340 Jadi dengan kata lain, kita tidak melakukan sesuatu yang menarik dengan operator ini 698 00:32:50,340 --> 00:32:51,850 dulu, operator ampersand ini. 699 00:32:51,850 --> 00:32:53,780 Ini adalah bitwise DAN operator. 700 00:32:53,780 --> 00:32:57,290 Tetapi ini adalah bahan melalui mana kita dapat melakukan 701 00:32:57,290 --> 00:32:59,240 hal-hal menarik, seperti yang kita akan segera melihat. 702 00:32:59,240 --> 00:33:02,790 >> Sekarang mari kita lihat hanya satu bar vertikal di sini di sebelah kanan. 703 00:33:02,790 --> 00:33:06,710 Jika saya memiliki 0 bit dan saya OR dengan, bitwise 704 00:33:06,710 --> 00:33:11,030 OR operator, yang lain 0 bit, itu akan memberi saya 0. 705 00:33:11,030 --> 00:33:17,540 Jika saya mengambil bit 0 dan OR dengan 1 bit, maka aku akan mendapatkan 1. 706 00:33:17,540 --> 00:33:19,830 Dan pada kenyataannya, hanya untuk kejelasan, biarkan aku kembali, 707 00:33:19,830 --> 00:33:23,380 sehingga bar vertikal saya tidak salah untuk 1 itu. 708 00:33:23,380 --> 00:33:26,560 Biarkan saya menulis ulang semua 1 saya sedikit lebih 709 00:33:26,560 --> 00:33:32,700 jelas, sehingga kita selanjutnya melihat, jika saya telah 1 atau 0, itu akan menjadi 1, 710 00:33:32,700 --> 00:33:39,060 dan jika saya memiliki 1 atau 1 itu, juga, akan menjadi 1. 711 00:33:39,060 --> 00:33:42,900 Sehingga Anda dapat melihat secara logis bahwa OR Operator berperilaku sangat berbeda. 712 00:33:42,900 --> 00:33:48,070 Ini memberi saya 0 OR 0 memberi saya 0, tapi setiap kombinasi lain memberi saya 1. 713 00:33:48,070 --> 00:33:52,480 Selama aku punya satu 1 di rumus, hasilnya akan menjadi 1. 714 00:33:52,480 --> 00:33:55,580 >> Sebaliknya dengan DAN operator, ampersand, 715 00:33:55,580 --> 00:34:00,940 hanya jika saya memiliki dua 1 dalam persamaan, saya benar-benar mendapatkan 1 keluar. 716 00:34:00,940 --> 00:34:02,850 Sekarang ada beberapa lainnya operator juga. 717 00:34:02,850 --> 00:34:04,810 Salah satunya adalah sedikit lebih terlibat. 718 00:34:04,810 --> 00:34:07,980 Jadi biarkan aku pergi ke depan dan menghapus ini untuk membebaskan beberapa ruang. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Dan mari kita lihat simbol sisipan, untuk sesaat. 721 00:34:16,460 --> 00:34:18,210 Ini biasanya karakter Anda dapat mengetik 722 00:34:18,210 --> 00:34:21,420 pada shift memegang keyboard dan maka salah satu nomor di atas US Anda 723 00:34:21,420 --> 00:34:22,250 Keyboard. 724 00:34:22,250 --> 00:34:26,190 >> Jadi ini adalah eksklusif OR operator, eksklusif OR. 725 00:34:26,190 --> 00:34:27,790 Jadi kita hanya melihat operator OR. 726 00:34:27,790 --> 00:34:29,348 Ini adalah eksklusif OR operator. 727 00:34:29,348 --> 00:34:30,639 Apa sebenarnya perbedaan? 728 00:34:30,639 --> 00:34:34,570 Nah mari kita lihat saja rumus, dan menggunakan ini sebagai bahan akhirnya. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Aku akan katakan adalah selalu 0. 731 00:34:39,650 --> 00:34:41,400 Itulah definisi XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 akan menjadi 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 akan menjadi 1, dan 1 XOR 1 akan menjadi? 734 00:34:58,810 --> 00:34:59,890 Salah? 735 00:34:59,890 --> 00:35:00,520 Atau benar? 736 00:35:00,520 --> 00:35:01,860 Saya tidak tahu. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Sekarang apa yang terjadi di sini? 739 00:35:04,700 --> 00:35:06,630 Nah berpikir tentang nama operator ini. 740 00:35:06,630 --> 00:35:09,980 Eksklusif OR, sehingga sebagai Nama, jenis, menunjukkan, 741 00:35:09,980 --> 00:35:13,940 jawabannya hanya akan menjadi 1 jika input yang eksklusif, 742 00:35:13,940 --> 00:35:15,560 eksklusif yang berbeda. 743 00:35:15,560 --> 00:35:18,170 Jadi di sini input adalah sama, sehingga output adalah 0. 744 00:35:18,170 --> 00:35:20,700 Berikut input adalah sama, sehingga output adalah 0. 745 00:35:20,700 --> 00:35:25,640 Berikut adalah output yang berbeda, mereka eksklusif, dan output adalah 1. 746 00:35:25,640 --> 00:35:28,190 Sehingga sangat mirip dengan DAN, itu sangat mirip, 747 00:35:28,190 --> 00:35:32,760 atau lebih tepatnya itu sangat mirip dengan OR, tapi hanya dengan cara eksklusif. 748 00:35:32,760 --> 00:35:36,210 Yang satu ini tidak lagi menjadi 1, karena kita memiliki dua 1 ini, 749 00:35:36,210 --> 00:35:38,621 dan tidak eksklusif, hanya salah satu dari mereka. 750 00:35:38,621 --> 00:35:39,120 Baiklah. 751 00:35:39,120 --> 00:35:40,080 Bagaimana dengan orang lain? 752 00:35:40,080 --> 00:35:44,220 Nah tilde, sementara itu, benar bagus dan sederhana, untungnya. 753 00:35:44,220 --> 00:35:46,410 Dan ini adalah unary operator, yang berarti 754 00:35:46,410 --> 00:35:50,400 itu diterapkan hanya satu masukan, satu operan, sehingga untuk berbicara. 755 00:35:50,400 --> 00:35:51,800 Bukan ke kiri dan kanan. 756 00:35:51,800 --> 00:35:56,050 Dengan kata lain, jika Anda mengambil tilde dari 0, jawabannya akan menjadi sebaliknya. 757 00:35:56,050 --> 00:35:59,710 Dan jika Anda mengambil tilde dari 1, Jawabannya akan ada sebaliknya. 758 00:35:59,710 --> 00:36:02,570 Jadi operator tilde adalah cara meniadakan sedikit, 759 00:36:02,570 --> 00:36:06,000 atau membalik sedikit dari 0-1, atau 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Dan yang membuat kita akhirnya dengan hanya dua operator akhir, 761 00:36:09,820 --> 00:36:13,840 disebut pergeseran kiri, dan disebut operator shift kanan. 762 00:36:13,840 --> 00:36:16,620 Mari kita lihat bagaimana mereka bekerja. 763 00:36:16,620 --> 00:36:20,780 Operator shift kiri, ditulis dengan dua kurung sudut seperti itu, 764 00:36:20,780 --> 00:36:22,110 beroperasi sebagai berikut. 765 00:36:22,110 --> 00:36:27,390 Jika saya masukan, atau operan saya, ke kiri Operator pergeseran cukup hanya 1. 766 00:36:27,390 --> 00:36:33,750 Dan saya kemudian memberitahu komputer untuk meninggalkan pergeseran yang 1, mengatakan tujuh tempat, 767 00:36:33,750 --> 00:36:37,150 hasilnya adalah seolah-olah saya mengambil 1, dan memindahkannya 768 00:36:37,150 --> 00:36:40,160 tujuh tempat lebih ke kiri, dan secara default, 769 00:36:40,160 --> 00:36:42,270 kita akan berasumsi bahwa ruang ke kanan 770 00:36:42,270 --> 00:36:44,080 akan menjadi empuk dengan nol. 771 00:36:44,080 --> 00:36:50,316 Dengan kata lain, 1 kiri pergeseran 7 akan memberi saya bahwa 1, diikuti oleh 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nol. 773 00:36:54,060 --> 00:36:57,380 Jadi dengan cara, memungkinkan Anda untuk mengambil sejumlah kecil seperti 1, 774 00:36:57,380 --> 00:37:00,740 dan jelas membuatnya lebih banyak, jauh lebih besar dengan cara ini, 775 00:37:00,740 --> 00:37:06,460 tapi kami benar-benar akan melihat pendekatan yang lebih pintar untuk itu 776 00:37:06,460 --> 00:37:08,080 sebaliknya, juga, 777 00:37:08,080 --> 00:37:08,720 >> Baiklah. 778 00:37:08,720 --> 00:37:10,060 Itu saja untuk minggu tiga. 779 00:37:10,060 --> 00:37:11,400 Kita akan melihat Anda waktu berikutnya. 780 00:37:11,400 --> 00:37:12,770 Ini adalah CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [MUSIC PLAYING] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Dia berada di snack bar makan es krim cokelat. 784 00:37:25,766 --> 00:37:28,090 Dia memiliki seluruh wajahnya. 785 00:37:28,090 --> 00:37:30,506 Dia mengenakan bahwa coklat seperti janggut 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Apa yang kamu lakukan? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Apa? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Apakah Anda hanya ganda dip? 790 00:37:36,800 --> 00:37:38,585 Anda ganda mencelupkan chip. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Permisi. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Anda mencelupkan chip, Anda menggigit, dan Anda mencelupkan lagi. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Jadi itu seperti menempatkan mulut seluruh hak Anda di dip. 795 00:37:48,440 --> 00:37:52,400 Lain kali Anda mengambil sebuah chip, hanya mencelupkan sekali, dan mengakhirinya. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Anda tahu apa, Dan? 797 00:37:53,890 --> 00:37:58,006 Anda mencelupkan cara yang ingin Anda mencelupkan. 798 00:37:58,006 --> 00:38:01,900 Aku akan mencelupkan cara yang saya ingin mencelupkan. 799 00:38:01,900 --> 00:38:03,194