>> [Bermain muzik]
>> PROFESOR: Baiklah.
Ini adalah CS50 dan ini adalah hujung minggu tiga.
Oleh itu, kita berada di sini hari ini, tidak dalam Sanders Teater, dan bukannya di Perpustakaan Weidner.
Di dalam yang merupakan studio dikenali sebagai Hauser Studio,
atau yang akan kita katakan Studio H, atau hendaklah kita iaitu- jika anda menikmati jenaka itu,
ia sebenarnya dari rakan sekelas, Mark, dalam talian,
yang mencadangkan sebanyak melalui Twitter.
Sekarang apa yang sejuk kira-kira berada di sini dalam studio
adalah bahawa saya dikelilingi oleh hijau ini dinding, skrin hijau atau chromakey,
boleh dikatakan, yang bermaksud bahawa ini CS50 pasukan pengeluaran, tanpa pengetahuan saya
sekarang, boleh meletakkan saya yang paling mana-mana sahaja di dunia,
untuk lebih baik atau untuk lebih teruk.
>> Sekarang apa yang akan berlaku, masalah set dua adalah di tangan anda untuk minggu ini,
tetapi dengan masalah set tiga minggu akan datang,
anda akan dicabar dengan permainan yang dipanggil 15 tahun,
pihak memihak lama yang anda mungkin ingat menerima
sebagai kanak-kanak yang mempunyai sejumlah nombor yang boleh slaid ke atas, ke bawah,
kiri dan kanan, dan ada satu jurang dalam teka-teki, di mana anda
sebenarnya boleh slaid orang-orang keping teka-teki.
Akhirnya anda menerima ini teka-teki dalam beberapa perintah semi rawak,
dan matlamatnya adalah untuk menyelesaikannya, atas ke bawah,
kiri ke kanan, dari satu sepanjang jalan sehingga melalui 15.
>> Malangnya, pelaksanaan anda akan mempunyai di tangan
akan menjadi perisian berdasarkan, bukan fizikal.
Anda sebenarnya akan perlu untuk menulis kod dengan mana seorang pelajar atau pengguna boleh
bermain permainan 15.
Dan sebenarnya, di penggodam edisi permainan 15 tahun,
anda akan menjadi satu cabaran untuk melaksanakan, bukan hanya bermain sekolah lama ini
permainan, tetapi penyelesaian yang daripadanya, melaksanakan mod tuhan,
boleh dikatakan, yang benar-benar menyelesaikan teka-teki untuk manusia,
dengan menyediakan mereka dengan tanda-tanda, selepas tanda-tanda, selepas tanda-tanda.
Jadi lebih pada minggu depan.
Tetapi itulah apa yang akan berlaku.
>> Buat masa ini masih ingat bahawa pada awal minggu ini kita mempunyai cliffhanger ini, jika anda akan,
mana yang terbaik yang kami lakukan menyusun bijak adalah had atas daripada besar o n
kuasa dua.
Dalam erti kata lain, jenis gelembung, jenis pemilihan, jenis kemasukan,
semua daripada mereka, manakala yang berbeza dalam pelaksanaannya,
diturunkan ke dalam n kuasa berjalan masa dalam kes yang paling teruk.
Dan kita biasanya menganggap bahawa kes yang paling teruk untuk menyusun
adalah salah satu yang input anda benar-benar ke belakang.
Dan sesungguhnya, ia mengambil masa agak beberapa langkah untuk melaksanakan setiap mereka algoritma.
>> Kini pada akhir sangat kelas ingat, kita berbanding jenis gelembung
terhadap jenis pemilihan terhadap seorang lain yang kita dipanggil merge pada masa itu,
dan saya mencadangkan supaya ia mengambil kesempatan daripada pengajaran dari minggu
sifar, membahagi dan menakluk.
Dan entah bagaimana mencapai beberapa jenis logaritma masa berjalan akhirnya,
bukan sesuatu itu semata-mata kuadratik.
Dan ia tidak cukup logaritma, ia agak lebih daripada itu.
Tetapi jika anda ingat dari kelas, ia adalah banyak, lebih cepat.
Mari kita lihat di mana kita berhenti.
>> Jenis Bubble berbanding pilihan semacam berbanding jenis merge.
Sekarang mereka semua berjalan, dalam teori, pada masa yang sama.
CPU sedang berjalan pada kelajuan yang sama.
Tetapi, anda boleh merasakan bagaimana membosankan ini sangat cepat akan menjadi,
dan betapa cepat, apabila kita menyuntik sedikit algoritma minggu sifar,
kita boleh mempercepatkan perkara.
>> Jadi semacam tanda kelihatan menakjubkan.
Bagaimana kita boleh memanfaatkan, dalam usaha untuk menyusun nombor dengan lebih cepat.
Nah mari kita berfikir kembali untuk ramuan yang kita
mempunyai kembali pada minggu sifar, iaitu mencari seseorang dalam buku telefon,
dan ingat bahawa pseudokod yang kita dicadangkan,
melalui mana kita boleh mencari seseorang seperti Mike Smith,
melihat sesuatu yang kecil seperti ini.
>> Sekarang kita lihat khususnya di garisan 7 dan 8, dan 10 dan 11,
yang mendorong gelung yang, di mana kami terus kembali ke garisan 3 lagi, dan sekali lagi,
dan lagi.
Tetapi ternyata bahawa kita boleh melihat algoritma ini, di sini dalam kod pseudo,
sedikit lebih holistik.
Malah, apa yang saya cari di sini pada skrin,
adalah satu algoritma untuk mencari Mike Smith di antara beberapa set halaman.
Dan sesungguhnya, kita boleh memudahkan ini algoritma mereka garis 7 dan 8,
dan 10 dan 11 untuk hanya mengatakan ini, yang saya telah dibentangkan di sini dalam kuning.
Dalam erti kata lain, jika Mike Smith yang lebih awal dalam buku ini,
kita tidak perlu untuk menentukan langkah demi langkah sekarang bagaimana untuk pergi mencari dia.
Kami tidak perlu nyatakan untuk kembali ke baris 3,
mengapa tidak kita sebaliknya, katakan, secara umum,
mencari Mike dalam separuh kiri buku ini.
>> Sebaliknya, jika Mike sebenarnya kemudian dalam buku ini,
mengapa tidak kita hanya memetik carian unquote untuk Mike dalam separuh kanan buku ini.
Dalam erti kata lain, mengapa tidak kita hanya semacam menyepak bola kepada diri kita sendiri dan berkata:
mencari Mike dalam ini subset buku ini,
dan menyerahkan kepada kami yang sedia ada algoritma untuk memberitahu kami
bagaimana untuk mencari Mike dalam bahawa separuh kiri buku ini.
Dengan kata lain, kita algoritma berfungsi sama ada
buku telefon tebal ini, ini ketebalan, atau mana-mana ketebalan sekalipun.
Oleh itu, kita boleh secara rekursif menentukan algoritma ini.
Dalam erti kata lain, pada skrin di sini, adalah algoritma
untuk mencari Mike Smith antara muka surat buku telefon.
Jadi dalam talian 7 dan 10, mari kita hanya mengatakan perkara tersebut.
Dan saya menggunakan istilah ini seketika lalu, dan sesungguhnya, rekursi
adalah topik yang hangat diperkatakan sekarang, dan ia adalah proses ini
melakukan sesuatu kitaran oleh entah bagaimana menggunakan kod yang anda sudah mempunyai,
dan memanggil sekali lagi, dan sekali lagi, dan lagi.
Kini ia akan menjadi penting yang kita entah bagaimana bawah
keluar, dan tidak berbuat demikian panjang tak terhingga.
Jika tidak kita akan mempunyai sesungguhnya gelung tak terhingga.
Tetapi mari kita lihat jika kita boleh meminjam idea ini rekursi, melakukan sesuatu lagi
dan lagi dan lagi, untuk menyelesaikan masalah sorting melalui merge
jenis, lebih-lebih cekap.
>> Oleh itu, saya memberikan anda bergabung apapun.
Mari kita lihat.
Jadi di sini adalah kod pseudo, dengan yang kita boleh melaksanakan menyusun,
menggunakan algoritma ini dipanggil jenis merge.
Dan ia cukup sekadar ini.
Dalam input n elemen, dalam erti kata lain, jika anda
diberikan n elemen dan nombor dan huruf atau apa-apa input adalah,
jika anda diberi n unsur, jika n adalah kurang daripada 2, hanya kembali.
Betul?
Kerana jika n adalah kurang daripada 2, yang bermakna bahawa senarai saya unsur-unsur
sama ada saiz 0 atau 1, dan dalam kedua-dua kes-kes remeh,
senarai tersebut sudah disusun.
Jika tidak ada senarai, ia disusun.
Dan jika ada senarai panjang 1, ia jelas disusun.
Jadi algoritma hanya perlu benar-benar melakukan sesuatu yang menarik,
jika kita mempunyai dua atau lebih unsur-unsur yang diberikan kepada kita.
Jadi mari kita lihat keajaiban itu.
Yang lain menyusun separuh kiri unsur-unsur, kemudian menyusun separuh yang betul unsur-unsur,
kemudian menggabungkan bahagian disusun.
Dan apa jenis minda lentur di sini, adalah bahawa saya tidak benar-benar
seolah-olah telah memberitahu anda apa-apa sahaja lagi, bukan?
Apa yang saya katakan adalah, diberikan senarai n unsur, menyusun separuh kiri,
daripada setengah yang betul, maka menggabungkan bahagian disusun,
tetapi di mana sos rahsia sebenar?
Di mana algoritma?
Nah ternyata bahawa kedua-dua baris pertama, separuh semacam meninggalkan unsur-unsur,
dan jenis kerja separuh daripada unsur-unsur, adalah panggilan rekursif, jadi untuk bercakap.
>> Lagipun, pada ini bila masa, saya perlu
algoritma yang boleh digunakan untuk menyusun sejumlah besar unsur?
Ya.
Ia adalah di sini.
Ia adalah di sini pada skrin, dan jadi saya boleh menggunakan set yang sama langkah-langkah
untuk menyusun separuh kiri, yang saya boleh separuh betul.
Dan sesungguhnya, sekali lagi, dan lagi.
Jadi entah bagaimana atau lain-lain, dan kita akan tidak lama lagi melihat ini, keajaiban merge
tertanam dalam yang sangat akhir line, menggabungkan bahagian disusun.
Dan yang seolah-olah agak intuitif.
Anda mengambil dua bahagian, dan anda, entah bagaimana, menggabungkan mereka bersama-sama,
dan kita akan melihat ini secara kukuh dalam seketika.
>> Tetapi ini adalah algoritma yang lengkap.
Dan mari kita melihat dengan jelas mengapa.
Well andaikan bahawa kita diberikan ini sama lapan elemen sini pada skrin, satu
melalui lapan, tetapi ia agar seolah-olah rawak.
Dan matlamat yang di tangan adalah untuk menyusun elemen-elemen ini.
Nah bagaimana saya boleh pergi tentang melakukannya menggunakan, sekali lagi,
bergabung apapun, seperti kod pseudo ini?
Dan sekali lagi, dicat di dlm wol ini dalam fikiran anda, hanya untuk seketika.
Kes pertama adalah cukup remeh, jika ia adalah kurang daripada 2,
hanya kembali, tidak ada kerja yang perlu dilakukan.
Jadi benar-benar ada hanya tiga langkah-langkah untuk benar-benar perlu diingat.
Sekali lagi, dan sekali lagi, Saya akan mahu mempunyai
untuk menyusun separuh kiri, menyusun separuh yang betul,
dan kemudian sekali mereka dua bahagian yang disusun,
Saya mahu bergabung mereka bersama-sama ke dalam satu senarai yang disusun.
Jadi menyimpan bahawa dalam fikiran.
>> Jadi di sini adalah senarai asal.
Mari kita merawat ini sebagai pelbagai, seperti yang kita mula
dalam seminggu dua, yang merupakan blok berdampingan memori.
Dalam kes ini, yang mengandungi lapan nombor, kembali ke belakang untuk kembali.
Dan mari kita kini memohon merge.
Jadi saya mula-mula mahu untuk menyusun separuh kiri senarai ini,
dan mari kita, oleh itu, memberi tumpuan kepada 4, 8, 6, dan 2.
>> Sekarang bagaimana saya boleh pergi tentang menyusun senarai saiz 4?
Well, saya perlu kini menganggap menyusun sebelah kiri separuh kiri.
Sekali lagi, mari kita putar balik hanya untuk seketika.
Jika kod pseudo adalah ini, dan saya diberi lapan elemen,
8 adalah jelas lebih besar daripada atau sama dengan 2.
Jadi dengan kes pertama tidak terpakai.
Jadi untuk menyelesaikan lapan elemen, aku menyusun separuh kiri unsur-unsur,
maka saya menyusun separuh yang betul, maka saya bergabung kedua-dua bahagian yang disusun, setiap saiz 4.
OKAY.
>> Tetapi jika anda baru sahaja memberitahu saya, menyusun separuh kiri, yang kini saiz 4,
bagaimana saya menyusun separuh kiri?
Baik jika saya mempunyai input daripada empat unsur,
Saya mula-mula menyusun kiri dua, maka dua yang betul,
dan kemudian saya menggabungkan mereka bersama-sama.
Jadi sekali lagi, ia menjadi agak fikiran yang lentur permainan di sini,
kerana anda, jenis, perlu ingat di mana anda berada di dalam cerita,
tetapi pada akhir hari, diberikan apa-apa bilangan elemen,
anda mula-mula mahu menyusun separuh kiri, kemudian separuh yang betul,
kemudian menggabungkan mereka bersama-sama.
Mari kita mulakan untuk melakukan perkara tersebut.
Berikut adalah input daripada lapan elemen.
Sekarang kita sedang melihat separuh kiri di sini.
Bagaimana saya menyusun empat elemen?
Well, saya pertama menyusun separuh kiri.
Sekarang bagaimana saya menyusun separuh kiri?
Well, saya telah diberi dua elemen.
Jadi mari kita menyelesaikan kedua-dua elemen.
2 adalah lebih besar atau sama dengan 2, sudah tentu.
Supaya kes pertama tidak terpakai.
>> Oleh itu, saya kini mempunyai untuk menyelesaikan kiri separuh daripada dua unsur.
Separuh kiri, sudah tentu, adalah hanya 4.
Jadi bagaimana saya menyusun senarai satu elemen?
Sekarang, yang kes asas khas sehingga atas, boleh dikatakan, terpakai.
1 adalah kurang daripada 2, dan saya senarai memang saiz 1.
Jadi saya hanya kembali.
Saya tidak melakukan apa-apa.
Dan sesungguhnya, melihat apa yang saya telah dilakukan, 4 sudah disusun.
Seperti saya sudah sebahagiannya berjaya di sini.
>> Sekarang seolah-olah jenis bodoh untuk menuntut, tetapi ia adalah benar.
4 adalah senarai saiz 1.
Ia sudah disusun.
Itulah separuh kiri.
Sekarang saya menyusun separuh betul.
Input saya adalah salah satu elemen, 8 begitu juga, sudah disusun.
Bodoh, juga, tetapi sekali lagi, prinsip asas ini
akan membolehkan kita kini membina di atas ini dengan jayanya.
4 disusun, 8 disusun, kini apakah langkah terakhir?
Jadi langkah ketiga dan terakhir, apa-apa kali anda menyusun senarai, ingat,
adalah untuk menggabungkan kedua-dua bahagian, kiri dan kanan.
Jadi mari kita melakukan perkara tersebut.
Separuh kiri saya adalah, sudah tentu, 4.
Separuh betul saya ialah 8.
>> Jadi mari kita buat ini.
Pertama saya akan memperuntukkan beberapa memori tambahan,
bahawa saya akan mewakili sini, sebagai hanya pelbagai menengah,
itu sudah cukup besar untuk memuatkan ini.
Tetapi anda boleh bayangkan melanjutkan yang segi empat panjang keseluruhan,
jika memerlukan lebih banyak kemudian.
Bagaimana saya mengambil 4 dan 8, dan bergabung kedua-dua senarai saiz 1 bersama-sama?
Di sini juga, agak mudah.
4 diutamakan, kemudian datang 8.
Kerana jika saya ingin menyusun separuh kiri, kemudian separuh yang betul,
dan kemudian menggabungkan kedua-dua bahagian bersama-sama, untuk disusun,
4 diutamakan, kemudian datang 8.
>> Oleh itu, kita seolah-olah membuat kemajuan, walaupun walaupun saya tidak melakukan apa-apa kerja yang sebenar.
Tetapi ingat di mana kita berada dalam cerita.
Kami asalnya mengambil lapan elemen.
Kami disusun separuh kiri, yang 4.
Kemudian kami disusun separuh kiri separuh kiri, iaitu 2.
Dan di sini kita pergi.
Kita sudah selesai dengan langkah itu.
>> Jadi, jika kita telah disusun yang separuh daripada 2 kiri, sekarang kita
perlu menyelesaikan separuh kanan 2.
Jadi separuh kanan 2 adalah kedua-dua nilai di sini, 6 dan 2.
Jadi mari kita kini mengambil input saiz 2, dan menyusun separuh kiri, dan kemudian
separuh yang betul, dan kemudian menggabungkan mereka bersama-sama.
Nah bagaimana saya menyusun senarai saiz 1, yang mengandungi hanya nombor 6?
Saya sudah selesai.
Itu senarai saiz 1 disusun.
>> Bagaimana saya menyusun lain senarai saiz 1, separuh kanan kononnya.
Dan ia juga sudah disusun.
Bilangan 2 adalah semata-mata.
Jadi sekarang saya mempunyai dua bahagian, kiri dan betul, saya perlu menggabungkan mereka bersama-sama.
Izinkan saya memberikan diri saya sedikit ruang tambahan.
Dan dimasukkan ke 2 di sana, kemudian 6 di sana, dengan itu
menyusun senarai itu, kiri dan kanan, dan penggabungan bersama-sama, akhirnya.
Oleh itu, saya dalam keadaan yang lebih baik sedikit.
Saya tidak dilakukan, kerana jelas 4, 8, 2, 6 tidak pesanan terakhir yang saya mahu.
Tetapi saya kini mempunyai dua senarai saiz 2, yang telah kedua-duanya, masing-masing, telah disusun.
Jadi sekarang jika anda putar balik dalam fikiran anda mata, di mana yang yang meninggalkan kami?
Saya bermula dengan lapan elemen, maka saya dikecutkan ia ke separuh kiri 4,
kemudian separuh kiri 2, dan kemudian separuh kanan 2,
Saya selesai, oleh itu, menyusun kiri separuh daripada 2, dan separuh kanan 2,
jadi apa langkah ketiga dan terakhir di sini?
Saya mempunyai untuk bergabung bersama-sama dua senarai saiz 2.
Oleh itu, marilah kita pergi ke hadapan.
Dan pada skrin di sini, memberi saya beberapa memori tambahan,
walaupun secara teknikal, notis bahawa saya telah mendapat sejumlah besar ruang kosong sehingga bahagian
sana.
Jika saya mahu menjadi sangat ruang yang cekap bijak,
Saya hanya boleh mula bergerak unsur-unsur dan ke belakang, atas dan bawah.
Tetapi hanya untuk kejelasan visual, Saya akan meletakkan ia ke bawah di bawah,
untuk menjaga perkara yang baik dan bersih.
>> Jadi saya telah mendapat dua senarai saiz 2.
Senarai pertama mempunyai 4 dan 8.
Senarai kedua mempunyai 2 dan 6.
Mari bergabung mereka bersama-sama untuk disusun.
2, sudah tentu, yang terdahulu, kemudian 4, kemudian 6, maka 8.
Dan sekarang kita seolah-olah mendapat di suatu tempat yang menarik.
Separuh Sekarang saya telah disusun daripada senarai, dan secara kebetulan, ia adalah
semua nombor genap, tetapi itu adalah, sememangnya, hanya kebetulan.
Dan saya kini telah disusun kiri separuh, supaya ia 2, 4, 6, dan 8.
Tiada apa-apa yang keluar perintah.
Yang berasa seperti kemajuan.
>> Kini ia berasa seperti saya telah telah bercakap selama-lamanya kini,
jadi apa yang masih belum dapat dilihat jika ini algoritma adalah, sememangnya, lebih cekap.
Tetapi kita akan melalui ia sangat teratur.
Komputer, sudah tentu, akan melakukannya seperti itu.
Jadi di mana kita?
Kami bermula dengan lapan elemen.
Saya disusun separuh kiri 4.
Saya seolah-olah dilakukan dengan itu.
Oleh sebab itu langkah seterusnya adalah untuk menyusun separuh kanan 4.
Dan bahagian ini kita boleh pergi melalui lebih sedikit
dengan cepat, walaupun anda selamat datang ke putar balik atau berhenti seketika, hanya
berfikir melaluinya di kelajuan anda sendiri, tetapi apa yang
kita ada sekarang adalah satu peluang untuk melakukan algoritma yang tepat sama kepada empat
nombor yang berlainan.
>> Jadi mari kita pergi ke hadapan, dan menumpukan kepada separuh yang betul, yang kita berada di sini.
Separuh kiri yang separuh betul, dan kini
separuh kiri kiri separuh daripada separuh hak itu,
dan bagaimana saya menyusun senarai saiz 1 yang mengandungi hanya nombor 1?
Ia sudah selesai.
Bagaimana saya melakukan perkara yang sama untuk senarai saiz 1 mengandungi hanya 7?
Ia sudah selesai.
Langkah tiga setengah ini maka adalah untuk menggabungkan kedua-dua elemen
ke dalam satu senarai baru saiz 2, 1 dan 7.
Seolah-olah tidak melakukan semua kerja yang menarik yang banyak.
Mari kita lihat apa yang berlaku seterusnya.
Saya hanya disusun separuh kiri separuh betul input asal saya.
Sekarang mari kita menyusun kanan separuh, yang mengandungi 5 dan 3.
Mari kita sekali lagi melihat kiri separuh, disusun, separuh betul, disusun,
dan bergabung kedua-dua bersama-sama, ke dalam beberapa ruang tambahan,
3 diutamakan, kemudian datang 5.
Dan sehingga kini, kami telah disusun yang separuh kiri separuh kanan
masalah asal, dan separuh kanan separuh kanan
masalah asal.
Apakah Langkah ketiga dan terakhir?
Yang baik untuk menggabungkan kedua-dua bahagian sekali.
Jadi biarlah saya mendapatkan diri beberapa ruang tambahan, tetapi, sekali lagi, saya
boleh menggunakan ruang sehingga lapang atas.
Tetapi kita akan terus ia mudah secara visual.
Biar saya bergabung dalam sekarang 1, dan kemudian 3, dan kemudian 5, dan kemudian 7.
Dengan itu meninggalkan saya sekarang dengan separuh kanan masalah asal
yang yang sempurna disusun.
>> Jadi apa yang tinggal?
Saya rasa seperti saya terus mengatakan perkara yang sama sekali lagi, dan sekali lagi,
tetapi itu mencerminkan Hakikat bahawa kita menggunakan rekursi.
Proses menggunakan algoritma lagi, dan sekali lagi,
pada subset yang lebih kecil masalah asal.
Jadi saya kini telah kiri yang disusun separuh daripada masalah asal.
Saya mempunyai separuh disusun hak masalah asal.
Apakah langkah ketiga dan terakhir?
Oh, ia bergabung.
Jadi mari kita buat itu.
Mari kita memperuntukkan beberapa tambahan memori, tetapi tuhan saya, kami
boleh meletakkan mana-mana sahaja sekarang.
Kami mempunyai ruang yang begitu banyak boleh didapati kepada kami, tetapi kami akan memastikan ia mudah.
Daripada pergi ke belakang dan sebagainya dengan memori asal kami,
mari kita hanya melakukannya visual turun di sini di bawah,
selesaikan menggabungkan separuh kiri dan separuh betul.
>> Jadi dengan menggabungkan, apa yang perlu saya lakukan?
Saya ingin mengambil unsur-unsur yang teratur.
Jadi melihat separuh kiri, Saya melihat nombor pertama adalah 2.
Saya melihat separuh yang betul, Saya melihat nombor pertama
adalah 1, jadi jelas yang nombor yang saya mahu untuk cabut,
dan meletakkan pertama dalam senarai terakhir saya?
Sudah tentu, 1.
Sekarang saya ingin bertanya soalan yang sama.
Pada separuh kiri, saya telah masih mendapat nombor 2.
Pada separuh yang betul, Saya telah mendapat nombor 3.
Yang mana satu yang saya mahu untuk memilih?
Sudah tentu, nombor 2 kini melihat calon-calon
4 di sebelah kiri, 3 di sebelah kanan.
Mari kita, sudah tentu, pilih 3.
Sekarang calon 4 pada kiri, 5 di sebelah kanan.
Kami, sudah tentu, memilih 4.
6 di sebelah kiri, 5 di sebelah kanan.
Kami, sudah tentu, memilih 5.
6 di sebelah kiri, 7 di sebelah kanan.
Kami memilih 6, dan kemudian kita pilih 7, dan kemudian kita memilih 8.
Voila.
>> Jadi besar kata-kata kemudian, kami telah disusun senarai ini lapan elemen
ke dalam senarai satu melalui lapan, yang yang semakin meningkat dengan setiap langkah,
tetapi berapa banyak masa melakukan ia membawa kita untuk berbuat demikian.
Well, saya telah sengaja perkara yang dibentangkan di bergambar
di sini, supaya kita boleh jenis melihat atau menghargai bahagian ini
dalam penaklukan yang sudah berlaku.
>> Malah jika anda melihat kembali bangun, Saya telah meninggalkan semua ini garisan bertitik
dalam pemegang tempat, anda boleh, jenis, lihat, secara terbalik,
jika anda jenis melihat kembali dalam Sejarah kini, senarai asal saya
adalah, sudah tentu, saiz 8.
Dan kemudian sebelum ini, saya berhadapan dengan dua senarai saiz 4,
dan kemudian empat senarai saiz 2, dan kemudian lapan senarai saiz 1.
>> Jadi apakah ini, jenis, mengingatkan anda?
Well, memang, mana-mana algoritma kami telah
melihat setakat mana kita jurang, dan bahagi, dan bahagi,
menyimpan mempunyai perkara-perkara lagi, dan sekali lagi, menyebabkan ini idea umum.
Dan supaya ada sesuatu logaritma berlaku di sini.
Dan ia tidak cukup log n, tetapi ada komponen logaritma
dengan apa yang kita baru sahaja selesai.
>> Sekarang mari kita memikirkan bagaimana yang sebenarnya.
Jadi log n, lagi adalah masa berjalan yang hebat,
apabila kita melakukan sesuatu seperti carian binari, seperti yang kita memanggilnya,
membahagi dan menakluk strategi yang melalui yang kami dapati Mike Smith.
Sekarang dari segi teknikal.
Itulah log asas 2 n, walaupun walaupun dalam kelas matematik yang paling,
10 biasanya asas yang mengambil alih.
Tetapi ahli-ahli sains komputer hampir selalu berfikir dan bercakap dari segi asas 2,
supaya kita biasanya hanya mengatakan log n, bukannya log asas 2 n,
tetapi ia sebenarnya satu dan sama dalam dunia komputer
sains, dan sebagai diketepikan, ada faktor yang tetap
Perbezaan antara kedua-dua, maka ia adalah mengusulkan pula, lebih sebab-sebab rasmi.
>> Tetapi buat masa ini, apa yang kita mengambil berat tentang adalah contoh ini.
Jadi mari kita tidak membuktikan melalui teladan, tetapi pada kurangnya menggunakan satu contoh nombor
di tangan sebagai cek kewarasan, jika anda akan.
Jadi sebelum formula adalah asas log 2 n, tetapi apa yang n dalam kes ini.
Saya mempunyai nombor n asal, atau 8 bilangan asal secara khusus.
Kini ia telah sedikit manakala, tetapi saya cukup
memastikan bahawa log asas 2 daripada nilai 8 adalah 3,
dan sesungguhnya, apa yang baik tentang yang bahawa 3 adalah betul-betul beberapa kali
bahawa anda boleh membahagikan senarai panjang 8 lagi, dan sekali lagi,
dan lagi, sehingga anda meninggalkan dengan senarai hanya saiz 1.
Betul?
8 pergi ke 4, pergi ke 2, pergi ke 1, dan itulah
reflektif yang betul-betul gambar kita baru sahaja sebentar tadi.
Jadi kewarasan sedikit menyemak ke mana logaritma sebenarnya terlibat.
>> Oleh sebab itu, apa lagi yang terlibat di sini? n.
Jadi notis bahawa setiap kali saya berpecah senarai,
walaupun secara terbalik dalam sejarah di sini, saya masih melakukan n sesuatu.
Langkah penggabungan mewajibkan Saya menyentuh setiap satu daripada nombor,
untuk masukkan ke dalam lokasi yang sesuai.
Jadi, walaupun ketinggian ini rajah adalah saiz log n n atau 3,
secara khusus, dengan kata lain, Saya melakukan tiga bahagian di sini.
Berapa banyak kerja yang saya buat secara mendatar bersama-sama carta ini setiap masa?
>> Well, saya lakukan n langkah-langkah bekerja, kerana jika saya telah
ada empat unsur-unsur dan empat elemen, dan saya perlu menggabungkan mereka bersama-sama.
Saya perlu melalui empat dan empat,
akhirnya untuk menggabungkan mereka kembali ke dalam lapan elemen.
Jika sebaliknya saya telah mendapat lapan jari di sini, yang saya tidak lakukan, dan lapan
fingers-- sorry-- Jika saya telah mendapat empat jari di sini,
yang saya lakukan, empat jari di sini, yang saya lakukan,
maka itulah yang sama contohnya seperti sebelum ini, jika saya lakukan
mempunyai lapan jari walaupun dalam jumlah, yang saya boleh, jenis, lakukan.
Saya betul-betul boleh lakukan di sini, maka saya boleh pasti
menggabungkan semua senarai ini saiz 1 bersama-sama.
Tetapi saya pasti perlu melihat di setiap elemen hanya sekali.
Jadi ketinggian proses ini adalah log n, lebar proses ini, boleh dikatakan,
adalah n, jadi apa yang kita seolah-olah untuk mempunyai, akhirnya, adalah
masa berjalan bersaiz n kali log n.
>> Dalam erti kata lain, kami dibahagikan senarai, log n kali,
tetapi setiap kali kita lakukan itu, kita mempunyai menyentuh setiap satu daripada unsur-unsur
untuk menggabungkan mereka semua bersama-sama, yang
telah bila n langkah, jadi kita perlu n kali log n, atau sebagai seorang saintis komputer akan berkata,
asimptot, yang adalah perkataan besar
untuk menggambarkan atas terikat pada masa yang berjalan,
kita berjalan dalam o besar log n masa, jadi untuk bercakap.
>> Sekarang ini adalah penting, kerana ingat apa yang masa berjalan adalah
dengan seperti gelembung, dan pemilihan jenis, dan sisipan jenis,
dan juga beberapa orang lain yang wujud, n kuasa adalah di mana kita berada di.
Dan anda boleh, jenis, lihat ini di sini.
Jika n kuasa jelas n kali n, tetapi di sini kita mempunyai n kali log n,
dan kita sudah tahu dari minggu sifar, bahawa log n, logaritma,
adalah lebih baik daripada sesuatu yang linear.
Lagipun, masih ingat gambar dengan merah dan kuning
dan garis hijau yang kita menarik, yang garis logaritma hijau adalah lebih rendah.
Oleh itu, lebih baik dan lebih cepat daripada garisan kuning dan merah,
n kali log n iaitu, sesungguhnya lebih baik, daripada n kali n, atau n kuasa dua.
>> Oleh itu, kita seolah-olah mempunyai mengenal pasti merge algoritma
jenis yang berjalan di banyak masa yang lebih pantas, dan sesungguhnya,
itulah sebabnya, awal minggu ini, apabila kita lihat pertandingan yang antara gelembung
jenis, jenis pemilihan, dan menggabungkan jenis, bergabung jenis benar-benar, benar-benar menang.
Dan sesungguhnya kami tidak menunggu untuk jenis gelembung dan jenis pemilihan
untuk menamatkan.
>> Sekarang mari kita satu laluan lain pada ini, daripada yang lebih sedikit
perspektif formal, hanya dalam kes, ini bergema lebih baik
daripada perbincangan peringkat yang lebih tinggi.
Jadi di sini adalah algoritma lagi.
Mari kita bertanya kepada diri sendiri, apa masa yang berjalan
adalah ini algoritma pelbagai langkah?
Mari kita berkongsi pengalaman menjadi yang pertama kes dan kes kedua.
IF dan ELSE Dalam kes IF, JIKA n adalah kurang daripada 2, hanya kembali.
Terasa seperti masa yang berterusan.
Ia, jenis, seperti dua langkah, JIKA n adalah kurang daripada 2, akan terus pulang.
Tetapi seperti yang kita katakan pada hari Isnin, masa yang berterusan, atau besar o 1,
boleh dua langkah, tiga langkah-langkah, walaupun 1000 langkah.
Apa yang penting ialah bahawa itu angka tetap langkah.
Jadi kuning yang diserlahkan pseudokod di sini berharga, kami akan memanggilnya,
masa yang berterusan.
Jadi lebih secara rasmi, dan kita akan supaya- ini
akan sejauh mana kita merasmikan hak ini sekarang-- T n,
masa berjalan masalah yang mengambil n somethings sebagai input,
sama besar o satu, JIKA n adalah kurang daripada 2.
Jadi ia adalah bersyarat pada itu.
Jadi untuk menjadi jelas, JIKA n adalah kurang daripada 2, kami mempunyai senarai yang sangat pendek, maka
masa berjalan, T n, di mana n adalah 1 atau 0, dalam kes ini sangat khusus,
ia hanya akan menjadi masa yang berterusan.
Ia akan mengambil satu melangkah, dua langkah, apa sahaja.
Ia adalah nombor tetap langkah.
>> Jadi bahagian berair pasti mesti dalam kes yang lain dalam pseudokod.
Kes ELSE.
Susun separuh kiri elemen, jenis hak separuh daripada unsur-unsur, bergabung bahagian disusun.
Berapa lama setiap langkah-langkah diambil?
Nah, jika berjalan masa untuk menyelesaikan n unsur
adalah, mari kita memanggilnya sangat secara umum, T n,
kemudian menyusun kiri separuh daripada unsur-unsur
adalah, jenis, seperti mengatakan, T n dibahagikan dengan 2,
dan begitu juga menyusun separuh kanan unsur-unsur adalah, jenis, seperti mengatakan,
T n dibahagikan 2, dan kemudian menggabungkan bahagian disusun.
Baik jika saya telah mendapat beberapa beberapa elemen sini,
seperti empat dan beberapa nombor unsur-unsur di sini, seperti empat,
dan saya perlu menggabungkan setiap satu daripada empat dalam, dan masing-masing empat, satu
selepas yang lain, supaya akhirnya saya mempunyai lapan elemen.
Rasanya seperti itulah besar o n langkah?
Jika saya ada n jari dan setiap mereka perlu digabungkan ke dalam tempat,
itu seperti yang lain n langkah.
>> Maka sesungguhnya formulaically, kita boleh menyatakan ini,
walaupun yang Scarily sedikit pada mulanya pandang, tetapi ia adalah sesuatu yang
yang menangkap tepat logik itu.
Masa berjalan, T n, JIKA n adalah lebih besar daripada atau sama dengan 2.
Dalam kes ini, kes ELSE, adalah T n dibahagikan dengan 2, ditambah T N dibahagikan dengan 2,
tambah besar o n, beberapa nombor linear langkah,
mungkin betul-betul n, mungkin 2 kali n, tetapi ia adalah secara kasar, tertib n.
Supaya, juga, adalah bagaimana kita boleh daftar ini formulaically.
Sekarang anda tidak akan tahu ini melainkan anda telah merakamkannya dalam fikiran anda,
atau melihat ia dalam belakang buku teks, yang
mungkin mempunyai sedikit menipu kunci pada akhirnya,
tetapi ini, sesungguhnya, akan memberikan kita besar o n log n,
kerana berulang yang anda lihat di sini pada skrin,
jika anda benar-benar yang berlaku di luar, dengan nombor terhingga contoh,
atau kamu lakukan formulaically, anda akan melihat bahawa ini, kerana formula ini
sendiri adalah rekursi, dengan t n atas sesuatu di sebelah kanan,
dan t bila n lebih di sebelah kiri, ini boleh sebenarnya dinyatakan, akhirnya,
go sebesar n log n.
Jika tidak yakin, itu denda untuk sekarang, hanya
mengambil iman, yang itu, sesungguhnya, apa yang berulang yang membawa kepada,
tetapi ini adalah hanya sedikit lebih daripada satu pendekatan matematik untuk mencari
pada masa yang berjalan merge berdasarkan kod pseudo saja.
>> Sekarang mari kita sedikit seketika dari semua itu,
dan mengambil lihat pada bekas senator tertentu, yang
mungkin kelihatan biasa sedikit, yang duduk dengan Eric Google
Schmidt, sedikit masa lalu, untuk temuduga di atas pentas, di hadapan sejumlah
orang, bercakap tentang akhirnya topik, yang cukup kini biasa.
Mari kita lihat.
>> Eric Schmidt: Sekarang Senator, anda di sini di Google,
dan saya suka untuk berfikir Presiden sebagai temu duga kerja.
Sekarang ia sukar untuk mendapatkan pekerjaan sebagai presiden.
PRESIDEN OBAMA: Betul.
Eric Schmidt: Dan anda akan melakukan [didengar] sekarang.
Ia juga sukar untuk mendapatkan pekerjaan di Google.
PRESIDEN OBAMA: Betul.
>> Eric Schmidt: Kami mempunyai soalan, dan kami meminta calon soalan kami,
dan yang satu ini adalah dari Larry Schwimmer.
>> PRESIDEN Belong: OK.
>> Eric Schmidt: Apa?
Kalian fikir saya bergurau?
Ia adalah di sini.
Apakah cara yang paling berkesan untuk menyusun satu juta 32 bit integer?
>> PRESIDEN Belong: Well--
Eric Schmidt: Kadang-kadang, mungkin saya minta maaf, maybe--
PRESIDEN Belong: Tidak, tidak, tidak, tidak, tidak, saya think--
Eric Schmidt: Itu bukan kitab itu
PRESIDEN Belong: Saya berfikir, saya rasa gelembung
jenis yang akan menjadi cara yang salah untuk pergi.
Eric Schmidt: Ayuh.
Siapakah yang telah memberitahukan kepadanya?
OKAY.
Saya tidak sains komputer pada--
>> PRESIDEN OBAMA: Kami telah mendapat mata-mata kami di sana.
PROFESOR: Baiklah.
Marilah kita pergi di belakang kita sekarang dunia teori algoritma
dalam analisis asimptot daripadanya, dan kembali kepada beberapa topik
dari minggu sifar dan satu, dan permulaan untuk menghapuskan beberapa roda latihan,
jika anda akan.
Supaya anda benar-benar memahami akhirnya dari bawah ke atas, apa yang
berlaku di bawah hood, apabila anda menulis, menyusun, dan melaksanakan program.
Ingat khususnya, bahawa ini adalah program C yang pertama kita melihat,
, program mudah berkanun pelbagai, secara relatif,
di mana, ia mencetak, Hello World.
Dan ingat bahawa saya berkata, proses kod sumber akan melalui
betul-betul ini.
Anda mengambil kod sumber anda, meluluskan melalui pengkompil, seperti dilafaz,
dan keluar datang kod objek, yang mungkin kelihatan seperti ini, sifar dan satu
bahawa CPU komputer, pusat unit pemprosesan atau otak,
akhirnya memahami.
>> Ia ternyata bahawa itu adalah satu sedikit melampaui batas,
bahawa kami kini dalam kedudukan untuk mengusik selain
untuk memahami apa yang benar-benar telah berlaku di bawah hud
setiap kali anda menjalankan Dilafaz, atau lebih umum,
setiap kali anda membuat program, menggunakan Membuat dan CF 50 IDE.
Khususnya, barangan seperti ini buat kali pertama,
apabila anda mula-mula menyusun program anda.
Dalam erti kata lain, apabila anda mengambil kod sumber anda
dan menyusun, apa yang pertama sedang outputted oleh dilafaz
adalah sesuatu yang dikenali sebagai kod pemasangan.
Dan sebenarnya, ia kelihatan betul-betul seperti ini.
>> Saya berlari arahan di baris arahan sebelum ini.
Hello.c dilafaz modal dash s, dan ini menjadi satu fail
bagi saya dipanggil hello.s, di dalam yang betul-betul
kandungan ini, dan lebih sedikit di atas dan sedikit lagi di bawah,
tetapi saya telah meletakkan juiciest maklumat di sini pada skrin.
Dan jika anda melihat dengan teliti, anda akan melihat sekurang-kurangnya beberapa kata kunci biasa.
Kami mempunyai utama di atas.
Kami printf turun di tengah-tengah.
Dan kami juga mempunyai hello dunia garis miring balik n dalam petikan turun di bawah.
>> Dan segala-galanya di sini adalah arahan tahap yang sangat rendah
bahawa CPU komputer memahami.
Arahan CPU yang bergerak memori sekitar, bahawa rentetan beban dari ingatan,
dan akhirnya, cetak perkara yang pada skrin.
Sekarang apa yang berlaku walaupun selepas kod perhimpunan ini dihasilkan?
Akhirnya, anda lakukan, sesungguhnya, masih menjana kod objek.
Tetapi langkah-langkah yang telah benar-benar telah berlaku di bawah hud
melihat lebih kecil seperti ini.
Kod sumber menjadi kod perhimpunan, yang kemudiannya menjadi kod objek,
dan perkataan pembedahan tersebut adalah, apabila anda menyusun kod sumber anda,
keluar datang kod pemasangan, dan kemudian apabila anda memasang kod pemasangan anda,
keluar datang kod objek.
>> Sekarang dilafaz adalah super canggih, seperti banyak penyusun,
dan ia semua langkah-langkah bersama-sama, dan ia tidak semestinya
mengeluarkan apa-apa perantaraan fail yang anda juga boleh melihat.
Ia hanya menyusun perkara-perkara, yang merupakan istilah umum yang
menerangkan keseluruhan proses ini.
Tetapi jika anda benar-benar mahu menjadi tertentu, ada
lebih banyak berlaku di sana juga.
>> Tetapi mari kita juga mempertimbangkan sekarang bahawa walaupun bahawa program super mudah, hello.c,
dipanggil fungsi.
Ia dipanggil printf.
Tetapi saya tidak menulis printf, sesungguhnya, yang datang dengan c, jadi untuk bercakap.
Ia adalah satu panggilan semula fungsi itu diisytiharkan dalam io.h standard, yang
Fail header, yang adalah topik yang kami akan benar-benar
menyelam ke dalam lebih mendalam tidak lama lagi.
Tetapi fail header adalah biasanya disertai
oleh fail kod, sumber fail kod, jadi sama seperti wujud io.h. standard
>> Satu ketika dulu, seseorang, atau someones, juga menulis
fail yang dipanggil io.c standard, dalam mana definisi sebenar,
atau perlaksanaan printf, dan tandan fungsi lain,
sebenarnya bertulis.
Jadi memandangkan, jika kita mempertimbangkan mempunyai di sini di sebelah kiri, hello.c, bahawa apabila
disusun, memberikan kita hello.s, walaupun Dilafaz tidak mengganggu penjimatan di tempat yang
kita dapat melihat, dan bahawa kod pemasangan mendapat dipasang ke hello.o, yang
adalah, sememangnya, nama lalai diberikan setiap kali anda menyusun sumber
memberi kod kepada kod objek, tetapi tidak cukup bersedia untuk melaksanakannya lagi,
kerana langkah lain telah berlaku, dan mempunyai
telah berlaku sejak beberapa lalu minggu, mungkin tanpa pengetahuan anda.
>> Secara khusus di suatu tempat dalam CS50 IDE, dan ini,
juga akan menjadi sedikit yang melampaui batas untuk seketika,
terdapat, atau pernah suatu masa dahulu, fail yang dipanggil io.c standard,
bahawa seseorang yang dikumpulkan ke dalam io.s standard atau yang setara dengannya,
bahawa seseorang kemudian dipasang ke dalam io.o standard,
atau ia ternyata menjadi file sedikit berbeza
format yang boleh memberi yang berbeza memfailkan lanjutan sama sekali,
tetapi dalam teori dan konsep, betul-betul langkah-langkah telah berlaku dalam bentuk tertentu.
Yang mengatakan, yang kini apabila saya menulis program,
hello.c, yang hanya berkata, hello dunia, dan saya menggunakan kod orang lain
seperti printf, yang pada suatu masa, dalam fail yang dipanggil io.c standard,
kemudian entah bagaimana saya perlu mengambil saya kod objek, sifar dan satu saya,
dan objek orang itu kod, atau sifar dan satu,
dan entah bagaimana menghubungkan mereka bersama-sama ke satu fail akhir, dipanggil hello, yang
mempunyai semua sifar dan orang-orang dari fungsi utama saya,
dan semua sifar dan orang-orang untuk printf.
>> Dan sesungguhnya, bahawa proses terakhir ialah dipanggil, menghubungkan kod objek anda.
Yang mana outputnya adalah fail boleh laku.
Jadi dalam keadilan, di akhir hari, tiada apa
telah berubah sejak minggu satu, apabila kita mula menyusun program.
Sesungguhnya, semua ini telah berlaku di bawah hood,
tetapi sekarang kita berada dalam kedudukan yang di mana kita boleh sebenarnya
mengusik selain ini pelbagai langkah.
Dan sesungguhnya, pada akhir hari ini, kami masih
ditinggalkan dengan sifar dan satu, yang sebenarnya adalah Shalawat besar sekarang
yang lain keupayaan C, yang kami telah tidak mempunyai untuk memanfaatkan kemungkinan besar
setakat ini, yang dikenali sebagai pengendali bitwise.
Dengan kata lain, setakat ini, bila-bila masa yang kita ada diuruskan data dalam C atau pembolehubah dalam C,
kita mempunyai perkara-perkara seperti aksara dan terapung dan ins
dan Roh meronta-ronta dan beregu dan seperti itu, tetapi semua mereka adalah sekurang-kurangnya lapan bit.
Kami tidak pernah lagi dapat memanipulasi bit individu,
walaupun bit individu, kami tahu, boleh mewakili 0 dan 1.
Kini ia ternyata bahawa dalam C, anda boleh mendapatkan akses kepada bit individu,
jika anda tahu sintaks, yang boleh digunakan untuk mendapatkan mereka.
>> Jadi mari kita lihat dan pengusaha-pengusaha bitwise.
Jadi digambarkan di sini adalah beberapa simbol yang kami telah, jenis, jenis, dilihat sebelum ini.
Saya melihat Ampersand, satu menegak bar, dan beberapa orang lain juga,
dan ingat bahawa Ampersand Ampersand adalah sesuatu yang kita lihat sebelum ini.
Pengendali logik DAN, di mana anda perlu kedua-dua mereka bersama-sama, atau logik ATAU
operator, di mana anda mempunyai dua bar menegak.
Pengendali Bitwise, yang kita akan melihat beroperasi pada bit secara berasingan,
hanya menggunakan Ampersand tunggal, bar menegak satu, simbol karet
yang akan datang, kecil tilde, dan kemudian meninggalkan
kurung kiri kurungan, atau tanda kurung kanan tanda kurung kanan.
Masing-masing mempunyai makna yang berbeza.
>> Malah, mari kita lihat.
Mari kita pergi sekolah lama hari ini, dan penggunaan skrin sentuh dari tadi,
dikenali sebagai papan putih.
Dan ini papan putih akan membolehkan kita
untuk menyatakan beberapa simbol-simbol yang agak mudah, atau sebaliknya beberapa formula yang agak mudah,
yang kita boleh kemudian akhirnya leverage, untuk
untuk mengakses individu bit dalam program C.
Dalam erti kata lain, mari kita buat ini.
Mari kita bercakap pertama bagi masa kira-kira Ampersand,
yang bitwise DAN operator.
Dalam erti kata lain, ini adalah pengendali yang membolehkan
saya mempunyai pembolehubah kiri tangan biasanya, dan pembolehubah kanan,
atau nilai individu, bahawa jika kita DAN mereka bersama-sama, memberikan saya hasil akhir.
Jadi, apa yang saya maksudkan?
Jika dalam program, anda mempunyai pembolehubah yang menyimpan salah satu daripada nilai-nilai ini,
atau mari kita memastikan ia mudah, dan hanya menulis sifar dan satu secara berasingan,
di sini adalah cara pengendali Ampersand berfungsi.
0 0 Ampersand akan menyamai 0.
Sekarang mengapa?
>> Ia hampir sama dengan Ungkapan Boolean,
yang kita telah dibincangkan setakat ini.
Jika anda rasa selepas semua, 0 adalah palsu, 0 adalah palsu, palsu dan palsu
, seperti yang kita telah dibincangkan secara logik, juga palsu.
Oleh itu, kita mendapat 0 di sini juga.
Jika anda mengambil 0 Ampersand 1, baik itu juga,
akan menjadi 0, kerana bagi ini ungkapan kiri adalah benar atau 1,
ia perlu benar dan benar.
Tetapi di sini kita mempunyai palsu dan benar, atau 0 dan 1.
Kini sekali lagi, jika kita mempunyai 1 Ampersand 0, yang juga akan menjadi 0,
dan jika kita mempunyai 1 Ampersand 1, akhirnya kita mempunyai sedikit 1.
Jadi dalam erti kata lain, kita tidak melakukan apa-apa yang menarik dengan pengendali ini
sahaja lagi, pengendali Ampersand ini.
Ia bitwise DAN operator.
Tetapi ini adalah bahan-bahan melalui yang boleh kita lakukan
perkara yang menarik, kerana kita tidak lama lagi akan melihat.
>> Sekarang mari kita lihat hanya tunggal bar menegak di sini di sebelah kanan.
Jika saya mempunyai bit 0 dan saya ATAU dengan, bitwise
ATAU operator, 0 bit lain, yang akan memberi saya 0.
Jika saya mengambil sedikit 0 dan OR dengan sedikit 1, maka saya akan dapatkan 1.
Dan sebenarnya, hanya untuk kejelasan, biarlah saya kembali,
supaya bar menegak saya tidak disalah anggap sebagai 1.
Biar saya menulis semula semua saya 1 lebih sedikit
jelas, supaya kita berikut lihat, jika saya telah 1 ATAU 0, yang akan menjadi 1,
dan jika saya mempunyai 1 ATAU 1 itu, juga, akan menjadi 1.
Jadi, anda boleh melihat secara logik bahawa ATAU pengendali berkelakuan sangat berbeza.
Ini memberikan saya 0 0 ATAU memberikan saya 0, tetapi setiap gabungan lain memberikan saya 1.
Selagi saya mempunyai satu 1 dalam formula, hasilnya akan menjadi 1.
>> Sebaliknya dengan AND operator, Ampersand,
hanya jika saya mempunyai dua 1. dalam persamaan, adakah saya benar-benar mendapatkan 1 keluar.
Sekarang ada yang lain beberapa Pengendali juga.
Salah seorang daripada mereka adalah sedikit lebih terlibat.
Jadi biarlah saya pergi ke hadapan dan memadamkan ini untuk membebaskan sedikit ruang.
Dan mari kita lihat pada simbol karet, hanya untuk seketika.
Ini biasanya yang watak anda boleh menaip
pada papan kekunci Shift pegangan anda dan kemudian salah satu nombor di atas AS anda
keyboard.
>> Jadi ini adalah eksklusif ATAU operator, eksklusif OR.
Oleh itu, kita hanya melihat operator OR itu.
Ini adalah eksklusif ATAU operator.
Apa sebenarnya perbezaan?
Nah mari kita hanya melihat formula, dan menggunakan ini sebagai bahan akhirnya.
0 XOR 0.
Saya akan katakan adalah sentiasa 0.
Itulah definisi XOR.
0 XOR 1 akan menjadi 1.
1 XOR 0 akan menjadi 1, dan 1 XOR 1 akan menjadi?
Salah?
Atau bukan?
Saya tidak tahu.
0.
Sekarang apa yang sedang berlaku di sini?
Juga berfikir tentang menamakan pengendali ini.
ATAU eksklusif, jadi sebagai nama, jenis, mencadangkan,
jawapannya hanya akan menjadi 1 jika input adalah eksklusif,
semata-mata yang berbeza.
Jadi di sini input adalah sama, maka keluaran adalah 0.
Di sini input adalah sama, maka keluaran adalah 0.
Berikut adalah output yang berbeza, mereka adalah eksklusif, dan keluaran adalah 1.
Jadi ia adalah hampir sama dengan DAN, ia adalah hampir sama,
atau sebaliknya ia hampir sama dengan ATAU, tetapi hanya dengan cara yang eksklusif.
Yang ini tidak lagi menjadi 1, kerana kita mempunyai dua 1-kanak,
dan tidak semata-mata, hanya satu daripada mereka.
Baiklah.
Bagaimana pula dengan yang lain?
Well tilde, sementara itu, adalah sebenarnya yang bagus dan mudah, bersyukur.
Dan ini adalah satu unari pengendali, yang bermaksud
ia digunakan untuk hanya satu input, satu operan, jadi untuk bercakap.
Belum kiri dan kanan.
Dalam erti kata lain, jika anda mengambil tilde daripada 0, jawapannya akan menjadi sebaliknya.
Dan jika anda mengambil tilde daripada 1, jawapan akan ada sebaliknya.
Jadi pengendali tilde adalah satu cara untuk menidakkan sedikit,
atau Melibas sedikit dari 0-1, atau 1-0.
>> Dan yang meninggalkan kita akhirnya dengan hanya dua pengendali akhir,
apa yang dikenali sebagai anjakan kiri, dan apa yang dikenali sebagai pengendali peralihan betul.
Mari kita lihat bagaimana mereka bekerja.
Pengendali shift kiri, bertulis dengan dua tanda kurung sudut seperti itu,
beroperasi seperti berikut.
Jika input saya, atau operan saya, ke kiri pengendali peralihan cukup sekadar 1.
Dan saya kemudian memberitahu komputer untuk anjakan lagi yang 1, berkata tujuh tempat,
hasilnya adalah seolah-olah saya mengambil bahawa 1, dan bergerak
tujuh tempat pula ke dalam kiri, dan secara lalai,
kita akan menganggap bahawa ruang ke kanan
akan dapat empuk dengan sifar.
Dengan kata lain, 1 meninggalkan anjakan 7 akan untuk memberi saya bahawa 1, diikuti dengan 1, 2, 3,
4, 5, 6, 7 sifar.
Jadi dalam erti kata lain, ia membolehkan anda untuk mengambil sebilangan kecil seperti 1,
dan jelas membuat ia lebih banyak, lebih besar dengan cara ini,
tetapi kita sebenarnya akan melihat pendekatan yang lebih bijak untuk itu
sebaliknya, dan juga,
>> Baiklah.
Itu sahaja untuk minggu tiga.
Kita akan lihat masa depan.
Ini adalah CS50.
>> [Bermain muzik]
>> SPEAKER 1: Beliau adalah di snek melarang makan fudge sundae panas.
Beliau mempunyai seluruh muka beliau.
Dia memakai coklat yang seperti janggut
SPEAKER 2: Apa yang anda buat?
SPEAKER 3: Hmmm?
Apa?
>> SPEAKER 2: Adakah anda hanya berenang dua kali?
Anda dua kali turun cip.
SPEAKER 3: Maafkan saya.
SPEAKER 2: Anda dicelup cip, anda mengambil santapan anda, dan anda menurun lagi.
SPEAKER 3:
SPEAKER 2: Jadi itu seperti meletakkan betul mulut semua hak dalam sos.
Lain kali anda mengambil cip, hanya mencelupkannya sekali, dan mengakhirinya.
>> SPEAKER 3: Anda tahu apa, Dan?
Anda mencelupkan cara yang anda mahu jatuh.
Saya akan mencelupkan cara yang saya mahu jatuh.