[Bermain muzik] DAVID MALAN: Baiklah. Baiklah, selamat datang kembali. Jadi, ini adalah Minggu 4, permulaan itu, sudah. Dan anda akan ingat bahawa minggu lepas, kita meletakkan kod diperuntukkan untuk hanya sedikit dan kita mula bercakap lebih sedikit peringkat tinggi, kira-kira perkara-perkara seperti mencari dan menyusun, yang walaupun idea-idea yang agak mudah, adalah wakil kelas masalah anda akan mula untuk menyelesaikan terutamanya kerana anda mula berfikir tentang akhir projek dan penyelesaian yang menarik anda mungkin mempunyai masalah sebenar. Sekarang jenis buih adalah salah satu yang paling mudah algoritma itu, dan ia bekerja dengan mempunyai nombor-nombor kecil dalam senarai atau dalam pelbagai jenis buih mereka untuk sampai ke atas, dan jumlah yang besar bergerak dengan cara mereka turun ke akhir senarai itu. Dan ingat bahawa kita boleh menggambarkan gelembung yang amat sedikit sesuatu seperti ini. Jadi biarlah saya pergi ke hadapan dan klik Mula. Saya diprapilih jenis gelembung. Dan jika anda masih ingat bahawa biru tinggi garis mewakili nombor besar, kecil garis biru mewakili jumlah yang kecil, kerana kita pergi melalui ini sekali lagi dan lagi dan lagi, membandingkan dua bar di sebelah setiap lain dalam merah, kita akan menukar terbesar dan yang paling kecil jika mereka berada di luar perintah. Jadi ini akan pergi dan pergi dan pergi pada, dan anda akan melihat bahawa yang lebih besar unsur-unsur yang membuat cara mereka ke betul, dan unsur-unsur yang lebih kecil membuat jalan mereka ke kiri. Tetapi kita mula mengira kecekapan, yang kualiti algoritma ini. Dan kita berkata bahawa dalam yang paling teruk kes, algoritma ini mengambil kira-kira berapa banyak langkah-langkah? Jadi n kuasa dua. Dan apa yang n? PENONTON: Bilangan unsur-unsur. DAVID MALAN: Jadi n adalah beberapa elemen. Dan dengan itu kita akan melakukan ini kerap. Bila-bila masa kita mahu bercakap tentang saiz satu masalah atau saiz yang input, atau jumlah masa yang diperlukan untuk menghasilkan output, kita akan hanya umum apa sahaja input adalah seperti n. Jadi kembali dalam Minggu 0, bilangan muka surat di dalam buku telefon adalah n. Bilangan pelajar dalam bilik itu n. Jadi di sini, juga, kami sedang mengikuti corak itu. Sekarang n kuasa dua tidak begitu cepat, jadi kami cuba untuk melakukan yang lebih baik. Dan supaya kita melihat beberapa algoritma yang lain, antaranya adalah jenis pilihan. Jadi apapun pemilihan adalah sedikit berbeza. Ia adalah hampir mudah, saya berani mengatakan, di mana saya bermula pada permulaan senarai sukarelawan kami dan saya sekali lagi dan lagi dan lagi telah melalui senarai, memetik daripada yang paling kecil elemen pada satu masa dan meletakkan dia atau beliau pada awal senarai. Tetapi ini juga, apabila kita mula berfikir melalui matematik dan lebih besar gambar, berfikir tentang berapa kali Saya telah pergi ke belakang dan sebagainya dan belakang dan sebagainya, kita berkata dalam kes terburuk, jenis pilihan, juga, adalah apa? n kuasa dua. Kini di dunia sebenar, ia mungkin benar-benar menjadi sedikit lebih cepat. Kerana sekali lagi, saya tidak perlu menyimpan berundur apabila saya telah disusun yang unsur-unsur yang paling kecil. Tetapi jika kita berfikir tentang yang sangat besar n, dan jika anda jenis keluar melakukan matematik sebagai Saya di papan, dengan n kuasa dua tolak sesuatu, segala-galanya selain n kuasa dua, sekali n mendapat benar-benar besar, tidak benar-benar perkara yang banyak. Jadi sebagai saintis komputer, kita menyelesaikan satu menutup mata kepada yang lebih kecil faktor dan tumpuan hanya pada faktor dalam satu ungkapan yang akan membuat perbezaan terbesar. Nah, akhirnya, kita melihat pada jenis kemasukan. Dan ini adalah sama dalam semangat, tetapi bukannya melalui iterative dan pilih salah satu elemen yang paling kecil di masa, saya sebaliknya mengambil tangan saya telah diuruskan, dan saya membuat keputusan, semua betul, anda tergolong di sini. Kemudian saya berpindah ke elemen yang seterusnya dan memutuskan bahawa dia atau dia tergolong di sini. Dan kemudian saya berpindah dan pada. Dan saya mungkin kepada, sepanjang jalan, beralih lelaki ini untuk memberi ruang untuk mereka. Jadi yang jenis pembalikan mental satu jenis pilihan yang kita dipanggil jenis kemasukan. Jadi topik-topik ini berlaku dalam dunia sebenar. Hanya beberapa tahun yang lalu, apabila tertentu senator telah menjalankan untuk presiden, Eric Schmidt, pada masa itu Ketua Pegawai Eksekutif Google, sebenarnya mempunyai peluang menemubual beliau. Dan kita fikir kita akan berkongsi YouTube klip untuk anda di sini, jika kita boleh bertukar sehingga kelantangan. [MAIN SEMULA VIDEO] -Sekarang, Senator, anda berada di sini di Google, dan saya suka untuk berfikir presiden seperti temu duga kerja. [Ketawa] -Kini ia Adalah sukar untuk mendapatkan kerja sebagai presiden. Dan anda akan melalui menggigil sekarang. Ia juga sukar untuk mendapatkan pekerjaan di Google. Kami mempunyai soalan dan kita minta calon-calon kita soalan. Dan yang satu ini dari Larry Schwimmer. [Ketawa] -Kamu fikir saya bergurau? Ia adalah di sini. Apakah cara yang paling berkesan untuk menyelesaikan satu juta dua integer-bit? [Ketawa] -Well, uh - : Saya minta maaf. Mungkin kita perlu - -Tidak, tidak, tidak, tidak, tidak. -Itu bukan satu - OK. -Saya rasa jenis gelembung akan menjadi cara yang salah untuk pergi. [Ketawa] [Bersorak dan tepukan] -Ayuh, yang memberitahu dia ini? OK. [AKHIR VIDEO MAIN SEMULA] DAVID MALAN: Jadi ada anda mempunyai ia. Oleh itu, kita mula mengira ini berjalan kali, jadi untuk bercakap, dengan sesuatu dipanggil notasi asimptot, yang merupakan hanya merujuk kepada jenis kita beralih mata yang buta kepada faktor-faktor yang lebih kecil dan hanya melihat pada masa yang berjalan, prestasi ini algoritma, sebagai n mendapat benar-benar besar dari masa ke masa. Dan supaya kita diperkenalkan besar O. Dan besar O sesuatu yang diwakili sehingga kami menyangka bahawa sebagai satu terikat atas. Dan sebenarnya, Barry, kita boleh mengurangkan daripada mikrofon sedikit? Kami fikir ini adalah terikat atas. Begitu besar O n cara kuasa bahawa dalam kes terburuk, sesuatu seperti jenis pilihan akan mengambil n langkah persegi. Atau sesuatu seperti jenis kemasukan n akan langkah-langkah dua. Sekarang untuk sesuatu seperti memasukkan apapun, apa yang mana-mana yang paling teruk? Memandangkan pelbagai, apa yang paling teruk senario yang mungkin anda mungkin mendapati diri anda berhadapan dengan? Ia adalah benar-benar ke belakang, bukan? Kerana jika ia adalah benar-benar ke belakang, anda perlu melakukan banyak keseluruhan kerja. Kerana jika anda benar-benar ke belakang, anda akan mencari unsur terbesar di sini, walaupun ia tergolong di bawah sana. Jadi, anda akan berkata, semua betul, di masa ini dalam masa, anda tergolong di sini, jadi anda biarkan dia bersendirian. Kemudian anda sedar, oh, celaka, saya perlu bergerak elemen ini sedikit lebih kecil untuk di sebelah kiri anda. Kemudian saya perlu berbuat demikian lagi dan lagi dan lagi. Dan jika saya berjalan ke belakang dan sebagainya, anda akan menyusun daripada rasa prestasi algoritma itu, kerana saya sentiasa shuffling orang lain ke dalam pelbagai untuk memberi ruang untuk itu. Itulah kes yang paling teruk. Sebaliknya - dan ini adalah cliffhanger masa lalu - kita katakan bahawa jenis kemasukan merupakan omega apa? Apakah berjalan kes terbaik masa jenis kemasukan? Jadi ia sebenarnya n. Itu adalah kosong yang kami meninggalkan di papan masa lalu. Dan ia omega n kerana mengapa? Nah, dalam kes yang terbaik, apa yang jenis kemasukan akan diserahkan? Nah, senarai itu benar-benar disusun sudah, kerja-kerja yang minimum yang perlu dilakukan. Tetapi apa yang kemas mengenai jenis kemasukan ialah kerana ia bermula di sini dan memutuskan, oh, anda bilangan satu, anda tergolong di sini. Oh, apa nasib yang baik. Anda nombor dua. Anda juga tergolong di sini. Nombor tiga, lebih baik, anda tergolong di sini. Sebaik sahaja ia sampai ke akhir pseudokod senarai, setiap kemasukan jenis ini yang kita berjalan melalui lisan masa lalu, ia dilakukan. Tetapi jenis pilihan, sebaliknya, disimpan melakukan apa? Terus berjalan melalui senarai lagi dan lagi dan lagi. Kerana wawasan utama terdapat hanya sekali anda telah melihat semua jalan ke akhir senarai yang anda boleh yakin elemen yang dipilih adalah sesungguhnya unsur kini terkecil. Jadi ini yang berbeza mental model akhir sehingga menghasilkan beberapa sangat dunia sebenar perbezaan untuk kita, serta ini perbezaan asimptot teori. Jadi untuk menggulung, maka, besar O n kuasa, kita telah melihat apa-apa beberapa algoritma setakat ini. Big O n? Apa algoritma yang boleh dikatakan besar O n? Dalam kes terburuk, ia mengambil masa beberapa linear langkah. OK, carian linear. Dan dalam kes paling teruk, di mana adalah unsur yang anda cari apabila memohon carian linear? OK, dalam kes paling teruk, ia tidak walaupun di sana. Atau dalam kes kedua paling teruk, ia sepanjang jalan pada akhirnya, yang merupakan campur-atau-tolak perbezaan satu langkah. Jadi, pada akhir hari, kita boleh mengatakan ia adalah linear. Big O n akan menjadi carian linear, kerana dalam kes yang paling teruk, unsur tidak walaupun di sana atau ia sepanjang jalan pada akhir. Nah, besar O log n. Kami tidak bercakap secara terperinci mengenai ini, tetapi kita telah melihat sebelum ini. Apa yang wujud dalam apa yang dipanggil logaritma masa, di mana-mana yang paling teruk? Ya, carian supaya binari. Dan carian binari dalam kes terburuk mungkin mempunyai elemen di suatu tempat di tengah-tengah, atau di tempat di dalam array. Tetapi anda hanya mendapati ia sebaik sahaja anda membahagikan senarai pada separuh, dalam separuh, pada separuh, pada separuh. Dan kemudian Voilà, ia adalah di sana. Atau sekali lagi, kes paling teruk, ia tidak walaupun di sana. Tetapi anda tidak tahu bahawa ia tidak ada sehingga anda mencapai bentuk yang terakhir bawah kebanyakan unsur dengan mengurangkan separuh dan mengurangkan separuh dan mengurangkan separuh. Big O 1. Jadi kita boleh besar O 2, besar O 3. Bila-bila masa yang anda mahu hanya sebilangan yang berterusan, kita hanya menyelesaikan hanya memudahkan yang sebesar O 1. Walaupun jika realistik, ia mengambil masa 2 atau 100 langkah-langkah, jika ia adalah bilangan berterusan langkah-langkah, kita hanya mengatakan O besar daripada 1. Apa algoritma itu dalam besar O 1? PENONTON: Mencari panjang pembolehubah a. DAVID MALAN: Mencari panjang pembolehubah? PENONTON: Tidak, panjang jika ia sudah disusun. DAVID MALAN: Baik. OK, jadi mencari panjang sesuatu jika panjang sesuatu itu, seperti array, disimpan di dalam beberapa berubah-ubah. Kerana anda hanya boleh membaca pembolehubah, atau mencetak berubah-ubah, atau hanya umumnya mengakses berubah-ubah itu. Dan Voilà, yang mengambil masa yang berterusan. Sebaliknya, berfikir kembali ke awal. Fikirkan kembali untuk minggu pertama C, memanggil hanya printf dan mencetak sesuatu pada skrin boleh dikatakan masa yang berterusan, kerana ia hanya mengambil beberapa nombor kitaran CPU untuk menunjukkan bahawa teks pada skrin. Atau tunggu - bukan? Bagaimana lagi kita mungkin model prestasi printf? Seseorang ingin untuk tidak bersetuju, bahawa mungkin ia bukan masa benar-benar berterusan? Dalam apa rasa mungkin printf berjalan masa, sebenarnya mencetak tali di skrin, sesuatu selain daripada berterusan. PENONTON: [didengar]. DAVID MALAN: Ya. Jadi ia bergantung kepada perspektif kita. Jika kita benar-benar berfikir daripada input kepada printf sebagai tali, dan Oleh itu, kita mengukur saiz yang input oleh panjangnya - jadi mari kita memanggilnya panjang yang n juga - boleh dikatakan, printf itu sendiri besar O n kerana ia akan mengambil langkah-langkah yang anda n untuk mencetak setiap orang n watak-watak, yang paling mungkin. Sekurang-kurangnya ke tahap yang kita anggap bahawa mungkin ia menggunakan untuk gelung di bawah hood. Tetapi kita perlu melihat bahawa kod untuk memahami dengan lebih baik. Dan sesungguhnya, apabila anda semua mula menganalisis algoritma anda sendiri, anda akan benar-benar berbuat demikian. Jenis biji mata kod anda dan berfikir tentang - semua hak, saya mempunyai gelung ini di sini atau saya mempunyai gelung bersarang di sini, yang akan melakukan perkara-perkara n n kali, dan anda boleh menyelesaikan sebab cara anda melalui kod, walaupun ia pseudokod dan tidak kod sebenar. Jadi apa yang kira-kira omega n kuasa dua? Apakah algoritma yang dalam yang terbaik kes, masih mengambil langkah-langkah n kuasa dua? Ya? PENONTON: [didengar]. DAVID MALAN: jenis pemilihan Jadi. Kerana dalam masalah yang benar-benar dikurangkan kepada hakikat bahawa sekali lagi, saya tidak tahu Saya dapati yang paling kecil semasa sehingga Saya telah memeriksa semua elemen-elemen darn. Jadi omega, berkata, n, kita hanya datang dengan satu. Jenis kemasukan. Jika senarai yang berlaku diselesaikan pun, dalam kes ini, kita hanya perlu untuk membuat satu pas melaluinya, di mana titik kita pasti. Dan kemudian yang boleh dikatakan menjadi linear, yang pasti. Bagaimana pula dengan omega 1? Apa, dalam kes yang terbaik, mungkin mengambil beberapa langkah-langkah yang berterusan? Carian linear Jadi, jika anda hanya mendapatkan bertuah dan elemen yang anda cari tepat pada awal senarai, jika itu di mana anda mula anda linear traversal senarai itu. Dan ini adalah benar daripada beberapa perkara. Sebagai contoh, walaupun binari carian omega daripada 1. Kerana apa yang jika anda mendapat benar-benar darn bertuah dan berbau-dab di tengah-tengah pelbagai anda adalah bilangan yang anda cari? Jadi, anda boleh mendapatkan bertuah di sana, juga. Yang ini, akhirnya, omega n log n. Jadi n log n, kita tidak benar-benar bercakap tentang lagi, tetapi - PENONTON: Gabung apapun? DAVID MALAN: jenis Gabung. Itu adalah cliffhanger masa lalu, di mana kami mencadangkan, dan kita menunjukkan visual, bahawa terdapat algoritma. Dan bergabung jenis hanya satu itu algoritma yang asasnya lebih cepat daripada beberapa lelaki lain. Malah, bergabung pendek bukan sahaja di kes terbaik n n log, yang paling teruk kes n n log. Dan apabila anda mempunyai kebetulan ini omega dan besar O menjadi perkara yang sama? Kita sebenarnya boleh menggambarkan bahawa apa yang dipanggil theta, walaupun ia adalah satu sedikit kurang biasa. Tetapi itu hanya bermakna kedua-dua batas, dalam kes ini, adalah sama. Jadi bergabung apapun, apakah ini benar-benar mendidih ke untuk kita? Well, ingat motivasi. Biar saya tarik sehingga animasi lain yang kita tidak melihat pada masa lalu. Yang ini, idea yang sama, tetapi ia sedikit lebih besar. Dan saya akan pergi ke hadapan dan menunjukkan pertama - kami mempunyai jenis kemasukan pada atas sebelah kiri, maka jenis pemilihan, jenis gelembung, beberapa jenis lain - shell dan cepat - bahawa kita tidak bercakap kira-kira, dan timbunan dan bergabung jenis. Jadi sekurang-kurangnya cuba untuk memberi tumpuan mata anda pada tiga teratas di sebelah kiri dan kemudian bergabung jenis apabila saya klik ini arrow hijau. Tetapi saya akan memberitahu semua mereka berjalan, hanya untuk memberi anda rasa kepelbagaian algoritma yang wujud di dunia. Saya akan membiarkan jangka ini hanya beberapa saat. Dan jika anda memberi tumpuan mata anda - memilih satu algoritma, memberi tumpuan kepada ia untuk hanya saat - anda akan mula melihat corak yang ia melaksanakan. Gabung jenis, notis, dilakukan. Jenis timbunan, jenis cepat, shell - jadi ia seolah-olah kita memperkenalkan tiga algoritma yang paling teruk minggu lepas. Tetapi itu adalah baik bahawa kita di sini hari ini untuk melihat merge jenis, yang merupakan salah satu orang-orang yang lebih mudah adalah untuk melihat, walaupun walaupun ia mungkin akan bengkok fikiran anda hanya sedikit. Di sini kita dapat melihat betapa banyak jenis pilihan menghisap. Tetapi di sebelah flip, ia benar-benar mudah untuk dilaksanakan. Dan mungkin untuk P Set 3, itu salah satu daripada algoritma anda memilih untuk melaksanakan untuk edisi standard. Betul-betul halus, sempurna betul. Tetapi sekali lagi, sebagai n mendapat besar, jika anda memilih untuk melaksanakan algoritma yang lebih cepat suka bergabung apapun, kemungkinan berada dalam yang lebih besar dan input yang lebih besar, kod anda hanya akan berjalan lebih cepat. Laman web anda akan bekerja lebih baik. Pengguna anda akan menjadi lebih bahagia. Dan begitu juga ada kesan-kesan ini sebenarnya memberi kami sedikit lebih berfikir. Jadi mari kita lihat apa yang bergabung apapun yang sebenarnya semua tentang. Perkara yang sejuk adalah yang bergabung apapun hanya ini. Ini adalah, sekali lagi, apa yang kita telah dipanggil pseudokod, makhluk pseudokod Sintaksis Bahasa Inggeris-seperti. Dan kesederhanaan adalah jenis yang menarik. Maka pada input n elemen - supaya hanya bermakna, di sini adalah array. Ia mempunyai perkara n di dalamnya. Itu semua kita katakan di sana. Jika n adalah kurang daripada 2, kembali. Jadi itu hanya kes remeh. Jika n adalah kurang daripada 2, maka jelas ia 1 atau 0, di mana perkara yang sudah disusun atau tidak wujud, jadi hanya kembali. Tiada apa-apa yang perlu dilakukan. Jadi itu adalah satu kes yang mudah untuk memetik off. Yang lain, kami mempunyai tiga langkah. Menyelesaikan separuh kiri elemen, jenis separuh yang betul unsur-unsur, dan kemudian menggabungkan bahagian disusun. Apa yang menarik di sini ialah Saya jenis punting, bukan? Ada jenis definisi pekeliling untuk algoritma ini. Dalam apa rasa adalah algoritma ini yang pekeliling definisi? PENONTON: [didengar]. DAVID MALAN: Ya, algoritma sorting saya, dua langkah-langkah yang "jenis sesuatu. "Dan supaya menimbulkan soalan, baik, apa yang saya akan menggunakan untuk menyelesaikan separuh kiri dan separuh yang betul? Dan kecantikan di sini ialah bahawa walaupun sekali lagi, ini adalah-lentur minda sebahagian yang berpotensi, anda boleh menggunakan sama algoritma untuk menyelesaikan separuh kiri. Tetapi tunggu satu minit. Apabila anda diberitahu untuk menyusun separuh kiri, apakah dua langkah-langkah yang akan datang? Kami akan menyelesaikan separuh kiri separuh kiri dan kanan separuh daripada separuh kiri. Damn, bagaimana saya boleh menyelesaikan kedua-dua bahagian, atau pihak, sekarang? Tetapi itu OK. Kami mempunyai algoritma sorting di sini. Dan walaupun anda mungkin bimbang sama pertama ini adalah jenis yang tidak terhad gelung, ia adalah satu kitaran yang tidak pernah akan berakhir - ia akan akhir sekali apa yang berlaku? Setelah n adalah kurang daripada 2. Yang akhirnya akan berlaku, kerana jika anda menyimpan dan mengurangkan separuh mengurangkan separuh dalam mengurangkan separuh bahagian ini, pasti akhirnya anda akan berakhir dengan hanya 1 atau 0 elemen. Di mana titik, algoritma ini kata anda selesai. Jadi sihir sebenar dalam ini algoritma seolah-olah berada di dalam langkah terakhir, bercantum. Itulah idea yang mudah hanya penggabungan dua perkara, itulah apa yang akhirnya akan untuk membolehkan kita untuk menyelesaikan pelbagai, katakan, lapan elemen. Jadi saya mempunyai lapan lebih bola tekanan sehingga di sini, lapan keping kertas, dan satu Google Kaca - yang saya dapat menyimpan. [Ketawa] DAVID MALAN: Jika kita boleh mengambil lapan sukarelawan, dan mari kita lihat jika kita boleh bermain ini keluar, jadi. Wow, OK. Sains komputer semakin menyeronokkan. Baiklah. Jadi bagaimana pula anda tiga, tangan terbesar di sana. Empat di belakang. Dan bagaimana pula kita akan adakah anda tiga berturut-turut ini? Dan empat di hadapan. Jadi anda lapan, datang ke atas. [Ketawa] DAVID MALAN: Saya sebenarnya tidak pasti apa yang ia adalah. Adakah ia bola tekanan? Lampu meja? Bahan? Internet? OK. Jadi datang di atas. Siapa yang akan suka - terus datang. Mari kita lihat. Dan ini meletakkan anda dalam location - anda berada di lokasi satu. Uh-oh, tunggu satu minit. 1, 2, 3, 4, 5, 6, 7 - oh, baik. Baiklah, kita yang baik. Baiklah, supaya semua orang mempunyai tempat duduk, tetapi tidak pada kaca Google. Biar saya beratur ini. Apa nama anda? Michelle: Michelle. DAVID MALAN: Michelle? Baiklah, anda boleh kelihatan seperti geek, jika itu OK. Well, saya lakukan juga, saya rasa, hanya untuk seketika. Baiklah, siap sedia. Kami telah cuba untuk tampil dengan menggunakan kes Google Glass, dan kami fikir ia akan menjadi seronok untuk hanya melakukan ini apabila orang di atas pentas. Kami akan mencatat dunia dari perspektif mereka. Baiklah. Tidak mungkin apa yang Google dimaksudkan. Baiklah, jika anda tidak keberatan memakai ini untuk minit janggal akan datang, yang akan menjadi indah. Baiklah, jadi kita ada di sini pelbagai unsur-unsur, dan lokasi itu, sebagai satu keping kertas dalam orang ' tangan, kini Unsorted. Michelle: Oh, yang begitu pelik. DAVID MALAN: Ia cukup banyak rawak. Dan hanya seketika, kita akan cuba untuk melaksanakan bergabung bersama-sama jenis dan melihat di mana bahawa wawasan utama adalah. Dan helah di sini dengan merge jenis adalah sesuatu yang kita tidak dianggap yet. Kami benar-benar memerlukan beberapa ruang tambahan. Jadi apa yang akan menjadi terutamanya menarik mengenai ini adalah bahawa lelaki akan bergerak sedikit bit, kerana saya akan menganggap bahawa terdapat pelbagai tambahan ruang, berkata, di belakang mereka. Jadi, jika mereka berada di belakang kerusi mereka, itulah pelbagai menengah. Jika mereka sedang duduk di sini, itu array utama. Tetapi ini adalah satu sumber yang kita ada tidak dimanfaatkan setakat ini dengan gelembung jenis, dengan jenis pemilihan, dengan jenis kemasukan. Ingat minggu lepas, semua orang hanya jenis shuffled di tempat. Mereka tidak menggunakan apa-apa memori tambahan. Kami membuat ruang untuk rakyat dengan bergerak orang di sekeliling. Jadi ini adalah satu wawasan utama, juga. Ada ini trade-off, secara umum di sains komputer, sumber. Jika anda mahu mempercepatkan sesuatu seperti masa, anda akan perlu membayar harga. Dan salah satu daripada mereka harga adalah sangat kerap ruang, jumlah memori atau keras ruang cakera yang anda gunakan. Atau, terus-terang, jumlah masa pengaturcara. Berapa banyak masa ia akan membawa anda, manusia, untuk benar-benar melaksanakan lebih banyak algoritma rumit. Tetapi hari ini, perdagangan-off adalah masa dan ruang. Jadi, jika anda semua hanya boleh memegang sehingga anda nombor supaya kita boleh melihat bahawa anda memang sepadan 4, 2, 6, 1, 3, 7, 8. Excellent. Jadi, saya akan cuba untuk mengatur perkara, jika anda semua boleh hanya mengikuti jejak saya di sini. Oleh itu, saya akan melaksanakan, pertama, langkah pertama pseudokod, yang merupakan input n unsur, jika n kurang daripada 2, kemudian kembali. Jelas sekali, yang tidak memohon, jadi kita bergerak ke atas. Jadi menyusun separuh kiri unsur-unsur. Jadi ini bermakna saya akan memberi tumpuan saya perhatian untuk hanya seketika atas empat lelaki di sini. Baiklah, apa yang saya lakukan seterusnya? PENONTON: Susun separuh kiri. DAVID MALAN: Jadi sekarang saya perlu menyelesaikan separuh kiri lelaki ini. Kerana sekali lagi, anggap diri anda matlamat adalah untuk menyelesaikan separuh kiri. Bagaimana anda berbuat demikian? Hanya ikut arahan, walaupun walaupun kita lakukan sekali lagi. Jadi menyusun separuh kiri. Sekarang saya mengasingkan kedua-dua lelaki. Apa yang datang seterusnya? PENONTON: Susun separuh kiri. DAVID MALAN: Susun separuh kiri. Jadi sekarang ini, kerusi ini di sini, adalah senarai saiz 1. Dan apa nama lagi? PRINCESS DAISY: Princess Daisy. DAVID MALAN: Princess Daisy di sini. Dan supaya dia sudah disusun, kerana senarai adalah saiz 1. Apa yang saya lakukan seterusnya? OK, kembali, kerana senarai itu adalah saiz 1, yang kurang daripada 2. Kemudian apa langkah seterusnya? Dan sekarang anda perlu jenis mundur dalam fikiran anda. Menyelesaikan separuh yang betul, yang - apa nama anda? LINDA: Linda. DAVID MALAN: Linda. Dan supaya apa yang kita lakukan sekarang bahawa kami mempunyai senarai saiz 1? PENONTON: Return. DAVID MALAN: Berhati-hati. Kita kembali pertama, dan kini ketiga langkah - dan jika saya jenis menggambarkan ia dengan memeluk dua kerusi sekarang, sekarang saya perlu menggabungkan kedua-dua elemen. Jadi sekarang malangnya, unsur-unsur berada di luar perintah. Tetapi itu di mana proses penggabungan mula mendapat menarik. Jadi, jika anda semua boleh berdiri hanya seketika, saya akan memerlukan anda, dalam masa, untuk melangkah di belakang kerusi anda. Dan jika Linda, kerana 2 adalah lebih kecil daripada 4, mengapa tidak anda datang sekitar pertama? Tinggal di sana. Jadi Linda, anda datang sekitar pertama. Sekarang dalam realiti jika ia hanya array kita hanya boleh bergerak beliau dalam masa nyata dari kerusi ini ke tempat ini. Cuba bayangkan, yang mengambil beberapa berterusan beberapa langkah 1. Dan sekarang - tetapi kita perlu meletakkan anda dalam lokasi pertama di sini. Dan sekarang jika anda boleh datang sekitar, juga, kita akan berada di lokasi dua. Dan walaupun ini berasa seperti ia adalah mengambil sedikit masa, apa yang baik sekarang ialah bahawa separuh kiri separuh kiri kini disusun. Jadi apa langkah seterusnya, jika kita kini memundurkan lagi dalam cerita? PENONTON: separuh kanan. DAVID MALAN: Susun separuh betul. Jadi anda lelaki itu mempunyai untuk melakukan ini, juga. Jadi, jika anda boleh berdiri hanya untuk seketika? Dan apa nama anda? JESS: Jess. DAVID MALAN: Jess. OK, jadi Jess kini kiri separuh daripada separuh yang betul. Dan supaya dia adalah senarai saiz 1. Dia jelas disusun. Dan nama anda lagi? Michelle: Michelle. DAVID MALAN: Michelle adalah jelas senarai saiz 1. Dia sudah disusun. Jadi sekarang keajaiban berlaku, proses penggabungan. Jadi siapa yang akan datang terlebih dahulu? Jelas Michelle. Jadi, jika anda boleh datang sekitar belakang. Ruang yang kita ada untuk dia sekarang tepat di belakang kerusi ini di sini. Dan sekarang jika anda boleh kembali juga, kita kini mempunyai, jelas, dua bahagian, setiap saiz 2 - dan hanya demi gambaran, jika anda boleh membuat sedikit ruang - salah satu ditinggalkan separuh di sini, satu setengah di sini. Memundurkan lagi dalam cerita. Apakah langkah yang akan datang? PENONTON: Gabung. DAVID MALAN: Jadi sekarang kita perlu bergabung. Jadi OK, jadi sekarang, bersyukur, kita hanya dibebaskan empat kerusi. Oleh itu, kita telah menggunakan dua kali ganda memori banyak, tetapi kita boleh memberi flip-flopping antara dua tatasusunan. Jadi yang nombor akan datang terlebih dahulu? Jadi Michelle, jelas. Jadi datang sekitar dan mengambil tempat duduk anda di sini. Dan kemudian nombor 2 jelas seterusnya, jadi anda datang ke sini. Nombor 4, nombor 6. Dan sekali lagi, walaupun terdapat sedikit berjalan kaki yang terlibat, benar-benar, ini boleh berlaku serta-merta, dengan bergerak satu - OK, juga dimainkan. [Ketawa] DAVID MALAN: Dan kini kami dalam bentuk yang agak baik. Separuh kiri keseluruhan input kini telah disusun. Baiklah, jadi ini lelaki mempunyai kelebihan saya - bagaimana ia berakhir dengan semua gadis-gadis di kiri dan semua anak lelaki di sebelah kanan? OK, jadi lelaki 'berubah sekarang. Jadi, saya tidak akan berjalan anda melalui langkah-langkah ini. Kita akan melihat jika kita boleh memohon semula pseudokod yang sama. Jika anda mahu pergi ke hadapan dan berdiri, dan anda semua, biarlah saya memberikan mikrofon itu. Lihat jika anda tidak boleh meniru apa kita lakukan di sini pada hujung lain senarai. Siapa yang memerlukan untuk bercakap pertama, berdasarkan algoritma? Jadi menjelaskan apa yang anda lakukan sebelum anda membuat apa-apa pergerakan kaki. SPEAKER 1: Baiklah, jadi sejak Saya separuh kiri separuh kiri, saya kembali. Betul? DAVID MALAN: Baik. SPEAKER 1: Dan kemudian - DAVID MALAN: Siapa yang mikrofon pergi ke depan? SPEAKER 1: bilangan Next. SPEAKER 2: Jadi saya separuh betul separuh kiri separuh kiri, dan saya kembali. DAVID MALAN: Baik. Anda kembali. Jadi sekarang apa yang sehingga seterusnya untuk kamu berdua? SPEAKER 2: Kami mahu melihat siapa yang lebih kecil. DAVID MALAN: Tepat sekali. Kami mahu bergabung. Ruang yang kita akan gunakan untuk bergabung anda ke dalam, walaupun mereka jelas sudah disusun, kita akan mengikuti algoritma yang sama. Jadi yang pergi di belakang pertama? Jadi 3, dan kemudian 7. Dan kini mikrofon pergi kepada lelaki, OK? SPEAKER 3: Jadi saya separuh kanan separuh kiri, dan n saya adalah kurang daripada 1, jadi saya hanya akan lulus - DAVID MALAN: Baik. SPEAKER 4: Saya separuh kanan bahagian kanan separuh yang betul, dan saya juga satu orang, jadi saya akan kembali. Jadi sekarang kita bergabung. SPEAKER 3: Jadi kita kembali. DAVID MALAN: Jadi anda pergi ke belakang. Jadi 5 dulu, maka 8. Dan sekarang penonton, yang merupakan melangkah kita perlu sekarang memundurkan kembali ke dalam fikiran kita? PENONTON: Gabung. DAVID MALAN: Menggabungkan separuh kiri dan kanan separuh daripada separuh kiri asal. Jadi sekarang - dan hanya untuk membuat ini jelas, membuat sedikit ruang di antara kamu dua lelaki. Jadi sekarang adalah dua senarai, kiri dan kanan. Jadi bagaimana kita kini bergabung kamu ke barisan hadapan tempat duduk lagi? 3 dulu. Kemudian 5, jelas. Kemudian 7, dan sekarang 8. OK, dan kini kita? PENONTON: Tidak dilakukan. DAVID MALAN: Tidak dilakukan, kerana jelas, ada satu langkah yang tinggal. Tetapi sekali lagi, sebab saya menggunakan ini istilah seperti "gulung semula dalam fikiran anda," ia adalah kerana itu benar-benar apa yang berlaku. Kita akan melalui semua langkah-langkah ini, tetapi kami jenis berhenti untuk masa, menyelam jauh ke dalam algoritma, berhenti seketika, menyelam jauh ke dalam algoritma, dan sekarang kita perlu menyusun satu gulung dalam kami fikiran dan membatalkan semua lapisan bahawa kita telah jenis ditunda. Jadi sekarang kita mempunyai dua senarai saiz 4. Jika anda semua boleh berdiri kali terakhir dan membuat sedikit ruang di sini untuk membuat jelas bahawa ini adalah kiri separuh daripada yang asal, bahagian kanan yang asal. Siapa bilangan pertama yang kita perlu tarik ke belakang? Michelle, sudah tentu. Jadi kita meletakkan Michelle sini. Dan yang mempunyai nombor 2? Nombor 2 datang di belakang juga. Bilangan 3? Excellent. Nombor 4, 5 nombor, nombor 6, nombor 7 dan nombor 8. OK, jadi ia berasa seperti banyak langkah-langkah, yang pasti. Tetapi sekarang mari kita lihat jika kita tidak boleh mengesahkan jenis intuitif bahawa ini algoritma asas, terutamanya n mendapat benar-benar besar, seperti yang kita telah melihat dengan animasi, adalah asasnya lebih cepat. Jadi saya menuntut algoritma ini, yang paling teruk kes dan juga di mana-mana yang terbaik, adalah besar O n kali log n. Iaitu, terdapat beberapa aspek ini algoritma yang mengambil langkah-langkah n, tetapi ada aspek lain di suatu tempat di lelaran itu, gelung itu, bahawa mengambil langkah-langkah yang log n. Bolehkah kita meletakkan jari kami pada apa yang mereka dua nombor adalah merujuk kepada? Nah, di mana - Dari mana asalnya mikrofon pergi? SPEAKER 1: Adakah yang log n menjadi memecahkan kita kepada dua - terbahagi kepada dua, pada asasnya. DAVID MALAN: Tepat sekali. Mana-mana masa yang kita lihat dalam mana-mana algoritma itu setakat ini, telah ada corak membahagikan, membahagikan, membahagikan. Dan ia biasanya dikurangkan kepada sesuatu yang logaritma, log asas 2. Tetapi ia benar-benar boleh menjadi apa-apa, tetapi log asas 2. Sekarang apa tentang n? Saya boleh melihat bahawa kita jenis dibahagikan anda lelaki - dibahagikan anda, dibahagikan anda, dibahagikan anda, dibahagikan anda. Di manakah akhirnya datang? Jadi ia adalah penggabungan. Kerana berfikir mengenainya. Apabila anda menggabungkan lapan orang bersama-sama, di mana separuh daripada mereka adalah satu set empat dan separuh lagi adalah satu lagi set empat, bagaimana anda pergi melakukan penggabungan? Nah, kalian melakukannya agak intuitif. Tetapi jika saya bukan melakukannya lebih sedikit teratur, saya mungkin telah menunjuk ke arah orang yang paling kiri pertama dengan kiri saya tangan, menunjuk pada orang yang paling kiri itu setengah dengan tangan kanan saya, dan hanya kemudian berjalan melalui senarai, menghala ke arah elemen terkecil setiap kali, menggerakkan jari saya ke atas dan lebih seperti yang diperlukan seluruh senarai. Tetapi apa yang penting tentang penggabungan ini proses adalah saya membandingkan kedua-pasangan unsur-unsur. Dari separuh kanan dan di sebelah kiri setengah, saya tidak pernah berundur. Jadi bergabung itu sendiri mengambil tidak lebih daripada n langkah. Dan berapa kali pula saya mempunyai untuk berbuat demikian bergabung? Well, tidak lebih daripada n, dan kita hanya melihat bahawa dengan bergabung akhir. Dan jadi jika anda melakukan sesuatu yang mengambil log n langkah n kali, atau sebaliknya, ia akan memberikan kita n kali log n. Dan mengapa ini yang lebih baik? Nah, jika kita sudah tahu bahawa log n adalah lebih baik daripada n - betul? Kita lihat dalam carian binari, buku telefon Sebagai contoh, log n memang lebih baik daripada linear. Ini bermakna n kali log n pasti lebih baik daripada n masa lain n, AKA n kuasa dua. Dan itulah yang kita akhirnya rasa. Pusingan begitu besar tepukan, jika kita boleh, bagi lelaki ini. [Tepuk tangan] DAVID MALAN: Dan hadiah perpisahan anda - anda boleh menyimpan nombor, jika anda ingin. Dan hadiah perpisahan anda, seperti biasa. Oh, dan kami akan menghantar kepada anda rakaman itu, Michelle. Terima kasih. Baiklah. Membantu diri anda dengan bola tekanan. Dan biarlah saya tarik sehingga, dalam masa yang sama, rakan kami Rob Bowden untuk menawarkan perspektif yang agak berbeza mengenai perkara ini, kerana anda boleh berfikir tentang ini langkah-langkah yang berlaku dalam yang agak cara yang berbeza. Malah, set-up untuk apa yang kira-kira Rob untuk menunjukkan kepada kita menganggap bahawa kita telah telah dilakukan yang membahagikan daripada senarai yang besar kepada lapan senarai kecil, setiap saiz 1. Jadi kita sedang berubah pseudokod suatu sedikit hanya untuk menyelesaikan daripada mendapatkan di idea teras bagaimana kerja-kerja bercantum. Tetapi masa menjalankan apa dia kira-kira untuk melakukan masih akan menjadi sama. Dan sekali lagi, set-up di sini adalah bahawa dia bermula dengan lapan senarai saiz 1. Jadi, anda telah terlepas bahagian di mana dia sebenarnya yang telah dilakukan log n, log n, log n membahagikan input. [MAIN SEMULA VIDEO] -Itu sahaja untuk satu langkah. Untuk langkah dua, berkali-kali bergabung pasang senarai. DAVID MALAN: Hm. Hanya audio akan datang daripada komputer saya. Mari kita cuba ini lagi. -Hanya sewenang-wenangnya memilih yang - sekarang kita mempunyai empat senarai. Belajar sebelum ini. DAVID MALAN: Ada kita pergi. Menghimpunkan-108 dan 15, kita akhirnya dengan senarai 15, 108. Menghimpunkan 50 dan 4, kita berakhir dengan 4, 50. Penggabungan 8 dan 42, kita berakhir dengan 8, 42. Dan penggabungan 23 dan 16, kita berakhir dengan 16, 23. Sekarang semua senarai kami saiz 2. Perhatikan bahawa setiap empat senarai yang disusun. Oleh itu, kita boleh mula bergabung pasang senarai lagi. Menghimpunkan 15 dan 108 dan 4 dan 50, kita pertama mengambil masa 4, maka 15, maka 50, maka 108. Penggabungan 8, 42 dan 16, 23, kita mula-mula mengambil 8, maka 16, maka 23, maka 42. Jadi sekarang kita mempunyai hanya dua senarai saiz 4, setiap yang disusun. Jadi sekarang kita menggabungkan kedua-dua senarai. Pertama, kita mengambil masa 4, maka kita mengambil 8, maka kita mengambil 15, kemudian 16, kemudian 23, kemudian 42, kemudian 50, kemudian 108. [AKHIR VIDEO MAIN SEMULA] DAVID MALAN: Sekali lagi, notis, dia tidak pernah menyentuh cawan yang diberikan lebih daripada satu masa selepas mara di luar itu. Jadi dia tidak pernah mengulangi. Jadi dia sentiasa bergerak ke tepi, dan di mana kita mendapat n kami. Mengapa tidak membiarkan saya tarik sehingga satu animasi yang kita lihat sebelum ini, tetapi kali ini hanya menumpukan pada merge jenis. Biar saya pergi ke hadapan dan zum di atas ini di sini. Pertama izinkan saya memilih input rawak, membesarkan ini, dan anda boleh menyusun daripada melihat apa yang kita mengambil untuk diberikan, sebelum ini, bergabung jenis sebenarnya lakukan. Jadi melihat bahawa anda mendapatkan ini bahagian atau pihak ini atau ini eighths daripada masalah yang tiba-tiba mula mengambil keadaan yang baik. Dan kemudian akhirnya, anda lihat di akhir sangat yang bam, semuanya digabungkan bersama-sama. Jadi ini adalah hanya tiga berbeza mengambil idea yang sama. Tetapi pandangan utama, seperti jurang dan menakluk di dalam kelas yang pertama, adalah bahawa kita memutuskan untuk entah bagaimana membahagikan masalah ini menjadi sesuatu yang besar, ke dalam sesuatu jenis sama dalam semangat, tetapi lebih kecil dan lebih kecil dan lebih kecil dan lebih kecil. Kini satu lagi cara yang menyeronokkan untuk menyusun daripada berfikir kira-kira ini, walaupun ia bukan akan memberi anda intuitif sama pemahaman, adalah animasi berikut. Jadi ini adalah satu video seseorang meletakkan bersama-sama yang berkaitan yang berbeza bunyi dengan pelbagai operasi untuk jenis kemasukan, untuk bergabung jenis, dan untuk beberapa orang lain. Jadi, dalam masa, saya akan melanda Play. Ia kira-kira satu minit panjang. Dan walaupun anda masih boleh melihat corak berlaku, kali ini anda boleh juga mendengar bagaimana algoritma adalah melaksanakan berbeza dan dengan corak yang agak berbeza. Ini adalah jenis kemasukan. [TONES DITAYANGKAN] DAVID MALAN: Ia sekali lagi cuba untuk memasukkan setiap elemen ke mana ia tergolong. Ini adalah jenis gelembung. [TONES DITAYANGKAN] DAVID MALAN: Dan anda boleh menyusun satu rasa bagaimana agak sedikit bekerja ia melakukan pada setiap langkah. Ini adalah apa yang tediousness bunyi seperti. [TONES DITAYANGKAN] DAVID MALAN: Ini adalah jenis pilihan, di mana kita pilih unsur yang kita mahu dengan melalui sekali lagi dan lagi dan lagi dan meletakkan ia pada permulaan. [TONES DITAYANGKAN] DAVID MALAN: Ini adalah bergabung jenis, yang anda benar-benar boleh mula rasa. [TONES DITAYANGKAN] [Ketawa] DAVID MALAN: Sesuatu dipanggil gnome jenis, yang mana kami tidak melihat. [TONES DITAYANGKAN] DAVID MALAN: Jadi biarlah saya lihat, sekarang, terganggu kerana anda adalah diharapkan oleh muzik, jika saya boleh tergelincir sedikit sedikit matematik di sini. Jadi ada cara yang keempat yang kita boleh berfikir tentang apa yang ia bermaksud fungsi untuk lebih cepat daripada orang-orang yang bahawa kami telah dilihat sebelum ini. Dan jika anda datang pada kursus dari latar belakang matematik, anda sebenarnya tahu mungkin sudah bahawa anda boleh menampar tempoh pada teknik ini - iaitu rekursi, fungsi yang entah bagaimana panggilan sendiri. Dan sekali lagi, ingat bahawa jenis merge pseudokod adalah rekursi dalam erti kata bahawa salah satu langkah-langkah merge jenis ini adalah untuk memanggil jenis - yang, sendiri. Tetapi bersyukur, kerana kita disimpan memanggil jenis, atau bergabung jenis, secara khusus, bagi yang lebih kecil dan lebih kecil dan senarai yang lebih kecil, akhirnya kita berdasar keluar terima kasih kepada apa yang kita akan memanggil kes asas, kes berkod keras yang berkata, jika senarai itu adalah kecil, kurang daripada 2 dalam kes itu, hanya kembali dengan segera. Jika kita tidak mempunyai kes khas, algoritma tidak akan berakhir tidak, dan anda benar-benar akan masuk ke dalam satu gelung tidak terhingga yang benar-benar selama-lamanya. Tetapi menganggap bahawa kita mahu kini meletakkan beberapa nombor di atas ini, sekali lagi, dengan menggunakan n memandangkan saiz input. Dan saya mahu bertanya kepada anda, apa yang jumlah masa yang terlibat dalam berjalan jenis merge? Atau lebih secara amnya, apa yang kos dalam masa? Baik ia agak mudah untuk mengukur itu. Jika n adalah kurang daripada 2, masa yang terlibat dalam menyusun n elemen, di mana n adalah 2, adalah 0. Kerana kita hanya kembali. Tidak ada kerja yang perlu dilakukan. Sekarang boleh dikatakan, mungkin ia adalah satu langkah atau dua langkah-langkah untuk memikirkan jumlah bekerja, tetapi ia cukup dekat dengan 0 yang Saya hanya akan mengatakan tidak kerja diperlukan jika senarai adalah begitu kecil untuk tidak menarik. Tetapi kes ini adalah menarik. Kes rekursi adalah cawangan pseudokod yang berkata lain, jenis separuh kiri, menyusun hak separuh, menggabungkan kedua-dua bahagian. Sekarang mengapa ungkapan ini mewakili perbelanjaan yang? Nah, T n hanya bermakna masa untuk menyelesaikan elemen n. Dan kemudian di sebelah kanan yang tanda sama ada, T n dibahagikan sebanyak 2 adalah merujuk kepada kos apa? Menyusun separuh kiri. T lain n dibahagikan dengan 2 ialah mungkin merujuk kepada kos untuk menyelesaikan separuh betul. Dan kemudian n campur? Adakah penggabungan. Kerana jika anda mempunyai dua senarai, salah satu saiz n lebih daripada 2 dan satu lagi saiz n lebih 2, anda perlu dasarnya menyentuh setiap unsur-unsur, seperti Rob menyentuh setiap cawan, dan hanya seperti yang kita berkata pada setiap sukarelawan di atas pentas. Jadi n perbelanjaan bercantum. Sekarang malangnya, formula ini juga dirinya rekursi. Jadi jika bertanya, jika n, berkata, 16, jika ada 16 orang di atas pentas atau 16 cawan dalam video, berapa jumlah langkah-langkah yang diperlukan untuk menyusun mereka dengan jenis merge? Ini sebenarnya bukan satu jawapan yang jelas, kerana sekarang anda perlu menyelesaikan satu Recursively menjawab formula ini. Tetapi itu OK, kerana biarlah saya mencadangkan yang kita lakukan yang berikut. Masa yang terlibat untuk menyelesaikan 16 orang atau 16 cawan akan diwakili umum sebagai T 16. Tetapi yang sama, menurut kami formula sebelumnya, 2 kali ganda masa yang diperlukan untuk menyelesaikan 8 cawan campur 16. Dan sekali lagi, ditambah 16 adalah masa untuk bergabung, dan T dua kali ganda 8 adalah masa untuk menyelesaikan separuh kiri dan bahagian kanan. Tetapi sekali lagi, ini tidak mencukupi. Kita perlu menyelam dalam lebih mendalam. Ini bermakna kita perlu menjawab soalan, apakah T 8? Well T 8 hanya 2 kali T 4 ditambah 8. Nah, apa yang T dari 4? T 4 hanya 2 kali T 2 ditambah 4. Nah, apa yang T 2? T 2 hanya 2 kali T 1 plus 2. Dan sekali lagi, kami mendapat jenis terperangkap dalam kitaran ini. Tetapi ia adalah kira-kira untuk memukul yang dipanggil kes asas. Kerana apa yang T 1, adakah kita membuat tuntutan? 0. Jadi sekarang akhirnya, kita boleh bekerja ke belakang. Jika T 1 adalah 0, saya kini boleh kembali sehingga satu beratur dengan lelaki ini di sini, dan saya boleh pasangkan 0 for T 1. Ini bermakna ia sama 2 kali sifar, atau dikenali sebagai 0, ditambah 2. Dan supaya ungkapan keseluruhan ialah 2. Sekarang, jika saya mengambil T 2, jawapan yang 2, palam ke dalam barisan tengah, T 4, yang memberikan saya 2 kali 2 plus 4, jadi 8. Jika saya kemudian palam dalam 8 hingga sebelumnya line, yang memberikan saya 2 kali 8, 16. Dan jika kita kemudian terus bahawa dengan 24, sambil menambah dalam 16, kami akhirnya mendapat nilai 64. Sekarang dalam dan dengan sendirinya jenis bercakap tiada notasi n itu, besar O, omega yang kita telah telah bercakap tentang. Tetapi ternyata bahawa 64 memang 16, saiz input, log asas 2 of 16. Dan jika ini adalah sedikit yang tidak dikenali, hanya berfikir kembali, dan ia akan kembali untuk anda akhirnya. Jika ini adalah log asas 2, ia seperti 2 dinaikkan kepada apa yang memberikan anda 16? Oh, itu 4, jadi ia adalah 16 kali 4. Dan sekali lagi, ia bukan satu masalah besar jika ini adalah jenis memori yang kabur sekarang. Tetapi untuk sekarang, mengambil iman bahawa 16 log 16 adalah 64. Dan begitu sesungguhnya, dengan kewarasan ini mudah memeriksa, kami telah disahkan - tetapi tidak dibuktikan secara rasmi - bahawa masa berjalan merge apapun memang n log n. Jadi tidak buruk. Ia pasti lebih baik daripada algoritma yang kita lihat setakat ini, dan ia adalah kerana kita telah dimanfaatkan, satu, teknik yang dipanggil rekursi. Tetapi yang lebih menarik daripada itu, bahawa konsep membahagikan dan menakluk. Sekali lagi, yang benar-benar minggu 0 barangan yang walaupun kini berulang dalam cara yang lebih menarik. Sekarang sedikit senaman menyeronokkan, jika anda telah pernah dilakukan ini - dan anda mungkin tidak perlu, kerana jenis normal orang tidak berfikir untuk melakukan ini. Tetapi jika saya pergi ke google.com dan jika Saya mahu belajar sesuatu tentang rekursi, Enter. [Ketawa] [Ketawa MORE] DAVID MALAN: jenaka Bad perlahan-lahan merebak. [Ketawa] DAVID MALAN: Hanya dalam kes ini, ia adalah di sana. Saya tidak menyatakan ia salah, dan ada jenaka. Baiklah. Menjelaskan kepada orang-orang datang kepada anda jika ia tidak cukup klik hanya lagi. Tetapi rekursi, secara umum, merujuk kepada proses fungsi memanggil sendiri, atau lebih amnya, membahagikan masalah menjadi sesuatu yang boleh diselesaikan sedikit demi sedikit dengan menyelesaikan sama masalah wakil. Nah, mari kita gear perubahan hanya untuk seketika. Kami ingin berakhir pada cliffhangers tertentu, jadi mari kita mulakan untuk menetapkan pentas, untuk beberapa minit, pada idea yang sangat mudah - bahawa bertukar-tukar dua unsur, bukan? Semua ini algoritma kita telah bercakap tentang pasangan yang lalu kuliah melibatkan beberapa jenis bertukar-tukar. Hari ini ia telah dilihat oleh mereka mendapat keluar dari kerusi mereka dan berjalan di sekitar, tetapi dalam kod, kita akan hanya mengambil elemen dari satu array dan mencebur ke dalam yang lain. Jadi bagaimana kita pergi tentang melakukan perkara ini? Baiklah, biar saya pergi ke hadapan dan menulis program cepat di sini. Saya akan pergi ke hadapan dan melakukan ini sebagai berikut. Mari kita panggil ini - apa yang kita mahu memanggil satu ini? Sebenarnya, tidak. Biar saya putar balik. Saya tidak mahu berbuat demikian cliffhanger yet. Ia akan merosakkan keseronokan. Mari kita buat ini sebaliknya. Katakan bahawa saya mahu menulis sedikit program dan bahawa sekarang ini merangkumi Idea rekursi. Saya jenis mendapat lebih awal daripada diri saya di sana. Saya akan melakukan yang berikut. Pertama, cepat termasuk standard io.h, serta termasuk daripada cs50.h. Dan kemudian saya akan pergi ke hadapan dan mengisytiharkan int sah utama dengan cara yang biasa. Saya sedar saya telah misnamed fail, jadi biarlah saya menambah. c lanjutan di sini supaya bahawa kita boleh menyusun dengan betul. Mula fungsi ini. Dan fungsi yang saya mahu menulis, agak semata-mata, adalah salah satu yang meminta pengguna untuk nombor dan kemudian menambah sehingga semua nombor antara yang bilangan dan, berkata, 0. Jadi pertama saya akan pergi ke hadapan dan mengisytiharkan n int. Kemudian saya tulis kod ada yang kita telah digunakan untuk sementara waktu. Walaupun sesuatu itu benar. Saya akan kembali ke bahawa dalam seketika. Apa yang saya mahu lakukan? Saya ingin katakan printf positif integer sila. Dan kemudian saya akan mengatakan n mendapat mendapatkan int. Jadi sekali lagi, beberapa kod boilerplate bahawa kami telah digunakan sebelum ini. Dan saya akan melakukan ini manakala n adalah kurang daripada 1. Jadi ini akan memastikan bahawa pengguna memberi saya integer positif. Dan sekarang saya akan melakukan yang berikut. Saya mahu untuk menambah sehingga semua nombor antara 1 dan dan n, atau 0 dan n, setara, untuk mendapatkan jumlah wang. Jadi simbol sigma besar yang mungkin anda ingat. Jadi, saya akan melakukan ini dengan panggilan pertama fungsi yang dipanggil sigma, lulus dalam n, dan kemudian saya akan printf berkata, jawapan yang tepat di sana. Jadi dalam jangka pendek, saya mendapat dan int dari pengguna. Saya memastikan ia adalah positif. Saya mengaku jawapan yang berubah-ubah yang dipanggil daripada int jenis dan kedai di dalamnya pulangan nilai sigma, lulus dalam n sebagai input. Dan kemudian saya mencetak di atas jawapan itu. Malangnya, walaupun sigma bunyi seperti sesuatu yang mungkin dalam fail math.h, perisytiharan itu, ia sebenarnya tidak. Jadi, itu OK. Saya boleh melaksanakan ini sendiri. Saya akan melaksanakan fungsi yang dipanggil sigma, dan ia akan mengambil parameter - mari kita hanya memanggilnya m, hanya jadi ia berbeza. Dan kemudian di sini, saya akan berkata, baik, jika m adalah kurang daripada 1 - ini adalah program yang sangat menarik. Jadi, saya akan pergi ke hadapan dan serta-merta mengembalikan 0. Ia hanya tidak masuk akal untuk menambah semua nombor antara 1 dan m jika m sendiri ialah 0 atau negatif. Dan kemudian saya akan pergi ke hadapan dan melakukan ini sangat iterative. Saya akan melakukan seperti ini lama-sekolah, dan saya akan pergi ke hadapan dan mengatakan bahawa saya akan mengisytiharkan jumlah wang yang menjadi 0. Kemudian saya akan mempunyai untuk gelung int - dan biarlah saya melakukannya untuk perlawanan kami kod pengedaran, supaya anda mempunyai salinan di rumah. int i mendapat 1 pada sehingga i adalah kurang daripada atau sama dengan m. i plus plus. Dan kemudian di dalam ini untuk gelung - kita sudah hampir - jumlah mendapat jumlah campur 1. Dan kemudian saya akan kembali jumlah. Jadi saya melakukan ini dengan cepat, agak diakui. Tetapi sekali lagi, fungsi utama agak mudah, berdasarkan kod yang kami telah ditulis setakat ini. Menggunakan gelung dwi untuk mendapatkan yang positif int dari pengguna. Saya kemudian lulus int itu kepada fungsi baru dipanggil sigma, memanggil ia, sekali lagi, n. Dan saya menyimpan nilai pulangan, jawapan dari kotak hitam kini dikenali sebagai sigma, di ubah dipanggil jawapan. Kemudian saya mencetaknya. Jika kita terus cerita, bagaimana sigma dilaksanakan? Saya mencadangkan untuk melaksanakan seperti berikut. Pertama, sedikit kesilapan semakan memastikan bahawa pengguna tidak main dengan saya dan lulus dalam beberapa nilai negatif atau 0. Kemudian saya mengisytiharkan pembolehubah yang dipanggil kesimpulan dan menetapkan kepada 0. Dan sekarang saya mula bergerak dari i sama 1 semua jalan sehingga dan termasuk m, kerana saya ingin termasuk semua nombor satu melalui m, termasuk. Dan di dalam ini untuk gelung, saya hanya melakukan jumlah mendapat apa-apa sekarang, ditambah dengan nilai i. Plus nilai i. Sebagai mengetepikan, jika anda tidak melihat ini sebelum ini, terdapat beberapa gula sintaktik untuk syarikat ini. Saya boleh menulis semula ini sebagai campur sama i, hanya untuk menyelamatkan diri saya beberapa ketukan kekunci dan melihat lebih sejuk sedikit. Tetapi itu semua. Ia adalah fungsi yang sama. Malangnya, kod ini ini tidak akan menyusun yet. Jika saya berjalan membuat sigma 0, bagaimana am Saya akan mendapatkan menjerit? Apa yang ia akan tidak suka? PENONTON: [didengar]. DAVID MALAN: Ya, saya tidak mengisytiharkan fungsi top up, kan? C adalah jenis bodoh, kerana ia hanya melakukan apa yang anda beritahu kepada lakukan, dan anda perlu melakukannya dalam perintah itu. Dan jadi jika saya tekan Enter sini, saya akan mendapat amaran mengenai sigma tersirat perisytiharan. Oh, tidak menjadi masalah. Saya boleh naik ke atas, dan saya boleh berkata, semua hak, tunggu satu minit. Sigma adalah satu fungsi yang mengembalikan int an dan ia menjangka int sebagai input, koma bertitik. Atau saya boleh meletakkan fungsi keseluruhan atas utama, tetapi secara umum, saya akan mencadangkan terhadap itu, kerana ia adalah bagus untuk sentiasa mempunyai utama di atas supaya anda boleh menyelam kanan dalam dan tahu apa program yang melakukan dengan membaca utama pertama. Jadi sekarang biarlah saya mengosongkan skrin. Remake sigma 0. Semua seolah-olah untuk menyemak. Izinkan saya menjalankan sigma 0. Antara positif. Saya akan memberikan nombor 3 untuk memastikan ia mudah. Jadi yang perlu memberikan saya 3 campur 2 campur 1, jadi 6. Memasuki, dan sesungguhnya saya mendapat 6. Saya boleh melakukan sesuatu yang lebih besar - 50, 12, 75. Sama seperti menyimpang, saya akan melakukan sesuatu yang tidak masuk akal seperti yang benar-benar besar nombor, Oh, yang benar-benar bekerja di luar - eh, saya tidak fikir itu betul. Mari kita lihat. Mari kita benar-benar kucar-kacir dengan ia. Itulah masalah. Apa yang berlaku? Kod ini bukan yang buruk. Ia masih linear. Whistling adalah kesan yang baik, walaupun. Apa yang berlaku? Tidak pasti jika saya mendengarnya. Jadi ia ternyata - dan ini adalah sebagai diketepikan. Ini bukan adalah teras kepada Idea rekursi. Rupa-rupanya, kerana saya cuba untuk mewakili satu jumlah yang besar, yang paling mungkin ia sedang disalah tafsir oleh C sebagai nombor tidak positif, tetapi bilangan negatif. Kita tidak bercakap tentang perkara ini, tetapi ia ternyata terdapat nombor negatif di dunia di samping kepada nombor positif. Dan cara-cara di mana anda boleh mewakili nombor negatif dasarnya ialah, anda menggunakan salah satu sedikit khas untuk menunjukkan positif dalam negatif. Ia sedikit lebih kompleks daripada itu, tetapi itulah idea asas. Lebih malang lagi, jika C adalah mengelirukan satu mereka bit yang sebenarnya bermaksud, oh, ini adalah satu nombor negatif, gelung saya di sini, misalnya, adalah sebenarnya tidak pernah akan menamatkan. Jadi jika saya sebenarnya mencetak sesuatu lagi dan lagi, kita akan lihat banyak keseluruhan. Tetapi sekali lagi, ini adalah selain titik. Ini adalah benar-benar hanya satu bentuk rasa ingin tahu bahawa kita akan datang kembali ke akhirnya. Tetapi untuk sekarang, ini adalah betul pelaksanaan jika kita menganggap bahawa pengguna akan menyediakan Ints yang patut dalam Ints. Tetapi saya mendakwa bahawa kod ini, terus-terang, boleh dilakukan lebih banyak lagi semata-mata. Jika matlamat di tangan adalah untuk mengambil nombor seperti m dan menambah sehingga semua nombor antara ia dan 1, atau sebaliknya antara 1 dan, saya menuntut bahawa saya boleh meminjam idea ini yang bergabung apapun yang telah, yang mengambil masalah saiz ini dan membahagikan menjadi sesuatu yang lebih kecil. Mungkin bukan separuh, tetapi lebih kecil, tetapi representatively yang sama. Idea yang sama, tetapi masalah yang lebih kecil. Jadi, saya sebenarnya - biarlah saya simpan fail ini dengan nombor versi yang berbeza. Kami akan memanggil versi ini 1 daripada 0. Dan saya mendakwa bahawa saya boleh sebenarnya reimplement ini dalam jenis ini fikiran-lentur cara. Saya akan meninggalkan sebahagian daripadanya sahaja. Saya akan mengatakan jika m adalah kurang daripada atau sama dengan 0 - Saya hanya akan menjadi sedikit lebih dubur masa ini dengan memeriksa kesilapan saya - Saya akan pergi ke hadapan dan kembali 0. Ini adalah sewenang-wenangnya. Saya hanya sekadar membuat keputusan jika pengguna memberi saya nombor negatif, saya kembali 0, dan mereka harus telah membaca dokumentasi yang lebih rapat. Yang lain - melihat apa yang saya akan lakukan. Yang lain saya akan kembali m plus - apakah sigma m? Nah, sigma m plus m tolak 1, plus m tolak 2, ditambah tolak m 3. Saya tidak mahu menulis semua bahawa. Mengapa tidak saya hanya menyepak bola? Recursively memanggil diri saya dengan sedikit masalah yang lebih kecil, koma bertitik, dan memanggilnya sehari? Betul? Sekarang di sini, juga, anda mungkin berasa bimbang atau bahawa ini adalah satu gelung tak terhingga bahawa saya mendorong, di mana saya melaksanakan sigma dengan menghubungi sigma. Tetapi itu sempurna OK, kerana saya fikir hadapan satu ditambah yang baris? PENONTON: [didengar]. DAVID MALAN: 23 hingga 26, yang adalah keadaan saya jika. Kerana apa yang bagus tentang penolakan di sini, kerana saya terus menyerahkan sigma masalah yang lebih kecil, lebih kecil masalah, yang lebih kecil - ia tidak separuh saiz. Ia hanya satu langkah bayi yang lebih kecil, tetapi itulah OK. Kerana akhirnya, kita akan bekerja cara kami ke 1 atau 0. Dan apabila kita mencapai 0, sigma tidak akan memanggil dirinya lagi. Ia akan segera kembali 0. Jadi kesan, jika anda jenis angin ini dalam fikiran anda, adalah untuk menambah m plus m tolak 1, ditambah m tolak 2, ditambah m tolak 3, ditambah dot, dot, dot, m tolak m, akhirnya memberikan anda 0, dan kesan akhirnya menambah semua perkara-perkara ini bersama-sama. Oleh itu, kita tidak mempunyai, dengan rekursi, menyelesaikan masalah yang kita tidak dapat menyelesaikan sebelum ini. Malah, versi 0 daripada ini, dan setiap masalah setakat ini, telah larut dengan hanya menggunakan untuk gelung atau semasa gelung atau membina yang sama. Tetapi rekursi, saya berani untuk menegaskan, memberikan kita cara yang berbeza berfikir tentang masalah, di mana jika kita boleh mengambil masalah, bahagikan ia daripada sesuatu agak besar ke dalam sesuatu yang agak lebih kecil, saya mendakwa bahawa kita boleh menyelesaikannya mungkin sedikit lebih elegan dari segi reka bentuk, dengan kod kurang, dan mungkin juga menyelesaikan masalah yang akan menjadi lebih sukar, seperti yang kita akan akhirnya lihat, penyelesaian semata-mata secara berulang. Tetapi cliffhanger yang saya lakukan mahu meninggalkan kami pada adalah ini. Biar saya pergi ke hadapan dan membuka sehingga fail dari - sebenarnya, saya pergi dan berpuasa sebenar ini. Biar saya pergi ke hadapan dan mencadangkan berikut. Antara kod hari ini adalah fail ini di sini. Yang satu ini di sini, noswap. Jadi ini adalah satu program kecil yang bodoh Saya disebat sehingga bahawa tuntutan untuk melakukan berikut. Di utama, ia mula-mula mengisytiharkan satu int dipanggil x dan menyerahkan ia nilai 1. Kemudian ia mengisytiharkan an y dan int menyerahkan ia nilai 2. Kemudian ia mencetak apa x dan y adalah. Kemudian ia berkata, bertukar-tukar, dot dot dot. Kemudian ia mendakwa memanggil fungsi dipanggil swap, lulus dalam x dan y, idea yang yang diharapkan x dan y akan kembali yang berbeza, sebaliknya. Kemudian ia mendakwa bertukar! dengan tanda seru. Kemudian ia mencetak keluar x dan y. Tetapi ternyata bahawa ini sangat demonstrasi mudah turun di sini adalah sebenarnya kereta. Walaupun saya mengisytiharkan sementara berubah dan meletakkan sementara di , maka saya penguntukan semula nilai yang b - yang merasakan yang munasabah, kerana saya telah disimpan satu salinan dalam temp. Kemudian saya mengemaskini b untuk sama Apa sahaja di dalam temp. Ini jenis permainan shell menggerakkan ke b dan b ke dalam dengan menggunakan ini tengah-lelaki yang dipanggil suhu merasakan sempurna yang munasabah. Tetapi saya mengatakan bahawa apabila saya berjalan ini kod, seperti yang saya akan lakukan sekarang - izinkan saya pergi ke hadapan dan tampalkannya di sini. Saya akan panggil noswap.c ini. Dan seperti namanya, ini tidak akan menjadi satu program yang betul. Buat noswap. / Tiada swap. x 1, y ialah 2, bertukar-tukar, bertukar. x 1, y ialah 2. Ini adalah asas yang salah, walaupun walaupun ini seolah-olah sempurna munasabah untuk saya. Dan tidak ada sebab, tetapi kita tidak akan mendedahkan sebab hanya lagi. Buat masa cliffhanger kedua saya mahu meninggalkan anda dengan adalah ini, pengumuman pelbagai pada kod kupon. Inovasi kami dengan hari-hari akhir tahun ini telah menimbulkan beberapa bukan remeh soalan, yang merupakan bukan niat kita. Tujuan kod kupon, di mana jika anda sebahagian daripada masalah set awal, dengan itu mendapat satu hari, adalah benar-benar untuk membantu anda semua membantu diri anda bermula awal, jenis oleh incentivizing anda. Membantu kita mengagihkan beban di seluruh waktu pejabat yang lebih baik supaya ia adalah sejenis menang-menang. Malangnya, saya fikir arahan saya belum, setakat ini, sangat jelas, jadi Saya kembali pada hujung minggu ini dan dikemaskini spec dalam yang lebih besar, lebih berani untuk teks menjelaskan peluru seperti ini. Dan hanya untuk mengatakan ia lebih kepada umum, dengan lalai, set masalah adalah disebabkan Khamis pada tengah hari, setiap sukatan pelajaran. Jika anda bermula awal, kemasan sebahagian daripada masalah yang ditetapkan oleh Rabu di 12:00 PM, bahagian yang berkaitan dengan kupon kod, idea adalah bahawa anda boleh melanjutkan tarikh akhir anda untuk P ditetapkan sehingga Jumaat. Iaitu, sedikit daripada sebahagian kecil daripada P ditetapkan berbanding dengan apa yang biasanya adalah masalah yang lebih besar, dan anda membeli diri anda satu hari. Sekali lagi, ia membawa anda berfikir tentang set masalah, membawa anda ke waktu pejabat lebih awal. Tetapi masalah kod kupon masih diperlukan, walaupun anda tidak hantar. Tetapi yang lebih compellingly adalah ini. (Berbisik STAGE) Dan orang-orang penduduk meninggalkan awal adalah gonna menyesal. Begitu juga dengan orang di balkoni. Saya memohon maaf terlebih dahulu kepada orang-orang di balkoni atas sebab-sebab yang akan jelas dalam seketika. Oleh itu, kita bernasib baik kerana mempunyai salah satu daripada Bekas rakan-rakan pengajaran kepala CS50 di sebuah syarikat yang dipanggil dropbox.com. Mereka telah sangat bermurah hati menderma kod kupon di sini untuk ruang ini banyak, yang meningkat daripada biasa 2 gigabait. Jadi apa yang saya fikir kita akan lakukan pada ini nota terakhir adalah melakukan sedikit giveaway, mana dalam hanya seketika, kita akan mendedahkan pemenang dan yang mempunyai kupon kod yang anda boleh pergi ke mereka laman web, menaip dalam, dan Voilà, mendapatkan banyak seluruh lebih Dropbox ruang untuk anda perkakas dan untuk fail peribadi anda. Dan pertama, yang ingin menyertai dalam lukisan ini? OK, sekarang yang menjadikan ia lebih menyeronokkan. Orang yang menerima ini 25-gigabit kod kupon - yang jauh lebih menarik daripada lewat hari kini, mungkin - adalah orang yang duduk di atas kusyen kerusi yang mengalir di bawahnya ada kod kupon. Anda kini boleh melihat di bawah kusyen tempat duduk anda. [MAIN SEMULA VIDEO] Satu, dua, tiga. [Menjerit] -Anda akan mendapat kereta! Anda akan mendapat kereta! DAVID MALAN: Kita akan melihat anda pada Rabu. -Anda akan mendapat kereta! Anda akan mendapat kereta! Anda akan mendapat kereta! Anda akan mendapat kereta! Anda akan mendapat kereta! DAVID MALAN: orang beranda, datang ke sini ke hadapan, di mana kita mempunyai tambahan. -Semua orang mendapat kereta! Semua orang mendapat kereta! [AKHIR VIDEO MAIN SEMULA] Pencerita: Pada CS50 seterusnya - SPEAKER 5: Oh cuilah duilah Astaga Astaga Astaga Astaga Astaga Astaga Astaga Astaga - [Memainkan UKELELE]