>> [Bermain muzik]
>> DAVID J. MALAN: Baiklah.
Jadi mengalu-alukan kembali.
Ini adalah CS50, dan adalah hujung minggu tiga.
>> Jadi ingat dalam beberapa minggu yang lalu, kita telah membelanjakan agak sedikit
masa di C, pengaturcaraan, pada sintaksis.
Dan ia adalah perkara biasa, jika anda masih bergelut dengan Set Masalah 2, menjadi
terhantuk kepala anda ke dinding.
Ia adalah mesej ralat samar-cari dan pepijat yang anda
tidak boleh agak mengejar ke bawah.
Kerana, yakinlah, bahawa hanya dalam masa beberapa minggu anda akan melihat kembali pada
perkara-perkara seperti Caesar, dan [? V-genair,?] mungkin juga Retak, dan
menyedari betapa jauh anda telah datang dalam tempoh masa yang singkat.
Jadi jika itu apa-apa saguhati, hang di sana buat masa ini.
>> Hari ini, walaupun, kita mula peralihan ke tahap yang lebih tinggi perkara.
Dan kita mula mengambil mudah bahawa anda semua tahu bagaimana untuk program, atau sekurang-
kurangnya permulaan bahawa tahap keselesaan.
Dan kita akan mula memikirkan bagaimana kita boleh pergi tentang bentuk program yang lebih
berkesan.
Bagaimana kita boleh pergi tentang mengoptimumkan kecekapan algoritma kami, dan
umumnya menyelesaikan lebih masalah yang menarik.
Dan mula mengambil mudah bahawa, jika kita mahu, kita boleh mana-mana kod
satu contoh yang kita ada dalam fikiran.
Jadi hari ini, kita tidak menyentuh papan kekunci apa-apa bentuk kod.
Ia akan menjadi tahap yang lebih tinggi, dan akhirnya, kira-kira penyelesaian masalah.
>> Jadi, untuk sampai ke tahap ini, biarlah saya mencadangkan bahawa tujuh berikut
segi empat tepat mewakili tujuh pintu, di belakang yang sejumlah besar
nombor, antaranya adalah nombor 50.
Biar saya projek ini pada ini skrin di sini juga.
Dan mencadangkan bahawa kita perlu sukarela untuk membantu mencari saya beberapa di hadapan
internet di sini untuk melihat.
Datang pada sehingga, dalam merah jambu.
Baiklah.
Apa nama anda?
>> JENNIFER: [didengar]
>> DAVID J. MALAN: Maaf?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Baiklah, Jennifer.
Nice untuk bertemu dengan kamu.
Ayuh up.
Jadi ini di sini adalah tujuh pintu, dan apa Saya ingin anda lakukan untuk kita di sini,
di hadapan semua rakan sekelas anda, adalah mencari kita bilangan, 50.
Untuk mengetahui nombor, anda boleh main belakang mana-mana pintu dengan hanya menoreh
di salah satu pintu, dan ia akan mendedahkan nombor.
Dan mari kita lihat berapa cepat anda boleh mencari kami nombor, 50.
>> 15.
16.
50.
Baik dilakukan.
Baiklah.
Pusingan tepukan untuk Jennifer.
>> [Tepuk tangan]
>> Baiklah.
Jadi apa yang strategi anda untuk mencari nombor, 50?
>> JENNIFER: Um, saya fikir mungkin jika -
[Didengar]
>> DAVID J. MALAN: Oh.
Memberikan satu saat.
Jadi adalah strategi anda untuk mencari nombor, 50?
>> JENNIFER: Jadi saya hanya bermula pada mula melihat apa yang nombor pertama
adalah, dan kemudian saya fikir, mungkin jika mereka disusun, saya hanya akan terus
mengetuk lebih tinggi?
>> DAVID J. MALAN: OK.
Dan kita seolah-olah telah menemui bahawa untuk menjadi kes itu.
Walaupun, mari kita mengupas kembali lapisan hanya sedikit, dan anda mahu pergi
hadapan dan mendedahkan pintu lain anda boleh memilih?
>> JENNIFER: Oh, sayang.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Jadi saya hanya mendapat bertuah.
>> DAVID J. MALAN: Jadi anda mendapat bertuah.
Baiklah.
Jadi tidak buruk.
Tetapi itulah yang menarik wawasan, bukan?
Jika anda diambil, dan anda tidak dapat, sememangnya, agak bernasib baik di sana.
Tetapi jika anda menganggap bahawa nombor yang disusun, anda boleh menjadi lebih tepat
tentang bagaimana yang mempengaruhi tingkah laku anda?
>> JENNIFER: Jadi, jika mereka telah diselesaikan, saya fikir mungkin terkecil hingga terbesar.
>> DAVID J. MALAN: OK.
>> JENNIFER: Atau jika ini akhirnya menjadi benar-benar besar, maka terbesar kepada terkecil.
>> DAVID J. MALAN: OK.
Jadi terbesar kepada terkecil, atau kecik hingga besar.
Tetapi biarlah saya mencadangkan, andaikan anda mempunyai mendapat malang, dan menganggap bahawa mereka
tidak, sebenarnya, disusun, berapa ramai pintu-pintu yang anda mungkin terpaksa mengintip
belakang dalam kes paling teruk?
>> JENNIFER: Semua daripada mereka.
>> DAVID J. MALAN: Semua daripada mereka.
Jadi mari kita umum bahawa n.
Terdapat berlaku kepada 7, tetapi mari lagi umumnya mengatakan ada n pintu pada
skrin di sini.
Jadi dalam kes paling teruk, anda perlu ke belakang 7 pintu, atau n pintu.
Dan hal ini benar-benar, ia adalah sedikit nasib hari ini, tetapi ia adalah benar-benar satu linear
algoritma pelbagai, walaupun anda adalah jenis ponteng sekitar.
Adakah adil?
>> JENNIFER: Ya.
>> DAVID J. MALAN: Baiklah, biarlah saya melihat jika anda perubahan strategi jika saya menggerakkan kita untuk
Contoh kedua kami di sini dengan 7 pintu yang berbeza.
Nombor yang sama, tetapi ini kali mereka disusun.
Apakah strategi anda di sini akan menjadi, cuba untuk meletakkan keluar dari fikiran anda apa
nombor-nombor lain adalah -
>> JENNIFER: OK.
>> DAVID J. MALAN: - lebih awal?
>> JENNIFER: Mari kita mulakan dengan yang pertama.
>> DAVID J. MALAN: Baiklah.
Mulakan dengan yang pertama.
4.
Sekarang di mana anda akan pergi, dan mengapa?
>> JENNIFER: 4 adalah benar-benar kecil.
Jadi, jika mereka mungkin jenis yang paling kecil hingga terbesar, ia perlu
menjadi dua kali ganda, dan -.
>> DAVID J. MALAN: OK.
Mari kita lihat, yang anda fikir?
>> JENNIFER: Cuba yang terakhir.
Nice.
>> DAVID J. MALAN: Sangat baik dilakukan.
Baiklah.
>> [Tepuk tangan]
>> DAVID J. MALAN: OK.
Jadi anda sebenarnya melakukan ini teruk, kerana anda
melakukannya dengan baik.
Yang meninggalkan kita tidak dapat membuat mata tertentu.
Jadi mari kita cuba untuk melancarkan kembali di sini.
>> JENNIFER: OK.
>> DAVID J. MALAN: Sangat baik dilakukan, tetap.
Jadi anda bermula pada awal, anda melihat bahawa ia adalah 4, maka anda
berpindah ke akhir.
Tetapi andaikan anda tidak bernasib baik sana, dan andaikan 50
adalah di tempat lain.
Apakah langkah yang ketiga anda telah?
>> JENNIFER: Pergi balik ke permulaan.
>> DAVID J. MALAN: Kembali untuk permulaan.
OK, jadi anda akan telah menyentuh pintu ini, yang 8.
Baiklah.
Jadi itu bukan 50.
Di mana anda akan kelihatan akan datang?
>> JENNIFER: Jika saya tidak tahu mereka disusun.
>> DAVID J. MALAN: Betul.
Nah, jika anda tidak tahu mereka telah disusun -
>> JENNIFER: Oh, tidak tahu, ya.
>> DAVID J. MALAN: - tetapi anda tidak tahu di mana 50 adalah lagi?
>> JENNIFER: Hanya menyimpan berterusan.
>> DAVID J. MALAN: Baiklah.
OK.
Teruskan usaha.
OK, saya boleh bekerja dengan.
>> JENNIFER: OK.
>> DAVID J. MALAN: Sekarang, jika anda hanya akan terus pergi, apa yang anda
algoritma devolving disokong ke dalam.
>> JENNIFER: The linear -.
>> DAVID J. MALAN: Ia adalah jenis linear.
Tetapi biarlah saya mencadangkan, biarlah saya meletakkan di tempat kejadian.
Biar saya menyegarkan halaman.
Bilangan yang sama, perkiraan sama, pintu yang sama.
Tetapi berfikir kembali kepada hari pertama dalam kelas apabila kita mengoyakkan buku telefon di
separuh, jenis, dan apa yang strategi kami di sana?
>> JENNIFER: Mula di tengah-tengah.
>> DAVID J. MALAN: OK.
Jadi bermula di tengah-tengah.
Jadi mari kita pergi ke hadapan dan meniru itu.
Mula di tengah-tengah oleh mendedahkan pintu itu.
Jadi nombor 16.
Jadi apa yang akan lelaki yang kuat telah dilakukan, yang mengoyakkan buku telefon pada separuh,
untuk mendapatkan rasa yang akan datang?
>> JENNIFER: Pergi pada separuh ini.
>> DAVID J. MALAN: Dan mengapa di sebelah kanan?
>> JENNIFER: Jika mereka jenis yang paling kecil hingga terbesar, maka 50 hendaklah
pada akhir itu.
>> DAVID J. MALAN: Baik.
Benar-benar munasabah.
Jadi seperti buku telefon, anda pergi ke betul bertentangan dengan kiri, tetapi di sini
adalah Fleet utama.
Anda kini boleh buang, atau mengoyakkan, separuh daripada masalah ini, meninggalkan anda tidak
dengan 7 pintu, tetapi benar-benar dengan hanya 3.
Yang merupakan kira-kira separuh daripada saiz masalah.
Baiklah.
Jadi sekarang apa yang anda akan mempunyai dilakukan selepas anda betul?
>> JENNIFER: Jadi 16 masih agak kecil, berbanding dengan 50, jadi mungkin saya akan cuba,
seperti, yang satu ini.
>> DAVID J. MALAN: Baiklah.
42.
Baiklah, jadi sekarang apa yang anda naluri memberitahu anda?
>> JENNIFER: Saya boleh buang ini dan kemudian hanya -
>> DAVID J. MALAN: OK.
Baik, anda boleh buang separuh kiri sana.
>> JENNIFER: - memilih satu ini.
>> DAVID J. MALAN: Dan kanan.
>> JENNIFER: Ya.
>> DAVID J. MALAN: Jadi, walaupun ia sukar untuk melihat mungkin, apabila ada sahaja
7 pintu, memikirkan, sekarang, yang konsisten
Algoritma anda hanya digunakan.
Dalam kes sebelum ini, anda pula bernasib baik, yang hebat.
Tetapi anda tidak menggunakan heuristik a, Saya akan berkata.
Anda menggunakan jenis naluri anda, dan mengetahui ia disusun, jika ia cukup
kecil pada permulaan, jelas, kami telah mendapat untuk pergi lebih ke kanan.
Tetapi dalam erti kata lain, anda mendapat bernasib baik, kerana mungkin ini adalah nombor 100,
50 dan mungkin lebih di tengah-tengah.
Mungkin 50 pun di sini.
>> Tetapi apa yang anda lakukan sedikit berbeza kali ini, anda melakukan perkara yang sama
lagi dan lagi.
Dan saya akan berhujah bahawa apa yang anda hanya tidak, walaupun dipengaruhi oleh telefon
contoh buku, adalah sesuatu yang lebih lebih algoritma, dan banyak
kurang khas bingkai.
Apalagi naluri.
Jadi pada akhir hari, bagaimana akan anda menggambarkan kecekapan
algoritma pertama, di mana anda pergi kiri ke kanan, berbanding
algoritma kedua di sini?
>> JENNIFER: Yang ini harus, seperti, mungkin mengurangkan separuh masa, atau lebih, ya.
>> DAVID J. MALAN: OK, mungkin lebih.
Mari kita menolak sedikit sukar pada itu.
Apa yang benar-benar, jika kita terus ini logik, kita pasti yang separuh
berjalan masa dengan algoritma kedua ini dengan membuang separuh daripada
nombor, tetapi apa yang kita lakukan pada seterusnya lelaran, apabila Jennifer mendedahkan
nombor kedua?
>> Kami separuh bilangan pintu lagi.
Dan kemudian apa yang kita lakukan selepas itu, jika terdapat lebih banyak pintu untuk bermain dengan?
Kami akan mengurangkan separuh mereka, dan sekali lagi, dan sekali lagi, dan lagi.
Dan ini adalah sama seperti kalian semua berdiri pada minggu pertama
kelas, separuh daripada anda duduk, separuh anda duduk, separuh daripada anda
duduk, sehingga satu-satunya jiwa berdiri.
Dan kita berkata bahawa masa berjalan itu, beberapa langkah yang diambil adalah
atas perintah apa?
>> SPEAKER 1: [didengar]
>> DAVID J. MALAN: Jadi log base 2 n, atau hanya lebih mudah, log n.
Jadi sesuatu logaritma.
Dan graf yang bukan satu garis lurus yang hanya mendapat lebih teruk dan lebih teruk, ia adalah
keluk yang menarik ini yang tidak begitu buruk dari masa ke masa.
Jadi mari kita berpegang kepada idea ini.
Mari kita mengucapkan terima kasih kepada Jennifer.
Terima kasih banyak untuk datang di atas.
Dan, salah satu saat.
Tiada lampu meja hari ini, tetapi kita tidak mempunyai CS50 bola tekanan.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Baiklah, di sini.
Terima kasih kerana menanggung tekanan di sini.
Baiklah.
Jadi mari kita lihat jika kita tidak boleh sekarang merasmikan ini sedikit lebih.
Jadi sekali lagi, apa yang kita lakukan ialah dasarnya perkara yang sama seperti yang kita lakukan
dalam minggu yang pertama.
Tetapi bukannya berakhir dengan hanya linear algoritma, yang kita digambarkan
sebelum ini sebagai garis lurus, di mana, jika kita meletakkan satu pintu lanjut mengenai
skrin, kemudian Jennifer akan terpaksa melihat, berpotensi,
di sebalik satu pintu lagi.
Jika kita meletakkan dua pintu, dia mungkin mempunyai ke belakang dua lagi pintu.
>> Dan sebagainya, ada ini linear Hubungan antara saiz
masalah di, berkata, paksi-x, dan jumlah masa yang diperlukan untuk
menyelesaikan pada paksi.
Tetapi gambaran yang saya merujuk kepada awal adalah garis hijau.
Green sengaja, kerana ia hanya berasa lebih baik.
Dalam teori, algoritma, apabila kita melakukannya dengan buku telefon, apabila kita melakukannya
dengan anda semua mengira sama lain, dan dalam kes kedua, apabila Jennifer hanya
adakah ia di sini, ia adalah jenis daripada asasnya yang lebih baik.
Kerana ia bukan sahaja dua kali lebih cepat.
Ia tidak pun empat kali dengan cepat.
Ia adalah bergantung sepenuhnya kepada apa yang saiz input itu, untuk berapa banyak
langkah-langkah yang ia akhirnya mengambil.
>> Dan sebagainya idea ini mudah yang kita semua mengambil untuk diberikan dengan buku telefon,
boleh juga digunakan kepada sesuatu yang seperti ini.
Dan ini mungkin lebih bersahaja dikenali sebagai, kerana anda mungkin
bayangkan, membahagi dan menakluk.
Tidak seperti apa yang kami lakukan, sudah tentu, dengan buku telefon.
>> Tetapi pseudokod itu, ingat, adalah ini.
Jadi kita tidak akan melakukan ini sekali lagi, tetapi ingat bahawa minggu pertama, kita semua berdiri
dan kemudian separuh daripada anda duduk, separuh daripada anda duduk, separuh daripada anda duduk.
Bahawa algoritma telah dilaksanakan dalam sedikit cara menipu, dalam itu, ia
tidak hanya salah satu daripada saya mengira, asasnya, lebih cekap.
Dalam kes itu, saya telah menggunakan sumber sekunder.
Jenis, pelbagai CPU, pelbagai otak, beberapa orang pintar dalam
bilik telah membantu saya dapat daripada sesuatu linear kepada sesuatu
logaritma, dari sesuatu merah kepada sesuatu yang hijau.
>> Tetapi dalam kes ini, Jennifer sahaja boleh asasnya menambah baik
prestasi algoritma pertama oleh, sekali lagi, hanya memikirkan sedikit lebih keras.
Dan sekarang, apabila ia datang masa untuk melaksanakan perkara-perkara ini, memikirkan
apa baris kod anda boleh menulis apa-apa bahawa anda boleh mengulangi sekali lagi, dan
sekali lagi, dan sekali lagi, jenis dengan cara yang menggelung.
Kerana anda tidak akan mempunyai mewah, seperti Jennifer lakukan pada pertama,
hanya mempunyai sejumlah besar IFS dan berkata, hmm, jika nombor pertama ini adalah 4,
biarlah saya melompat sepanjang jalan ke akhir.
Aduh, jika nombor yang terlalu besar, biarlah saya bergerak kembali sewenang-wenangnya
kepada elemen kedua.
Anda akan mendapati bahawa ia akan menjadi lebih sukar untuk merasmikan apa yang kita manusia
ambil untuk diberikan sebagai sangat munasabah heuristik, tetapi komputer hanya
akan melakukan apa yang anda beritahu ia lakukan.
>> Sekarang ini telah sangat menarik implikasi.
Graf ini semacam bertujuan untuk menyusun daripada mengatasi visual, tetapi notis, di mana
adalah garis lurus dalam graf ini?
Di manakah graf linear yang kita panggil n?
Nah, itu jenis ke arah bawah gambar ini, bukan?
Jadi semua yang kita lakukan ialah kita telah jenis dizum keluar ke x-paksi dan
paksi-y cuba untuk mendapatkan rasa apa lain-lain jenis keluk kelihatan seperti.
>> Dan khusus matematik ungkapan hari ini tidak akan perkara itu
banyak, tetapi notis bahawa terdapat banyak algoritma yang jauh lebih teruk daripada
sesuatu yang linear.
Sesungguhnya, n cubed kelihatan cukup buruk.
2 hingga n kelihatan cukup buruk. n kuasa dua kelihatan cukup buruk.
Dan kita akan melihat apa yang beberapa orang mungkin dalam realiti hari ini.
Dan log n tidak berasa seperti tidak baik, tetapi lebih baik daripada n log asas 2 n.
Tetapi anda tahu, ia akan menjadi lebih lebih hebat jika Jennifer, atau jika kita,
bahawa minggu pertama, telah tampil dengan sesuatu yang log log n.
>> Jadi, dalam erti kata lain, ada keseluruhan ini pelbagai penyelesaian yang mungkin untuk
masalah, tetapi di sini, notis apa yang akan berlaku.
Apabila saya zum keluar, yang mana satu keluk akan membuktikan untuk menjadi mutlak
paling teruk orang-orang yang pada skrin sekarang?
Jadi n cubed kelihatan cantik buruk pada masa ini.
Tetapi jika kita zum keluar dan melihat lebih banyak x dan paksi-y, yang akan
menguasai akhirnya?
Jadi ia sebenarnya ternyata bahawa 2 kepada n, dan anda boleh memikirkan ini hanya dengan
memasang dalam beberapa semakin besar nombor, dan anda akan melihat bahawa 2 kepada
n, sesungguhnya semakin besar lebih cepat.
Jika kita benar-benar zum keluar, 2 kepada n algoritma benar-benar menghisap.
Maksud saya, ini akan mengambil agak sedikit masa untuk
komputer untuk melahirkan melalui.
>> Tetapi anda akan melihat dari masa ke masa, terutamanya dengan set masalah masa depan dan juga
projek akhir, adalah data anda set mendapat besar, betul?
Malah dalam versi pertama Facebook, kerana bilangan kawan-kawan, dan
bilangan pengguna berdaftar mendapat besar, anda boleh menyusun telefon dalam dan
melaksanakan sesuatu dengan carian linear, atau pengasingan sangat mudah
algoritma, seperti yang kita akan lihat hari ini.
Anda perlu mula berfikir sukar dan lebih keras mengenai masalah ini.
Dan jenis masalah tempat seperti Facebook, dan Google, dan Microsoft,
dan lain-lain kerja-kerja betul-betul ini jenis jenis data yang besar soalan-soalan
semakin hari ini.
>> Baiklah.
Jadi kejayaan Jennifer dalam yang kedua algoritma, terus-terang, dia menakjubkan
baik kali pertama, tetapi mari menulis sebagai nasib supaya kita
boleh membuat hal ini.
Dalam kes kedua, dia memanfaatkan satu algoritma yang berulang lagi dan
sekali lagi, tetapi dia mengambil masa untuk diberikan andaian tertentu yang kita dibenarkan
, tetapi dia dieksploitasi beberapa terperinci kali kedua dia tidak mempunyai
kali pertama.
Iaitu apa?
>> Bahawa senarai itu disusun.
Jadi sebaik sahaja senarai itu disusun, kami mendakwa bahawa Jennifer berupaya untuk melakukan
asasnya yang lebih baik.
7 pintu, ya, tidak begitu menarik, tetapi rasa ia kami 7 juta pintu.
Log n pasti akan untuk melaksanakan banyak, lebih
cepat dalam jangka masa panjang.
Tetapi dia terpaksa mempunyai pintu disusun untuk beliau.
Sekarang, saya mengambil kebebasan berbuat demikian terlebih dahulu pada skrin komputer
di sini, tetapi rasa Jennifer bahawa terpaksa melakukannya sendiri?
Katakan bahawa pintu berkenaan data diwakili dalam pangkalan data, atau
rakan-rakan mendaftar untuk Facebook, atau mana-mana laman web di internet yang
pelbagai laman web mungkin perlu kepada indeks atau cari lebih.
>> Katakan anda hanya mempunyai data mentah ditetapkan dan ianya dibiarkan untuk anda, atau untuk
Jennifer untuk melakukan pengasingan itu?
Itu, sebaliknya, memerlukan kita menjawab soalan, baik, berapa banyak masa
akan mengambil Jennifer, atau saya, untuk menyusun nombor-nombor tersebut terlebih dahulu supaya
bahawa dia boleh mengambil kesempatan daripada itu?
Betul?
Kerana implikasi, sudah tentu, adalah jika ia mengambil masa saya yang agak lama untuk menyelesaikan
nombor, yang palang pintu yang peduli bahawa anda boleh menemui beberapa seperti 50 dengan begitu pantas,
seperti dalam kes Jennifer, jika kita lebih daripada terharu jumlah keseluruhan masa
ia mengambil masa oleh sorting perkara terlebih dahulu?
>> Jadi mari kita lihat jika kita tidak boleh yang gambaran di sini.
Saya mempunyai sejumlah besar tekanan yang lebih bola, jika yang membantu
memecahkan ais di sini.
Dan jika anda tidak keberatan, kita perlu tujuh sukarelawan -
pada, OK.
Wow.
Oleh itu, kita tidak perlu untuk menghabiskan pada lampu meja, ia seolah-olah.
Baiklah.
Jadi bagaimana pula kamu berdua di hadapan.
Bagaimana pula dengan anda dua lelaki di belakang.
Itulah empat.
Bagaimana pula dengan anda di hadapan lima, enam dan tujuh.
Di sana.
Rakan anda yang menunjukkan anda keluar, supaya anda mendapat hadiah.
>> Baiklah.
Ayuh up.
Dan mengapa tidak, kita perlu anda lelaki datang di sini.
Saya akan memberikan anda setiap nombor.
Dan pergi ke depan dan mengatur diri sepercaman kepada apa yang
yang digambarkan pada skrin.
>> [INTERPOSING suara]
>> DAVID J. MALAN: Oop, maaf.
Bug.
Baiklah.
Nah, di sini kita pergi.
Nombor lima.
Bilangan enam.
Satu, dua, tiga, empat, lima, enam, tujuh.
Oh, ini adalah janggal.
>> SPEAKER 2: saya hanya akan mendapat -.
>> DAVID J. MALAN: perjanjian yang baik.
Baiklah.
Terima kasih kerana mengambil bahagian.
>> [Tepuk tangan]
>> OK.
Baiklah.
Oleh itu, kita mempunyai empat, dua, enam, satu, tiga, tujuh, lima.
Perfect jadi kami mempunyai tujuh sukarelawan di sini yang sama lebar kepada
array yang kita sedang bermain dengan lebih awal.
Dan saya memilih tujuh atas sebab-sebab yang akan hanya
mudah sedikit.
Dan saya akan mencadangkan pertama yang kita menyusun tujuh sukarelawan.
Jika anda ingin, pertama, untuk bertanya khabar walaupun.
Kerana ini akan menjadi satu janggal beberapa minit.
Perkenalkan diri kamu sendiri.
>> GRACE: Hi, saya Grace.
Saya seorang mahasiswa tingkat kedua di Leverett House.
>> Branson: Hi.
Saya Branson.
Saya bayat di Weld.
>> Gabe: Hi.
Saya Gabe.
Saya seorang junior di Cabot.
>> NEIL: Saya Neil.
Saya bayat di Matthews.
>> Jason: Saya Jason.
Saya bayat di Greenough.
>> MIKE: Saya Mike.
Saya bayat di Grays.
>> JESS: Saya Jess.
Saya seorang mahasiswa tingkat kedua di Leverett.
>> DAVID J. MALAN: Excellent.
Baiklah.
Well, terima kasih kepada semua kami sukarelawan di sini setakat ini.
Dan cabaran yang ada sekarang akan sebagai untuk menyusun daripada lelaki ini, tetapi kemudian
kita akan perlu berfikir sedikit keras tentang bagaimana cekap kita sebenarnya
disusun mereka.
Jadi mari kita mula-mula cuba ini.
Kamu boleh melihat nombor masing-masing hanya dengan meletakkan sekitar sudut.
Teruskan dan mengambil beberapa saat, dan jenis dirimu dari kecik pada
dibiarkan terbesar di sebelah kanan.
Go.
>> OK.
Baik.
Itu adalah benar-benar cepat darn.
Sekarang seseorang di sini, apa yang algoritma bahawa lelaki digunakan?
>> SPEAKER 1 kurangnya untuk terbesar.
>> DAVID J. MALAN: OK.
Kurangnya terbesar adalah benar-benar menyelesaikan satu objektif, tetapi saya tidak pasti itu
benar-benar satu algoritma.
Kurangnya terbesar tidak memberitahu saya langkah demi langkah apa yang perlu dilakukan.
Ya?
>> SPEAKER 1: [didengar]
>> DAVID J. MALAN: OK.
Jadi, jika anda melihat seseorang yang lebih kecil daripada nombor anda, kemudian bergerak ke
hak mereka.
Jadi yang kini semakin ekspresif, lebih seperti algoritma, kerana anda
boleh berkata, jika ini, maka itu.
Oleh itu, kita mempunyai beberapa jenis membina bersyarat.
Dan lelaki ini seolah-olah untuk berbuat demikian beberapa kali, kerana sesetengah daripada anda berpindah sedikit
dari jauh.
Jadi ada mungkin beberapa jenis gelung yang berlaku di dalam fikiran mereka.
>> Tetapi mari kita cuba untuk merasmikan itu.
Jika anda semua boleh menetapkan semula kembali kepada perkiraan ini.
Mari kita lihat jika kita tidak boleh merasmikan ini bit, dan kemudian bertanya soalan, hanya
bagaimana cekap ini?
Sudah tentu, apabila kita melakukan ini lebih perlahan, ia akan berasa seolah-baik
algoritma, tetapi mari kita lihat jika kita boleh meletakkan jari kami pada langkah-langkah yang tepat.
>> Jadi, anda dua lelaki empat dan dua.
Atau anda susunan yang betul atau tidak betul?
Jelas sekali tidak betul.
Jadi kita bertukar.
Sekarang saya akan bergerak ke tepi di sini dan berkata, empat hingga enam.
Adakah anda betul atau salah?
>> Gabe: Betul.
>> DAVID J. MALAN: Betul.
Enam dan satu?
Nope.
Swap.
Itulah dua swap.
Enam dan tiga?
Nope.
Swap.
Enam dan tujuh?
Kelihatan baik.
Tujuh dan lima?
>> JESS: [didengar]
>> DAVID J. MALAN: OK, menukar.
Dan disusun.
Baiklah.
Jadi jelas tidak, kan?
Jadi ada adalah lebih berlaku.
Tetapi, sesungguhnya, orang-orang ini, walaupun hanya naluri.
disimpan bergerak.
Mereka tidak hanya berhenti, apabila mereka diperbetulkan satu masalah.
Jadi.
Malah, saya akan mempunyai untuk melakukan perkara yang sama.
Saya akan perlu menyelesaikan satu memundurkan kembali untuk permulaan masalah ini,
atau awal pelbagai ini orang, mari kita mula memanggil mereka.
>> Dan kini apa yang perlu saya algoritma pada lulus kedua menjadi?
>> SPEAKER 1: Perkara yang sama.
>> DAVID J. MALAN: Perkara yang sama.
Dan ini, saya mula suka, kan?
Sebaik sahaja anda boleh mendapati diri anda melakukan perkara yang sama sekali lagi dan sekali lagi, itu
menjadi lebih seperti algoritma, dan kurang naluri manusia.
>> Jadi sekarang, di sini kita pergi lagi.
Dua dan empat?
No
Empat dan satu?
Ah, ada sememangnya merupakan beberapa kerja masih perlu dilakukan.
Untuk dan tiga?
Baik.
Empat dan enam?
Enam dan lima?
Enam dan tujuh?
OK, sekarang, dilakukan.
OK, tidak.
Saya perlu pergi ke belakang.
>> Jadi sekarang, sekali lagi, kita lakukan ini sedikit lebih sengaja.
Dan kini, terdapat hanya satu otak melaksanakan algoritma ini.
Satu CPU, jika anda akan.
Dan terus-terang, itulah satu-satunya sumber kita akan mempunyai akses kepada.
Dan apabila kita kembali ke papan kekunci dan mempunyai sesuatu seperti C pada kami
pelupusan, kita hanya menulis program yang boleh melakukan satu perkara pada satu masa.
Manakala, lelaki ini masa yang lalu, kita dimanfaatkan otak kolektif mereka
seperti kamu lakukan pada sifar minggu.
Jadi mari kita terus melakukan ini.
>> Dua dan satu.
Dua dan tiga.
Tiga dan empat.
Empat dan lima.
Lima dan enam.
Enam dan tujuh.
Selesai?
Jadi saya, tetapi biarlah saya bermain peguam bela syaitan.
Adakah saya, jenis komputer yang hanya dibuat pas melalui pelbagai ini
orang, tahu bahawa saya lakukan?
>> SPEAKER 1: No
>> DAVID J. MALAN: Jadi mengapa?
Apa yang perlu saya lakukan untuk kesimpulan tegas bahawa saya dilakukan?
Mungkin salah satu pas lagi.
Betul?
Kerana semua yang saya tahu dari yang sebelumnya pas adalah bahawa saya diperbetulkan kesilapan.
Dan yang bermakna, mungkin ada masih kesilapan lain
yang saya perlukan untuk membetulkan.
Jadi saya hanya boleh pasti oleh gulung semula, dan kemudian memeriksa, satu kepada dua, dua
tiga, tiga dan empat, empat dan lima, lima dan enam, enam dan tujuh.
OK, sekarang saya tidak melakukan kerja.
>> Saya pasti boleh ingat bahawa saya tidak bekerja dengan sesuatu seperti pembolehubah,
suka int an.
Memanggilnya swap, dan jika swap adalah 0 sekali saya mendapatkan di sini, dan ia bermula pada 0, maka
Saya hanya akan menjadi bodoh untuk terus pergi ke belakang dan sebagainya, menyemak semula, dan
sekali lagi, dan sekali lagi, bukan?
Kerana anda terjebak dalam beberapa jenis gelung tak terhingga.
Jadi sebaik sahaja ada 0 swap, kita boleh mengatakan bahawa ini
algoritma memang lengkap.
>> Sekarang, mari kita meletakkan nama pada ini.
Algoritma yang saya mencadangkan kita hanya dilaksanakan adalah sesuatu yang dipanggil gelembung
jenis, yang dikenali sebagai apa-apa dalam erti kata bahawa nombor-nombor yang lebih besar daripada jenis
buih mereka untuk sampai ke atas, atau sehingga untuk akhir pelbagai nombor.
Tetapi bagaimana berkesan adalah algoritma ini?
Berapa banyak langkah-langkah yang tidak saya secara fizikal perlu mengambil, sebagai contoh, untuk menyelesaikan ini
tujuh manusia?
>> Empat hingga lima?
OK, terlalu banyak akhirnya akan menjadi jawapannya.
Tetapi kemudian, bilangan tertentu tidak begitu menarik.
Mari umum sebagai n.
Jadi, jika saya n orang di sini, dan mereka adalah, jenis, dalam susunan rawak di
permulaan, dalam susunan asal.
Nah, berapa banyak langkah-langkah yang tidak saya mempunyai untuk mengambil pas pertama?
Ia adalah salah satu, dua, tiga, empat, lima, enam, dan mereka tujuh orang, maka
itulah tujuh, enam -, supaya n minus one langkah kali pertama.
>> Sekarang, berapa banyak langkah-langkah yang tidak saya mempunyai untuk mengambil apabila saya digulung?
Nah, kita sebenarnya boleh dua kali ganda jika kita benar-benar mahu, tetapi untuk sekarang, saya
hanya akan berkata, semua betul, lain n tolak 1.
Jadi n tolak 1 akan mendapat menjengkelkan untuk mengesan, jadi mari kita
hanya pusingan sedikit.
Jadi 2n langkah.
Jadi 14 langkah-langkah, memberi atau mengambil.
>> Berapa kali saya mengambil satu langkah masa depan?
Nah, itu 3n.
benar-benar.
Dan kini, dalam kes paling teruk, untuk contoh, berapa kali saya akan mempunyai
pergi ke belakang dan sebagainya, belakang dan sebagainya, melaksanakan algoritma ini, bertukar-tukar
orang-orang di setiap laluan, kira-kira?
Ini sebenarnya n kuasa dua, bukan?
>> Kerana dalam kes paling teruk, anda boleh jenis daripada berfikir tentang perkara ini intuitif,
walaupun ia mungkin mengambil sedikit sedikit masa untuk tenggelam masuk
Dalam kes terburuk, apa yang akan ini tujuh orang kelihatan seperti, dalam
segi susunan nombor mereka?
Sepenuhnya ke belakang, bukan?
Dan hanya untuk meniru itu, apakah nama anda lagi?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, anda hanya boleh menyertai saya lebih di sini hanya satu kedua?
Sebenarnya, tidak.
Maaf Mike, memutar balik mari.
Apa nama anda lagi?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, anda datang dengan saya, jika anda tidak keberatan.
Jadi, saya akan mencadangkan, hanya untuk kesederhanaan, yang Neil kini beliau
kes terburuk mungkin.
Tetapi ingat bagaimana saya telah melaksanakan algoritma saya.
Saya membandingkan, membandingkan, membandingkan, membandingkan, membandingkan, oh.
Kini mereka berada di luar perintah, jadi saya menetapkan.
Jadi kamu menukar.
Tetapi menganggap sekarang, berapa banyak lebih jauh Neil tidak perlu pergi?
Ia kira-kira n.
Anda tahu, ia tidak benar-benar n.
Ia seperti, n tolak 1, tetapi saya mendapat trek menyimpan marah yang sedikit
nombor, jadi mari kita hanya memanggilnya n.
>> Jadi jika Neil bergerak satu langkah maksima setiap masa, dan untuk bergerak Neil satu langkah,
Saya mempunyai untuk membuat pas benar-benar membosankan ini ke belakang dan sebagainya, ini adalah kira-kira
melakukan ini, n langkah, sebanyak n kali, kerana ia akan membawa saya
bahawa banyak langkah-langkah untuk mendapatkan Neil semua jalan ke mana dia tergolong.
Apatah lagi orang lain jika anda semua semuanya salah diperintahkan juga.
>> Jadi mari kita panggil jenis gelembung n kuasa dua.
Masa berjalan algoritma ini, Prestasi algoritma ini,
keberkesanan algoritma ini, kami hanya akan menerangkan lebih
amnya n kuasa dua.
Yang bagus, kerana saya boleh melakukan contoh yang sama dengan lapan orang, sembilan
orang, satu juta orang, dan bahawa jawapan tidak akan berubah.
>> Jadi, jika anda semua tidak keberatan, mari kita semula anda ke mana anda bermula.
Dan mari kita cuba dua pendekatan yang lain dan lihat jika kita tidak boleh melakukan asasnya
yang lebih baik daripada ini.
Jadi kali ini, saya akan mencadangkan sejenis algoritma yang berbeza.
Itu adalah sangat pandai daripada kita masa lalu, dan anda semua adalah hak untuk mempunyai
naluri kanan hanya jenis daripada bertukar-tukar pasangan demi pasangan.
Tetapi jika saya benar-benar mahu untuk pendekatan ini semata-mata, dan matlamat saya adalah untuk menggerakkan
semua nombor sedikit cara ini, dan menolak semua nombor besar yang
cara, mengapa tidak saya hanya berbuat demikian dalam paling naif cara yang mungkin dan lihat jika saya
boleh melakukan lebih baik daripada apa yang merupakan agak algoritma kompleks?
>> Jadi mari kita lihat.
Empat adalah nombor yang agak kecil, jadi saya akan meninggalkan anda ada masa.
Ooh, nombor dua adalah lebih baik.
Jadi anda hanya boleh melangkah ke hadapan untuk seketika?
Ini sedang bernombor paling kecil saya calon, dan saya akan ingat
dengan, seperti, pembolehubah.
Tetapi saya akan terus menyemak.
Adakah terdapat seseorang yang nombor adalah lebih kecil?
Enam, tidak.
Oh, ada Neil lagi.
>> Jadi, saya akan menolak anda kembali jenis konsep.
Neil akan tampil ke hadapan.
Dan kini, berubah-ubah yang saya gunakan untuk menjejaki yang mempunyai terkecil
nombor dikemaskini untuk mengandungi Neil lokasi itu.
Nah, mari kita lihat.
Tiga, tujuh, lima.
OK, saya tahu Neil adalah yang paling kecil.
Apakah perkara yang paling mudah bagi saya lakukan sekarang?
Saya tidak akan membuang masa saya dengan hanya menggelegak Neil satu tempat ke kiri.
Kenapa saya tidak hanya meletakkan Neil di mana beliau milik, yang sudah tentu di mana?
>> Semua jalan pada permulaan.
Jadi Neil, datang dengan saya.
Dan apakah nama anda lagi?
>> GRACE: Rahmat.
>> DAVID J. MALAN: Rahmat.
OK.
Jadi Grace, malangnya, anda jenis di jalan.
Jadi bagaimana kita menyelesaikan masalah ini?
Betul?
Jika ini adalah array, terdapat hanya tujuh lokasi.
Ingat bahawa, dengan Rob, kita bercakap tentang mengisytiharkan peringkat umur, dan kita hanya mempunyai
beberapa terhingga peringkat umur?
Idea yang sama di sini.
Kita hanya mempunyai beberapa terhingga Ints.
Grace adalah jenis dalam kami cara, jadi bagaimana kita menetapkan?
>> Cara yang paling mudah adalah seperti, Grace, maaf.
Anda akan perlu pergi ke ada supaya kita boleh membuat bilik.
Sekarang, jika anda berfikir tentang perkara ini, mungkin kita hanya membuat masalah lebih teruk.
Dan mungkin kita lakukan, kerana apa yang jika Rahmat berada di tempat yang betul?
Tetapi kita tahu dia tidak, kerana sebaliknya, dia akan menjadi
berdiri di hadapan dan bukannya Neil pada masa ini, bukan?
Kita sudah diperiksa nombor dia keluar.
>> Baiklah.
Jadi sekarang, Neil adalah di tempat yang betul, dan Boleh saya lakukan pengoptimuman sedikit.
Untuk minit seterusnya, saya akan mengabaikan Neil semua bersama-sama, supaya tidak
membuang masa, atau tidak sengaja menukar ke tempat yang salah.
Jadi sekarang, bagaimana saya mencari seterusnya elemen itulah yang paling kecil?
Dua.
Itulah beberapa cukup baik, jika anda mahu melangkah ke hadapan dan
Saya akan mengingati anda.
Enam, tidak baik.
Empat, tiga, tujuh, lima, tidak baik.
Jadi biarlah saya bergerak anda untuk tempat yang tepat anda.
Dan kita hanya mendapat bernasib baik kali ini.
>> Sekarang, saya akan mengabaikan dua lelaki, dan kini melakukan satu lagi
melalui ini.
Enam, bahawa beberapa agak kecil.
Ayuh ke hadapan.
Oh, maaf.
Bilangan Grace adalah lebih baik, jadi langkah di hadapan.
Empat.
Maaf, Grace.
Kembali lagi.
Nombor tiga adalah lebih baik.
Tujuh.
Five.
Dan kini apa nama anda lagi?
>> Jason: Jason.
>> DAVID J. MALAN: Jason.
Jadi Jason kini yang paling kecil elemen saya dipilih.
Di mana dia akan pergi?
Jadi di mana enam adalah.
Dan nama anda sekali lagi?
>> Gabe: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe adalah di jalan.
Apakah perkara yang paling mudah untuk dilakukan?
Menukar kedua-dua lelaki dan berterusan.
Jadi sekarang mari kita lihat.
Siapa yang paling kecil?
Empat.
Biar saya hanya jenis menipu.
Lima akan menjadi yang paling kecil.
Saya dapati akan datang, jika, anda mahu melangkah ke hadapan, apa yang saya perlu lakukan dengan
lelaki ini, dengan Gabe?
Bertukar lagi.
Jadi sekarang, masih sedikit daripada perintah.
Saya dapati Gabe menjadi kecil, jadi Saya pop dia keluar, bergerak anda semua lebih.
Dan dilakukan.
>> Jadi jawapannya adalah sama.
Keputusan akhir adalah sama.
Antara kedua-dua algoritma yang lebih baik?
Yang kedua, saya mendengar.
Mengapa?
>> SPEAKER 3: Ia n langkah [didengar].
>> DAVID J. MALAN: Ia langkah n paling banyak.
Menarik.
Jadi adakah ia walaupun?
Jadi bagaimana saya mencari elemen terkecil?
Berapa banyak langkah-langkah yang tidak saya perlu mengambil mendapati elemen terkecil?
Saya telah kelihatan sepanjang jalan pada akhirnya, bukan?
Kerana dalam kes paling teruk, apa jika Neil adalah di sini?
Jadi hanya mencari elemen terkecil mengambil langkah-langkah yang saya n, atau n tolak 1.
Tetapi, OK.
Jadi menetapkan Neil.
Ingat bahawa, satu minit atau lebih yang lalu.
>> Tetapi bagaimana saya mendapati seterusnya elemen terkecil?
Ia n tolak 1, atau n tolak 2 benar-benar, daripada bilangan langkah-langkah.
Jadi OK.
Jadi saya n tolak 2.
Baiklah.
Jadi yang merasakan sedikit lebih baik.
Baiklah.
Berapa banyak langkah-langkah masa depan mencari nombor tiga?
Jadi n tolak 4.
Jadi ia berkurangan, satu kurang melangkah pada setiap lelaran.
Jadi ini tidak berasa lebih baik, bukan?
Jika masa lalu, ia adalah kira-kira n kali n, masa ini, ia n tolak 1, ditambah n tolak
2, ditambah n tolak 3, campur n tolak 4, dot, dot, dot.
Tetapi jika anda ingat dari sekolah tinggi anda buku teks, menipu sedikit
kunci di belakang yang mempunyai formula, jika anda menambah siri nombor,
apakah jumlah langkah-langkah yang akan menjadi yang saya ambil di sini?
>> Ini adalah salah satu dari orang-orang, seperti, n tolak 1, kali n, dibahagikan dengan 2.
Jadi biarlah saya melihat jika saya boleh tarik sehingga ini hanya seketika.
Dan sekali lagi, saya jenis pembundaran beberapa nombor hanya untuk menjaga hidup kita mudah,
tetapi seperti yang saya ingat, ia adalah sesuatu seperti jika Saya n tolak 1 perkara, maka n tolak
2, maka n tolak 3, ia adalah kira-kira sesuatu seperti ini lebih 2, dan jika saya
membiak di luar ini, itulah sebenarnya n persegi.
Itu tidak berasa terlalu baik. n tolak n lebih 2.
>> Tetapi di sini perkara itu.
Dalam sains komputer, apabila masalah mula mendapat menarik ialah apabila n
mendapat benar-benar besar.
Dan apabila n menjadi benar-benar besar, yang mana satu nilai-nilai ini akan menguasai semua
yang lain?
Ia adalah jenis n kuasa dua, bukan?
Ya, membahagikan oleh 2 adalah cukup baik.
Tetapi jika anda bercakap tentang berbilion-bilion keping data, atau berjuta-juta
keping data, OK, jadi anda dua kali lebih cepat.
Tetapi yang benar-benar peduli jika jumlah yang besar, jika faktor ini adalah apa yang mendapat
yang lebih besar dan lebih besar.
Dan sesungguhnya, ia membuatkan lebih perbezaan daripada lelaki ini.
Jadi, walaupun anda semua adalah betul, algoritma kedua, kami akan memanggilnya
jenis pemilihan, adalah, dalam dunia sebenar, sedikit lebih cepat berpotensi, kerana saya
mengambil kurang dan kurang langkah setiap kali.
>> Ia tidak benar-benar asas cepat.
Kerana jika kita benar-benar bermain ini keluar untuk nilai n yang besar, pada akhir
hari, untuk n cukup besar, ia masih akan berasa cukup perlahan.
Baiklah, biar saya mengambil satu pas lepas pada itu.
Itulah yang saya akan memanggil jenis pilihan.
Bolehkah anda semua semula diri satu masa lalu?
Dan dalam kes ini lepas, saya akan untuk mencadangkan sesuatu
dipanggil jenis kemasukan.
Jenis kemasukan menjadi konsep, sedikit berbeza.
>> Daripada pergi ke belakang dan sebagainya dan memilih elemen terkecil, saya
hanya akan berurusan dengan masing-masing lelaki kerana saya bertemu dengan mereka, dan memasukkan
mereka ke tempat yang betul.
Jadi, saya hanya akan bermula dengan Grace, dan saya melihat bahawa dia adalah nombor empat.
Di manakah nombor empat tergolong?
Saya belum mula menyusun apa-apa, jadi Grace mendapat untuk tinggal di sana.
Dan sekarang saya akan mendakwa, jika anda boleh mengambil langkah ke kanan anda, ini
senarai disusun saya, ini adalah saya senarai baki Unsorted.
Jadi sekarang saya akan meneruskan akan datang, dan apa nama lagi?
>> Branson: Branson.
>> DAVID J. MALAN: Branson.
Jadi Branson adalah nombor dua.
Jadi, saya akan membawa anda keluar untuk seketika.
Dan sekarang, di manakah anda tergolong dalam pelbagai ini?
Jadi untuk hak Rahmat.
Jadi sekali lagi, kita jenis membuat Grace melakukan banyak kerja di sini.
Di manakah kita meletakkan anda?
Jadi, kita akan ke slaid anda ke kiri, dan memasukkan Branson sana.
Tetapi sekarang saya mendakwa bahawa anda semua telah selesai.
Tetapi notis, saya tidak menggunakan ruang tambahan.
Ia masih 2 unsur-unsur di sini, 5 di sini.
Jumlah saiz array adalah 7, jadi saya tidak menipu, semua betul?
>> Jadi sekarang kita mempunyai, dengan Gabe di sini, nombor enam, di mana anda tergolong?
Anda bernasib baik lagi.
Jadi anda mendapat untuk tinggal di sana.
Hanya mengambil satu langkah yang sedikit ke kanan hanya untuk membuat jelas bahawa anda disusun.
Dan sekarang kita mempunyai Neil lagi, bilangan satu, di mana anda pergi?
Dan kini adalah di mana kita akan mula melihat bahawa algoritma ini, walaupun pada pertama
pandangan, berasa cukup bijak, menonton apa yang akan berlaku.
Jika anda boleh melangkah ke hadapan.
>> Di mana kita mahu meletakkan Neil?
Jadi jelas di sini, jadi bagaimana kita mendapatkan Neil sana?
Mari kita melakukan ini langkah demi langkah.
Gabe, di mana anda perlu pergi?
Ya, supaya mengambil satu langkah yang besar, atau dua setengah langkah-langkah untuk membuat
satu langkah di sana.
Grace, di mana anda pergi?
Baik.
Jadi langkah yang lain.
Dan akhirnya, Branson?
Satu lagi langkah.
Dan sekarang kita boleh meletakkan Neil ke tempatnya.
>> Jadi sekarang, terus logik ini.
Walaupun kita tidak beralih Neil atas, dan ke atas, dan ke atas, untuk meletakkan dia
mana dia pergi, dalam kes paling teruk, nombor yang berikutnya kita mungkin menghadapi boleh
menjadi nombor, berkata, terdapat sebilangan sifar, maka kita akan beralih semua
lelaki ini.
Katakan bahawa ada beberapa, negatif satu, maka kita perlu beralih
semua lelaki.
Oleh itu, kita benar-benar hanya jenis Melibas masalah di sekeliling, seperti yang kita
memindahkan perbelanjaan daripada proses pemilihan supaya kemasukan
proses, seperti yang anda lelaki hanya mempunyai untuk bergerak kira-kira n tolak sesuatu
beberapa langkah.
Dan bilangan yang langkah-langkah yang hanya akan meningkat kerana saya memilih lebih nombor,
jika saya perlu menyimpan shoving kamu belakang, dan kembali, dan kembali.
>> Jadi perkara yang menyedihkan sekarang ialah semua ini algoritma n kuasa dua.
Mari kita pergi ke hadapan dan terima kasih kepada lelaki, dan menggambarkan ini sedikit
berbeza.
Sangat baik dilakukan.
>> [Tepuk tangan]
>> Baiklah.
Terdapat anda pergi.
Terima kasih kerana -
>> Branson: [didengar] menyimpan nombor.
>> DAVID J. MALAN: Tidak, anda boleh menyimpan nombor juga.
Baiklah.
Baik dilakukan.
Baiklah.
Jadi mari kita lihat jika kita tidak boleh kini merumuskan lebih cepat, dan lebih visual,
apa yang hanya berlaku di sini seperti berikut.
Saya akan pergi ke hadapan dan tarik sehingga Firefox.
Kami akan menghubungkan demonstrasi ini di laman web kursus ini.
Java adalah sedikit menjengkelkan untuk mendapatkan kerja dalam sesetengah pelayar hari ini.
Jadi, jika anda bermain dengan ini di rumah, menyedari bahawa anda mungkin perlu menggunakan Firefox
untuk mendapatkan ia bekerja.
Dan apa yang saya akan lakukan dengan ini demonstrasi adalah seperti berikut.
>> Di bahagian bawah, saya mempunyai sejumlah besar pilihan menu, termasuk permulaan dan
butang berhenti.
Juga, sebagai diketepikan, terdapat seolah-olah menjadi bug dalam program-program ini, di mana anda
tidak boleh benar-benar melihat permulaan atau berhenti butang melainkan jika anda memegang Perintah atau Alt
campur dan zoom in, yang ingin tahu menunjukkan kepada anda lebih banyak butang.
Jadi hanya FYI jika anda bermain dengan ini di rumah.
Sekarang saya akan klik Mula dalam hanya masa, selepas menyatakan kelewatan,
seperti, 200 milisaat di sini, hanya supaya kita dapat melihat apa yang berlaku.
>> Jadi saya mendakwa bahawa ini adalah visualisasi a algoritma yang pertama
lelaki ini lakukan, jenis buih, di mana kita orang bertukar pasangan-bijak.
Wawasan utama untuk visualisasi ini ialah ketinggian bar
mewakili saiz nombor.
Oleh itu, lebih tinggi bar, lebih besar nombor.
Pendek bar, bilangan yang lebih kecil.
Dan jika anda notis, kita akan melalui lelaran pertama algoritma ini,
bertukar-tukar nombor besar dan kecil, supaya sebilangan kecil datang pertama dan
bilangan besar pergi ke kanan.
>> Dan sebaik sahaja kita mendapat akhir pelbagai banyak lebih nombor daripada tujuh, kami
akan kembali ke permulaan.
Dan menjangka ini.
Pada yang jauh kiri, lelaki yang sedikit akan untuk menukar ke tepi, dan ini
proses mengulangi.
Sekarang visualisasi ini dengan cepat mendapat membosankan, jadi biarlah saya pergi ke hadapan dan berhenti
ia, tukar kelewatan sesuatu yang lebih cepat hanya untuk mendapatkan sekarang, rasa untuk
algoritma ini.
>> Jadi, walaupun saya telah dipercepatkan ia, ini adalah seperti menaik taraf pemproses saya, membeli
sebuah komputer baru.
Saya tidak asasnya berubah saya algoritma, tetapi anda benar-benar boleh melihat lebih banyak
jelas daripada dengan manusia, yang besar nombor-nombor itu menggelegak sehingga ke atas,
dan nombor-nombor kecil yang menggelegak turun ke bawah.
Dan sekarang perkara ini di sini disusun.
Dan sebagai diketepikan, di dataran, ada hanya beberapa simpan kira di sana untuk
membantu anda mengira berapa banyak perbandingan, atau berapa banyak swap mempunyai
sebenarnya telah dilakukan.
>> Nah, mari kita cuba salah satu yang lain yang kita lihat.
Biar saya klik pada jenis buih di sini, dan biarlah saya memilih, dan laman web ini secara keseluruhan
adalah sebuah kereta kecil.
Mari kita menerima risiko dan berjalan lagi.
Ada kita pergi.
Jadi mari kita buat jenis pilihan.
Saya tidak tahu mengapa menu muncul di sana.
Mari kita zoom dalam untuk menetapkan bahawa bug, menukar ini kepada 50.
Ah, mari kita benar-benar melakukan yang lebih cepat.
Lima milisaat atau lebih, dan Mula.
>> Jadi ini adalah jenis pilihan.
Jadi sekali lagi, berfikir tentang apa yang kita lakukan dengan manusia di sini.
Kami telah melalui pelbagai dan dipilih unsur yang paling kecil lagi,
dan sekali lagi, dan lagi.
Sekarang saya mendakwa bahawa masih cukup buruk.
Ia masih n kuasa dua, memberi atau mengambil, tetapi ia adalah, dalam dunia sebenar, sedikit
lebih cepat, kerana saya memang mengambil sedikit kurang langkah-langkah setiap kali.
Tetapi kita hanya bercakap apa?
Mungkin 40 atau jadi bar di sini?
Kami tidak bercakap 40 juta.
Jadi ia tidak benar-benar jelas bagi saya bahawa sememangnya keuntungan yang ketara.
>> Izinkan saya kembali dan menukar kepada kami algoritma ketiga, yang telah memilih
jenis kemasukan.
Dan kini ia benar-benar kereta kerana menu benar-benar tidak perlu di bawah sana.
Jadi sekarang kita akan skrol kembali di sini dan mula algoritma ini.
Sorak, mula dan berhenti.
Jadi jenis ini salah satu mempunyai corak cantik kepadanya, di mana kita sekali lagi
memasukkan manusia, atau dalam kes ini, ke dalam bar
lokasi yang sesuai mereka.
Dan ia sudah dilakukan sebelum Saya menoleh.
Tetapi yang satu ini juga, dalam teori, masih n kuasa dua.
>> Jadi mari kita lihat jika kita tidak boleh merumuskan ini seperti berikut.
Saya akan pergi ke hadapan dan hanya untuk memberi kita jenis cara biasa bercakap
mengenai perkara-perkara ini, izinkan saya memperkenalkan hanya sedikit catatan di sini.
Anda akan melihat sesuatu yang dipanggil besar O, kerana ia adalah benar-benar besar-besaran
O. Dan ini adalah cara yang komputer ahli sains atau ahli matematik juga menggunakan
untuk menggambarkan masa larian beberapa algoritma.
Berapa banyak langkah-langkah yang ia benar-benar mengambil?
>> Sekarang saya akan memalukan diri saya dengan tulisan saya di sini hanya seketika.
Tetapi biarlah saya pergi ke hadapan dan mengatakan bahawa ini akan menjadi O besar di sini.
Dan izinkan saya memperkenalkan satu lagi simbol, omega modal.
Omega akan menjadi sebaliknya, pada asasnya, daripada besar O. Manakala besar O
bermakna, dalam kes paling teruk, berapa banyak masa beberapa algoritma mungkin mengambil masa, dalam
segi n, Omega akan menjadi berapa banyak masa ia mungkin
mengambil mana-mana yang terbaik.
Dan kita akan melihat apa yang kita maksudkan dengan hal terbaik dalam seketika.
>> Jadi mari kita mulakan sesuatu yang mudah.
Biar saya mulakan dengan carian linear.
Jadi tidak sorting.
Kami akan memanggil carian ini linear.
Dan kini, membuat sedikit jadual keluar dari ini.
Dan kini, dalam kes carian linear, dalam kes paling teruk, berapa banyak langkah-langkah yang
ia akan membawa saya untuk mencari beberapa pilihan sewenang-wenangnya?
Dan ada jumlah pintu n atau n jumlah nombor.
Kes terburuk.
Berapa banyak langkah-langkah yang saya akan perlu ambil untuk mencari nombor 50 dalam array
n pintu?
Dan mengapa?
Kerana ia mungkin semua cara lebih ke akhir.
Begitu banyak seperti Jennifer dihadapi, Bilangan 50 adalah semua cara di atas, maka dalam
kes terburuk carian linear adalah besar O n, kami akan katakan.
>> Apa kira-kira mana-mana yang terbaik, jika anda mendapat benar-benar bertuah?
Ia hanya akan mengambil satu langkah, atau nombor berterusan langkah-langkah.
Jadi kita akan menggambarkan bahawa sebagai 1.
Jadi ini adalah cukup baik.
Sekarang apa jika kita melakukan sesuatu yang suka carian binari?
Carian supaya perduaan, yang paling teruk kes, mengambil berapa banyak masa?
>> [INTERPOSING suara]
>> DAVID J. MALAN: Jadi sebenarnya, saya mendengar dalam satu tempat pasangan.
Jadi ia sebenarnya log n, memberi atau mengambil, kerana seperti yang kita membahagikan senarai pada separuh
sekali lagi, dan sekali lagi, dan sekali lagi, kami dapat untuk mencari, akhirnya, nilai,
jika ia di sana, tetapi ada tangkapan.
Apakah andaian bahawa kita perlu mengambil mudah untuk carian binari?
Ia perlu disusun.
Ia tidak disusun, anda boleh berpecah perkara pada separuh lagi dan lagi, dan anda
boleh pergi kiri, dan anda boleh pergi ke kanan, dan anda boleh pergi ke kiri dan kanan, tetapi anda
tidak akan mendapati elemen jika senarai itu tidak diselesaikan, kerana
anda mungkin ketinggalan.
Kerana heuristik anda, untuk pergi kiri atau kanan akan menjadi cacat jika ia
sememangnya tidak disusun.
Jadi ada jenis kos tersembunyi untuk menggunakan sesuatu seperti ini.
>> Sekarang, mari kita pergi ke sorting kami algoritma tidak mencari -
oh, sebenarnya mari kita pergi kosong ini.
Carian binari dalam kes ini?
Ia juga 1 jika ia hanya berlaku untuk menjadi di tengah-tengah sangat pelbagai, atau
tengah-tengah buku telefon.
Sekarang mari kita buat apapun gelembung.
Jadi sekali lagi, sekarang kita sedang memasuki pelbagai, bukan carian.
>> Dalam kes terburuk, berapa banyak langkah-langkah yang kita tuntutan gelembung jenis akan mengambil?
n kuasa dua.
Jadi saya akan menarik itu.
Aduh, tulisan saya kelihatan lebih teruk apabila ia dijangka bahawa besar.
Baiklah.
Jadi itu n kuasa dua.
Dan dalam kes yang terbaik daripada jenis buih, berapa banyak langkah-langkah yang ia akan mengambil?
1, saya dengar.
>> SPEAKER 1: n.
>> DAVID J. MALAN: n, saya mendengar.
>> SPEAKER 1: 2.
>> DAVID J. MALAN: 2, saya dengar.
Adakah saya mendengar 3?
Baiklah.
Jadi, saya telah mendengar 1, n, 2, tetapi mari kita mengambil selain sekurang-kurangnya orang yang awal pertama
cadangan, 1.
Ia bukan naluri yang tidak baik, kerana ia jenis corak di sini.
Tetapi jika ia hanya mengambil 1 langkah, bagaimana dalam dunia saya boleh mendakwa bahawa senarai
disusun, kerana jika saya hanya dibenarkan mengambil 1 langkah, bagaimana banyak unsur
Saya sebenarnya boleh memeriksa untuk memastikan?
Nah, hanya 1, yang bermaksud ada n tolak 1 unsur-unsur yang boleh keluar dari
perintah, dan saya hanya berlaku selepas iman melihat 1 elemen bahawa
benda disusun.
Jadi 1 tidak betul di sini.
Jadi minimum, berapa banyak saya perlu melihat?
>> [INTERPOSING suara]
>> DAVID J. MALAN: n tolak 1, atau benar-benar, n, kerana saya perlu melihat setiap
elemen memastikan bahawa ia tidak keluar perintah.
Tetapi sekali lagi, kita akan menyelesaikan gelombang kami tangan di nombor yang lebih kecil dan
menganggap bahawa, sebagai n mendapat besar, mereka tidak menarik juga.
Jadi itulah jenis gelembung.
Dan kini, mari kita buat kedua-dua lepas.
Pemilihan jenis, dan kemudian kami akan melakukan jenis kemasukan.
Dan kemudian kita akan meniup anda minda dengan sesuatu yang lebih
lebih baik daripada semua ini.
Baiklah.
>> Apakah kes terburuk berjalan masa jenis pilihan?
>> SPEAKER 4: n kuasa dua.
>> DAVID J. MALAN: n persegi, saya mendengar.
Tetapi mengapa n kuasa dua, intuitif?
>> SPEAKER 4: Kerana kita hanya melakukannya.
>> DAVID J. MALAN: Kerana kita hanya melakukannya.
OK.
Baik jawapan.
Tetapi intuitif, mengapa pemilihan jenis n kuasa dua?
Apa yang perlu kita lakukan lagi dan lagi?
Kami terpaksa menyimpan imbasan melalui, adalah anda yang paling kecil, yang anda
kecil, adakah anda yang paling kecil.
Dan diberikan, kita dapat mengambil n langkah-langkah, maka n tolak 1, maka n tolak 2.
Tetapi jika anda jenis menambah mereka semuanya, atau mengambil ia pada kepercayaan bahawa saya telah menambah
mereka terlebih dahulu, kita akan mendapat kira-kira n kuasa dua tolak beberapa nombor yang lebih kecil.
Jadi, saya akan memanggil n ini kuasa dua.
Tetapi dengan jenis pemilihan dalam yang terbaik kes, berapa banyak langkah-langkah yang ia
akan mengambil saya?
>> SPEAKER 5: [didengar]
>> DAVID J. MALAN: Ia malangnya masih n kuasa dua, bukan?
Kerana jika saya memilih yang paling kecil unsur, dan kami mempunyai tujuh orang di sini,
Saya hanya tahu, apabila saya sampai ke sangat akhir tahun, yang saya dapati yang paling kecil
nombor, di mana sahaja dia atau dia mungkin telah.
Tetapi bagaimana saya mendapati seterusnya bilangan paling kecil?
Saya perlu melakukan pas lain.
Jadi, dalam kes ini, apakah input untuk menyusun pemilihan?
Ia merupakan satu senarai jenis pun, nombor satu, nombor dua, nombor tiga, nombor empat.
Tetapi saya komputer.
Saya hanya boleh melihat pada satu-satu perkara pada satu masa.
Saya tidak boleh menyusun daripada mengambil langkah kembali seperti manusia dan berkata,
aduh, ini kelihatan betul.
>> Saya hanya boleh mengadili kebenaran dalam jenis pilihan dengan memilih
bilangan terkecil.
Tetapi, jika saya mencari nombor yang pertama, jika saya tidak tahu apa-apa lagi mengenai
nombor-nombor lain, yang saya tidak lakukan, semua saya tahu bahawa saya telah menyerahkan array
atau satu set pintu belakang yang nombor, satu-satunya cara yang saya tahu bahawa salah satu
adalah yang paling kecil?
Jika saya mendapat sepanjang jalan di sini dan sedar, damn, salah sememangnya yang paling kecil.
>> Tetapi bagaimana saya kemudian menentukan bahawa kedua-dua adalah yang paling kecil akan datang?
Dengan melakukan ketidakcekapan yang sama lagi dan lagi.
Jadi akhirnya, dengan jenis kemasukan, bagaimana, dalam kes terburuk,
adakah kita mengatakan ia melakukan?
Ia juga adalah n kuasa dua.
Dan bagaimana pula dengan kes yang terbaik?
Kami akan meninggalkan bahawa cliffhanger a.
Kami akan mengisi yang kosong masa akan datang, tetapi pada mulanya, biarlah saya mencadangkan supaya kita
asasnya melakukan lebih baik daripada semua ini, betul?
>> Jadi berfikir untuk diri sendiri apa kemasukan jenis yang akan menjadi.
Nah, yang tidak begitu dramatik, kerana saya satu-satunya
yang menyaksikan perubahan itu.
Wow.
OK.
Jadi di sini kita mempunyai yang agak demonstrasi yang berbeza.
Jika saya mengezum masuk di sini, anda akan melihat bahawa pada kiri kita mempunyai jenis gelembung, dalam
tengah kita mempunyai jenis pilihan, dan pada jauh betul, kita mempunyai sesuatu yang kita
tidak melihat lagi dipanggil bergabung jenis.
Tetapi menganggap apa yang kita telah lakukan di sini setakat hari ini.
Apabila Jennifer pertama datang di atas pentas, kita pergi melalui pelbagai nombor
sekali lagi, dan sekali lagi, dengan carian linear, dan kita ada masa linear berjalan, besar O
n, jadi untuk bercakap.
>> Apabila kita kini menganggap minggu pertama kelas, apabila kita telah membahagi dan menakluk,
dan kami telah buku telefon berair, dan Jennifer, dan kita secara kolektif
dimanfaatkan bahawa wawasan utama, iaitu untuk mengulangi diri lagi dan lagi oleh
entah bagaimana membuang, membuang, membuang, separuh daripada masalah, atau
secara amnya, membahagikan masalah pada separuh, dan kemudian merawat sekeping kecil
masalah seperti konsep bersamaan kepada yang lain, kita entah bagaimana tidak
asasnya yang lebih baik.
Tetapi dengan jenis buih, dengan pilihan jenis, dengan jenis kemasukan, kita telah boleh
ada pandangan itu bahawa Jennifer lakukan.
Kami cukup banyak hanya berjalan ke belakang dan sebagainya sejumlah besar masa, dan kita
perkara mengagak sedikit, bertukar-tukar dalam usaha ini, mungkin
memasukkan atau memilih.
Tetapi pada akhir hari, saya banyak daripada berjalan janggal belakang dan sebagainya.
Kami tidak benar-benar memanfaatkan sesuatu pintar seperti Jennifer tidak seperti membahagikan
dan menakluk.
>> Jadi bergabung jenis, sebaliknya, yang kita tidak akan melihat sehingga minggu depan, ia akan
untuk memanfaatkan bahawa idea utama dengan membahagikan input, dan kemudian mengurangkan separuh, dan kemudian
mengurangkan separuh, dan kemudian mengurangkan separuh.
Dan pada setiap lelaran gelung itu, menyusun separuh kiri, dan kanan
separuh, kemudian sebelah kiri separuh separuh kiri, dan separuh kanan kiri, kemudian
separuh kiri separuh yang betul, dan separuh benar separuh betul.
Dan mengulangi lagi dan lagi.
>> Jadi, anda akan melihat ini visual, tetapi ini adalah apa yang menanti kita minggu depan.
Dan secara umum, apabila kita berfikir sedikit agak sukar pada mana-mana masalah tersebut.
Kami telah n kuasa dua di sebelah kiri, n kuasa di tengah-tengah, dan n
log n di sebelah kanan.
Jadi ada cliffhanger sebenar anda.
Kami akan melihat anda pada hari Isnin.
>> [Tepuk tangan]