[Bermain muzik] DAVID J. MALAN: Ini adalah CS50. Dan ini adalah permulaan minggu tiga. Jadi kita telah mendapat banyak menarik perkara yang melindungi hari ini. Banyak peluang-peluang untuk sukarelawan di atas pentas. Dan akhirnya, hari ini adalah tidak tentang kod sama sekali. Tetapi ia adalah tentang idea-idea, dan ia mengenai algoritma, dan benar-benar membawa kembali beberapa pengajaran daripada minggu sifar, mana ingat, kita diperkenalkan barang ganjil ini. Dan inspirasi pinjaman itu, untuk memulakan untuk menyelesaikan yang lebih canggih masalah algorithmically. Tetapi pertama, beberapa pengumuman. Jadi salah, jika anda ingin menyertai Kakitangan dan rakan-rakan sekelas CS50 di makan tengah hari Jumaat ini, dan di dalam Cambridge, dan di New Haven, sila layari kursus ini laman web, di mana URL yang boleh didapati. Kuliah Rabu ini akan tidak berada di sini di Sanders. Ia akan berada dalam talian sahaja, jadi menonton di laman web CS50, sama ada di sini di Cambridge atau New Haven juga. Dan kemudian masalah menetapkan dua sudah di tangan anda. Jika anda belum menyelam dalam lagi, izinkan saya untuk menawarkan cadangan kuat worded itu, terutamanya sekarang, kerana masalah ini menetapkan terlebih dahulu, anda benar-benar ingin memulakan sekarang, jika tidak cuba-cuba sedikit di hujung minggu atau sebelum apabila mereka mula-mula keluar pada Jumaat, kerana anda akan mendapati bahawa mereka tidak semestinya semakin panjang atau lebih mencabar setiap se. Saya rasa anda akan mendapati bahawa, dalam Secara umum, mereka cenderung untuk mengambil lebih kurang sekitar jumlah sama. Tetapi ia sudah tentu bergantung ke atas pelajar, dan ia bergantung kepada pemikiran yang anda mendekatinya. Tetapi selalunya, anda akan untuk menjalankan menentang beberapa dinding, dan anda akan melanda beberapa bug, dan anda hanya tidak akan dapat mendapat lebih pada satu ketika. Dan ia sangat berharga yang dapat untuk melangkah jauh, kembali pada hari berikutnya, pergi ke waktu pejabat, paparkan dalam CS50 Bincangkan atau seumpamanya, untuk benar-benar mendapatkan dinyahsekat. Jadi menyimpan bahawa dalam fikiran. Bermula awal yang mungkin adalah perkara yang terbaik anda boleh lakukan. Jadi di sini adalah di mana kita bermula kelas, lebih dalam seminggu sifar. Dan kita boleh mendapatkan sukarelawan di sini untuk membantu saya mencari mics? OKAY. Berdiri sudah. Naiklah. Rasa itu bagaimana ia akan bekerja. Siapa nama anda? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Naiklah. Gembira Mengenali Anda. ALAN ESTRADA: Selamat berkenalan. DAVID J. MALAN: Dan anda berada di sini dengan kami dalam minggu sifar, sudah tentu. ALAN ESTRADA: saya. Saya telah. DAVID J. MALAN: Jadi boleh anda pergi hadapan dan mencari untuk kita Mike Smith, secepat yang anda boleh? Secepat yang anda boleh. Secara harfiah mengoyak masalah pada separuh yang anda perlukan untuk. ALAN ESTRADA: Um. DAVID J. MALAN: Secara lisan mengoyak masalah pada separuh. ALAN ESTRADA: Oh. Mm. Sangat bagus. DAVID J. MALAN: OK. Yang baik. Terima kasih. ALAN ESTRADA: Sangat baik. OKAY. DAVID J. MALAN: Dan sehingga kini, anda telah dikecutkan ke bawah untuk separuh saiz masalah. Kini, kami turun ke suku. Adakah anda memberi perhatian kepada pihak mana kita menjaga? [LAUGHING] ALAN ESTRADA: Ya, saya think-- DAVID J. MALAN: Apa bahagian kita dalam? ALAN ESTRADA Mufflers, demikian. DAVID J. MALAN: OK. Tetapi Mike Smith akan menjadi selepas Mufflers. So-- [LAUGHING] Baiklah. ALAN ESTRADA: Di mana yang kita cari? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Sekarang, kita berada dalam pembedahan. Kini, pakar-pakar perubatan. Sekarang-- ALAN ESTRADA: Let's- mari kita pergi dengan nyata. Real. DAVID J. MALAN: Real. OKAY. Jika anda memerlukan Real. Kini, jalan mana Mike Smith? ALAN ESTRADA: Dengan cara ini. DAVID J. MALAN: Arah mana? ALAN ESTRADA: Tunggu. Hak M is--? Kami bermula with-- DAVID J. MALAN: Ya. Mereka ditinggalkan. Kanan anda. ALAN ESTRADA: Ya. DAVID J. MALAN: Jadi Mike di sini. ALAN ESTRADA: Apa? [LAUGHING] Contoh buruk, guys. Maaf. DAVID J. MALAN: ini akan mengajar anda untuk melompat keluar dari kerusi anda. ALAN ESTRADA: Oh. Oh. Saya mendapat anda. Saya mendapat anda. Oh. Oh. Ini is-- OK, saya mendapat anda. Smith di sini? DAVID J. MALAN: Smith, terima kasih. Jadi saya akan terus mencari sehingga Smith? ALAN ESTRADA: Oh, ya. Tidak, tidak, tidak. Oh tidak. Ini adalah saya. DAVID J. MALAN: Oh, anda mendapat Smith. OKAY. ALAN ESTRADA: Ya, saya mendapat Smith di sini. Maaf, guys. Saya fikir kita Michael-- cari Michael. Maaf. DAVID J. MALAN: Tidak mengapa. Baiklah, sekarang kita ke dalam Paccini dan Sons. ALAN ESTRADA: Paccini dan anak. DAVID J. MALAN: Hanya anda dan saya adalah di dalam perkara ini. OKAY. Cari kami Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Kami berada dalam R untuk sampah. ALAN ESTRADA: Sampah. Oh. Ini akan mengambil sedikit masa. [LAUGHING] DAVID J. MALAN: Shoes. Kami berada dalam kasut. ALAN ESTRADA: Sekarang kita gonna-- DAVID J. MALAN: Nice. ALAN ESTRADA: yang- [LAUGHING] Oh, ini adalah besar. [LAUGHING] DAVID J. MALAN: Tidak mengapa. ALAN ESTRADA: Oh, ini adalah baik. Saya tidak fikir saya akan mempunyai teman PSAT selepas ini. DAVID J. MALAN: Baik. Sukan. ALAN ESTRADA: Sukan. Um, L, M, N, O, P. DAVID J. MALAN: OK. Jadi mari kita air mata ini pada separuh. Tidak mengapa. Ini berakhir dengan baik juga, kerana Mike Smith tidak akan berada di halaman kuning. ALAN ESTRADA: Aw. DAVID J. MALAN: Tidak, ia adalah OK. Tetapi mari kita berpura-pura seperti dia di laman ini. Oleh sebab itu, anda telah dikecutkan masalah ke bawah untuk satu halaman, dan kami mendapati Mike Smith. [Bersorak] Baiklah Terima kasih. OKAY. Itu adalah luar biasa. Tetapi ia masih lebih cepat daripada carian linear, di mana kita bermula pada permulaan buku ini, dan kita bergerak perjalanan dari kiri ke kanan, akhirnya mencari Mike Smith. Justeru, jika buku telefon mempunyai mungkin 1000 muka surat, mungkin ia akan mengambil kami 10 atau lebih air mata halaman. Tetapi anda mungkin telah memanfaatkan menyentuh andaian ketika semua itu, yang mengatakan bahawa buku telefon terlebih dahulu adalah apa? PENONTON: Susun. DAVID J. MALAN: Ia disusun. Betul? Ia disusun mengikut abjad, supaya bahawa semua nama-nama dan nombor yang disusun dari A ke Z, dan mengikut abjad di antara. Tetapi hari ini, kita meminta soalan, baik, bagaimanakah Verizon atau telefon syarikat mendapatkan ke dalam negeri itu? Kerana ia adalah satu perkara untuk memanfaatkan andaian itu, dan oleh itu, menyelesaikan masalah dengan algoritma dengan lebih cekap. Tetapi kita tidak pernah benar-benar ditanya dalam minggu sifar, baik, berapa banyak ia lakukan kos Verizon atau orang lain untuk mendapatkan bahawa buku telefon untuk disusun? Betul? Ia tidak kira jika melihat ke atas Mike Smith adalah super cepat, jika ia mengambil masa anda tahun untuk menyusun halaman mulanya. Betul? Anda mungkin juga hanya menapis melalui buku telefon rawak, jika ia akan menjadi super mahal untuk mengatasinya. Jadi, jika kita boleh mempunyai sukarelawan lain. Mari kita melihat di sini di bagaimana kita might-- datang pada up-- bagaimana kita mungkin pergi tentang menyusun ini. Dan jika Jordan boleh sebenarnya sertai kami di sini di atas pentas. Naiklah hanya untuk seketika. Siapa nama anda? CAROLINE: Caroline. DAVID J. MALAN: Caroline, datang ke atas. Dan anda akan menyertai oleh saya dan Jordan di sini. Caroline, terima kasih. Baiklah. Jadi apa yang kita ada di sini untuk Caroline adalah 26 buku biru bahawa FAS menggunakan untuk mentadbir peperiksaan akhir tertentu. Ini semakin sukar untuk mencari, tetapi apa yang kita lakukan terlebih dahulu adalah bahawa kita telah meletakkan nama seseorang di hadapan masing-masing, tetapi kami telah disimpan mudah oleh kemudian meletakkan nama-nama penuh. Oleh itu, kita akan meletakkan orang dengan nama yang L, D, J, B, sepanjang jalan A hingga Z, tetapi mereka berada dalam susunan rawak. Dan jadi jika anda akan, bercakap anda jalan melalui masalah seperti yang anda melakukannya, anda boleh pergi ke hadapan dan menyusun ini untuk kita, dari A ke Z. PENONTON: OK, jadi L adalah seperti, tengah-tengah. C adalah permulaan. B. J sebelum L. B, Q. DAVID J. MALAN: Kekal yang berfikir untuk satu saat. Kerana jika tidak, ini hanya menarik kepada anda, saya, dan Jordan. Di sana kami pergi. PENONTON: [didengar]. R. DAVID J. MALAN: OK. Apa yang anda lakukan? CAROLINE: M datang selepas O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Baik. CAROLINE: E. DAVID J. MALAN: E, F. Yeah. CAROLINE: T, U, V DAVID J. MALAN: V, T, U, V. Oleh itu, ia kelihatan seperti anda making-- terus. Ia kelihatan seperti anda membuat longgokan besar di sini, dan jenis longgokan besar di sana. Jadi separuh pertama abjad, Separuh kedua abjad. OKAY. Yang baik. Jenis membelah masalah ini dalam dua. M, N, X. Yeah. CAROLINE: K. DAVID J. MALAN: OK. K. Jadi anda jenis memilih mereka satu demi satu, meletakkan ia sama ada kiri atau kanan, atau Z yang berlaku di lantai. OKAY. CAROLINE: Z yang berlaku di lantai. DAVID J. MALAN: OK. Y akan di atas lantai. Sekarang kita boleh meletakkan X. CAROLINE: G. DAVID J. MALAN: G akan ke kiri. S akan betul. Baiklah, A akan sepanjang jalan kiri. CAROLINE: A, B, C, D. DAVID J. MALAN: Sekarang, baik. Kami telah mendapat A, B, C. W yang sedang berlaku di bawah sana. Baiklah, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. baik. CAROLINE: Di bahagian tengah, saya gonna-- DAVID J. MALAN: OK. Oleh sebab itu, kita akan jenis daripada bergabung ini pelbagai buasir. Jadi A hingga C, maka saya lihat A, dan E, dan F dan G, dan H dan I. Nice. J, K. Dan kemudian, cerucuk ini adalah terbalik, tetapi itu OK. Pasti. Kita boleh memotong beberapa sudut. OKAY. Dan kemudian kita perlu W, X, Y, Z. CAROLINE: Ya. DAVID J. MALAN: Cemerlang. Jadi terima kasih kepada Caroline untuk menyusun ini. [Bersorak] Terima kasih. Terima kasih banyak. Jadi sekarang mari kita mempertimbangkan untuk seketika bagaimana Caroline pergi tentang berbuat demikian, dan apa sebenarnya kita dapat supaya- bagaimana kita dapat menyelesaikan itu masalah apabila kami hanya diberikan sejumlah besar input rawak. Nah, ia kelihatan seperti ada adalah sedikit sistem di sana? Betul. Jadi huruf awal dalam abjad, dia adalah meletakkan ke kiri, dan surat kemudian dalam abjad, dia meletakkan ke kanan. Dan sebaik sahaja dia mendapati beberapa surat proksimal, orang-orang yang yang pergi betul-betul bersebelahan antara satu sama lain, dia akan meletakkan mereka dalam perintah. Dan supaya kita jenis mempunyai ini kecil timbunan input disusun berlaku. Dan supaya cukup seperti apa kebanyakan kita manusia akan lakukan. Kami akan semacam menapis melaluinya, dan kita akan jenis mempunyai satu mekanisme. Tetapi ia mungkin sukar untuk menulis menurunkan ke atas formula semata-mata. Ia merasakan lebih sedikit organik daripada itu. Jadi mari kita lihat jika kita boleh sekarang terikat masalah ini dengan sedikit input. Daripada 26, mari kita melakukan sesuatu yang jauh lebih kecil dengan hanya berkata, tujuh, di belakang pintu-pintu ini, jadi untuk bercakap. Adakah terdapat hanya tujuh nombor? Dan jika matlamat sekarang di tangan adalah untuk mencari nilai, mari kita lihat bagaimana cekap kita boleh pergi tentang melakukan ini. Dan mari kita lihat jika kita boleh sekarang mula memohon beberapa nombor, atau beberapa formula yang boleh digunakan untuk menggambarkan kecekapan buku telefon kami algoritma, algoritma buku peperiksaan kami, dan lebih umum, mencari maklumat. Jadi untuk ini, saya pergi ke hadapan, dan pada skrin sentuh di sini, meletakkan pelayar web yang mempunyai betul-betul tujuh pintu. Dan jika kita boleh mendapatkan satu lain secara sukarela untuk datang ke sini, Saya telah meletakkan ini pintu sama di sini. Sukarelawan Pantas. Ini demo one-- akan untuk yang lebih cepat dan lebih cepat sekarang. Ayuh ke bawah. Siapa nama anda? TREVOR: Trevor. DAVID J. MALAN: Trevor? Baiklah, Trevor, datang ke atas ke bawah. Jadi Trevor secara sukarela di sini untuk melakukan masalah yang sama, tetapi satu yang sempit dalam skop, dan perkara yang berlaku untuk membolehkan kita untuk mencuba untuk merasmikan sekarang proses untuk menyusun nombor-nombor ini. Jadi Trevor, baik untuk bertemu dengan kamu. Jadi di sini adalah pelbagai, jadi untuk berkata-kata, senarai tujuh pintu. Teruskan dan mencari kami jumlah 50. Dan kemudian selepas fakta, memberitahu kami bagaimana anda menjumpainya. Sekiranya adalah- hak semua. Ya, ini adalah salah di sini? Uh-oh. OKAY. Anda klik salah satu. Yang baik. Dan baik. Sekarang anda klik salah satu. Dan biarlah saya memberikan anda mikrofon, supaya anda mempunyai dalam hanya seketika. Teruskan dan klik sebelah yang anda berniat. Ya baik. TREVOR: Bolehkah saya Nyahklik pintu? DAVID J. MALAN: Tidak, anda tidak boleh Nyahklik. TREVOR: OK. Satu ini. DAVID J. MALAN: Di manakah anda mahu pergi? Yang mana satu? TREVOR: Yang itu. DAVID J. MALAN: No. TREVOR: OK. Satu ini. DAVID J. MALAN: Ya. Itu adalah baik. Baiklah. Oleh itu, apa algoritma atau prosedur untuk melakukan ini, Trevor? TREVOR: Saya hanya pergi melalui pintu sehingga saya mendapati 50. DAVID J. MALAN: OK. Algoritma yang sangat baik. Jadi itulah denda. Kerana sebenarnya, jika saya mendedahkan apa yang di belakang kedua-dua pintu yang lain, apa yang kita akan dapati di sini adalah bahawa kita hanya mempunyai input rawak. Jadi yang sebenarnya sebagai baik seperti yang anda boleh mendapatkan. Dan sebenarnya, anda mendapat lebih baik daripada mendalam mencari seluruh array, kerana ia akan menjadi benar-benar malang jika anda telah mencecah bilangan yang 50 di pintu yang terakhir. Tetapi bagaimana jika kita bukannya memberikan anda satu andaian. Kira saya semacam semua pintu-pintu ini di sekeliling, supaya anda mempunyai nombor disusun masa ini, tetapi kali ini ia sebenarnya yang different-- masa ini, ia sebenarnya disusun untuk anda. Dan kini matlamat di tangan adalah untuk memukul bilangan 50. TREVOR: OK. DAVID J. MALAN: Apa algoritma anda akan menjadi? TREVOR: Nah, jika ia disusun, ia sama ada akan untuk adalah- jika terbesar untuk terbesar, turun, ia akan menjadi yang pertama, atau jika ia adalah sebaliknya, ia akan menjadi yang terakhir. Jadi saya hanya akan ketuk pintu ini, dan kemudian hanya ketuk pintu lepas. DAVID J. MALAN: Cemerlang. Baiklah. Oleh itu, kita mendapati jumlah 50. Jadi sebaik sahaja anda tahu mereka telah disusun, kita dapat memanfaatkan andaian ini. Jadi mereka terlalu banyak seperti contoh buku telefon. Sebaik sahaja anda mempunyai, walaupun dengan masalah kecil seperti ini, input anda pra-disusun, kita boleh sebenarnya mencari nilai boleh dikatakan dengan lebih cekap. Dan saya tidak memberitahu anda jika ia disusun kecil kepada yang besar, atau besar ke kecil, dan jadi ia adalah sangat wajar bermula pada satu hujung atau yang lain untuk benar-benar mendapati bahawa nilai sasaran. Jadi terima kasih kepada Trevor juga. Dan saya akan propose-- baik dilakukan. Kami mempunyai music sedikit, sebenarnya, yang adalah antara detik-detik kegemaran kami di CS50, di mana kadang-kadang demo ini tidak cukup pergi mengikut perancangan. Dan sesungguhnya sekarang, saya ditarik ke atas antara muka salah yang boleh digunakan untuk menggunakan skrin sentuh. Supaya adalah kesilapan saya di sana. Jadi ini akan menjadikan music tahun depan sebagai mengapa saya klik pada skrin saya sendiri. Tetapi mari kita lihat yang cepat apa yang berlaku pada tahun lepas dengan Jay, yang datang, banyak seperti Trevor sini, secara sukarela, dan dalam klip pendek ini, anda akan melihat bagaimana ini demo sama tidak cukup mendedahkan pelajaran yang sama dipelajari. [VIDEO MAIN SEMULA] -Semua Saya mahu anda lakukan sekarang ialah untuk mencari untuk saya, dan bagi kami, benar-benar, jumlah 50 satu langkah pada satu masa. -The Nombor 50? -The Nombor 50. Dan anda boleh mendedahkan apa yang di belakang setiap pintu-pintu ini hanya dengan menyentuhnya dengan jari. Tak guna. [LAUGHING] [AKHIR MAIN SEMULA] DAVID J. MALAN: Jadi yang pergi dengan baik. Mereka itulah pintu terisih. And Jay, sudah tentu, mendapati ia terlalu cepat. Trevor melakukan kerja yang lebih baik dari segi masa yang diajar, boleh dikatakan, tahun ini di mengambil masa yang lama untuk merasa. Sudah tentu, kita memberi Jay peluang kedua, mana kita disusun pintu, seperti yang kita lakukan untuk Trevor, dan Trevor lakukan super baik kali ini. Tetapi Jay melakukannya separuh cepat. [VIDEO MAIN SEMULA] Matlamat -The sekarang adalah untuk juga mencari kami nombor 50, tetapi melakukannya algorithmically, dan memberitahu kami bagaimana anda akan mengenainya. -OKAY. -Dan Jika anda merasa, anda menyimpan filem. Jika anda tidak merasa, anda memberikan kembali. -man. -Oh! - [Didengar] OK. Jadi, saya akan menyemak hujung pertama untuk menentukan jika there's-- Oh. [Tepuk tangan] [AKHIR MAIN SEMULA] DAVID J. MALAN: OK. Jadi menyusun pintu jelas membawa kepada kecekapan yang lebih tinggi. Dan sebagainya, dua kali lebih cepat apa yang saya maksudkan di sana. Dan sebagainya Jay bernasib baik kedua-dua kali. Dan dia juga bernasib baik kerana lepas tahun, saya mengarahkan beberapa cakera Blu-ray untuk benar-benar memberi. Saya minta maaf tahun ini, kami tidak mempunyai yang sama, Trevor. Tetapi lebih baik lagi adalah beberapa tahun lalu. Dan sebahagian daripada anda mungkin tahu ini rakan-rakan, Sean, yang ketika ia ada di CS50, telah dicabar dengan tepat Masalah yang sama, walaupun dalam SD, kerana anda tidak lama lagi akan melihat, pada zaman dahulu. Dan anda akan mendapati bahawa bukan sahaja melakukan ia mengambil masa lebih lama daripada Jay, lebih lama daripada Trevor, ia sebenarnya peluang ini indah untuk melibatkan hampir semua orang dalam orang ramai la Harganya kanan, menggalakkan beliau untuk mencari nombor yang kita cari. Mari kita. mengambil melihat cepat. [VIDEO MAIN SEMULA] -OKAY. Jadi tugas anda di sini, Sean, adalah seperti berikut. Saya telah tersembunyi di sebalik ini pintu nombor tujuh. Tetapi terletak jauh di beberapa pintu-pintu ini dan juga adalah nombor negatif yang lain. Dan matlamat anda adalah untuk berfikir ini baris atas nombor kerana hanya pelbagai, atau hanya urutan keping kertas dengan nombor di belakang mereka. Dan matlamat anda adalah, hanya menggunakan bahagian atas lokasi di sini, mendapati aku sebagai nombor tujuh. Dan kami kemudian pergi untuk mengkritik bagaimana anda pergi tentang melakukannya. -Semua Betul. Kita-Cari nombor tujuh, sila. No. Lima, 19, 13. [LAUGHING] Ia bukan satu soalan helah. One. [LAUGHING] Pada ketika ini, skor anda tidak begitu yang baik, jadi anda mungkin juga menyimpan berterusan. Tiga. [LAUGHING] Teruskan. Terus terang, saya tidak boleh membantu tetapi tertanya-tanya apa yang anda berfikir tentang, so-- [LAUGHING] Hanya baris atas, jadi anda mempunyai tiga kiri. Jadi mencari saya tujuh. [LAUGHING] 17. Tujuh. [Tepuk tangan] Baiklah. [AKHIR MAIN SEMULA] DAVID J. MALAN: Jadi kita boleh menonton sepanjang hari. Dan sudah tentu, beberapa demo tahun ini mungkin sekarang akan berakhir di depan video tahun ini juga. Jadi sekarang mari kita sebenarnya menumpukan kepada algoritma di sini, dan lihat jika kita tidak boleh kini bermula untuk merasmikan bagaimana kita boleh pergi tentang mendapatkan data kami ke negeri ini bahawa ia disusun, supaya akhirnya, kita boleh sebenarnya mencari ia lebih cekap. Dan walaupun kita akan untuk menggunakan set data yang agak kecil, seperti yang kita lapan nombor ada di atas kapal, akhirnya idea-idea yang sama boleh memohon 1,000 input, satu juta input, 4000000000 input, kerana algoritma akan menjadi asas yang sama. Dan jadi ini adalah terakhir kami peluang untuk sukarelawan hari ini, tetapi mungkin salah satu yang paling terlibat, yang mana kita memerlukan lapan sukarelawan untuk datang dan berjalan kita melalui proses mengasingkan apa yang akan tidak lama lagi berada di muzik ini berdiri di sini. Biar saya mulakan semula di sini. Jadi, satu dalam hijau turquoise-- ia? Adakah anda melakukan? Dua. Ayuh ke bawah. OKAY. Tiga. Empat. Mari me-- OK, lima. Anda sedang dicalonkan oleh rakan anda. Enam, tujuh dan lapan. Naiklah. Baiklah. Terima kasih banyak-banyak. Naiklah. Naiklah. Baiklah. Jadi apa yang kita ada sini-- dan ini merupakan antara yang lebih janggal, kerana ini akan memerlukan anda humor saya untuk hanya sedikit masa. Anda hendaklah menjadi nombor satu. Siapa nama anda? ANNAN: Annan. DAVID J. MALAN: Annan. Daud. Siapa nama anda? JOSEPH: Yusuf. DAVID J. MALAN: Joseph, anda adalah nombor dua. SERENA: Serena, nombor tiga. Stefan, nombor empat. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, nombor lima. [Didengar] DAVID J. MALAN: [didengar]. David, nombor enam. MATT: Mat. DAVID J. MALAN: nombor Matt tujuh. Dan? WAVERLY: Waverly. DAVID J. MALAN: Waverly, nombor lapan. Baiklah. Jika anda could-- whoops. Jika anda semua, kerana anda Cabaran pertama, terdapat lapan tempat duduk penonton muzik di sini menghadapi audiens. Jika anda boleh meletakkan nombor pada muzik ini berdiri dalam apa-apa cara yang bahawa mereka beratur dengan nombor yang sama di papan tulis. Oleh itu, kamu kelihatan seperti dengan meletakkan nombor pada muzik ini berdiri di sini. Cemerlang setakat ini. Sangat baik. OKAY. Oleh sebab itu, kita akan meminta soalan dalam beberapa cara yang berbeza. Bagaimana kita boleh pergi tentang menyusun orang ini di sini? Kerana kami mempunyai beberapa pendekatan sebelum ini, di mana kita berada sejenis membuat dua baldi yang berbeza. Dan kemudian kita secara amnya piecing perkara bersama-sama. Sebaik sahaja kami melihat dua nombor milik bersama-sama, kita meletakkan mereka bersama-sama. Dua huruf yang tergolong bersama-sama. Tetapi mari kita lihat jika kita tidak boleh merasmikan ini, supaya kita akhirnya mempunyai beberapa pseudo-kod anda akan, yang mana anda boleh menyelesaikan masalah ini. Oleh sebab itu, saya melihat keluar di nombor-nombor di sini. Dan saya lihat sejumlah besar kesilapan. Akhirnya, saya ingin satu di kiri dan lapan di sebelah kanan. Dan jadi saya melihat kedua-dua, empat dan dua. Dan apa masalahnya, jelas? Yeah. So. Dua jelas datang sebelum empat, supaya anda tahu apa? Terlebih dahulu saya mengambil pendekatan tamak, jika anda akan, banyak masalah seperti menetapkan one-- jika anda masih ingat dari Standard Edition Masalah Set One, di mana saya hanya dalam negara menyelesaikan masalah ini bahawa di sini di depan saya dan melihat di mana ia membawa saya. OKAY. Jadi dua dan empat, saya pergi hadapan dan hanya menukar kamu berdua. Jika anda secara fizikal boleh bergerak Peliharalah diri kamu dan kertas anda, Saya seolah-olah telah mendapat senarai dalam keadaan yang lebih baik. Sekarang, mereka yang baik. Saya akan bergerak ke atas, empat dan enam, kelihatan baik. Tidak menjadi masalah. Enam dan lapan, OK. Lapan dan satu, satu lagi masalah. Kerana apa yang benar tentang lapan dan satu? Seorang pun yang datang sebelum lapan, dan sebagainya apa yang patut kita buat? Mari kita menukar kedua-dua. Satu hingga lapan. Dan sekarang, saya akan terus pergi. Saya akan terus mencari di hadapan. Dan mari kita lihat apa yang berlaku. Lapan dan tiga, sudah Sudah tentu, daripada perintah. Mari kita swap. Lapan dan tujuh tahun, sudah tentu. Telah habis. Mari kita swap. Swap lapan dan lima, sudah tentu, mari kita. Baiklah. Senarai disusun. ya? OK, jelas tidak. Tetapi ia adalah sedikit lebih baik, bukan? Oleh kerana notis apa yang berlaku. Setiap kali kami melakukan swap, yang lebih kecil beberapa jenis meresap cara itu, dan nombor yang lebih besar meresap cara ini, atau kita akan mula pepatah dipam kepada kiri atau dipam ke kanan. Kini, ia tidak mencukupi, kerana yang terbaik sebilangan mungkin telah berpindah satu tempat ke hadapan, atau paling teruk, bilangan yang mungkin mempunyai bergerak satu tempat lagi. Supaya anda tahu apa, jenis ini daripada bekerja dengan baik setakat ini. Biar saya cuba sekali lagi. Dua dan empat, mereka OK. Empat hingga enam, mereka OK. Enam dan satu, keluar perintah. Jadi mari kita menukar kamu berdua. Dan kini, melihat masalah ini mula mendapat sedikit lebih baik lagi. Enam dan tiga, keluar perintah. Mari kita menukar kamu berdua. Enam dan tujuh, anda baik. Tujuh dan lima, sudah tentu, daripada perintah. Tujuh dan lapan, teratur. Dan sekarang, saya mungkin perlu melakukan ini beberapa kali. Dan sebenarnya, berfikir untuk diri kamu sendiri mungkin berapa kali maksima mungkin saya perlu berjalan kaki ke belakang dan sebagainya? Kami akan kembali kepada itu. Jadi dua dan empat masih OK. Empat dan satu, nope. Jadi, mari kita swap. Dan sekali lagi, melihat visual satu adalah jenis menggelegak ke kiri, di mana ia sepatutnya. Empat dan tiga swap. Empat dan enam. Enam dan lima swap. Enam dan tujuh. Tujuh dan lapan bagus. Yang baik. Kami mendapat lebih baik. Jadi mari kita lihat. Sekarang, kita mempunyai dua dan satu. Sudah tentu, menukar. Dua dan tiga, tiga dan empat, empat dan enam dan tujuh lapan lima, tujuh dan. Yang baik. Dan anda tahu apa? Kerana saya membuat satu perubahan di sana, biarlah saya lakukan salah kewarasan cek. Biar saya pergi sepanjang jalan kembali ke permulaan. OKAY. Satu, two-- yup, lihat? Sesuatu yang salah. Tiga, empat, lima, enam, tujuh, lapan. Dan dalam pas terakhir ini, adalah anda selesa dengan saya sekarang mengaku ia disusun? OKAY. Visual, itu sememangnya benar. Tetapi fungsi, apa itu juga hanya berlaku dalam pas lepas yang membolehkan anda mengesahkan bahawa senarai ini memang disusun? Apa yang saya buat atau tidak pas lepas ini? PENONTON: Tiada sebarang perubahan. DAVID J. MALAN: Maaf? PENONTON: Tiada perubahan. DAVID J. MALAN: Tiada sebarang perubahan. Jadi ia akan menjadi bodoh saya melakukan algoritma yang sama sekali lagi jika saya tidak membuat apa-apa perubahan kali pertama. Dan negeri ini tidak pernah berubah. Sesungguhnya, saya tidak akan membuat apa-apa perubahan kali kedua. Dan sebagainya, ia adalah selamat sekarang berkata, senarai disusun. Dan sesungguhnya, ini kini sesuatu yang kita akan umumnya panggilan gelembung jenis, di mana dari segi pasangan, anda membetulkan kesilapan sekali lagi, dan lagi, dan lagi, dan anda terus pergi ke belakang dan sebagainya, dan belakang dan sebagainya, sehingga anda tidak membuat pertukaran tersebut, di mana titik anda boleh yakin, ya, saya selesai memasang semua kesilapan. Mari kita menetapkan semula dan cuba pendekatan lain. Jika anda semua boleh kembali ke dalam perintah itu anda adalah masa yang lalu, yang kelihatan seperti ini. Sekarang, mari kita mengambil pendekatan yang sedikit lebih seperti buku peperiksaan, di mana kami sentiasa memilih huruf abjad yang kita jenis mahu menangani depan. Mungkin ia adalah surat yang tinggi, seperti A, atau Z. surat yang rendah Jadi semua orang yang kembali teratur ini. Dan sekarang mari saya melakukan ini. Mari kita lihat Saya tahu saya mempunyai lapan nombor tersebut di sini. Saya akan pergi ke depan dan hanya sengaja pilih unsur-unsur yang paling kecil. Betul? Ini seolah-olah intuitif juga. Kenapa saya tidak mencari yang paling kecil elemen, meletakkan ia di mana ia tergolong, kemudian mendapatkan unsur yang paling kecil yang akan datang, meletakkan ia di mana ia tergolong, dan hanya mengulangi. Kerana intuitif, yang perlu bekerja juga. Jadi empat, itu adalah satu jumlah yang cukup kecil. Saya akan ingat di mana ini adalah. Tunggu sekejap. Dua adalah lebih kecil. Kini saya akan ingat di mana dua adalah, dan melupakan empat. Kami akan berurusan dengan itu kemudian. Enam, saya tidak berminat. Lapan, saya tidak berminat. Satu adalah nombor baru saya kecil. Jadi, saya akan ingat di mana seseorang itu. Tiga, tidak berminat. Tujuh, tidak berminat. Lima, tidak berminat. Jadi tanpa terjatuh dari peringkat tahun ini, Saya akan merebut nombor one-- dan apa yang nama anda lagi? ANNAN: Annan. DAVID J. MALAN: Annan. Dan jika anda boleh bersama dengan saya di awal senarai, mari kita meletakkan anda di mana anda berada. Unfortunately-- apa nama anda? STEFAN: Stefan. DAVID J. MALAN: Stefan adalah di jalan. Jadi sebelum Stefan menyelesaikan ini masalah, apa yang patut kita buat? Apa yang kita lakukan dengan Stefan? PENONTON: [didengar]. DAVID J. MALAN: OK. Oleh itu, kita boleh berbuat demikian. Kita boleh semacam mengambil Stefan dan beliau empat, dan hanya meletakkan ia dalam pembolehubah dan berpegang kepadanya untuk beberapa jumlah masa, dan dengan itu membuat ruang untuk nombor satu. Dan itu bukan tidak baik. Saya boleh mencadangkan, mengapa tidak melakukan kita hanya meletakkan Stefan di sini? Mengapa ini mungkin melanggar salah satu daripada idea-idea kami mula bercakap tentang masa lalu, minggu lepas? Ya? PENONTON: [didengar]. DAVID J. MALAN: Tidak ada indeks untuk itu. Jika anda berfikir ini, sesungguhnya, sebagai lokasi, ini adalah seperti yang negatif, jadi tidak ada memori sebenarnya di sini jika ini memang pelbagai, seperti kita mengisytiharkan minggu lepas dalam kuliah. Oleh itu, kita tidak boleh melakukan ini. Kita mungkin menyimpannya dalam pembolehubah. Atau anda tahu apa? Saya mendengar orang lain mencadangkan ia. Apa lagi yang kita boleh lakukan dengan Stefan? Apa kata kita hanya mengusir dia dan meletakkan dia lebih di mana nombor satu itu. Jadi, jika anda mahu pergi ke sana. Dan sesungguhnya, ini adalah satu penyelesaian yang cukup baik. Sekarang dalam satu tangan, saya telah baik hati daripada memberikan masalah yang lebih teruk. Empat kini lebih jauh dari mana ia sepatutnya. Ia perlu ke arah separuh ini. Tetapi anda tahu apa? Yang boleh menjadi nasib malang. Nombor lapan Mungkin berada di sini. Dan sebagainya, mungkin kita akan telah mendapat bernasib baik, dan menolak lapan lebih dekat kepada akhir. Jadi pada akhir hari, ia jenis semua Purata keluar. Kita tidak perlu mengambil berat tentang empat. Apa yang saya mengambil berat tentang sekarang adalah memilih elemen yang paling kecil. Dan sekarang, apa yang saya akan lakukan adalah melupakan nombor satu selama-lamanya, kerana saya tahu Senarai di belakang saya kini disusun. Jadi senarai saya sebelum ini saiz lapan. Kini, ia saiz tujuh. Jadi masalah saya semakin lebih kecil, walaupun secara linear. Oleh sebab itu, saya akan memilih unsur semasa kecil, dua. Enam, lapan, empat, tiga, tujuh, lima. Itu adalah unsur yang paling kecil. Jadi apa yang saya akan lakukan with-- apakah nama anda lagi? JOSEPH: Yusuf. DAVID J. MALAN: Yusuf? Kita akan meninggalkan Yusuf di tempat. Sekarang, saya akan berpura-pura bahawa lelaki ini ialah- baik, Saya tahu bahawa kedua-dua sudah disusun. Sekarang mari kita memberi tumpuan kepada baki senarai. Enam yang paling kecil semasa. Lapan adalah lebih besar. Empat kini yang paling kecil semasa. Tiga kini yang paling kecil semasa. Dan sekarang, saya akan memilih tiga, yang is-- apa nama anda lagi? SERENA: Serena. DAVID J. MALAN: Serena, jika anda boleh merebut bilangan dan swap anda with-- KALSANG: Kalsang. DAVID J. MALAN: Kalsang. Ayuh kembali, dan kami akan menukar kedua-dua. Dan sekarang, mari kita meletakkan ini secara autopilot. Saya akan pergi dan serahkan kepada anda semua untuk memilih unsur-unsur kecil yang akan datang. Dun, dun, dun, dun. Nombor empat, apa yang perlu anda lakukan? Sangat baik. Sekarang, saya akan membuat pas lain. Dun, dun, dun, dun. Saya melihat lima yang paling kecil yang akan datang. Sekarang, saya akan mengambil pas lain. Dun, dun, dun, dun. Enam yang paling kecil. Yang baik. Tujuh adalah yang paling kecil. Tiada perubahan. Lapan adalah yang paling kecil. Selesai. Jadi apa yang kita baru sahaja dilakukan oleh secara berulang memilih salah satu elemen demi satu adalah melaksanakan sesuatu yang kita akan merasmikan sebagai jenis pemilihan. Dan ia mungkin juga lebih mudah untuk menjelaskan, dalam yang benar-benar semua yang anda mahu lakukan adalah hanya menyimpan pergi dan balik melalui senarai memilih, elemen yang paling kecil akan datang, sehingga anda selesai. Jadi ia adalah lebih mudah, mungkin intuitif, daripada lepas. Mari kita cuba salah satu lepas. Jika anda semua boleh menetapkan semula diri ke dalam jawatan-jawatan berikut satu masa akhir, mari kita lihat jika kita tidak boleh sekarang merasmikan satu pendekatan lain. Malah, akan seseorang di luar sana suka untuk mencadangkan bagaimana lagi kita boleh pergi tentang melakukan ini? Tanpa melambung keluar buzzwords atau jenis jawapan yang sudah diketahui, hanya mengikut gerak hati, apa yang kita boleh buat? PENONTON: [didengar]. DAVID J. MALAN: Ya. Jadi ada beberapa gerak hati besar di sana. Perkara-perkara baik seolah-olah berlaku setakat ini dalam bidang sains komputer apabila kita membahagikan dan menakluk masalah membahagikan pada separuh dan separuh dan separuh. Dan sebagainya sesungguhnya kami boleh mula berbuat demikian. Dan sebenarnya, yang akan menjadi, kami akan lihat, salah satu penyelesaian yang terbaik lagi. Tetapi mari kita kembali kepada yang lama. Malah, kita akan lakukan yang sedikit pada minggu ini. Apa lagi yang boleh kita lakukan untuk menyelesaikan masalah ini? Jadi semua orang di sini di perintah seolah-olah rawak. Awak tahu tak? Daripada pergi ke belakang dan sebagainya, belakang dan sebagainya, ke belakang dan sebagainya setiap kali, ini berasa seperti Saya melakukan banyak berjalan. Mengapa saya tidak hanya bermula pada awal senarai, dan hanya meletakkan empat di mana ia tergolong? Jadi biarlah saya menganggap buat masa ini yang senarai saya hanya elemen pertama ini. Apakah empat disusun pada masa ini dalam masa, jika semua saya mengambil berat tentang adalah segala-galanya di sini? Ini adalah jenis trivially benar, bukan? Seperti senarai yang mengandungi satu nombor, dan yang nombor empat jelas disusun. Jadi biarlah saya hanya menetapkan bahawa senarai ini disusun. Tetapi sekarang saya mempunyai yang lain dalam senarai ini. Oleh sebab itu, saya menghadapi dua. Di manakah dua jelas milik berkenaan dengan empat? Sebelum empat. Jadi apa yang boleh saya lakukan di sini? Apa nama anda lagi? JOSEPH: Yusuf. DAVID J. MALAN: Joseph, jika anda boleh langkah ke belakang hanya untuk seketika dengan nombor anda. Dan kini apa yang perlu Stefan lakukan di sini? Mari kita beralih Stefan di sini. Dan sekarang, mari Yusuf datang di sini. Dan sekarang, saya mendakwa bahawa segala-galanya di sini disusun. Jadi, hasilnya sama, tetapi pendekatan dasar yang berbeza. Saya belum pun melihat apa yang di bawah sana. Saya hanya terus mengambil unsur-unsur kerana mereka diserahkan kepada saya, dan berurusan dengan mereka. Oleh sebab itu, saya melihat nombor enam. Di manakah nombor enam tuanmu? Kami mempunyai dua, empat, enam. Tepat di mana dia sekarang. Jadi mari kita meninggalkan itu sahaja, dan sekarang mendakwa bahawa ini sebahagian daripada senarai kini disusun. Dan sebagainya, ini berasa asasnya berbeza dalam bahawa saya hanya bergerak melalui senarai di sini linear, dan saya tidak pernah berpatah balik. Ya. Baiklah. Jadi lapan, di mana tuanmu? Di sini. Perfect. Oleh sebab itu, satu. Uh-oh. Ini berasa seperti ia akan menjadi mahal. Sekarang, dalam algoritma sebelumnya, Saya hanya bertukar orang. Jadi saya dapat dihukum sepanjang jalan di mulanya, tetapi kemudian berpindah Yusuf. Tetapi jika saya bergerak Joseph, kini apa yang akan menjadi salah? Sekarang, saya telah semacam undone-- saya telah mengambil satu langkah ke hadapan dan kemudian satu langkah ke belakang, kerana sekarang Joseph akan keluar perintah. Jadi mari kita buat ini. Jika anda boleh mengambil nombor satu dan langkah ke belakang hanya untuk seketika. Bagaimana kita boleh put-- apa adalah nama anda lagi? ANNAN: Annan. DAVID J. MALAN: Annan di tempat? Apa yang perlu berlaku berkenaan kepada dua, empat, enam dan lapan? Mereka semua perlu beralih. Jadi, jika lapan ingin beralih pertama, kemudian enam, kemudian empat, kemudian dua. Dan kemudian Annan, jika anda lebih suka untuk datang di sini, baik. Tetapi di sini, kami baru sahaja jenis membayar harga yang pada titik yang berbeza dalam algoritma. Sedangkan masa lalu dengan pilihan jenis, dan walaupun gelembung jenis, Aku berjalan ke belakang dan sebagainya, belakang dan sebagainya, yang sudah pasti menjumlahkan masa-bijak, dan benar-benar langkah demi langkah. Jenis kemasukan, pada mulanya pandang, kelihatan seperti ia super bijak, kerana saya hanya membuat perlahan, kemajuan tambahan, tetapi saya tidak akan ini dan ke belakang. Tetapi jika seseorang itu memang daripada perintah, notis semua kerja yang saya hanya terpaksa lakukan. Saya terpaksa berpindah separuh daripada senarai itu hanya untuk memberi ruang kepada nombor satu. Jadi ia adalah jumlah yang sama kerja setakat ini ia merasakan, hanya berlainan jenis kerja. Mari kita terus. Jadi sekarang kita tahu bahawa semua orang antara satu dan lapan disusun. Di sini, saya mempunyai nombor tiga. Jika anda suka untuk mengambil nombor tiga, langkah ke belakang satu. Dan apa yang anda semua perlu lakukan? Ya. Jadi, itu satu sama lain, dua, tiga langkah. Tiga unit masa itu hanya kos saya, supaya tiga kini patut. Akhir sekali, tujuh. Mari kita pergi ke hadapan dan mempunyai anda mengambil kembali langkah. Ini hanya akan kos kita satu unit masa, tetapi tidak apa-apa. Dan kini, lima yang akan menjadi sedikit lebih mahal. Jika anda lebih suka untuk langkah ke belakang. Kita perlu bergerak lapan, dan tujuh, dan enam. Dan kemudian semua orang kini disusun. Jadi tangan besar kepada sukarelawan kami di sini. Terima kasih banyak-banyak. [Tepuk tangan] Terima kasih semua. Terima kasih semua. Jadi mari kita lihat sekarang betapa mahal semua itu adalah. Mari kita pertimbangkan mungkin paling mudah ini, gelembung macam. Aku berkata paling mudah, hanya kerana anda boleh menyelesaikannya dgn rakus dengan hanya menyelesaikan masalah dari segi pasangan di sini. Menyelesaikan masalah dari segi pasangan di sini, sekali lagi dan sekali lagi dan sekali lagi, mengulangi sebanyak kali yang anda benar-benar perlu. Jadi ia ternyata bahawa dengan sejenis gelembung, baik, berapa banyak langkah yang perlu saya mengambil pas pertama algoritma itu? Saya mungkin take-- mari see-- satu, dua, tiga, empat, lima, enam, tujuh. Dan ada lapan elemen di sini. Jadi ia seperti n tolak 1 langkah-langkah untuk dapat dari awal senarai ke akhir senarai. Tetapi dengan jenis pemilihan, ingat bahawa saya memilih unsur-unsur lagi dan lagi dan sekali lagi bahawa yang paling kecil, Saya meletakkan di tempat, tetapi kemudian saya tidak mencari di belakang saya lagi. Jadi saya fikir ia sedikit lebih jelas maka yang pertama kali, saya mungkin perlu mengambil semua n tolak 1 langkah-langkah untuk mencari elemen yang paling kecil. Kemudian saya meletakkan mereka di tempat, dan saya mengusir sesiapa yang berada di sini sebelum ini. Tetapi saya tidak perlu menjaga melihat unsur ini, kerana saya tahu ia pun yang paling kecil. Jadi sekarang, saya boleh melihat hanya tujuh unsur-unsur, maka enam elemen, kemudian lima elemen, kemudian empat elemen. Dan sebagainya secara matematik, jika n ialah bilangan elemen atau nombor yang kami bermula dengan, anda boleh bayangkan bahawa ini adalah sama seperti n tolak 1, tambah n tolak 2 langkah, tambah n tolak 3 langkah, tambah n tolak 4 langkah, semua cara turun ke hanya satu langkah. Dan saya kepada orang terakhir saya. Dan jika anda masih ingat bahawa banyak daripada stats buku atau buku matematik mempunyai orang-orang formula pada Paperback belakang atau hadapan mereka, ternyata bahawa siri ini boleh dinyatakan lebih mudah sebagai n kali n tolak 1 lebih 2. Dan ia adalah baik jika itu tidak di barisan hadapan dalam fikiran anda. Tetapi ini adalah benar. Itu hanya cara yang lebih mudah untuk menulisnya. Dan kemudian jika anda berfikir kembali ke sekolah gred, apabila anda hanya mula membiak perkara, ini sudah tentu, hanya n kuasa dua tolak n dibahagikan dengan 2. Apa yang saya lakukan adalah mengembangkan ungkapan di sana. Dan jadi mari kita menulis semula ini sedikit berbeza. Itu n kuasa dua dibahagikan dengan 2 tolak n / 2. Jadi sekali lagi, saya hanya jenis memohon beberapa aritmetik memerintah di sana. Tetapi perhatikan sekarang bahawa istilah yang paling besar dalam ungkapan ini, boleh dikatakan, ialah n kuasa dua. Jadi ya, ia adalah n kuasa dua dibahagikan dengan 2, tolak n / 2. Tetapi secara amnya, jika n akan menjadi satu nilai yang besar, Saya akan mendakwa bahawa n kuasa akan menjadi faktor yang dominan. Ia hanya akan menjadi penyumbang yang lebih besar untuk bilangan langkah daripada n / 2. Jadi, apa yang saya maksudkan dengan ini? Mari kita cuba contoh yang mudah, walaupun walaupun matematik mendapat besar sedikit. Jadi andaikan kita mempunyai 1 juta orang di atas pentas, atau 1 juta perkara yang kita mahu untuk menyusun. Mari kita pasang juta ke dalam formula yang betul-betul untuk melihat berapa banyak langkah-langkah yang diperlukan jumlah untuk menyusun satu juta elemen menggunakan katakan, jenis pemilihan. Oleh itu, kita akan mempunyai formula yang sama seperti sebelum ini. Saya sedang pasang juta, supaya saya dapat satu juta dibahagikan dengan kuasa dua 2, tolak satu juta dibahagikan dengan 2. Jika saya melakukan matematik yang lebih awal di sini, kami mempunyai 500 bilion tolak 500,000, yang memberikan kita 499999500000, yang cukup darn besar. Malah, jika anda membandingkan sekarang 499000000000, 999 juta, 500,000 berbanding nilai asal kita, 500 bilion, ia begitu sialan rapat. Betul? n kuasa dua dibahagikan dengan 2 memberikan us-- atau sebaliknya, n kuasa dua bahagi 2 memberikan kita 500 bilion. Itulah darn cukup dekat untuk 499999500000, yang mengatakan menolak kira 500,000, atau lebih umum, menolak off n kuasa dua, tidak benar-benar masalah besar. N kuasa dua membuat ini nombor berkembang dengan pantas. Sekarang, ini adalah penting hanya setakat seperti yang kita, sebagai saintis komputer, secara amnya tidak akan mengambil berat tentang nuansa formula ini dan apa yang jawapan yang tepat berada. Kami mengambil berat sahaja, anda tahu apa? Pada akhir hari, formula ini adalah pada perintah itu n kuasa dua. Ya, kita membahagi dengan 2 di sana. Ya, kami menolak off n tolak 2. Tetapi pada akhir hari, istilah yang benar-benar menyakitkan kita dan kos kami banyak langkah-langkah adalah bahawa istilah persegi. Dan supaya apa yang seorang saintis komputer akan pada amnya melaksanakan adalah mengabaikan semua orang-orang terma-terma perintah yang lebih kecil, dan hanya melihat satu yang menyumbang paling banyak kepada kos. Dan ini adalah bagus, kerana kita boleh sekarang bercakap dalam keluasan lebih besar mengenai algoritma, dan boleh membandingkan mereka. Dan hakikat bahawa saya menggunakan O ini adalah sengaja. Apabila saya katakan pada perintah itu daripada, saya secara khusus merujuk kepada sesuatu dipanggil O. besar dan besar O notasi yang komputer saintis menggunakan untuk menggambarkan yang atas terikat pada sesuatu. Jadi, jika anda mengatakan bahawa algoritma adalah di O besar n kuasa dua, seperti yang saya dicadangkan hanya masa lalu, cara yang bahawa dari segi perjalanan Pertubuhan masa atau kecekapan, yang diperlukan pada perintah itu n kuasa dua langkah. Mungkin lebih, mungkin kurang. Tetapi ia adalah atas perintah n kuasa dua. Dan itu atas terikat. Ia tidak akan menjadi lebih menyakitkan daripada itu. Ia tidak akan menjadi n cubed, atau 2 untuk n, atau sesuatu yang lebih besar. Ini adalah had atas pada apa sahaja kos yang. Jadi memandangkan itu, mari kita mempertimbangkan hanya beberapa contoh. Dan ini adalah hanya satu senarai terhingga masa-masa yang biasa berjalan untuk algoritma yang bertujuan untuk menjadi penerangan mengenai beberapa perkara yang kami telah dilihat sudah. Jadi misalnya, dalam hal jenis pemilihan, apa yang saya menuntut di sini SEMAKIN bahawa pemilihan jenis ini masa adalah atas perintah n kuasa dua. Dalam kes terburuk, saya akan mempunyai sejumlah besar nombor rawak di sini. Dan seperti yang kita lihat secara matematik, jika saya terus berjalan melalui senarai, melalui senarai, memilih seterusnya terkecil elemen lagi dan lagi, jika saya sebenarnya menulis semua langkah-langkah Saya mengambil sebagai saya mencadangkan formulaically sebelum ini, ia adalah atas perintah n kuasa dua langkah-langkah yang saya ambil. Dan ternyata gelembung yang menyusun dan memasukkan jenis hanya sebagai perlahan dalam kes yang paling teruk. Pertimbangkan, sebagai contoh, jenis kemasukan, algoritma yang terakhir kita ditangani, yang mempunyai kita lihat unsur, dan kemudian masukkannya mana ia tergolong. Dan kemudian kita melihat elemen yang akan datang, dan memasukkannya dengan mana ia tergolong. Oleh itu fikirkanlah senario yang terbaik. Katakan saya telah sukarelawan saya beratur literal seperti ini, satu melalui lapan, sudah disusun. Berapa banyak langkah adalah jenis kemasukan akan mengambil untuk menyusun lapan orang, jika mereka tiba di atas pentas kelihatan seperti ini? Lapan orang sudah disusun. Dan saya menggunakan jenis kemasukan. Yang terakhir algoritma. Nah, mari kita melakonkan semula cepat nyata. Jadi, jika saya bermula di sini, saya melihat satu. Di manakah seseorang tuanmu? Ia tergolong di sini. Saya melihat dua. Di manakah dua tuanmu? Di sini. Saya melihat tiga. Di manakah tiga tuanmu? Di sini. Ada empat. Di sini. Lima, enam, tujuh, lapan. Tiada sebab untuk mengulangi diri saya sendiri. Dan langkah-langkah ya, berapa adalah bahawa dari segi n? Ia adalah atas perintah n langkah-langkah, bukan? n tolak 1. Tetapi saya mengambil beberapa linear langkah-langkah, dan kini saya dilakukan. Jadi itulah kes ini, walaupun. Bagaimana pula dengan kes yang paling teruk? Apa lapan adalah di sana, dan tujuh adalah di bawah sana, dan satu dan dua adalah di sini, jadi bahawa senarai itu telah benar-benar diterbalikkan? Nah, apa yang berlaku memang jika ini adalah bilangan? Dan kami akan melakukan hanya beberapa contoh. Bagaimana jika, sesungguhnya, nombor lapan di sini, dan yang whoops number--. Jadi apa jika, sesungguhnya, bilangan lapan adalah sepanjang jalan di sini, dan saya menggunakan jenis kemasukan? OKAY. Saya menuntut pada masa ini ia adalah di tempat. Tetapi sekarang, seven-- di manakah tujuh pergi? Sudah tentu, ia pergi di sini. Jadi saya perlu bergerak lapan lebih satu tempat. Kini enam, di mana ia pergi? Nah, baiklah. Sekarang, saya perlu bergerak lapan lebih tempat, dan tujuh lebih tempat, dan kemudian saya mencebur ke bawah enam. Jadi kali pertama, ia kos saya satu langkah untuk menetapkan perkara-perkara, maka ia kos saya dua langkah untuk menetapkan perkara-perkara. Berapa banyak langkah yang ia akan ambil untuk membaiki perkara yang perlu meletakkan lima di tempat yang betul? Tiga. Kerana sekarang saya perlu bergerak satu, dua, tiga. Berapa banyak langkah yang ia akan mengambil untuk meletakkan empat di tempat yang betul? 4 plus 5, ditambah 6, ditambah 7. Oleh karena itu, secara matematik sama dengan apa yang kita diterangkan untuk jenis pemilihan. Kami mempunyai siri ini yang hanya meningkat. 1 tambah 2 tambah 3 tambah 4, atau sebaliknya, 7 plus 6 ditambah 5 ditambah 4 menambah sehingga untuk hari ini tujuan ke atas perintah n kuasa dua. Jadi biarlah saya menetapkan juga bahawa gelembung jenis juga dalam n kuasa dua. Kerana dengan gelembung jenis, masing-masing kali saya pergi melalui senarai, Saya mengambil kira-kira berapa banyak langkah? Setiap kali saya benar-benar berjalan dari sana ke sana? Secara kasar n langkah. Tetapi berapa kali mungkin saya perlu melalui senarai? Well, secara kasar n masa. Mungkin n tolak 1, tetapi secara kasar n kali. Nah, mengapa? Nah, dengan semacam gelembung, jika kita mulakan dengan jenis gelembung, dengan senarai dalam yang paling teruk mungkin keadaan, yang sekali lagi adalah ke belakang, apa yang akan berlaku? Saya memeriksa senarai, dan nombor salah tergolong sepanjang jalan di sana. Tetapi dengan jenis gelembung, sejauh melakukan satu bergerak pas pertama saya melalui senarai? Berapa banyak tempat dia mendapatkan lebih dekat ke tempat yang betul? Hanya satu. Jadi, jika anda jenis sebab melalui ini, setiap kali melalui algoritma ini, Mengambil secara kasar n langkah Daud. Tetapi berapa ramai pas melalui senarai adalah ia akan mengambil selama satu hingga gelembung ke kiri di mana ia tergolong? Dia ada untuk bergerak seperti, n ruang dengan cara ini. Jadi hanya untuk melakukan pengasingan senarai, Saya perlu berjalan kaki berulang-alik n kali. Dan setiap kali, saya melihat n unsur-unsur. Begitu n perkara n kali pada perintah n kuasa dua. Sekarang, kita akan melihat dalam beberapa daripada seluar pendek yang tertanam dalam Masalah seterusnya CS50 ditetapkan, pendekatan lain pada ini, tetapi buat masa ini, mari kita mempertimbangkan beberapa masa yang lain sedang berjalan, terutamanya jika orang-orang yang menyusun mengambil sedikit masa untuk tenggelam dalam. Apa yang algoritma kita lihat sudah yang mengambil atas perintah n langkah? Apakah yang perlu mengambil beberapa linear daripada beberapa langkah yang kita lihat setakat ini? Apa itu? Pencarian direktori telefon. Algoritma pertama. Betul? Di mana kita berada linear mencari Mike Smith? Sesungguhnya. Dari minggu sifar, apabila saya mula menjadikan satu halaman pada satu masa, dan saya juga berkata bahawa ia adalah jenis algoritma perasaan linear, dan kami bahawa gambar pada papan dengan garis merah yang lurus dan kuning lurus line, mereka sememangnya algoritma yang ada di O besar n. Kerana untuk mencari Mike Smith dalam telefon buku n muka surat, dalam kes paling teruk, mungkin mengambil masa saya n langkah. Bagaimana pula dengan mengambil kehadiran? Satu dua tiga empat lima enam. Apa yang masa berjalan ini algoritma untuk mengambil kehadiran? O Big n, kerana dalam teori saya perlu menunjukkan semua orang di dalam bilik. Sekarang sebagai diketepikan, bagaimana pula dengan pengoptimuman lain dari minggu sifar? Dua, empat, enam, lapan, 10, 12. Seorang saintis komputer akan sedar, tunggu satu minit, itu atas perintah n dibahagikan dengan dua langkah. Betul? Kerana saya lakukan dua orang pada satu masa. Tetapi kita akan mengabaikan terma perintah yang lebih rendah, dan kami hanya akan buang jurang dengan 2, dan hanya berkata, Wahai besar n untuk algoritma itu juga. Bagaimana dengan yang ini? Kami akan melewati beberapa ini, tetapi apa yang adalah satu algoritma yang telah log n? Yang telah mengambil kira-kira log n langkah? Ini pecah dan perintah. Tepat sekali. Seperti contoh buku telefon di minggu sifar dan awal hari ini, di mana kita dibahagikan masalah lagi dan lagi dan lagi. Kita menarik ke atas pesawat pada minggu sifar dalam garisan hijau melengkung, dan kami berkata hari itu ia algoritma logaritma. Dan sesungguhnya, bilangan langkah-langkah yang yang diperlukan untuk melaksanakan pecah dan menakluk, atau carian binari seperti yang kita akan mula memanggil ia, seperti dalam buku telefon, adalah atas perintah log dan langkah-langkah. Dan ini adalah sedikit satu yang pelik. Apa yang mengambil satu langkah, atau lebih khusus beberapa langkah berterusan? Mungkin ia dua, mungkin ia adalah tiga, tetapi seorang saintis komputer hanya memudahkan ia sebagai O besar 1, beberapa nombor tetap langkah. Apakah sesuatu yang anda boleh berbuat demikian mengambil beberapa langkah-langkah yang berterusan? Apa yang masa berjalan bertepuk tangan? Masa yang berterusan. Betul? Seperti, apa yang masa berjalan melakukan apa-apa yang mengambil masa hanya satu operasi, seperti mencetak F Hello World. Yang mungkin dikatakan sebagai masa yang berterusan, melainkan jika kurang kes sudut dengan cap F, apa mungkin masa yang berjalan cetak F sebenarnya berlaku? Dan mengapa? Apakah n pengukur dalam kes itu? PENONTON: [didengar]. DAVID J. MALAN: Tepat sekali. Bilangan aksara kita ingin cetak. Jadi ia amat peka konteks. Hari ini, kita telah memberi tumpuan banyak pada huruf dan nombor di atas kapal. Tetapi ia juga mungkin watak-watak dalam rentetan yang sebenar. Jadi, ternyata terdapat satu lagi langkah yang akan mula mengambil berat tentang, dan itu bertentangan dengan O besar, jadi untuk bercakap. Itulah notasi omega. Manakala O besar bermakna apa yang, yang atas terikat pada masa anda berjalan? Maksima, berapa banyak masa mungkin sesuatu yang diambil? Omega-- maaf ini terus datang up-- adalah bertentangan dengan itu, di mana ia adalah lebih rendah terikat pada jumlah masa sesuatu yang mungkin mengambil masa. So. misalnya, apa yang algoritma yang mengambil langkah-langkah sentiasa n kuasa? Nah, salah satu daripada algoritma yang kami telah lihat hari ini, sebenarnya, mungkin itu juga. Jenis pemilihan. Pemilihan jenis agak bodoh. Walaupun maaf algorithm--, walaupun jika array sudah disusun, jenis pemilihan akan terus berjalan melalui senarai memastikan ia mempunyai yang paling kecil elemen lagi dan lagi dan lagi. Juga, meskipun manusia dalam penonton tahu bahawa, tunggu satu minit, anda sudah lulus unsur yang paling kecil, komputer tidak tahu bahawa sehingga ia kelihatan sepanjang jalan melalui senarai. Begitu juga, terikat yang lebih rendah mungkin juga diambil kira mungkin masa linear. Berapa banyak masa yang diperlukan untuk jenis n elemen dalam yang terbaik kes menggunakan sesuatu seperti jenis gelembung? Katakan senarai anda sudah disusun. Kami berkata semacam gelembung mengambil perintah n kuasa dua langkah. Tetapi bagaimana jika ia sudah disusun? Bagaimana jika anda sedar selepas satu pas melalui array yang anda telah membuat sebarang pertukaran? Adakah anda perlu untuk terus membuat lebih pas? No. Jadi terikat lebih rendah pada gelembung jenis mungkin dikatakan linear. Omega n. Dan kita boleh melihat yang lain dari ini juga. Jadi mari kita lihat cepat pada hanya visualisasi di sini untuk melihat bagaimana membezakan diri mereka. Saya akan pergi ke sini ke dalam ini halaman yang boleh didapati di laman web C50-kanak, tetapi ia akan menjadi sakit untuk mendapatkan kerja, kerana ia menggunakan teknologi yang dipanggil Java applet, yang merupakan sebahagian besarnya disokong hari ini, sekurang-kurangnya oleh Chrome dan lain-lain yang tertentu. Dan biarlah saya pergi ke hadapan dan mempercepatkan ini dan menjelaskan apa yang berlaku. Ini adalah demonstrasi gelembung jenis, algoritma pertama kita melihat. Dan ia adalah satu visualisasi di mana setiap bar ini mewakili nombor. Semakin besar bar, yang lebih besar nombor. Semakin kecil bar, yang lebih kecil nombor. Dan apa yang anda lihat secara visual, walaupun walaupun ini akan super cepat, adalah bahawa bar merah adalah seperti saya, berjalan berulang-alik menetapkan masalah. Anda boleh melihat bahawa unsur-unsur yang lebih besar memang menggelegak sehingga ke kanan, dan unsur-unsur yang lebih kecil sedang menggelegak sehingga kiri. Dan turun di sini, jika kita benar-benar melihat dengan lebih dekat, kita sebenarnya boleh mengira beberapa perbandingan dan swap yang sedang dibuat. Tetapi sebaliknya, mari kita lihat di algoritma kedua kita melihat lebih awal dengan kami sukarelawan, jenis pemilihan. Visual, ia mempunyai kesan yang sangat berbeza. Tetapi ia adalah, sekali lagi, sangat intuitif, dalam bahawa kita terus memilih seterusnya terkecil elemen, dan kami mendapat sedikit bertuah. Yang merasakan asasnya lebih cepat. Tetapi jika kita berlari ini lagi dan lagi dan sekali lagi dengan banyak input, kita akan melihat bahawa itu memang masih di O besar n kuasa dua. Mari kita buat satu yang terakhir gula-jenis kemasukan, yang merupakan algoritma ketiga kita melihat, dan ingat yang satu ini memperkatakan unsur-unsur sebagai ia menghadapi mereka, tetapi kemudian ia mungkin perubahan perkara yang lebih untuk memberi ruang, memasukkan unsur-unsur mana mereka berada. Dan ini juga berakhir memberikan Keputusan akhir. Sekarang semua tiga daripada berasa cukup cepat. Dan sesungguhnya, saya berlari mereka pada klip yang cukup baik. Tetapi asasnya, mereka semua cukup dahsyat, untuk bersikap jujur. Semua algoritma ini setakat ini yang berjalan di O besar n kuasa dua mengambil agak sedikit masa untuk menjalankan pada akhirnya. Dan sesungguhnya, kita dapat melihat dan rasa ini akhir sekali jika saya tarik demo ketiga dan terakhir ini. Ini merupakan satu lagi visualisasi yang akan untuk menunjukkan jenis gelembung di sebelah kiri, jenis pemilihan di tengah, dan sesuatu, sebagai salah satu daripada kami tangan menimbulkan sebelum ini mencadangkan, bergabung apapun di sebelah kanan. A pecah dan perintah strategi di sebelah kanan. Dan itu, sebenarnya, apa yang kita akan melihat pada hari Rabu. Tetapi mari kita masa ini untuk dijalankan secara selari. Ia adalah kira-kira jumlah yang sama elemen, semua berjalan pada masa yang sama. Bubble jenis vs pilihan jenis vs merge. Kini, mereka semua berjalan dalam teori pada masa yang sama. CPU sedang berjalan di kelajuan yang sama, tetapi anda dapat merasakan bagaimana membosankan ini adalah dengan cepat akan menjadi, dan betapa cepat ketika kita menyuntik sedikit minggu algoritma sifar boleh kita mempercepatkan perkara. Dan sekarang mari kita bandingkan ini dalam satu bentuk lepas. Saya akan pergi ke hadapan ke laman web CS50, di mana kami mempunyai pautan akhir ini untuk hari ini, di mana seseorang di internet sila meletakkan bersama-sama video yang menangkap apa pengasingan yang berbeza algoritma bunyi seperti. Ini adalah jenis sisipan. [Bip] Di mana anda memohon frekuensi yang berdasarkan ketinggian bar bar. Ini adalah jenis gelembung. [Bip sesat] Datang berikut is-- datang sehingga is-- pilihan jenis datang, di mana lagi, kita memilih unsur terkecil yang akan datang, dan kita dapat melihat ia berkembang dari kiri ke kanan. Bergabung apapun, pemenang kami setakat hari ini. Perhatikan bagaimana ia membahagikan perkara ke dalam [didengar] separuh dan pihak. Jenis Gnome, yang kita tidak mempunyai bercakap tentang, dan mewujudkan visual dan audally sedikit bentuk yang berbeza dan bunyi. Pergi dan balik, membersihkan keadaan. Juga menyemak heapsort di laman web ini lelaki itu. Dan itu sahaja. Kita akan lihat masa depan. [Whooshing DAN MUZIK]