>> SPEAKER: Baiklah, ini adalah CS50.
Ini adalah akhir minggu tiga, dan jika anda tidak mengambil kesempatan sudah,
tahu bahawa akan ada makan tengah hari Jumaat ini seperti biasa, di mana
anda boleh menikmati perbualan yang baik dan makanan di Bomba dan Ais
dengan beberapa CS50 ini kakitangan dan rakan-rakan sekelas.
Menuju ke URL ini di sini.
>> Sekarang mana yang diketahui, atau anda tidak lama lagi boleh mengetahui,
perkara-perkara ini di sini, yang yang diberikan pada akhir
satu semester bagi banyak kelas.
Yang dipanggil peperiksaan buku biru, di mana anda tulis jawapan anda untuk peperiksaan.
Sekarang saya ada di sini 26 seperti buku biru, pada setiap daripada mereka
ditulis nama, A melalui Z. Dan memang nama-nama yang mudah itu, A
melalui Z. Dan salah satu matlamat di tangan hari ini
akan menjadi untuk meneruskan apa yang kami bermula pada hari Isnin, yang tidak
banyak melihat kod, tetapi benar-benar mencari idea dan penyelesaian masalah.
Salah satu matlamat dan janji kursus ini
adalah untuk mengajar anda untuk berfikir lebih berhati-hati, lebih teratur,
dan untuk menyelesaikan masalah dengan lebih cekap.
Dan sesungguhnya, kita boleh melakukan yang benar-benar tanpa menyentuh garis kod.
Jadi, saya mempunyai beberapa ekor gajah di sini hari ini, oren dan biru,
jika kita boleh mendapatkan satu sukarela, mungkin dari jauh ke belakang daripada biasa.
Bagaimana pula di sana, datang ke atas ke bawah.
Matlamat yang akan menjadi untuk membantu serta mentadbir peperiksaan ini di sini.
Apa nama anda?
>> PENONTON: Mary Beth.
SPEAKER: Mary Beth, datang ke atas.
Biar saya mendapatkan mikrofon di sini untuk anda.
Nice untuk bertemu dengan kamu.
>> PENONTON: Nice untuk bertemu dengan kamu.
SPEAKER: Baiklah, jadi saya perlu di sini buku biru A melalui Z,
dan saya akan berpura-pura bahawa Saya salah seorang pelajar,
dan mereka datang agak rawak pada akhir peperiksaan blok tiga jam,
supaya mereka memasuki beberapa perintah separa rawak seperti ini.
Sekarang tugas anda hanya dalam masa yang akan untuk adalah-- ini sebenarnya cara mereka mendapatkan
mencatatkan pada akhir kelas, kemungkinan besar.
Pekerjaan anda sekarang akan menjadi, agak hanya, untuk menyusun buku-buku biru untuk kita
dari A hingga Z.
>> PENONTON: Oh, ini adalah akan mengambil selama-lamanya.
>> SPEAKER: Dan kami akan menonton seperti yang anda lakukan ini, tidak ada tekanan.
PENONTON: Tidak, tidak tekanan atau apa-apa.
>> SPEAKER: Dan untuk bersenang-senang, mari kita meletakkan pemasa.
>> PENONTON: seronok, menyeronokkan begitu banyak.
>> SPEAKER: Saya boleh memegang mikrofon untuk anda.
Baiklah, kita baru sahaja dua kali ganda kelajuan kita.
Jadi, dalam pada itu, biarlah saya memberikan apa yang akan menjadi soalan untuk Mary Beth
adalah apa yang dia lakukan, bagaimana dia akan mengenai menyelesaikan ini?
Dan sebenarnya, anda mungkin tidak mempunyai terfikir tentang sesuatu
begitu mudah apabila anda memilih sehingga 26 buku-buku seperti ini,
yang tidak mempunyai semula jadi memerintahkan kepada mereka.
Apakah proses yang bahawa anda benar-benar digunakan?
Adakah ia hanya agak rawak memilih salah satu yang pertama yang anda lihat
dan meletakkannya di tempatnya?
Adakah anda pertama bergerak tangan anda di sekitar mencari A kemudian mencari B?
Adakah anda lihat pada sepasang mereka sebelah menyebelah
dan hanya berkata, tunggu satu minit, ini tidak betul, dan kemudian menukar perintah itu?
Kami melihat sudah pada hari Isnin bahawa ada beberapa cara
di mana kita boleh melakukan ini, dan memang seperti yang kita berhampiran akhir di sini,
Saya akan mengambil nota mungkin daripada apa yang Mary Beth lakukan.
Kami mempunyai beberapa buasir ia seolah-olah, yang lebih besar, tiga yang lebih kecil.
>> PENONTON: Saya mengarahkan mereka apabila saya dapati dua surat
yang saya tahu bersama-sama dalam satu urutan, Saya meletakkan mereka bersama-sama supaya saya tidak
perlu bimbang tentang menjaga lagu satu barisan keseluruhan buku.
Ia hanya, oh, adalah pertama, Saya telah mendapat timbunan ini di sini.
SPEAKER: Jadi, hampir seperti satu keping teka-teki yang
mempunyai bentuk yang betul kepada sepadan dengan satu sama lain.
PENONTON: Pretty banyak, yeah.
SPEAKER: OK, yang sangat baik.
Dan sekarang ini setiap buasir adalah mungkin disusun?
>> PENONTON: Yeah.
>> SPEAKER: Baiklah, A melalui Z. Semua betul, tahniah, anda melakukannya.
Anda mempunyai pilihan anda.
Blue?
Baiklah, terima kasih untuk itu.
Jadi Mary Beth tidak mencadangkan apa pendekatan beliau adalah,
tetapi apa yang satu lagi pendekatan bagaimana anda mungkin pergi tentang menyusun perkara-perkara ini?
Apa yang akan anda lakukan?
Rekod untuk mengalahkan akan menjadi satu atau lebih 50 saat dan minit,
ditambah yang saya terlupa untuk mengira.
Apa yang akan anda lakukan?
Yeah?
PENONTON: Ambil tindanan.
Mulakan dari awal.
Memeriksa kertas anda.
Dan jika salah satu bahagian atas adalah lebih tinggi daripada, mungkin, mereka,
satu bahagian bawah adalah lebih tinggi, kemudian menukar mereka.
>> SPEAKER: OK, jadi bermula di bahagian atas dan bahagian bawah,
dan kemudian bekerja cara anda masuk seperti itu, pertukaran mereka?
OK, jadi yang sama sedikit dalam semangat untuk jenis gelembung,
tetapi memilih yang keterlaluan tidak pasangan bersebelahan.
Tetapi kekurangan itu adalah bahawa ada pasti banyak cara yang berbeza
kita boleh melakukan ini, dan terus-terang, saya rasa anda jenis
mengguna pakai pendekatan pasangan, bukan?
Anda membuat semacam empat buasir disusun, dan kemudian digabungkan dengan berkesan mereka bersama-sama.
Dan itu, berani mengatakan, satu lagi teknik sama sekali.
Anda tidak menganggap ia sebagai satu longgokan besar, anda dibahagikan masalah itu kepada empat quads,
jika anda akan, dan kemudian entah bagaimana digabungkan mereka pada akhirnya.
>> Jadi mari kita mempertimbangkan, akhirnya, bagaimana lagi kita mungkin melakukan ini.
Kami secara rasmi tanggapan gelembung semacam masa lalu,
dan penarikan balik semacam gelembung adalah algoritma yang kita dilihat
dengan lapan daripada rakan sekelas anda di sini, seolah-olah secara rawak disusun pada mulanya.
Dan kita mengambil keputusan dari segi pasangan, jika dua elemen berada di luar perintah,
hanya menukar mereka.
Jadi empat dan dua jelas daripada perintah,
supaya kedua-dua rakan-rakan sekelas beralih kedudukan.
Dan kemudian kita berulang-ulang dengan empat dan enam, maka enam dan lapan, pada setiap lelaran,
bergerak ke kanan.
>> Jadi diberi lapan orang, berapa banyak dari segi pasangan perbandingan yang saya lakukan ketika berjalan dari
kiri ke kanan dalam satu lelaran seperti itu?
Berapa perbandingan?
Tujuh, bukan?
Kerana jika ada lapan orang tetapi anda perlu pasangan
mereka dan anda terus bergerak satu hop ke kanan,
anda tidak akan mempunyai lapan perbandingan kerana anda tidak boleh membandingkan
elemen dengan dirinya sendiri, atau ia akan hanya menjadi sia-sia, supaya anda mempunyai tujuh.
Atau lebih umum, jika kita n orang, kami
melakukan n tolak 1 perbandingan dengan jenis gelembung.
>> Jadi mari kita mempertimbangkan sekarang bagaimana baik atau gelembung buruk semacam sebenarnya adalah, dan cuba
untuk memberikan diri kita dengan perbendaharaan kata untuk algoritma kritikan seperti ini,
dan tidak lama lagi kita sendiri.
Jadi pas pertama menerusi semacam gelembung, kali pertama
Saya berjalan dari kiri ke kanan di seluruh peringkat, membawa saya n tolak 1 perbandingan.
Dan itu akan menjadi saya unit ukuran, bukan?
Saya jenis bercakap dan berjalan, agak cepat, agak perlahan,
jadi saya mengira bilangan saat tidak terutamanya memberitahu,
tetapi mengira bilangan operasi yang saya lakukan pada hari Isnin,
membandingkan dua orang, yang terasa seperti unit bagus langkah.
>> Jadi n tolak 1 langkah kali pertama, tetapi apa yang berlaku selepas itu?
Apa yang terbalik salah satu pas melalui senarai terisih sebaliknya?
Apa yang anda boleh memberitahu saya tentang elemen yang adalah semua jalan di sana?
Yeah?
Itu adalah unsur terbesar, bukan?
Nombor lapan, walaupun dia bermula di sini, setiap kali saya
berbanding menentang jiran, dia terus
menggelegak sehingga hak sebelah senarai.
Dan sesungguhnya, itu di mana algoritma mendapat namanya.
>> Sekarang berdasarkan logik tersebut, berapa banyak perbandingan perlu saya membuat pada kali kedua
Saya membuat pas yang dari kiri ke kanan?
n tolak 2, bukan?
Ia hanya akan membuang masa saya jika saya menyimpan membandingkan lapan terhadap seseorang
lagi kerana kita sudah tahu dia berada di tempat yang betul.
Jadi itulah sedikit satu pengoptimuman, jadi pas seterusnya
akan menjadi tambah n tolak dua langkah, di mana n ialah bilangan orang.
Sekarang anda jenis boleh membuat anggaran, walaupun jika anda bukan seorang ahli sains komputer,
bagaimana ini berakhir.
Pada akhir algoritma ini, mungkin anda mempunyai hanya satu perbandingan kiri.
Anda perlu jenis menetapkan bermula daripada senarai dalam kes dua
dan satu berada di luar perintah dan harus menjadi satu dan dua,
jadi ini selamat minum sekurang- ditambah 1 perbandingan akhir.
>> Sekarang titik, dot, dot jenis gelombang itu tangan di beberapa butiran banyak jus,
tetapi mari kita pergi ke depan dan memudahkan.
Jika anda ingat dari tinggi sekolah, terus-terang, banyak anda
mempunyai buku matematik yang mempunyai kunci cheat sedikit
pada kulit depan atau semula penutup yang menunjukkan anda
apa siri penjumlahan seperti ini akhirnya menambah sehingga.
Dalam kes umum, jika anda mempunyai pembolehubah seperti n, dan sememangnya satu ini,
jika anda melihat anda buku matematik sekolah lama,
anda akan melihat bahawa ini sebenarnya menambah sehingga jumlah ini di sini,
n masa n tolak 1 semua dibahagikan dengan 2.
Jadi buat masa ini biarlah saya menyatakan ini adalah benar, sebagainya lonjakan iman,
itulah yang ini jumlah wang sehingga, dan kita boleh
membuktikan bahawa dalam kes yang lebih umum.
Tetapi sekarang mari kita berkembang ini keluar.
Jadi mari kita membiak ini keluar, supaya n kuasa dua, tolak n, semua dibahagikan dengan 2.
Itu benar-benar n kuasa dua, dibahagikan dengan 2, tolak n lebih 2,
jadi itu sahaja yang bagus dan menarik.
Tetapi apa yang berlaku jika kita kini plug-in nilai?
Katakan saya tidak mempunyai lapan orang, tetapi mengatakan juta.
Dan satu juta hanya kerana ia adalah satu jumlah yang cukup besar,
mari kita pasangkan itu dan lihat apa yang berlaku.
Jadi jika saya palam juta ke dalam formula yang Saya akan mendapatkan satu juta kuasa dua,
dibahagikan dengan 2, tolak juta, dibahagikan dengan 2.
Sekarang apa yang yang akan sama?
Jadi 500 bilion, tolak 500,000.
Dan jika saya benar-benar melakukan matematik yang keluar, cara yang
yang menyusun satu juta orang-orang yang semacam gelembung
mungkin mengambil masa saya 499999500000 langkah-langkah atau perbandingan pada akhirnya,
kami hanya menentuluar.
>> Yang terasa agak lambat, tetapi terus-terang berukuran satu input tertentu
seperti ini, tidak semua menunjukkan yang.
Tetapi sesungguhnya ia mencadangkan bahawa sebagai n mendapat, algoritma ini lebih besar dan lebih besar
jenis berasa lebih teruk dan lebih teruk lagi, atau anda benar-benar
mula berasa kesakitan yang exponentiation, n kuasa dua,
yang menambah sehingga agak cepat.
Dan butiran ini tidak hilang pada orang, sebenarnya
beberapa tahun lalu, seorang senator tertentu yang merupakan berkempen, duduk untuk temuduga
Eric dengan Google Schmidt, Ketua Pegawai Eksekutif pada masa itu,
dan telah dicabar dengan soalan sama seperti kita meneroka hari ini.
Mari kita lihat.
>> [VIDEO MAIN SEMULA]
>> -Senator, Anda di sini di Google, dan saya suka
memikirkan jawatan presiden seperti temu duga kerja.
Kini, ia sukar untuk mendapatkan pekerjaan sebagai presiden,
dan anda akan melalui cabaran hebat yang diberikan sekarang.
Ia juga sukar untuk mendapatkan pekerjaan di Google.
Kami mempunyai soalan, dan kami meminta calon-calon soalan kami,
dan ini adalah dari Larry Schwimmer.
What-- kalian fikir saya main-main, ia adalah di sini.
Apakah cara yang paling berkesan untuk menyusun satu juta 32-bit integer?
>> -Well--
>> -I'm Maaf, maybe--
>> Tidak, tidak, tidak.
Saya rasa semacam gelembung akan menjadi cara yang salah untuk pergi.
>> -Ayuh, Yang memberitahu dia ini?
Saya tidak melihat komputer sains di latar belakang anda.
>> -We've Mendapat mata-mata kita di sana.
>> -OK, Mari kita bertanya yang berbeza soalan temuduga.
>> [VIDEO AKHIR MAIN SEMULA]
>> SPEAKER: Jadi bercakap tentang nombor tertentu walaupun,
tidak akan menjadi apa yang berguna.
Ia bukan satu pengajaran hidup gelembung yang jenis, diberi sejuta input,
mungkin mengambil masa sebanyak 500 bilion langkah.
Anda tidak boleh benar-benar umum terlalu berkesan itu
dan membuat keputusan reka bentuk yang baik semasa menulis program.
Jadi mari kita memberi tumpuan walaupun bagaimana kita mungkin memudahkan keputusan ini.
>> Jadi saya telah ditonjolkan dalam kuning di sini hasil daripada kuasa dua n dibahagikan dengan 2,
jadi kuasa dua juta dibahagikan dengan 2, dan kemudian
Saya telah menekankan apa jawapan muktamad adalah
sebaik sahaja kami ditolak off n dibahagi dengan 2.
Dan tuntutan itu saya akan buat sekarang adalah, yang palang pintu yang peduli jika anda tolak off
a n lama lebih kurang 2 apabila pertama sebahagian daripada formula ini begitu banyak lebih besar?
Ia menguasai yang lain jangka, n kuasa dua dibahagikan dengan 2
ini lebih besar, jelas, sebagai n menjadi besar seperti satu juta,
yang benar-benar terdapat perbezaan yang besar di akhirnya di antara 500 bilion
dan 499999500000?
Tidak benar-benar.
Dan apa yang kita akan lakukan sebagai saintis komputer
mengabaikan terma perintah yang lebih rendah dan mengambil sesuatu seperti ini dan benar-benar
hanya memudahkan kepada jangka yang berlaku untuk perkara itu.
Semakin besar set data kami mendapatkan, semakin besar pangkalan data kami mendapatkan, halaman web yang lebih
kita perlu mencari, yang lebih rakan-rakan anda di Facebook.
>> Sebagai n bertambah besar, kami benar-benar akan mengambil berat tentang yang terbesar
tempoh dalam mana-mana analisis apa-apa Prestasi algoritma kami.
Dan saya akan berkata, anda tahu apa, semacam gelembung adalah atas perintah O besar,
atas perintah n kuasa dua.
Ia tidak betul-betul n kuasa dua seperti yang kita lihat,
tetapi yang benar-benar mengambil berat mengenai istilah-istilah yang lebih kecil,
dan terus-terang, yang benar-benar peduli jika kita membahagikan oleh 2?
Itu hanya satu faktor yang berterusan.
Dan 500 bilion berbanding 250 bilion benar-benar masalah besar yang?
Saya hanya boleh menunggu satu tahun, membiarkan komputer riba saya secara literal
mendapatkan dua kali lebih cepat dalam perkakasan, dan yang jenis perbezaan
hanya akan hilang secara semula jadi dari masa ke masa.
>> Apa yang kita mengambil berat tentang adalah ungkapan, bahagian
ungkapan yang berlaku untuk mengubah sebagai input kami mendapat lebih besar dan lebih besar.
Dan memang, dalam dunia sebenar, itulah apa yang berlaku semakin
merupakan input kepada masalah kita dan algoritma mendapat lebih besar.
Jadi O besar akan menjadi notasi, notasi asimptot, bahawa kita hanya
digunakan sebagai saintis komputer untuk menggambarkan prestasi, atau masa berjalan,
satu algoritma.
Supaya kita boleh membandingkan algoritma pada komputer yang berbeza bertulis
oleh orang-orang yang berbeza, dengan menggunakan beberapa metrik pada asasnya serupa
seperti bilangan perbandingan anda membuat, atau mungkin bilangan swap
anda membuat.
>> Apa yang kita tidak akan kiraan adalah jumlah masa
yang berlalu pada jam di dinding biasanya.
Apa yang kita tidak akan bimbang tentang adalah berapa banyak memori
anda menggunakan hari ini di kurangnya, walaupun itu
sumber lain kita mungkin mengukur.
Kami akan cuba untuk mendasarkan analisis kami hanya pada operasi asas, yang,
terus terang, bahawa anda boleh melihat yang paling visual.
Jadi dengan sesuatu seperti O besar n kuasa dua, saya mendakwa bahawa O n kuasa dua
adalah satu atas terikat pada apa yang dikenali sebagai berjalan masa semacam gelembung.
Dalam erti kata lain, jika anda mahu mendakwa bahawa ada
had ini atas kepada berapa banyak langkah algoritma mungkin mengambil masa,
ia akan berada dalam O besar n kuasa dua dalam kes ini, had atas.
>> Bagaimana sekiranya saya bukannya menukar cerita menjadi tidak mengenai jenis gelembung,
tetapi tentang ini had atas.
Bolehkah anda memikirkan algoritma yang kita telah melihat sudah
yang terikat atas, maksimum mengukur masa atau operasi,
akan dikatakan disempadani dengan n, fungsi linear,
bukan satu kuadratik itu melengkung?
Apa algoritma yang sentiasa mengambil masa tidak lebih
daripada langkah-langkah seperti n, atau Langkah 2n, atau langkah-langkah 3n?
Yeah?
>> PENONTON: Mencari jumlah terbesar dalam senarai?
>> SPEAKER: Perfect, mencari jumlah terbesar dalam senarai.
Jika saya diberikan satu senarai orang misalnya,
setiap yang memegang nombor, apa yang bilangan maksimum
daripada langkah-langkah yang perlu mengambil saya, orang yang semunasabahnya pintar,
untuk mencari orang yang terbesar di dalam senarai itu?
n, bukan?
Kerana dalam kes yang paling teruk, di mana mungkin nilai terbesar menjadi?
Betul, semua cara di akhir.
Jadi dalam kes yang paling teruk atas terikat, saya mungkin
perlu pergi sepanjang jalan di sini dan menjadi seperti,
oh, inilah nombor lapan, atau apa sahaja nilai yang.
Sekarang ia hanya akan menjadi bodoh jika saya terus berjalan, bukan?
Mencari lebih banyak unsur-unsur jika yang terakhir daripada mereka ada di sana?
Jadi sudah tentu, n adalah had atas.
Saya tidak perlu mengambil langkah yang lebih daripada itu.
>> Jadi apa jika sebaliknya saya mencadangkan terdapat algoritma di dunia ini yang
mempunyai masa yang berjalan itu disempadani oleh O besar log n, log n?
Di mana telah kita lihat sebelum ini?
Yeah?
>> PENONTON: Dalam masalah buku telefon?
SPEAKER: Seperti masalah buku telefon.
Apakah ukuran bagaimana banyak masa atau berapa banyak air mata itu
mengambil masa saya untuk mencari seseorang seperti Mike Smith dalam buku telefon?
Kita mendakwa ia adalah log n, dan walaupun tidak biasa atau ia itu
yang kabur sedikit apa yang logaritma atau eksponen adalah,
hanya ingat bahawa log n biasanya merujuk kepada proses,
dalam kes ini, membahagikan sesuatu pada separuh lagi, dan sekali lagi,
dan sekali lagi, dan sekali lagi, seperti yang ia mendapat semakin kecil seperti yang anda lakukan itu.
>> Jadi log n merujuk, pasti, kepada contoh buku telefon,
dengan carian binari dalam teori, apabila kita mempunyai pintu maya pada lembaga,
atau apabila Sean adalah mencari sesuatu.
Jika dia telah menggunakan carian binari, log n akan menjadi had atas kepada berapa banyak
masa yang mengambil.
Tetapi orang-algoritma yang berlari dalam Log n diandaikan apa terperinci utama?
Bahawa senarai itu disusun, bukan?
Algoritma anda adalah salah jika input anda tidak disusun,
dan lagi anda menggunakan sesuatu seperti carian binari
kerana anda mungkin boleh melompat hak ke atas elemen
tanpa menyedari ia memang ada.
>> Sekarang apa yang mungkin ini bermakna wahai besar satu?
Ini tidak bermakna bahawa algoritma anda mengambil satu dan hanya satu langkah,
ia hanya bermaksud ia mengambil bilangan berterusan langkah.
Mungkin ia adalah 1, mungkin ia 10, mungkin ia 1,000,
tetapi ia bebas daripada saiz masalah itu.
Tidak kira berapa besar n adalah, algoritma masa tetap
sentiasa mengambil jumlah yang sama langkah-langkah.
Jadi apa yang mungkin menjadi algoritma kita bercakap tentang atau hanya
intuitif yang datang kepada anda bahawa sentiasa berjalan dalam apa yang dikenali sebagai pemalar masa?
Yeah?
>> PENONTON: Tambah dua nombor.
SPEAKER: Tambah dua nombor, 2 plus 2 sama dengan 4, dilakukan.
Jadi yang mungkin bekerja, apa lagi?
Bagaimana tentang dunia lebih nyata, ya?
>> PENONTON: Mencari Perkara pertama dalam senarai.
SPEAKER: Mencari yang pertama elemen dalam senarai, pasti.
Kami benar-benar telah bercakap mengenai tatasusunan sudah,
bagaimana anda mendapat di Elemen pertama dalam array,
tidak kira berapa lama array adalah dalam kod C?
Anda hanya gunakan seperti pendakap notasi sifar, bam, anda di sana.
Dan sesungguhnya tatasusunan, sebagai diketepikan, sokongan sesuatu yang diketahui umum
akses rawak, akses rawak ingatan, kerana anda boleh benar-benar
melompat ke mana-mana satu tempat.
Kita boleh melakukan ini lebih semata-mata kita boleh putar balik untuk minggu sifar
apabila kita lakukan Scratch.
Berapakah masa yang diambil untuk mengatakan blok Scratch untuk melaksanakan?
Hanya masa yang berterusan, bukan?
Mengatakan sesuatu, katakan sesuatu, tidak kira
bagaimana calar besar dunia adalah, ia sentiasa akan mengambil jumlah yang sama masa
dengan hanya mengatakan sesuatu.
>> Jadi itulah masa yang berterusan, tetapi apa yang sebelah flip?
Jika itu adalah atas batas, bagaimana jika kita mahu
untuk menggambarkan batas bawah algoritma kami berjalan masa?
Hampir satu kes terbaik berpotensi, jika anda akan,
walaupun syarat-syarat ini boleh terpakai bagi terbaik kes, kes-kes paling teruk, kes-kes purata lebih
secara amnya, tetapi mari kita hanya tertumpu pada batas bawah amnya.
Apa algoritma yang mempunyai yang lebih rendah terikat n langkah,
atau langkah-langkah 2n, atau langkah-langkah 3n?
Beberapa faktor n langkah, itulah yang lebih rendah terikat.
Yeah?
>> PENONTON: semacam gelembung?
>> SPEAKER: jenis Bubble mengambil anda minimum n langkah, mengapa?
Mengapa?
Mengapa permulaan yang akan datang kepada anda intuitif, walaupun ia bukan sahaja
lagi?
Yeah?
>> PENONTON: [didengar].
SPEAKER: Tepat sekali.
Dalam senario yang terbaik daripada semacam gelembung, dan banyak algoritma,
jika saya menyerahkan anda lapan orang yang telah disusun,
ia akan menjadi bodoh untuk anda, algoritma,
untuk berulang-alik lebih daripada sekali, bukan?
Kerana sebaik sahaja anda berjalan melalui senarai sekali,
anda perlu sedar, oh, saya tidak membuat sebarang swap, senarai ini disusun, keluar.
Tetapi itu akan mengambil langkah-langkah yang anda n.
>> Dan sebaliknya, apa yang lain cara berfikir tentang perkara ini?
Jenis Bubble adalah omega satu, boleh dikatakan, n,
kerana jika anda melihat penggunaan di kurang dari n unsur, apa
adalah isu asas di sana?
Anda tidak tahu jika ia disusun, betul.
Kita manusia kekuatan renungan lapan orang dan menjadi seperti, oh, ia disusun,
yang tidak mengambil langkah-langkah yang saya n, tetapi melakukannya.
Mata anda, walaupun anda jenis daripada mempunyai bidang besar penglihatan,
anda melihat lapan elemen, anda melihat lapan orang,
itulah lapan langkah-langkah yang berkesan.
Dan hanya jika saya berjalan melalui seluruh Senarai saya menyedari, ya, disusun.
Jika saya berhenti separuh jalan berfikir, semua betul, ia cantik disusun setakat ini,
apakah kemungkinan ia tidak disusun?
Bahawa algoritma tidak akan menjadi betul.
Mungkin lebih cepat, tetapi tidak betul.
>> Jadi sekarang kita mempunyai cara menggambarkan batas yang lebih rendah,
dan bagaimana pula dengan masa yang berterusan?
Apa algoritma yang mempunyai yang lebih rendah terikat pada masa perjalanan sebanyak satu?
1 langkah, 2 langkah, 10 langkah, tetapi tetap, bebas daripada n,
saiz input?
Ya, di belakang.
>> PENONTON: printf?
SPEAKER: Apakah itu?
PENONTON: printf?
SPEAKER: printf.
OK, pasti.
Jadi ia mengambil beberapa langkah-langkah yang tetap.
Dan saya perlu now-- sekarang kita berbicara tentang kod C
dan tidak Scratch, sesuatu seperti berkata, dengan printf,
kita harus mula mendapat berhati-hati.
Printf kerana tidak mengambil input, ia adalah rentetan,
dan rentetan yang mempunyai panjang dari segi teknikal.
Jadi, jika kita mahu memilih kepada anda, jika anda tidak keberatan,
secara teknikal kita boleh berhujah bahawa printf tidak mengambil input panjang berubah-ubah,
dan sesungguhnya ia mungkin mengambil masa lebih masa untuk mencetak rentetan yang panjang,
daripada ini panjang.
>> Jadi apa jika kami mengambil kira hanya menyusun dan mencari contoh?
Bagaimana Mike Smith dalam telefon buku, atau carian binari secara umum?
Dalam kes ini, apa yang mungkin berlaku?
Saya membuka buku telefon dan, bam, ada beberapa Mike Smith.
Saya boleh memanggilnya segera.
>> Mengambil satu langkah, mungkin dua langkah, tetapi beberapa langkah-langkah berterusan
jika saya bernasib baik.
Dan terus-terang, kita lihat pada Isnin rakan sekelas anda
mendapatkan cukup bertuah dua kali berturut-turut.
Dan itu sememangnya berterusan masa dalam batas yang lebih rendah
algoritma yang berkenaan untuk mencari bilangan 50 di belakang mereka ditutup
pintu.
>> Sekarang, sebagai diketepikan, jika anda menemui bahawa kedua-dua O besar, had atas,
dan omega, lebih rendah terikat, adalah satu dalam yang sama, yang
adalah formula yang sama dalam kurungan, anda juga boleh
berkata, hanya untuk mewah, sesuatu yang di theta
n atau theta beberapa nilai lain.
Yang hanya bermakna apabila besar O dan omega adalah sama.
Sekarang bagaimana pula jenis pemilihan?
Mari kita gunakan perbendaharaan kata baru ini.
Dalam jenis pemilihan, apakah kita melakukan sekali lagi, dan sekali lagi, dan sekali lagi?
Saya akan berulang-alik melalui senarai, mencari siapa?
Bilangan yang paling kecil.
>> Jadi berapa banyak langkah-langkah, bagaimana perbandingan banyak yang saya lakukan
perlu membuat untuk memikirkan yang unsur yang paling kecil dalam senarai itu?
n tolak 1, bukan?
Kerana jika saya hanya bermula dengan satu yang saya diberikan dan saya mula membandingkan dia atau dia,
kemudian dia atau dia, dia atau dia, dia atau dia, saya
hanya boleh berpasangan elemen bersama-sama n tolak 1 kali.
Jadi pemilihan jenis juga mengambil n tolak 1 langkah pertama kali.
>> Berapa banyak langkah-langkah yang diperlukan saya untuk mendapati elemen kedua paling kecil?
n tolak 2, kerana saya keadaan terpinga jika saya terus mencari orang yang sama
sekali lagi jika saya telah dipilih beliau atau beliau dan meletakkan mereka di tempat mereka.
Dan langkah yang ketiga, n tolak 3, maka n tolak 4.
Kita lihat corak ini sebelum ini, dan sesungguhnya
pemilihan jenis juga mempunyai had atas
n kuasa dua jika kita lakukan sehingga penjumlahan itu.
Apakah batasan bawah, pemilihan jenis ini?
Minimum, berapa banyak masa kemestian pemilihan semacam mengambil, seperti yang kita ditakrifkan ia pada hari Isnin?
Mencadangkan dua pilihan.
Mungkin ia n, seperti sebelum ini.
Mungkin ia n kuasa dua, kerana ia kini sebagai had atas.
>> PENONTON: n kuasa dua.
SPEAKER: n kuasa dua.
Mengapa?
>> PENONTON: Oleh kerana anda mempunyai untuk menentukan [didengar].
>> SPEAKER: Tepat sekali.
Sekurang-kurangnya seperti yang saya ditakrifkan jenis pilihan ia agak naif, terus pergi,
mencari elemen yang paling kecil.
Pergi lagi, cari elemen yang paling kecil.
Tidak ada jenis pengoptimuman di sana yang
mungkin saya akan membatalkan selepas hanya n atau lebih langkah.
Jadi sesungguhnya, pemilihan jenis, omega n kuasa dua.
>> Bagaimana pula dengan jenis sisipan, di mana saya telah mengambil yang saya telah diberikan, dan kemudian saya plopped dia
atau dia di tempat yang betul?
Kemudian saya berjalan kepada orang yang kedua, plopped dia atau dia di tempat yang betul.
Kemudian orang yang seterusnya, plopped dia atau dia di tempat yang betul.
Perhatikan bahawa ini adalah sangat linear, jadi untuk bercakap.
Saya garis lurus, saya tidak akan berulang-alik,
Saya tidak pernah benar-benar melihat ke belakang, tetapi apa yang berlaku apabila saya memasukkan dia
atau dia ke permulaan senarai seperti yang kita lakukan pada hari Isnin?
Apa yang berlaku?
Yeah?
PENONTON: [didengar].
SPEAKER: Ya, yang adalah tangkapan, bukan?
Anda mungkin ingat dari rakan sekelas anda, jika mereka
telah membuat apa-apa pergerakan dengan kaki mereka, itu adalah pembedahan.
Jadi, jika ada tiga orang di sini dan orang yang baru milik cara di sana,
di atas pentas yang panjang seperti ini, pasti, dia atau dia hanya boleh pergi ke akhir sangat.
Tetapi jika kita berfikir tentang yang komputer dan pelbagai memori,
orang-orang ini akan terpaksa shuffle lebih
untuk memberi ruang kepada orang itu.
Dan supaya n tolak 1 shufflings, n tolak 2 shufflings, n
tolak 3 shufflings adalah hanya jenis berlaku di belakang saya, tidak di depan saya
seperti sebelum ini, dalam erti kata lain.
Sekarang sebagai diketepikan, dan sebagai anda mungkin telah melihat dalam talian
jika anda mula poking sekitar kira-kira macam, ada begitu banyak yang berbeza
di luar sana, sebahagian daripada mereka lebih baik daripada yang lain.
Sesungguhnya, bogosort adalah satu itulah jenis menyeronokkan untuk melihat.
Bogosort mengambil satu set nombor atau mengatakan dek kad,
secara rawak Shuffle mereka, dan cek jika mereka disusun.
Dan jika tidak, adakah sekali lagi.
Jika tidak, adakah sekali lagi.
Sangat bodoh.
>> Dan sesungguhnya, jika anda membaca seperti artikel Wikipedia,
nama samaran adalah jenis bodoh.
Ia akhirnya akan bekerja, mudah-mudahan, diberi masa yang cukup,
tetapi jumlah masa boleh mengambil beberapa waktu.
Jadi, jika saya boleh, mari kita perkara-perkara kelajuan dari contoh Mary Beth sebelum ini,
dengan mempunyai lebih beberapa elemen, tetapi dua lagi pemproses.
Dua orang, jika anda tidak keberatan menyertai saya.
Bagaimana kira-kira 1 di sini, dan mari go-- tidak ada di sana?
Tiada siapa di sana?
OK.
Anda dengan hitam shirt, ya, datang ke bawah.
Baiklah, apa nama anda?
>> PENONTON: Peter.
>> SPEAKER: Apakah itu?
>> PENONTON: Peter.
SPEAKER: Peter, David, baik untuk bertemu dengan kamu.
Baiklah, kita mempunyai Peter di sini, jika anda mahu datang ke meja di sini.
Dan apa nama anda?
>> PENONTON: Elena.
SPEAKER: Elena.
OK, baik untuk bertemu dengan kamu.
Elena memenuhi Peter.
Peter, Elena.
Dan kita perlu Andrew di sini juga, sila.
Dan cabaran anda akan menjadi untuk menyusun dek kad.
Dan jika tidak biasa, dek kad perlu akhirnya
diselesaikan sesuatu yang kecil seperti ini di mana kami akan buat kelab-kelab, maka
yang penyodok, maka hati dan berlian, dari ace sebagai satu,
sepanjang jalan sehingga kepada raja.
>> Kad saya akan memberikan anda akan menjadi 52 dalam kuantiti.
Kami akan juga masa anda, dalam hanya seketika.
Kami akan membuang Andrew pada skrin di sini,
untuk menonton seperti yang anda lakukan ini.
Dan supaya semua ini adalah lebih ketara,
ini adalah kad saya di Amazon.
Jadi mereka sudah secara rawak disusun, dan kita akan ke semasa anda.
Dan kita akan menyimpan ia sebenar masa ini,
jadi kita akan cuba untuk memberi tekanan kepada anda kerana jika tidak, ini akan mendapat membosankan
dengan cepat.
Jika anda boleh meneruskan untuk menyusun 52 unsur-unsur bersama-sama melalui beberapa cara, sekarang.
>> Dan sekali lagi, seperti yang kita menonton ini lelaki melakukan apa yang, pada akhirnya
akan menghasilkan jelas hasil, benar-benar berfikir tentang
bagaimana ia setiap melakukannya, bagaimana anda boleh menggambarkannya.
Kerana sekali lagi, ini adalah semua proses, algoritma
yang kita ambil untuk diberikan sebagai manusia.
Tetapi anda mungkin lama mempunyai gerak hati, lama sebelum anda
berfikir tentang mengambil sains komputer kelas anda
mungkin mempunyai gerak hati yang dengan untuk menyelesaikan masalah seperti ini.
Tetapi sebaik sahaja anda menyedari corak dan mula
untuk merasmikan dengan langkah-langkah yang anda menyelesaikan masalah-masalah ini,
anda akan mendapati bahawa anda boleh menyelesaikan banyak lebih menarik dan lebih kompleks
masalah dengan cepat.
Jadi seseorang dari penonton, apa yang sekurang-kurangnya satu elemen algoritma
bahawa mereka menggunakan di sini?
>> PENONTON: [didengar]
SPEAKER: Apakah itu?
PENONTON: Dengan saman.
SPEAKER: Dengan saman.
Oleh itu mereka berkelompok semua berlian bersama-sama
ia seolah-olah, semua hati bersama-sama ia seolah-olah,
dan sebagainya, tanpa berkenaan untuk nombor tersebut pada kad.
Dan kini terdapat, misalnya, untuk menyusun mereka dengan nombor.
Sangat baik.
>> Baiklah, jadi apa yang akan menjadi langkah terakhir maka di sini?
Apabila kita mempunyai empat saman disusun, apa kita perlu lakukan untuk empat buasir
untuk mencapai satu dek disusun, cukup hanya?
Jadi, kita perlu untuk menggabungkan mereka lagi.
>> Jadi ada idea menarik yang sekali lagi, berani mengatakan, adalah sangat intuitif walaupun
jika anda mungkin tidak pernah menampar yang jenis label di atasnya.
Ini tanggapan asas membahagikan masalah itu tidak pada separuh masa ini,
tetapi sekurang-kurangnya kepada empat keping.
Menyelesaikan cukup banyak masalah asas yang sama
secara berasingan daripada satu sama lain, dan kemudian menggabungkan keputusan.
Dan, yang sangat baik, dilakukan.
Baiklah, satu pusingan besar tepukan, jika kita boleh.
>> [Tepuk tangan]
>> SPEAKER: Saya tidak tahu apa yang anda akan lakukan dengan ini, tetapi di sini anda pergi.
Terima kasih banyak.
Jadi mari kita lihat, dua minit dan lapan saat,
jika anda ingin mencabar rakan-rakan anda.
Apa yang kemudian akan menjadi mengambil dari ini
kita dapat memanfaatkan secara umum?
Nah, berfikir kembali ke array ini nombor,
dan berfikir kembali sekarang untuk beberapa pseudokod kita telah menulis pada masa lalu,
dan ini adalah pseudokod untuk menyelesaikan masalah buku telefon.
Manakala dalam pseudokod saya yang disebut satu persatu cara yang lebih teratur
menggambarkan bagaimana saya lakukan yang sangat intuitif algoritma manusia membahagikan telefon
buku pada separuh, ulang, ulang, ulang, sehingga saya mencari seseorang seperti Mike Smith,
jika dia memang di dalam buku telefon.
>> Tetapi saya jenis yang digunakan apa yang saya akan panggil pendekatan yang sangat lelaran di sini,
dalam notis tertentu talian 8 dan talian 11.
Mereka adalah bukti satu lelaran pendekatan, pendekatan gegelung,
kerana itulah tingkahlaku yang mendorong.
Mereka kedua-dua garisan mengatakan pergi ke jenis garis tiga, dan anda boleh dalam
memikirkan bahawa anda mata minda sebagai gelung.
Ia memberitahu anda untuk naik semula ke langkah tiga dan ulangi, sekali lagi, dan sekali lagi,
dan lagi.
>> Tetapi bagaimana jika kita memanfaatkan idea utama di sini bahawa yang kita lakukan bukan kali terakhir,
dan memudahkan talian 8 dan talian 11 dan jiran-jiran mereka
sebagai hanya ini, dalam kuning.
Ia tidak asasnya memendekkan pseudokod yang sangat banyak,
tetapi ia asasnya mengubah sifat algoritma saya.
Apa yang saya kini mengatakan dalam langkah 7, dalam langkah 10,
adalah untuk mencari Mike dengan cara yang sama yang tepat,
tetapi hanya di sebelah kiri setengah atau separuh betul.
>> Jadi dalam erti kata lain, jika Saya bermula dari langkah satu,
mengambil buku telefon, terbuka ke tengah buku telefon, lihat pada nama,
jika Smith adalah antara nama ini, hubungi Mike, lain
jika Smith lebih awal di dalam buku, melangkah tujuh mencari Mike pada separuh kiri buku.
Tetapi itu jenis berasa seperti ia meninggalkan saya tergantung, bukan?
Kuning, adalah arahan, tetapi bagaimana saya
mencari Mike di sebelah kiri separuh daripada buku telefon?
Di mana saya mempunyai algoritma yang aku
boleh mencari seseorang seperti Mike Smith?
Nah, ia merenung kita di muka.
Saya benar-benar boleh menggunakan sama program berkesan naik ke atas
lagi dan berlari semula garis yang sama kod.
>> Jadi walaupun ini harus berasa seperti sedikit definisi kitaran
mana anda hendak pergi menjawab seseorang adalah soalan dengan hanya jenis bertanya
soalan yang sama sekali lagi, seperti mengapa, mengapa, mengapa?
Realitinya adalah kerana kita telah keras dikodkan beberapa garis khas, langkah 4,
yang jika, dan langkah 12, yang adalah berkesan cawangan yang lain,
kerana kita mempunyai langkah-langkah pengganti sementara, algoritma ini akan ditamatkan jika kita
mencari Mike, atau jika kita tidak.
Tetapi dalam langkah 7 dan 10 sekarang, kita mempunyai apa yang kita akan memanggil algoritma rekursif.
Dan rekursi memang idea yang kuat itulah fikiran sedikit lenturan pada mulanya,
bahawa kita kini boleh memohon seperti berikut.
>> Bergabung jenis akan jenis yang lepas bahawa kita melihat, sekurang-kurangnya di dalam kelas secara formal.
Dan ia berbeza dari tiga lepas, dan sudah tentu
separuh akhir jika kita termasuk bogosort.
Berikut adalah pseudokod untuk jenis merge.
Apabila input n elemen, jadi diberikan pelbagai saiz n, jika n adalah kurang daripada 2,
kembali.
Jadi mengapa perlu saya bahawa kewarasan cek pertama?
Apakah implikasi sekiranya saya menyerahkan anda pelbagai yang panjang n adalah kurang daripada 2?
Ia telah pun disusun, jelas, bukan?
Oleh kerana senarai itu sama ada mempunyai satu elemen yang trivially
disusun kerana ia satu-satunya perkara di sana.
Atau, ia saiz sifar yang bermaksud tiada apa-apa untuk menyelesaikan, jadi secara semula jadi
ia disusun.
Hanya ada apa yang salah di sana.
Supaya kes asas kami kononnya.
>> Yang sama dalam semangat dengan apa yang kita lakukan dengan Mike.
Jika Mike dalam buku telefon, memanggil dia.
Jika dia tidak ada, menyerah.
Ia satu kes asas yang dipanggil, memastikan algoritma ini pada akhir hari
akan berhenti dalam keadaan tertentu.
>> Tetapi di sini yang lompatan iman sekarang, lain, menyusun separuh kiri unsur-unsur,
kemudian menyusun kanan separuh daripada unsur-unsur,
dan kemudian menggabungkan bahagian disusun.
Dan di sini di mana ia berasa seperti kita copping keluar.
Saya meminta anda untuk menyusun n unsur-unsur, dan saya
berkata, OK, adakah ia oleh sorting ke kiri dan sorting kanan.
Tetapi saya katakan satu benda lain, dan ini
adalah tema utama ia seolah-olah dalam gerak hati ini setakat ini,
ada ini langkah ketiga bergabung.
Yang walaupun ia seolah-olah jadi bisu dalam roh,
seperti hanya bergabung perkara bersama-sama, ia seolah-olah
menjadi satu langkah utama ke arah Pemasangan semula dua masalah yang
dibahagikan akhirnya pada separuh.
>> Jadi bergabung jenis, mari kita melakukan ini, jika anda akan jenaka saya, dengan satu demonstrasi lanjut,
hanya supaya kita mempunyai beberapa nombor untuk bekerja dengan.
Bolehkah saya menukar lapan tekanan bola selama lapan orang?
Baiklah, bagaimana pula anda tiga, anda empat dalam seksyen ini, lima, enam, dan mari kita
yang 7, 8, datang ke atas.
OK, yeah OK.
Tolak 8, ada kita pergi, campur 1.
Cemerlang.
Semua datang betul-betul di atas, mari kita cepat memberikan anda nombor.
Nombor dua, nombor tiga, nombor empat, nombor lima, enam, tujuh dan lapan.
Saya lapan dengan betul kali ini.
>> OK, jadi teruskan jika anda boleh, dan mari menyusun dalam perintah asal
bahawa kita mempunyai semalam yang kelihatan seperti ini, jika anda tidak keberatan.
Dan mari kita melakukannya di hadapan meja.
Baiklah, jadi bergabung jenis.
Ini adalah di mana ia akan untuk mendapatkan jenis yang menarik,
kerana saya seolah-olah memberi diri saya begitu banyak maklumat hari ini kurang.
>> Jadi bergabung jenis pertama sekali input n unsur,
dan jelas tidak kurang daripada dua orang, ia lapan, jadi saya mempunyai beberapa kerja lagi yang perlu dilakukan.
Jadi sekarang mental kita sebagai sebuah kelas kini di cawangan lain yang,
yang bermaksud tiga langkah.
Pertama, saya perlu menyusun separuh kiri unsur-unsur.
Jadi bagaimana Aku tidak melakukan ini?
Well, saya akan jenis mental membahagikan senarai di sini,
anda tidak perlu fizikal bergerak, dan saya
akan memberi tumpuan hanya pada separuh kiri unsur-unsur di sini.
Jadi bagaimana saya pergi tentang sorting senarai kini saiz empat?
Apa algoritma saya?
Pertama saya menyemak adalah n kurang daripada dua, tidak, jadi saya pergi ke blok lain lagi.
Susun meninggalkan separuh daripada unsur-unsur.
>> Jadi sekarang lagi, mental, dan di sinilah
anda perlu terakru banyak Sejarah mental, jika anda akan.
Kini saya sorting kiri separuh daripada separuh kiri.
Baiklah, jadi sekarang saya menyeru merge sama saya sorting algoritma, n adalah kurang daripada dua?
Tidak, ia adalah dua, jadi saya perlu menyusun separuh di sebelah kiri, dan separuh yang betul.
Jadi di sini kita pergi, menyusun separuh kiri.
Mengapa tidak anda hanya mengambil satu langkah ke hadapan.
Apa nama anda?
>> PENONTON: Darren.
>> SPEAKER: Dan.
Dan telah melangkah ke hadapan.
>> PENONTON: Darren.
SPEAKER: Darren, dilakukan.
Adakah anda berkata atau Darren Dan?
>> PENONTON: Darren.
>> SPEAKER: Darren.
OK, Darren telah melangkah ke hadapan dan dia kini disusun.
Dan ini adalah hampir satu tuntutan bodoh, bukan?
Saya tidak benar-benar seolah-olah mencapai apa-apa, tetapi mari kita teruskan.
Sekarang, saya akan menyusun kanan separuh daripada unsur-unsur.
Apa nama anda?
>> PENONTON: Lukas.
>> SPEAKER: Lukas.
Ayuh, melangkah ke hadapan.
Selesai, saya telah disusun Lukas.
Separuh kiri kini disusun dan separuh yang betul kini disusun,
tetapi sekali lagi, ada satu langkah yang penting di sini.
Apa yang saya akan datang perlu lakukan?
Menggabungkan bahagian disusun.
Sekarang kita akan hanya perlu semua orang berulang-alik dengan cara ini,
kerana saya jenis perlu beberapa ruang kosong.
Ia hampir seperti ini lelaki adalah di atas meja,
dan saya memerlukan bilik untuk memindahkan mereka sekitar di.
Jadi saya akan bergabung kalian dengan melihat
pada separuh kiri dan separuh yang betul.
Dan yang jelas datang pertama, separuh kiri atau separuh betul?
Jadi separuh betul, jadi mari kita bergerak Lukas lebih di sini untuk kedudukan asal Darren.
Dan sekarang untuk bergabung separuh kiri mereka dalam, Darren yang sedang bergerak di sana.
>> Jadi rasanya hampir kesan semacam gelembung,
tetapi algoritma asas saya, sangat berbeza kali ini.
Tetapi sekarang di mana perkara mendapatkan sedikit menjengkelkan kerana anda
perlu putar balik mental di mana saya meninggalkan off.
Saya baru sahaja bergabung di bahagian disusun, yang bermaksud saya di mana dalam algoritma saya?
Saya perlu menyusun separuh yang betul, bukan?
>> Jika anda memutar balik, secara literal pada video, anda akan
melihat bahawa kita mendapat ini titik Luke dan Darren
oleh sorting kiri separuh daripada separuh kiri.
Kemudian kami bergabung mereka bahagian disusun, yang
bermakna langkah seterusnya adalah jenis yang bahagian kanan separuh kiri.
Baiklah, jadi mari kita melakukan ini dengan lebih cepat.
Baiklah, enam, saya akan menuntut anda kini disusun, datang ke hadapan.
Apa nama anda?
>> PENONTON: Adriano.
>> SPEAKER: Adriano.
Adriano kini disusun.
Dan apa nama anda?
>> PENONTON: Alex.
>> SPEAKER: Alex kini disusun.
Separuh kiri, separuh betul, apa langkah terakhir?
Bergabung.
Pretty remeh, jadi saya akan bergabung dalam enam,
mengambil langkah ke belakang, lapan, mengambil langkah ke belakang.
Dan kini notis ini yang bisa dibesarkan berguna, apa yang
kini benar tentang separuh kiri senarai, tidak kira bagaimana kita bermula?
Ia disusun.
>> Sekarang ia tidak disusun dalam skim besar perkara,
tetapi ia disusun secara bebas daripada separuh yang lain.
Sekarang apa langkah aku di jika saya terus gulung semula bagaimana kisah itu bermula?
Sekarang saya perlu menyusun separuh betul.
Jadi sekarang kita kembali pada cara permulaan cerita,
dan mari kita melakukan ini dengan lebih cepat.
Jadi saya akan menyusun bahagian kanan seluruh senarai.
Apa langkah seterusnya?
Menyusun separuh kiri separuh betul.
Menyusun separuh kiri yang separuh kiri separuh betul.
Dan apa nama anda?
>> PENONTON: Omar.
>> SPEAKER: Omar, melangkah ke hadapan, dilakukan.
Separuh kiri adalah disusun.
Dan apa nama anda?
>> PENONTON: Chris.
>> SPEAKER: Chris, mengambil langkah yang ke hadapan, anda kini disusun.
Apakah langkah penting sekarang?
Bergabung.
Jadi siapa yang akan bergabung menjadi tempat di sini, jika anda boleh mengambil langkah ke belakang,
dan tiga akan mengambil langkah ke belakang, bergabung.
Jadi separuh kiri bahagian kanan, kini disusun.
Terus terang, algoritma ini berasa seperti kita cara membuang lebih banyak masa berbanding sebelum ini,
tetapi jika kita melakukan ini dalam masa sebenar, kita akan melihat apa yang bawa pulang akan menjadi.
Sekarang di sini saya, betul separuh daripada separuh yang betul,
biarlah saya pergi ke hadapan dan menyusun separuh kiri.
Melangkah ke hadapan, apa nama anda?
PENONTON: Ramsey.
SPEAKER: Ramsey kini disusun.
Apa nama anda?
>> PENONTON: Marina.
>> SPEAKER: Marina kini disusun sebagai juga, jika anda mengambil satu langkah ke hadapan.
Langkah utama di sini kini bergabung, saya akan memetik dari dua senarai saya,
kiri dan kanan.
Lima akan datang pertama, dan tujuh akan datang akan datang.
Dan sekali lagi, ini adalah disengajakan.
Hakikat bahawa mereka mengambil langkah ke hadapan dan belakang
bertujuan untuk menyatakan bahawa kita tidak boleh melakukan algoritma ini di tempat yang mudah
sebagai semacam gelembung, dan jenis pemilihan, dan jenis sisipan di mana kita hanya
disimpan pertukaran orang.
Saya benar-benar memerlukan satu jenis kertas gores di mana
untuk meletakkan orang ini semasa saya melakukan penggabungan itu,
dan kemudian saya boleh meletakkan mereka kembali di tempat.
Dan itu penting kerana saya menggunakan sumber baru, ruang, bukan sahaja masa.
>> OK, ini luar biasa.
Separuh kiri disusun, separuh kanan adalah disusun, sekarang bahawa kunci menggabungkan langkah.
Bagaimana saya akan bergabung ini?
Jadi, jika anda akan mengikuti saya tangan kiri dan tangan kanan,
Saya akan menunjukkan tangan kiri saya pada separuh kiri, tangan kanan saya
pada separuh yang betul, dan sekarang saya perlu memutuskan langkah demi langkah yang bergabung dalam.
Yang jelas datang pertama?
Nombor satu.
Jadi datang ke sini, di sini pad awal kami.
Jadi sekarang nombor satu, dan notis apa yang saya akan lakukan dengan tangan kanan saya,
Saya akan bergerak satu tangan kanan saya melangkah ke titik ketiga,
dan sekarang saya perlu membuat keputusan sama.
Dan benar-benar berdiri betul-betul di hadapan Luke di sini jika anda boleh,
kerana ini adalah pad awal kami.
Jadi yang datang akan datang?
Kami mempunyai Luke dengan nombor dua atau Chris dengan nombor tiga.
Jelas Lukas, bilangan dua, jadi anda datang ke sini.
>> Tetapi tangan kiri saya kini akan akan incremented untuk menunjuk ke arah Darren,
dan di sini yang utama dengan mengambil bergabung, saya akan terus melakukan ini,
jelas, jika anda jenis daripada mengikuti logik.
Tetapi tangan saya tidak pernah akan pergi ke belakang,
yang bermaksud saya hanya pernah berpindah ke kiri dengan proses penggabungan saya,
dan itu akan menjadi kunci kepada analisis kami dalam hanya seketika.
>> Jadi sekarang mari kita selesai ini dengan pesat.
Jadi tiga datang akan datang, kemudian empat datang akan datang,
dan kini lima datang berikutnya, kemudian enam, dan tujuh, dan akhirnya lapan.
Terasa seperti algoritma paling perlahan lagi, tetapi tidak jika kita benar-benar
jalankan ia jenis yang sama kelajuan jam, jadi untuk
bercakap, dengan yang sama berdetik jam seperti sebelum ini.
Mengapa?
Nah, Mari kita melihat hasil akhir.
>> Mari kita kembali di sini, biar saya tarik demonstrasi visual
apa yang kita lakukan.
Zoom masuk di sini, ini Laman di sini, memberitahu Firefox
yang kita mahu beratur di dalam kotak ini, mari kita
mengatakan semacam gelembung, dengan yang kami kini juga biasa,
jenis pemilihan, yang merupakan satu lagi agak satu mudah,
dan kini semacam merge hari ini, yang akan berakhir klimaks kami.
Sebab ia mengambil masa yang lebih lama di sini dengan manusia dan saya secara lisan adalah,
jelas, saya menerangkan setiap langkah.
Tetapi jika anda hanya melaksanakan ini, banyak seperti yang kami lakukan gelembung jenis dan pemilihan
jenis bukan sahaja visual, jam tangan betapa banyak dengan lebih cekap
memanfaatkan ini bahagian dan menakluk
boleh apabila digunakan untuk satu set data itu tidak saiz lapan, tetapi walaupun banyak,
lebih besar.
Saya memberi anda bergabung jenis, sebelah- sampingan dengan ini algoritma lain.
Ini akan mendapatkan menyakitkan cepat, dan akhir yang
tidak terlalu klimaks, mereka hanya berakhir disusun.
Tetapi kunci mengambil ialah bagaimana kelihatan lebih cepat bergabung jenis
adalah, melainkan jika anda fikir saya hanya jenis kerunsingan dengan anda.
Jika kita melakukan ini sekali akhir, Mari kita menambah nilai ini, mari kita kembali
dan memilih jenis gelembung, dan hanya untuk tendangan,
mari kita memilih sisipan jenis, hanya sebagai langkah yang baik.
Dan masa ini lagi, mari kita memilih jenis merge dan mari kita
sebenarnya berjalan sebelah menyebelah ini.
>> Dan bukan, sebenarnya, kebetulan.
Apa yang saya lakukan adalah berkesan saya telah dibahagikan input saya pada separuh, sekali lagi,
dan sekali lagi, dan sekali lagi.
Dan hanya ada banyak kali anda boleh membahagikan input anda ke bahagian, kiri
dan kanan.
Apakah formula yang kita terus melihat yang menggambarkan bahagian ini pada separuh
sekali lagi, dan sekali lagi, dan sekali lagi, dan sekali lagi?
>> PENONTON: Log n.
>> SPEAKER: Log n.
Tetapi kemudian ada satu langkah utama yang lain, algoritma ini tidak log n langkah.
Jika ia hanya log n langkah, kami akan berada dalam masalah yang sama
seperti sebelum ini di mana kita tidak boleh memastikan semuanya ini disusun.
Anda perlu melihat secara minimum di n elemen untuk memastikan n unsur-unsur disusun,
jika tidak ia adalah satu lonjakan iman.
>> Jadi log minimum n langkah, tetapi apa tentang perkara ini langkah penggabungan utama
di mana saya digabungkan separuh kiri dan kanan setengah dan berjalan di seluruh peringkat?
Berapa banyak langkah-langkah ialah untuk bergabung?
Ia n, tetapi saya tidak hanya bergabung masa akhir.
Pada setiap panggilan yang bersarang, pada setiap dari orang-orang bergabung bersarang, saya masih disusun.
Saya digabungkan kedua-dua perempuan, maka kedua-dua perempuan, maka kedua-dua lelaki dan sebagainya.
>> Jadi saya bergabung sekali lagi, dan lagi.
Berapa kali?
Jadi setiap kali saya membahagikan senarai dua, saya merge a.
Bahagikan senarai pada separuh, melakukan merge a.
Jadi jika membahagikan senarai boleh dilakukan log n kali,
dan penggabungan yang akhirnya mengambil n langkah, apa yang mungkin sekarang atas
terikat pada berjalan masa algoritma kami?
n log n.
>> Dan sesungguhnya, itulah yang kami telah dicapai di sini.
Jadi rasa yang anda lihat secara visual apabila tiga perkara yang berjalan sebelah menyebelah
adalah n kuasa dua terhadap n kuasa dua terhadap n log n.
Yang pada dasarnya kita akan melihat, bukan sahaja hari ini tetapi pada masa akan datang,
jauh, jauh lebih cepat.
Satu pusingan tepukan untuk lelaki ini, Saya akan memberi ganjaran kepada mereka dengan bola tekanan.
Mari kita menangguhkan di sini hari ini, dan kita akan melihat anda pada hari Isnin.