>> [MUSIC PLAYING]
>> PROFESSOR: Baiklah.
Ini adalah CS50 dan ini akhir minggu tiga.
Jadi kita di sini hari ini, tidak di Sanders Teater, bukan di Weidner Perpustakaan.
Dalam yang studio dikenal sebagai Hauser Studio,
atau harus kami katakan Studio H, atau akan kami say-- jika Anda menikmati lelucon itu,
itu benar-benar dari teman sekelas, Mark, online,
yang menyarankan sebanyak via Twitter.
Sekarang apa yang keren tentang berada di sini di studio
adalah bahwa saya dikelilingi oleh orang-hijau dinding, layar hijau atau chromakey,
sehingga untuk berbicara, yang berarti bahwa CS50 ini tim produksi, tanpa sepengetahuan saya
sekarang, bisa menempatkan saya paling mana saja di dunia,
untuk lebih baik atau buruk.
>> Sekarang apa yang ada di depan, masalah ditetapkan dua adalah di tangan Anda untuk minggu ini,
tetapi dengan masalah mengatur tiga minggu mendatang,
Anda akan ditantang dengan yang disebut permainan 15,
sebuah nikmat partai lama yang Anda mungkin ingat menerima
sebagai anak yang memiliki seluruh banyak angka yang bisa geser ke atas, ke bawah,
kiri dan kanan, dan ada satu celah dalam teka-teki, di mana Anda
benar-benar dapat geser potongan-potongan teka-teki.
Pada akhirnya Anda menerima ini teka-teki dalam beberapa urutan setengah acak,
dan tujuannya adalah untuk semacam itu, atas ke bawah,
kiri ke kanan, dari satu semua jalan melalui 15.
>> Sayangnya, pelaksanaan Anda akan memiliki di tangan
akan menjadi perangkat lunak berdasarkan, tidak secara fisik.
Anda benar-benar akan harus menulis kode dengan yang diterima oleh siswa atau pengguna dapat
memainkan permainan 15.
Dan pada kenyataannya, di hacker edisi permainan 15,
Anda akan menjadi tantangan untuk melaksanakan, bukan hanya bermain sekolah tua ini
permainan, melainkan pemecahan yang itu, menerapkan modus dewa,
sehingga untuk berbicara, yang benar-benar memecahkan teka-teki bagi manusia,
dengan menyediakan petunjuk, setelah hint, setelah sedikit.
Jadi lebih pada minggu depan.
Tapi itulah yang ada di depan.
>> Untuk saat ini ingat bahwa awal pekan ini kami memiliki cliffhanger ini, jika Anda mau,
dimana yang terbaik yang kami lakukan pengurutan bijaksana adalah batas atas dari besar o n
kuadrat.
Dengan kata lain, bubble sort, semacam seleksi, insertion sort,
semua dari mereka, sementara yang berbeda dalam implementasinya,
diserahkan ke sebuah n kuadrat berjalan waktu dalam kasus terburuk.
Dan kita umumnya menganggap bahwa kasus yang paling buruk untuk menyortir
adalah salah satu yang Anda masukan benar-benar mundur.
Dan memang, butuh beberapa langkah untuk melaksanakan masing-masing algoritma.
>> Sekarang di akhir kelas ingat, kami membandingkan bubble sort
terhadap pilihan semacam terhadap satu lainnya bahwa kita disebut merge semacam pada saat itu,
dan saya mengusulkan bahwa itu mengambil keuntungan dari pelajaran dari seminggu
nol, membagi dan menaklukkan.
Dan entah bagaimana mencapai beberapa jenis logaritmik waktu berjalan akhirnya,
bukan sesuatu itu murni kuadrat.
Dan itu tidak cukup logaritmik, itu sedikit lebih dari itu.
Tetapi jika Anda ingat dari kelas, itu jauh, jauh lebih cepat.
Mari kita lihat di mana kita tinggalkan.
>> Bubble sort dibandingkan pilihan semacam vs merge sort.
Sekarang mereka semua berjalan, di teori, pada saat yang sama.
CPU berjalan pada kecepatan yang sama.
Tapi Anda bisa merasakan bagaimana membosankan ini sangat cepat akan menjadi,
dan hanya seberapa cepat, ketika kita menyuntikkan sedikit algoritma minggu nol ini,
bisa kita mempercepat.
>> Jadi tanda semacam tampak luar biasa.
Bagaimana kita bisa memanfaatkan itu, dalam rangka untuk mengurutkan nomor lebih cepat.
Nah mari kita berpikir kembali untuk bahan yang kami
memiliki kembali minggu nol, yang dari mencari seseorang di buku telepon,
dan ingat bahwa pseudocode yang kita diusulkan,
melalui mana kita dapat menemukan seseorang seperti Mike Smith,
tampak sedikit sesuatu seperti ini.
>> Sekarang kita lihat pada khususnya pada baris 7 dan 8, dan 10 dan 11,
yang menginduksi lingkaran itu, dimana kami terus akan kembali ke jalur 3 lagi, dan lagi,
dan lagi.
Tapi ternyata bahwa kita dapat melihat algoritma ini, di sini di pseudocode,
sedikit lebih holistik.
Bahkan, apa yang saya cari di sini di layar,
adalah algoritma untuk mencari Mike Smith antara beberapa set halaman.
Dan memang, kita bisa menyederhanakan ini algoritma dalam garis 7 dan 8,
dan 10 dan 11 untuk hanya mengatakan ini, yang saya sudah disajikan di sini dalam kuning.
Dengan kata lain, jika Mike Smith adalah awal dalam buku ini,
kita tidak perlu menentukan langkah demi langkah sekarang bagaimana untuk pergi menemukannya.
Kami tidak harus menentukan kembali ke jalur 3,
kenapa tidak kita hanya sebaliknya, mengatakan, lebih umum,
mencari Mike di kiri setengah dari buku ini.
>> Sebaliknya, jika Mike adalah sebenarnya nanti dalam buku ini,
kenapa tidak kita hanya mengutip pencarian tanda kutip untuk Mike di bagian kanan buku.
Dengan kata lain, kenapa tidak kita hanya semacam menyepak bola untuk diri kita sendiri mengatakan,
mencari Mike dalam bagian dari buku,
dan menyerahkan kepada kami yang ada algoritma untuk memberitahu kami
bagaimana mencari Mike di yang kiri setengah dari buku ini.
Dengan kata lain, kami algoritma bekerja apakah itu
buku telepon ketebalan ini, ini ketebalan, atau ketebalan apapun.
Jadi kita bisa rekursif mendefinisikan algoritma ini.
Dengan kata lain, pada layar di sini, adalah sebuah algoritma
untuk mencari Mike Smith antara halaman buku telepon.
Jadi sejalan 7 dan 10, mari kita hanya mengatakan hal itu.
Dan saya menggunakan istilah ini sejenak lalu, dan memang, rekursi
adalah kata kunci untuk saat ini, dan itu proses ini
melakukan sesuatu siklus oleh entah bagaimana menggunakan kode yang sudah Anda miliki,
dan menyebutnya lagi, dan lagi, dan lagi.
Sekarang itu akan menjadi penting bahwa kita entah bagaimana bawah
keluar, dan tidak melakukan itu panjang tak terhingga.
Jika tidak kita akan memiliki memang loop tak terbatas.
Tapi mari kita lihat apakah kita dapat meminjam ide ini rekursi, melakukan sesuatu lagi
dan lagi dan lagi, untuk memecahkan masalah menyortir melalui penggabungan
semacam, semua lebih efisien.
>> Jadi saya memberikan menggabungkan semacam.
Mari lihat.
Jadi di sini adalah pseudocode, dengan yang kita bisa menerapkan pemilahan,
menggunakan algoritma ini disebut merge sort.
Dan itu cukup sederhana ini.
Masukan dari elemen n, dengan kata lain, jika Anda
diberikan n elemen dan angka dan surat atau apapun input,
jika Anda diberi unsur n, jika n kurang dari 2, hanya kembali.
Benar?
Karena jika n kurang dari 2, yang berarti bahwa daftar elemen
adalah salah satu dari ukuran 0 atau 1, dan dalam kedua kasus tersebut sepele,
daftar tersebut sudah diurutkan.
Jika tidak ada daftar, itu diurutkan.
Dan jika ada daftar panjang 1, itu jelas diurutkan.
Jadi algoritma hanya perlu benar-benar melakukan sesuatu yang menarik,
jika kita memiliki dua atau lebih elemen yang diberikan kepada kita.
Jadi mari kita lihat keajaiban kemudian.
Lain menyortir kiri setengah dari unsur-unsur, kemudian mengurutkan kanan setengah dari elemen,
kemudian menggabungkan bagian diurutkan.
Dan apa jenis pikiran membungkuk di sini, adalah bahwa saya tidak benar-benar
tampaknya telah mengatakan kepada Anda apa dulu, kan?
Semua sudah saya katakan adalah, diberikan daftar n elemen, mengurutkan setengah kiri,
maka setengah benar, maka menggabungkan bagian diurutkan,
tetapi di mana adalah saus rahasia yang sebenarnya?
Dimana algoritma?
Nah ternyata dua baris pertama, setengah semacam meninggalkan elemen,
dan hak semacam setengah dari elemen, panggilan rekursif, sehingga untuk berbicara.
>> Setelah semua, ini titik waktu, saya harus
algoritma yang dapat digunakan untuk mengurutkan sejumlah elemen?
Iya nih.
Ada di sini.
Ada di sini di layar, dan jadi saya bisa menggunakan set yang sama langkah
memilah kiri setengah, yang saya bisa kanan setengah.
Dan memang, lagi, dan lagi.
Jadi entah bagaimana, dan kami akan segera melihat ini, keajaiban semacam penggabungan
tertanam dalam sangat akhir line, menggabungkan bagian diurutkan.
Dan yang tampaknya cukup intuitif.
Anda mengambil dua bagian, dan Anda, entah bagaimana, menggabungkan mereka bersama-sama,
dan kami akan melihat ini konkret dalam sekejap.
>> Tapi ini adalah algoritma lengkap.
Dan mari kita lihat persis mengapa.
Nah misalkan kita diberi ini sama delapan elemen di sini di layar, satu
melalui delapan, tapi mereka dalam rangka acak.
Dan tujuan di tangan adalah untuk mengurutkan elemen-elemen ini.
Nah bagaimana saya bisa pergi tentang melakukannya menggunakan, lagi,
menggabungkan semacam, sesuai pseudocode ini?
Dan lagi, menanamkan ini di pikiran Anda, untuk sesaat.
Kasus pertama adalah cukup sepele, jika kurang dari 2,
hanya kembali, tidak ada pekerjaan yang harus dilakukan.
Jadi benar-benar hanya ada tiga langkah-langkah untuk benar-benar perlu diingat.
Lagi, dan lagi, aku akan ingin memiliki
memilah kiri setengah, mengurutkan bagian kanan,
dan kemudian sekali mereka dua bagian diurutkan,
Saya ingin menggabungkan mereka bersama-sama menjadi satu daftar diurutkan.
Jadi ingatlah bahwa dalam pikiran.
>> Jadi, inilah daftar asli.
Mari kita memperlakukan ini sebagai array, seperti yang kita mulai
di minggu kedua, yang merupakan blok memori yang berdekatan.
Dalam hal ini, berisi delapan angka, kembali ke belakang ke belakang.
Dan mari kita sekarang berlaku merge sort.
Jadi saya pertama kali ingin mengurutkan kiri setengah dari daftar ini,
dan mari kita, oleh karena itu, fokus pada 4, 8, 6, dan 2.
>> Sekarang bagaimana aku pergi tentang menyortir daftar ukuran 4?
Yah aku harus sekarang mempertimbangkan menyortir kiri kiri setengah.
Sekali lagi, mari kita mundur untuk sesaat.
Jika pseudocode adalah ini, dan aku diberi delapan elemen,
8 jelas lebih besar dari atau sama dengan 2.
Jadi dengan kasus pertama tidak berlaku.
Jadi untuk mengurutkan delapan elemen, saya pertama kali mengurutkan kiri setengah dari elemen,
maka saya mengurutkan bagian kanan, maka saya menggabungkan dua bagian diurutkan, masing-masing ukuran 4.
OKE.
>> Tetapi jika Anda baru saja mengatakan kepada saya, mengurutkan setengah kiri, yang sekarang ukuran 4,
bagaimana cara mengurutkan setengah kiri?
Nah jika saya memiliki masukan dari empat elemen,
Saya pertama kali mengurutkan kiri dua, maka dua yang benar,
dan kemudian saya menggabungkan mereka bersama-sama.
Jadi sekali lagi, itu menjadi sedikit dari pikiran membungkuk permainan di sini,
karena Anda, jenis, harus ingat di mana Anda berada dalam cerita,
tapi pada akhir hari, diberikan sejumlah elemen,
Anda pertama kali ingin mengurutkan setengah kiri, maka bagian kanan,
kemudian menggabungkan mereka bersama-sama.
Mari kita mulai untuk melakukan hal itu.
Berikut masukan dari delapan elemen.
Sekarang kita sedang melihat kiri setengah di sini.
Bagaimana cara memilah empat elemen?
Yah aku pertama mengurutkan setengah kiri.
Sekarang bagaimana cara mengurutkan setengah kiri?
Yah aku sudah diberi dua elemen.
Jadi mari kita mengurutkan kedua elemen ini.
2 lebih besar dari atau sama dengan 2, tentu saja.
Sehingga kasus pertama tidak berlaku.
>> Jadi saya sekarang harus memilah kiri setengah dari dua elemen tersebut.
Kiri setengah, tentu saja, hanya 4.
Jadi bagaimana cara mengurutkan daftar satu elemen?
Nah sekarang, bahwa kasus dasar khusus di bagian atas, sehingga untuk berbicara, berlaku.
1 kurang dari 2, dan saya Daftar memang ukuran 1.
Jadi aku hanya kembali.
Saya tidak melakukan apa-apa.
Dan memang, melihat apa yang telah saya dilakukan, 4 sudah diurutkan.
Seperti aku sudah sebagian berhasil di sini.
>> Sekarang tampaknya agak bodoh untuk mengklaim, tapi itu benar.
4 adalah daftar ukuran 1.
Ini sudah diurutkan.
Itulah setengah kiri.
Sekarang saya mengurutkan bagian kanan.
Masukan saya adalah salah satu elemen, 8 sama, sudah diurutkan.
Bodoh juga, tapi sekali lagi, Prinsip dasar ini
akan memungkinkan kita untuk membangun sekarang di atas ini berhasil.
4 diurutkan, 8 diurutkan, sekarang apa itu langkah terakhir?
Jadi langkah ketiga dan terakhir, setiap waktu Anda menyortir daftar, recall,
adalah untuk menggabungkan dua bagian, kiri dan kanan.
Jadi mari kita melakukan hal itu.
Setengah kiri saya, tentu saja, 4.
Setengah kanan saya adalah 8.
>> Jadi mari kita lakukan ini.
Pertama aku akan mengalokasikan beberapa memori tambahan,
bahwa saya akan mewakili di sini, hanya sebagai array sekunder,
itu cukup besar untuk muat ini.
Tapi Anda bisa bayangkan memperluas bahwa persegi panjang seluruh panjang,
jika kita membutuhkan lebih banyak nanti.
Bagaimana cara mengambil 4 dan 8, dan menggabungkan kedua daftar ukuran 1 bersama-sama?
Di sini juga, cukup sederhana.
4 datang pertama, kemudian datang 8.
Karena jika saya ingin mengurutkan setengah kiri, maka bagian kanan,
dan kemudian menggabungkan dua bagian bersama-sama, dalam rangka diurutkan,
4 datang pertama, kemudian datang 8.
>> Jadi kita tampaknya akan membuat kemajuan, bahkan meskipun saya tidak melakukan pekerjaan yang sebenarnya.
Tapi ingat di mana kita berada dalam cerita.
Kami awalnya mengambil delapan elemen.
Kami diurutkan setengah kiri, yaitu 4.
Kemudian kita diurutkan kiri setengah dari kiri setengah, yang 2.
Dan di sini kita pergi.
Kita sudah selesai dengan langkah itu.
>> Jadi jika kita sudah diurutkan meninggalkan setengah dari 2, sekarang kita
harus memilah kanan setengah dari 2.
Jadi bagian kanan 2 adalah kedua nilai di sini, 6 dan 2.
Jadi mari kita sekarang mengambil masukan dari ukuran 2, dan mengurutkan setengah kiri, dan kemudian
bagian kanan, dan kemudian menggabungkan mereka bersama-sama.
Nah bagaimana cara mengurutkan daftar ukuran 1, yang berisi hanya nomor 6?
Saya sudah dilakukan.
Daftar yang ukuran 1 diurutkan.
>> Bagaimana cara mengurutkan daftar lain ukuran 1, yang disebut setengah benar.
Baik itu, juga, sudah diurutkan.
Jumlah 2 sendirian.
Jadi sekarang aku punya dua bagian, kiri dan benar, saya perlu untuk menggabungkan mereka bersama-sama.
Biarkan saya memberi diriku beberapa ruang tambahan.
Dan menempatkan 2 di sana, kemudian 6 di sana, sehingga
menyortir daftar itu, kiri dan kanan, dan penggabungan bersama-sama, akhirnya.
Jadi aku dalam kondisi yang sedikit lebih baik.
Aku belum selesai, karena jelas 4, 8, 2, 6 bukanlah memesan terakhir yang saya inginkan.
Tapi saya sekarang memiliki dua daftar ukuran 2, yang memiliki keduanya, masing-masing, telah disortir.
Jadi sekarang jika Anda mundur dalam pikiran Anda mata, mana yang meninggalkan kita?
Saya mulai dengan delapan elemen, maka saya whittled itu ke kiri setengah dari 4,
kemudian kiri setengah dari 2, dan kemudian kanan setengah dari 2,
Aku selesai, oleh karena itu, penyortiran kiri setengah dari 2, dan kanan setengah dari 2,
jadi apa langkah ketiga dan terakhir di sini?
Saya harus bergabung bersama dua daftar ukuran 2.
Jadi mari kita pergi ke depan.
Dan pada layar di sini, memberikan saya beberapa memori tambahan,
meskipun secara teknis, perhatikan bahwa saya telah mendapat sejumlah ruang kosong di bagian atas
ada.
Jika saya ingin menjadi terutama ruang yang efisien bijaksana,
Aku hanya bisa mulai bergerak elemen bolak-balik, atas dan bawah.
Tapi hanya untuk kejelasan visual, Aku akan meletakkannya di bawah ini,
untuk menjaga hal-hal baik dan bersih.
>> Jadi saya punya dua daftar ukuran 2.
Daftar pertama memiliki 4 dan 8.
Daftar kedua memiliki 2 dan 6.
Mari kita gabungkan bersama-sama dalam rangka diurutkan.
2, tentu saja, datang pertama, kemudian 4, kemudian 6, kemudian 8.
Dan sekarang kita tampaknya akan mendapatkan suatu tempat yang menarik.
Sekarang saya sudah diurutkan setengah dari daftar, dan kebetulan, itu
semua angka bahkan, tapi itu adalah, memang, hanya kebetulan.
Dan saya sekarang telah diurutkan kiri setengah, sehingga itu 2, 4, 6, dan 8.
Tidak ada yang rusak.
Yang terasa seperti kemajuan.
>> Sekarang rasanya seperti saya sudah berbicara selamanya sekarang,
jadi apa masih harus dilihat apakah ini algoritma, memang, lebih efisien.
Tapi kita akan melalui super metodis.
Sebuah komputer, tentu saja, akan melakukannya seperti itu.
Jadi di mana kita?
Kami mulai dengan delapan elemen.
Saya diurutkan kiri setengah dari 4.
Saya tampaknya dilakukan dengan itu.
Jadi sekarang langkah berikutnya adalah untuk mengurutkan bagian kanan 4.
Dan bagian ini kita bisa pergi melalui lebih sedikit
cepat, meskipun Anda dipersilahkan untuk mundur atau berhenti, hanya
memikirkan itu pada kecepatan Anda sendiri, tapi apa
kita miliki sekarang adalah kesempatan untuk melakukan algoritma yang sama yang sebenarnya di empat
nomor yang berbeda.
>> Jadi mari kita pergi ke depan, dan fokus pada bagian kanan, yang kita di sini.
Kiri setengah dari yang setengah benar, dan sekarang
kiri setengah dari kiri setengah dari yang setengah benar,
dan bagaimana cara mengurutkan daftar ukuran 1 hanya berisi nomor 1?
Ini sudah dilakukan.
Bagaimana saya melakukan hal yang sama untuk daftar ukuran 1 yang mengandung hanya 7?
Ini sudah dilakukan.
Langkah ketiga untuk setengah ini kemudian adalah untuk menggabungkan dua unsur ini
dalam daftar baru ukuran 2, 1 dan 7.
Jangan tampaknya telah melakukan semua bahwa banyak pekerjaan yang menarik.
Mari kita lihat apa yang terjadi selanjutnya.
Aku hanya diurutkan kiri setengah dari setengah hak masukan asli saya.
Sekarang mari kita mengurutkan kanan setengah, yang berisi 5 dan 3.
Mari kita kembali melihat kiri setengah, diurutkan, setengah benar, diurutkan,
dan menggabungkan dua bersama-sama, ke beberapa ruang tambahan,
3 datang pertama, kemudian datang 5.
Dan sekarang, kami telah diurutkan setengah kiri kanan setengah
dari masalah asli, dan kanan setengah dari kanan setengah
dari masalah asli.
Apa Langkah ketiga dan terakhir?
Nah untuk menggabungkan dua bagian bersama-sama.
Jadi biarkan aku mendapatkan diriku beberapa ruang ekstra, tapi, sekali lagi, saya
bisa menggunakan ruang yang di bagian atas cadangan.
Tapi kami akan terus sederhana visual.
Biarkan saya bergabung dalam 1 sekarang, dan kemudian 3, dan kemudian 5, dan kemudian 7.
Sehingga meninggalkan saya sekarang dengan kanan setengah dari masalah asli
yang sempurna diurutkan.
>> Jadi apa yang tersisa?
Saya merasa seperti saya terus mengatakan hal yang sama lagi, dan lagi,
tapi itu mencerminkan Fakta bahwa kita sedang menggunakan rekursi.
Proses menggunakan algoritma lagi, dan lagi,
pada subset kecil dari masalah asli.
Jadi saya sekarang telah kiri diurutkan setengah dari masalah asli.
Saya memiliki diurutkan setengah benar dari masalah asli.
Apa langkah ketiga dan terakhir?
Oh, itu penggabungan.
Jadi mari kita lakukan itu.
Mari kita mengalokasikan beberapa tambahan memori, tetapi Tuhan, kita
bisa menempatkannya di mana saja sekarang.
Kami memiliki begitu banyak ruang yang tersedia kepada kami, tapi kami akan tetap sederhana.
Alih-alih akan kembali dan balik dengan memori asli kami,
mari kita lakukan saja visual di sini di bawah ini,
untuk menyelesaikan penggabungan setengah kiri dan kanan setengah.
>> Jadi dengan menggabungkan, apa yang harus saya lakukan?
Saya ingin mengambil unsur-unsur dalam rangka.
Jadi melihat kiri setengah, Aku melihat nomor pertama adalah 2.
Aku melihat bagian kanan, Saya melihat angka pertama
adalah 1, jadi jelas yang nomor yang saya ingin mencabut,
dan menempatkan pertama dalam daftar terakhir saya?
Tentu saja, 1.
Sekarang saya ingin menanyakan hal yang sama.
Pada babak kiri, saya sudah masih punya nomor 2.
Pada bagian kanan, Aku punya nomor 3.
Yang mana yang ingin saya pilih?
Tentu saja, nomor 2 dan sekarang melihat calon
4 di sebelah kiri, 3 di sebelah kanan.
Mari kita, tentu saja, memilih 3.
Sekarang calon 4 di kiri, 5 di sebelah kanan.
Kami, tentu saja, pilih 4.
6 di sebelah kiri, 5 di sebelah kanan.
Kami, tentu saja, memilih 5.
6 di sebelah kiri, 7 di sebelah kanan.
Kami memilih 6, dan kemudian kita memilih 7, dan kemudian kita memilih 8.
Voila.
>> Jadi sejumlah besar kata-kata kemudian, kami telah diurutkan daftar ini delapan elemen
dalam daftar satu sampai delapan, yang meningkat dengan setiap langkah,
tapi berapa banyak waktu melakukan itu membawa kita untuk melakukan itu.
Yah aku sudah sengaja hal meletakkan keluar pictorially
di sini, sehingga kita bisa jenis melihat atau menghargai divisi
di menaklukkan yang telah terjadi.
>> Memang jika Anda melihat kembali bangun, Saya sudah meninggalkan semua ini garis putus-putus
di pemegang tempat, Anda bisa, jenis, melihat, dalam urutan terbalik,
jika Anda jenis melihat kembali sejarah sekarang, daftar asli saya
adalah, tentu saja, dari ukuran 8.
Dan kemudian sebelumnya, saya berurusan dengan dua daftar ukuran 4,
dan kemudian empat daftar ukuran 2, dan kemudian delapan daftar ukuran 1.
>> Jadi, apa ini, jenis, mengingatkan Anda tentang?
Nah, memang, salah algoritma kami telah
memandang sejauh mana kita membagi, dan membagi, dan membagi,
tetap memiliki hal lagi, dan lagi, menghasilkan ide umum ini.
Dan jadi ada sesuatu logaritmik yang terjadi di sini.
Dan itu tidak cukup log n, tapi ada komponen logaritmik
apa yang baru saja kita lakukan.
>> Sekarang mari kita mempertimbangkan bagaimana yang sebenarnya.
Jadi log n, lagi adalah waktu berjalan yang besar,
ketika kita melakukan sesuatu seperti pencarian biner, seperti sekarang kita menyebutnya,
membagi dan menaklukkan strategi melalui yang kami menemukan Mike Smith.
Sekarang teknis.
Itu log basis 2 dari n, bahkan meskipun dalam kebanyakan kelas matematika,
10 biasanya dasar yang Anda berasumsi.
Tapi ilmuwan komputer hampir selalu berpikir dan berbicara dalam hal basis 2,
jadi kita umumnya hanya mengatakan log n, bukannya log basis 2 dari n,
tapi mereka tepat satu dan sama dalam dunia komputer
ilmu pengetahuan, dan sebagai samping, ada faktor konstan
Perbedaan antara keduanya, sehingga diperdebatkan pula, untuk alasan yang lebih formal.
>> Tapi untuk saat ini, apa yang kita peduli tentang adalah contoh ini.
Jadi mari kita tidak membuktikan dengan contoh, tetapi pada Setidaknya menggunakan contoh angka
di tangan sebagai cek kewarasan, jika Anda mau.
Jadi sebelumnya rumus adalah log basis 2 dari n, tapi apa n dalam kasus ini.
Aku punya nomor n asli, atau 8 dari nomor asli khusus.
Sekarang ini sudah sedikit sementara, tapi aku cukup
memastikan bahwa log basis 2 dari nilai 8 adalah 3,
dan memang, apa yang baik tentang itu adalah bahwa 3 adalah persis berapa kali
Anda dapat membagi daftar panjang 8 lagi, dan lagi,
dan lagi, sampai Anda meninggalkan dengan daftar hanya ukuran 1.
Benar?
8 pergi ke 4, pergi ke 2, pergi ke 1, dan itulah
reflektif persis yang gambar kami memiliki beberapa saat yang lalu.
Jadi kewarasan sedikit periksa ke mana logaritma sebenarnya terlibat.
>> Jadi sekarang, apa lagi yang terlibat di sini? n.
Jadi perhatikan bahwa setiap waktu aku membagi daftar,
meskipun dalam urutan terbalik dalam sejarah di sini, saya masih melakukan hal-hal n.
Langkah penggabungan diperlukan bahwa Aku menyentuh setiap salah satu nomor,
untuk geser ke lokasi yang sesuai.
Jadi meskipun ketinggian ini diagram adalah ukuran log n dari n atau 3,
khusus, dengan kata lain, Saya melakukan tiga divisi di sini.
Berapa banyak pekerjaan yang saya lakukan secara horizontal bersama grafik ini setiap kali?
>> Yah, aku n langkah bekerja, karena jika saya sudah
punya empat elemen dan empat elemen, dan saya perlu untuk menggabungkan mereka bersama-sama.
Saya perlu melalui empat dan empat ini,
akhirnya untuk menggabungkan mereka kembali menjadi delapan elemen.
Jika sebaliknya aku punya delapan jari di sini, yang tidak saya lakukan, dan delapan
fingers-- sorry-- Jika saya sudah mendapat empat jari di sini,
yang saya lakukan, empat jari di sini, yang saya lakukan,
maka itu sama Misalnya seperti sebelumnya, jika saya lakukan
memiliki delapan jari meskipun dalam total, yang saya dapat, jenis, lakukan.
Aku benar-benar bisa lakukan di sini, maka saya pasti bisa
menggabungkan semua daftar ini ukuran 1 bersama-sama.
Tapi aku pasti harus melihat di setiap elemen tepat satu kali.
Jadi ketinggian proses ini adalah log n, lebar proses ini, sehingga untuk berbicara,
adalah n, sehingga apa yang kita tampaknya untuk memiliki, akhirnya, adalah
waktu berjalan dari ukuran n kali log n.
>> Dengan kata lain, kami membagi daftar, log n kali,
tapi setiap kali kita melakukan itu, kita memiliki menyentuh setiap salah satu elemen
untuk menggabungkan mereka semua bersama-sama, yang
itu n langkah, jadi kita harus n kali log n, atau sebagai seorang ilmuwan komputer akan mengatakan,
asimtotik, yang akan menjadi kata yang besar
untuk menggambarkan atas terikat pada waktu berjalan,
kita berjalan di o besar log n waktu, sehingga untuk berbicara.
>> Sekarang ini penting, karena ingat apa yang kali berjalan yang
dengan bubble sort, dan seleksi macam, dan insertion sort,
dan bahkan beberapa orang lain yang ada, n kuadrat adalah di mana kami berada di.
Dan Anda dapat, jenis, lihat ini di sini.
Jika n kuadrat jelas n kali n, tapi di sini kita memiliki n kali log n,
dan kita sudah tahu dari seminggu nol, bahwa log n, logaritmik itu,
lebih baik daripada sesuatu yang linear.
Setelah semua, mengingat gambar dengan merah dan kuning
dan garis-garis hijau yang kita menarik, yang baris logaritmik hijau jauh lebih rendah.
Dan karena itu, jauh lebih baik dan lebih cepat dari garis kuning dan merah langsung,
n kali log n adalah, memang, lebih baik dari n kali n, atau n kuadrat.
>> Jadi kita tampaknya memiliki mengidentifikasi merge algoritma
semacam yang berjalan di banyak waktu yang lebih cepat, dan memang,
itu sebabnya, awal pekan ini, ketika kita melihat bahwa kontes antara gelembung
sort, selection sort, dan menggabungkan semacam, menggabungkan semacam benar-benar menang.
Dan memang, kita bahkan tidak menunggu untuk bubble sort dan seleksi semacam
menyelesaikan.
>> Sekarang mari kita satu lulus lainnya ini, dari sedikit lebih
perspektif formal, hanya di kasus, ini bergema baik
dari itu diskusi tingkat tinggi.
Jadi, inilah algoritma lagi.
Mari kita bertanya pada diri sendiri, apa waktu berjalan
adalah ini algoritma berbagai langkah?
Mari kita membaginya menjadi yang pertama kasus dan kasus kedua.
IF dan ELSE Dalam kasus IF, JIKA n kurang dari 2, hanya kembali.
Terasa seperti waktu yang konstan.
Ini, jenis, seperti dua langkah, JIKA n kurang dari 2, kemudian kembali.
Tapi seperti yang kita mengatakan pada hari Senin, waktu yang konstan, atau besar o dari 1,
bisa dua langkah, tiga langkah, bahkan 1.000 langkah.
Yang penting adalah bahwa hal itu sejumlah konstan langkah.
Jadi kuning disorot pseudocode di sini berjalan di, kita akan menyebutnya,
waktu yang konstan.
Jadi lebih formal, dan kita akan to-- ini
akan sejauh mana kita meresmikan hak ini sekarang-- T dari n,
waktu berjalan dari masalah yang mengambil n somethings sebagai masukan,
sama besar o dari satu, JIKA n kurang dari 2.
Jadi itu tergantung pada itu.
Jadi harus jelas, IF n kurang dari 2, kita memiliki daftar yang sangat singkat, maka
waktu berjalan, T n, di mana n adalah 1 atau 0, dalam kasus yang sangat spesifik ini,
itu hanya akan menjadi waktu yang konstan.
Ini akan mengambil satu langkah, dua langkah, apa pun.
Ini tetap jumlah langkah.
>> Jadi bagian berair pasti harus dalam kasus lain di pseudocode.
Kasus ELSE.
Urutkan kiri setengah dari elemen, jenis hak setengah dari elemen, menggabungkan bagian diurutkan.
Berapa lama masing-masing langkah mengambil?
Nah, jika menjalankan waktu untuk memilah elemen n
adalah, sebut saja sangat umum, T n,
kemudian menyortir kiri setengah dari elemen
adalah, jenis, seperti mengatakan, T dari n dibagi 2,
dan juga memilah bagian kanan elemen adalah, jenis, seperti mengatakan,
T dari n dibagi 2, dan kemudian penggabungan bagian diurutkan.
Nah jika saya punya beberapa jumlah elemen di sini,
seperti empat, dan beberapa nomor elemen di sini, seperti empat,
dan saya harus menggabungkan masing-masing empat ini di, dan masing-masing empat di, salah satu
setelah yang lain, sehingga akhirnya saya memiliki delapan unsur.
Rasanya seperti itu besar o langkah n?
Jika saya punya n jari dan masing- mereka harus bergabung ke tempat,
itu seperti langkah n lain.
>> Jadi memang dirumuskan secara, kita dapat mengekspresikan ini,
meskipun scarily kecil pada awalnya Sekilas, tapi itu adalah sesuatu
yang menangkap persis logika itu.
Waktu berjalan, T n, IF n lebih besar dari atau sama dengan 2.
Dalam hal ini, kasus ELSE, adalah T n dibagi 2, ditambah T N dibagi 2,
ditambah besar o n, beberapa jumlah linear langkah,
mungkin persis n, mungkin 2 kali n, tapi kira-kira, urutan n.
Jadi itu juga, adalah bagaimana kita bisa mengungkapkan ini dirumuskan secara.
Sekarang Anda tidak akan tahu ini kecuali Anda telah direkam dalam pikiran Anda,
atau mencarinya di belakang buku teks, yang
mungkin memiliki sedikit contekan pada akhirnya,
tapi ini, memang, akan memberi kita besar o n log n,
karena kekambuhan yang Anda lihat di sini di layar,
jika Anda benar-benar melakukan itu, dengan jumlah tak terbatas contoh,
atau Anda melakukannya dirumuskan secara, Anda akan melihat bahwa ini, karena formula ini
sendiri adalah rekursif, dengan t n atas sesuatu di sebelah kanan,
dan t dari n lebih di sebelah kiri, ini bisa sebenarnya dinyatakan, akhirnya,
pergi sebagai besar dari n log n.
Jika tidak yakin, itu baik untuk saat ini, hanya
mengambil iman, bahwa itu, memang, apa kekambuhan yang mengarah ke,
tapi ini hanya sedikit lebih dari Pendekatan matematis untuk mencari
pada saat berjalan dari merge sort berdasarkan pseudocode-nya saja.
>> Sekarang mari kita sedikit nafas dari semua itu,
dan lihatlah sebuah mantan senator tertentu, yang
mungkin terlihat sedikit akrab, yang duduk dengan Google Eric
Schmidt, beberapa waktu lalu, untuk wawancara di atas panggung, di depan seluruh bunch
orang, berbicara tentang akhirnya topik, itu cukup sekarang akrab.
Mari lihat.
>> ERIC SCHMIDT: Sekarang Senator, Anda berada di sini di Google,
dan saya suka berpikir dari presiden sebagai wawancara kerja.
Sekarang sulit untuk mendapatkan pekerjaan sebagai presiden.
PRESIDEN OBAMA: Benar.
ERIC SCHMIDT: Dan kau akan melakukan [tidak terdengar] sekarang.
Ini juga sulit untuk mendapatkan pekerjaan di Google.
PRESIDEN OBAMA: Benar.
>> ERIC SCHMIDT: Kami memiliki pertanyaan, dan kami bertanya kandidat kami,
dan yang satu ini dari Larry Schwimmer.
>> PRESIDEN OBAMA: OK.
>> ERIC SCHMIDT: Apa?
Kalian pikir aku bercanda?
Ada di sini.
Apa cara yang paling efisien untuk mengurutkan bilangan bulat juta 32 bit?
>> PRESIDEN OBAMA: Well--
ERIC SCHMIDT: Kadang-kadang, mungkin aku minta maaf, maybe--
PRESIDEN OBAMA: Tidak, tidak, tidak, tidak, tidak, aku think--
ERIC SCHMIDT: Itu tidak itu--
PRESIDEN OBAMA: Saya berpikir, saya pikir gelembung
semacam akan menjadi cara yang salah untuk pergi.
ERIC SCHMIDT: Ayo.
Yang mengatakan kepadanya ini?
OKE.
Saya tidak ilmu komputer on--
>> PRESIDEN OBAMA: Kami sudah mendapat mata-mata kita di sana.
PROFESSOR: Baiklah.
Mari kita tinggalkan di belakang kami sekarang dunia teoritis algoritma
dalam analisis asimtotik daripadanya, dan kembali ke beberapa topik
dari minggu nol dan satu, dan mulai untuk menghapus beberapa roda pelatihan,
jika Anda mau.
Sehingga Anda benar-benar memahami akhirnya dari bawah ke atas, apa
terjadi di bawah tenda, ketika Anda menulis, mengkompilasi, dan menjalankan program.
Ingat khususnya, bahwa ini adalah program C pertama kita melihat,
kanonik, program yang sederhana macam, relatif berbicara,
dimana, mencetak, Hello World.
Dan ingat bahwa aku mengatakan, proses bahwa kode sumber melewati
adalah persis ini.
Anda mengambil kode sumber Anda, lulus melalui compiler, seperti dentang,
dan keluar datang kode objek, yang mungkin terlihat seperti ini, nol dan satu
bahwa CPU komputer, pusat unit pengolahan atau otak,
akhirnya mengerti.
>> Ternyata itu adalah sedikit terlalu menyederhanakan,
bahwa kita sekarang dalam posisi untuk menggoda terpisah
untuk memahami apa yang benar-benar telah terjadi di bawah tenda
setiap kali Anda menjalankan Dentang, atau lebih umum,
setiap kali Anda membuat sebuah program, menggunakan Membuat dan CF 50 IDE.
Secara khusus, hal-hal seperti ini pertama dihasilkan,
ketika Anda pertama kali mengkompilasi program Anda.
Dengan kata lain, ketika Anda mengambil kode sumber Anda
dan kompilasi, apa yang pertama yang dikeluarkan oleh dentang
adalah sesuatu yang dikenal sebagai kode assembly.
Dan pada kenyataannya, tampak persis seperti ini.
>> Aku berlari perintah di baris perintah sebelumnya.
Hello.c dentang dasbor modal s, dan ini menciptakan sebuah file
bagi saya disebut hello.s, dalam yang tepat
isi ini, dan sedikit lebih di atas dan sedikit lebih bawah,
tapi aku sudah menempatkan juiciest Informasi di sini di layar.
Dan jika Anda melihat dekat, Anda akan melihat setidaknya beberapa kata kunci akrab.
Kami memiliki utama di atas.
Kami telah printf turun di tengah.
Dan kami juga memiliki hello world backslash n dalam tanda kutip di bawah.
>> Dan segala sesuatu yang lain di sini adalah petunjuk tingkat yang sangat rendah
bahwa CPU komputer mengerti.
Instruksi CPU yang bergerak memori sekitar, bahwa string beban dari memori,
dan akhirnya, cetak hal di layar.
Sekarang apa yang terjadi meskipun setelah kode assembly ini dihasilkan?
Pada akhirnya, Anda lakukan, memang, masih menghasilkan kode objek.
Tapi langkah-langkah yang harus benar-benar telah terjadi di bawah tenda
terlihat sedikit lebih seperti ini.
Source code menjadi kode assembly, yang kemudian menjadi kode objek,
dan kata-kata operasi di sini adalah bahwa, ketika Anda mengkompilasi kode sumber Anda,
keluar datang kode perakitan, dan kemudian ketika Anda merakit kode perakitan Anda,
keluar datang kode objek.
>> Sekarang dentang super canggih, seperti banyak kompiler,
dan itu semua langkah ini bersama-sama, dan itu tidak selalu
output apapun antara file yang Anda bahkan dapat melihat.
Itu hanya mengkompilasi hal, yang merupakan istilah umum yang
menggambarkan seluruh proses ini.
Tetapi jika Anda benar-benar ingin menjadi tertentu, ada
lebih banyak terjadi di sana juga.
>> Tapi mari kita juga mempertimbangkan bahwa bahkan sekarang bahwa program super sederhana, hello.c,
disebut fungsi.
Ini disebut printf.
Tapi aku tidak menulis printf, memang, yang datang dengan c, sehingga untuk berbicara.
Ini adalah recall fungsi yang dideklarasikan di io.h standar, yang
adalah file header, yang adalah topik kita akan benar-benar
menyelam ke kedalaman lebih lama.
Tapi file header biasanya disertai
oleh file kode, berkas kode sumber, sehingga seperti terdapat io.h. standar
>> Beberapa waktu yang lalu, seseorang, atau someones, juga menulis
file bernama io.c standar, di yang definisi yang sebenarnya,
atau implementasi dari printf, dan tandan fungsi lainnya,
benar-benar ditulis.
Jadi mengingat bahwa, jika kita mempertimbangkan memiliki di sini di sebelah kiri, hello.c, bahwa ketika
disusun, memberi kita hello.s, bahkan jika Dentang tidak mengganggu tabungan di tempat
kita bisa melihat itu, dan bahwa kode perakitan akan dirakit menjadi hello.o, yang
adalah, memang, nama default diberikan setiap kali Anda mengkompilasi sumber
kode ke dalam kode objek, tetapi tidak cukup siap untuk melaksanakannya belum,
karena langkah lain harus terjadi, dan memiliki
telah terjadi selama beberapa masa lalu minggu, mungkin tanpa sepengetahuan Anda.
>> Khusus di suatu tempat di CS50 IDE, dan ini,
juga, akan menjadi sedikit penyederhanaan sejenak,
ada, atau ada pada waktu, file bernama io.c standar,
bahwa seseorang dikompilasi ke io.s standar atau setara,
bahwa seseorang kemudian dirakit ke io.o standar,
atau ternyata menjadi File yang sedikit berbeda
format yang dapat memiliki yang berbeda mengajukan perpanjangan sama sekali,
tetapi dalam teori dan konseptual, tepatnya langkah-langkah harus terjadi dalam beberapa bentuk.
Yang mengatakan, bahwa sekarang ketika saya sedang menulis sebuah program,
hello.c, yang hanya mengatakan, halo dunia, dan aku menggunakan kode orang lain
seperti printf, yang dulunya di atas waktu, dalam sebuah file bernama io.c standar,
kemudian entah bagaimana aku harus mengambil saya kode objek, nol dan yang,
dan objek orang itu kode, atau nol dan satu,
dan entah bagaimana menghubungkan mereka bersama-sama ke satu file akhir, yang disebut halo, yang
memiliki semua nol dan yang dari fungsi utama saya,
dan semua nol dan orang-orang untuk printf.
>> Dan memang, bahwa proses terakhir adalah disebut, menghubungkan kode objek.
Output yang adalah file executable.
Jadi dalam keadilan, di akhir hari, tidak ada
telah berubah sejak satu minggu, ketika kita pertama mulai menyusun program.
Memang, semua ini telah terjadi di bawah kap mesin,
tapi sekarang kami dalam posisi di mana kita bisa benar-benar
menggoda selain berbagai langkah.
Dan memang, di akhir hari, kami masih
kiri dengan nol dan satu, yang sebenarnya Shalawat besar sekarang
dengan kemampuan lain dari C, yang kita tidak harus meningkatkan kemungkinan besar
sampai saat ini, dikenal sebagai operator bitwise.
Dengan kata lain, sejauh ini, kapan saja kita sudah berurusan dengan data di C atau variabel di C,
kami sudah hal-hal seperti karakter dan mengapung dan ins
dan rindu dan ganda dan seperti, tapi semua orang setidaknya delapan bit.
Kami sudah pernah belum mampu memanipulasi bit individu,
meskipun bit individu, kita tahu, bisa mewakili 0 dan 1.
Sekarang ternyata bahwa di C, Anda bisa mendapatkan akses ke bit individu,
jika Anda tahu sintaks, yang dapat digunakan untuk mendapatkan mereka.
>> Jadi mari kita lihat di operator bitwise.
Jadi digambarkan di sini adalah beberapa simbol yang kami, jenis, jenis, terlihat sebelumnya.
Saya melihat ampersand, vertikal bar, dan beberapa orang lain juga,
dan ingat bahwa ampersand ampersand adalah sesuatu yang telah kita lihat sebelumnya.
Logika AND operator, di mana Anda memiliki dua dari mereka bersama-sama, atau logika OR
operator, di mana Anda memiliki dua bar vertikal.
Operator bitwise, yang kita akan melihat beroperasi pada bit individual,
hanya menggunakan ampersand tunggal, tunggal vertikal, simbol tanda sisipan
datang berikutnya, kecil tilde, dan kemudian meninggalkan
braket kiri braket, atau braket kanan braket yang tepat.
Masing-masing memiliki arti yang berbeda.
>> Bahkan, mari kita lihat.
Mari kita pergi sekolah tua hari ini, dan penggunaan layar sentuh dari masa lampau,
dikenal sebagai papan tulis.
Dan papan tulis ini akan memungkinkan kita
untuk mengungkapkan beberapa simbol yang cukup sederhana, atau lebih tepatnya beberapa rumus cukup sederhana,
yang kita dapat kemudian akhirnya leverage, dalam rangka
untuk mengakses individu bit dalam program C.
Dengan kata lain, mari kita lakukan ini.
Mari kita pertama berbicara untuk sejenak tentang ampersand,
yang merupakan bitwise DAN operator.
Dengan kata lain, ini adalah operator yang memungkinkan
saya memiliki variabel kiri biasanya, dan variabel kanan,
atau nilai individu, bahwa jika kita DAN mereka bersama-sama, memberi saya hasil akhir.
Jadi apa yang saya maksud?
Jika dalam sebuah program, Anda memiliki variabel yang menyimpan salah satu nilai-nilai ini,
atau mari kita tetap sederhana, dan hanya menulis nol dan satu secara individual,
berikut adalah cara operator ampersand bekerja.
0 ampersand 0 akan sama 0.
Sekarang kenapa begitu?
>> Ini sangat mirip dengan Ekspresi Boolean,
yang telah kita bahas sejauh ini.
Jika Anda berpikir setelah semua, 0 adalah palsu, 0 adalah palsu, palsu dan palsu
adalah, seperti yang telah kita bahas logis, juga palsu.
Jadi kita mendapatkan 0 sini juga.
Jika Anda mengambil 0 ampersand 1, baik itu juga,
akan menjadi 0, karena untuk ini ekspresi kiri untuk menjadi kenyataan atau 1,
itu akan perlu untuk menjadi kenyataan dan benar.
Tapi di sini kita memiliki palsu dan benar, atau 0 dan 1.
Sekarang lagi, jika kita memiliki 1 ampersand 0, itu juga, akan menjadi 0,
dan jika kita memiliki 1 ampersand 1, akhirnya kita memiliki 1 bit.
Jadi dengan kata lain, kita tidak melakukan sesuatu yang menarik dengan operator ini
dulu, operator ampersand ini.
Ini adalah bitwise DAN operator.
Tetapi ini adalah bahan melalui mana kita dapat melakukan
hal-hal menarik, seperti yang kita akan segera melihat.
>> Sekarang mari kita lihat hanya satu bar vertikal di sini di sebelah kanan.
Jika saya memiliki 0 bit dan saya OR dengan, bitwise
OR operator, yang lain 0 bit, itu akan memberi saya 0.
Jika saya mengambil bit 0 dan OR dengan 1 bit, maka aku akan mendapatkan 1.
Dan pada kenyataannya, hanya untuk kejelasan, biarkan aku kembali,
sehingga bar vertikal saya tidak salah untuk 1 itu.
Biarkan saya menulis ulang semua 1 saya sedikit lebih
jelas, sehingga kita selanjutnya melihat, jika saya telah 1 atau 0, itu akan menjadi 1,
dan jika saya memiliki 1 atau 1 itu, juga, akan menjadi 1.
Sehingga Anda dapat melihat secara logis bahwa OR Operator berperilaku sangat berbeda.
Ini memberi saya 0 OR 0 memberi saya 0, tapi setiap kombinasi lain memberi saya 1.
Selama aku punya satu 1 di rumus, hasilnya akan menjadi 1.
>> Sebaliknya dengan DAN operator, ampersand,
hanya jika saya memiliki dua 1 dalam persamaan, saya benar-benar mendapatkan 1 keluar.
Sekarang ada beberapa lainnya operator juga.
Salah satunya adalah sedikit lebih terlibat.
Jadi biarkan aku pergi ke depan dan menghapus ini untuk membebaskan beberapa ruang.
Dan mari kita lihat simbol sisipan, untuk sesaat.
Ini biasanya karakter Anda dapat mengetik
pada shift memegang keyboard dan maka salah satu nomor di atas US Anda
Keyboard.
>> Jadi ini adalah eksklusif OR operator, eksklusif OR.
Jadi kita hanya melihat operator OR.
Ini adalah eksklusif OR operator.
Apa sebenarnya perbedaan?
Nah mari kita lihat saja rumus, dan menggunakan ini sebagai bahan akhirnya.
0 XOR 0.
Aku akan katakan adalah selalu 0.
Itulah definisi XOR.
0 XOR 1 akan menjadi 1.
1 XOR 0 akan menjadi 1, dan 1 XOR 1 akan menjadi?
Salah?
Atau benar?
Saya tidak tahu.
0.
Sekarang apa yang terjadi di sini?
Nah berpikir tentang nama operator ini.
Eksklusif OR, sehingga sebagai Nama, jenis, menunjukkan,
jawabannya hanya akan menjadi 1 jika input yang eksklusif,
eksklusif yang berbeda.
Jadi di sini input adalah sama, sehingga output adalah 0.
Berikut input adalah sama, sehingga output adalah 0.
Berikut adalah output yang berbeda, mereka eksklusif, dan output adalah 1.
Sehingga sangat mirip dengan DAN, itu sangat mirip,
atau lebih tepatnya itu sangat mirip dengan OR, tapi hanya dengan cara eksklusif.
Yang satu ini tidak lagi menjadi 1, karena kita memiliki dua 1 ini,
dan tidak eksklusif, hanya salah satu dari mereka.
Baiklah.
Bagaimana dengan orang lain?
Nah tilde, sementara itu, benar bagus dan sederhana, untungnya.
Dan ini adalah unary operator, yang berarti
itu diterapkan hanya satu masukan, satu operan, sehingga untuk berbicara.
Bukan ke kiri dan kanan.
Dengan kata lain, jika Anda mengambil tilde dari 0, jawabannya akan menjadi sebaliknya.
Dan jika Anda mengambil tilde dari 1, Jawabannya akan ada sebaliknya.
Jadi operator tilde adalah cara meniadakan sedikit,
atau membalik sedikit dari 0-1, atau 1-0.
>> Dan yang membuat kita akhirnya dengan hanya dua operator akhir,
disebut pergeseran kiri, dan disebut operator shift kanan.
Mari kita lihat bagaimana mereka bekerja.
Operator shift kiri, ditulis dengan dua kurung sudut seperti itu,
beroperasi sebagai berikut.
Jika saya masukan, atau operan saya, ke kiri Operator pergeseran cukup hanya 1.
Dan saya kemudian memberitahu komputer untuk meninggalkan pergeseran yang 1, mengatakan tujuh tempat,
hasilnya adalah seolah-olah saya mengambil 1, dan memindahkannya
tujuh tempat lebih ke kiri, dan secara default,
kita akan berasumsi bahwa ruang ke kanan
akan menjadi empuk dengan nol.
Dengan kata lain, 1 kiri pergeseran 7 akan memberi saya bahwa 1, diikuti oleh 1, 2, 3,
4, 5, 6, 7 nol.
Jadi dengan cara, memungkinkan Anda untuk mengambil sejumlah kecil seperti 1,
dan jelas membuatnya lebih banyak, jauh lebih besar dengan cara ini,
tapi kami benar-benar akan melihat pendekatan yang lebih pintar untuk itu
sebaliknya, juga,
>> Baiklah.
Itu saja untuk minggu tiga.
Kita akan melihat Anda waktu berikutnya.
Ini adalah CS50.
>> [MUSIC PLAYING]
>> SPEAKER 1: Dia berada di snack bar makan es krim cokelat.
Dia memiliki seluruh wajahnya.
Dia mengenakan bahwa coklat seperti janggut
SPEAKER 2: Apa yang kamu lakukan?
SPEAKER 3: Hmmm?
Apa?
>> SPEAKER 2: Apakah Anda hanya ganda dip?
Anda ganda mencelupkan chip.
SPEAKER 3: Permisi.
SPEAKER 2: Anda mencelupkan chip, Anda menggigit, dan Anda mencelupkan lagi.
SPEAKER 3:
SPEAKER 2: Jadi itu seperti menempatkan mulut seluruh hak Anda di dip.
Lain kali Anda mengambil sebuah chip, hanya mencelupkan sekali, dan mengakhirinya.
>> SPEAKER 3: Anda tahu apa, Dan?
Anda mencelupkan cara yang ingin Anda mencelupkan.
Aku akan mencelupkan cara yang saya ingin mencelupkan.