DAVID Malan: Baiklah. Kami kembali. Jadi di segmen ini pada pemrograman apa Saya pikir kami akan lakukan adalah campuran dari hal-hal. Satu, melakukan sedikit sesuatu tangan-on, meskipun menggunakan lebih playful pemrograman environment-- salah satu yang demonstratif dari persis jenis ide kita sudah bicarakan, tapi sedikit lebih formal. Dua, melihat beberapa cara yang lebih teknis bahwa programmer benar-benar akan memecahkan masalah seperti masalah mencari bahwa kita melihat sebelum dan juga lebih mendasar masalah yang menarik penyortiran. 

Kami hanya menduga dari bisa pergi bahwa buku telepon diurutkan, tapi itu saja sebenarnya semacam masalah yang sulit dengan berbagai cara untuk menyelesaikannya. Jadi kita akan menggunakan ini sebagai kelas masalah wakil dari hal-hal yang mungkin diselesaikan secara umum. Dan kemudian kita akan berbicara tentang dalam beberapa detail apa disebut Data structures-- cara pengujian seperti daftar terkait dan tabel hash dan pohon-pohon yang programmer benar-benar akan menggunakan dan umumnya menggunakan pada papan tulis untuk melukis gambar apa yang dia Visi untuk menerapkan beberapa bagian dari perangkat lunak. 

Jadi mari kita lakukan tangan-on bagian pertama. Jadi hanya mendapatkan tangan Anda kotor dengan lingkungan disebut scratch.mit.edu. Ini adalah alat yang kita gunakan di kelas sarjana kita. Meskipun dirancang untuk usia 12 tahun ke atas, kita menggunakannya untuk up bagian dari yang sedikit karena itu bagus, menyenangkan cara grafis belajar sedikit sesuatu tentang pemrograman. Jadi kepala ke URL itu, di mana Anda harus melihat halaman cukup seperti ini, dan pergi ke depan dan klik Bergabunglah Scratch di kanan atas dan memilih username dan kata sandi dan akhirnya mendapatkan diri Anda sebuah scratch.mit.edu account--. Saya pikir saya akan menggunakan ini sebagai kesempatan pertama untuk menunjukkan ini. Sebuah pertanyaan muncul selama istirahat tentang apa kode benar-benar terlihat seperti. Dan kami berbicara selama istirahat tentang C, di particular-- khususnya tingkat yang lebih rendah dalam bahasa yang lebih tua. Dan saya hanya melakukan cepat Google mencari untuk menemukan kode C untuk pencarian biner, algoritma yang kita digunakan untuk mencari buku telepon sebelumnya. contoh khusus ini, tentu saja, tidak mencari buku telepon. Ini hanya mencari sejumlah besar nomor di memori komputer. Tetapi jika Anda ingin hanya mendapatkan visual rasa apa pemrograman yang sebenarnya bahasa seperti, terlihat sedikit sesuatu seperti ini. Jadi itu sekitar 20-plus, 30 atau lebih baris kode, tapi percakapan kami yang memiliki lebih dari istirahat adalah tentang bagaimana ini benar-benar akan berubah menjadi nol dan satu dan jika Anda tidak bisa hanya kembali bahwa memproses dan pergi dari nol dan satu kembali ke kode. 

Sayangnya, proses begitu transformatif bahwa itu jauh lebih mudah diucapkan daripada dilakukan. Aku pergi ke depan dan benar-benar berubah Program itu, Binary Search, menjadi nol dan satu dengan cara Program yang disebut Compiler The bahwa saya kebetulan memiliki sini tepat di Mac saya. Dan jika Anda melihat layar di sini, dengan fokus khusus pada ini enam kolom tengah saja, Anda akan melihat hanya nol dan satu. Dan mereka adalah nol dan orang-orang yang menulis persis bahwa program pencarian. 

Dan setiap potongan lima bit, setiap byte dari nol dan satu di sini, mewakili beberapa instruksi biasanya dalam komputer. Dan pada kenyataannya, jika Anda pernah mendengar slogan pemasaran "Intel dalam" - itu, Tentu saja, hanya berarti Anda memiliki Intel CPU atau otak di dalam komputer. Dan apa artinya menjadi CPU adalah bahwa Anda memiliki set instruksi, boleh dikatakan. 

Setiap CPU di dunia, banyak dari mereka dibuat oleh Intel hari ini, mengerti yang terbatas jumlah instruksi. Dan instruksi tersebut adalah tingkat sangat rendah sebagai menambahkan dua angka ini bersama-sama, kalikan dua angka ini bersama-sama, memindahkan sepotong data dari sini di sini dalam memori, menyimpan ini informasi dari sini ke sini dalam memori, dan begitu forth-- begitu sangat, sangat tingkat rendah, rincian hampir elektronik. Tapi dengan orang-matematika operasi ditambah dengan apa yang kita bahas sebelumnya, representasi data sebagai nol dan satu, bisa Anda membangun segalanya bahwa komputer dapat lakukan hari ini, apakah itu tekstual, grafis, musik, atau sebaliknya. 

Jadi ini sangat mudah untuk mendapatkan hilang dalam gulma dengan cepat. Dan ada banyak tantangan sintaksis dimana jika Anda membuat sederhana, terbodoh dari kesalahan ketik tidak ada program akan bekerja apapun. Dan bukannya menggunakan bahasa seperti C pagi ini, Saya pikir ini akan menjadi lebih menyenangkan untuk benar-benar melakukan sesuatu yang lebih visual, yang sementara dirancang untuk anak-anak sebenarnya merupakan manifestasi sempurna sebuah pemrograman yang sebenarnya language-- kebetulan menggunakan gambar, bukan teks untuk mewakili ide-ide mereka. 

Jadi, sekali Anda memang memiliki account di scratch.mit.edu, klik tombol Create di sebelah kiri atas situs. Dan Anda akan melihat lingkungan seperti satu Aku akan melihat di layar saya sini. Dan kita akan menghabiskan hanya sedikit sedikit waktu bermain di sini. Mari kita lihat apakah kita tidak bisa semua memecahkan beberapa masalah bersama-sama dengan cara berikut. 

Jadi apa yang Anda akan melihat dalam hal ini environment-- dan benar-benar hanya membiarkan saya berhenti sejenak. Apakah ada yang tidak di sini? Tidak disini? BAIK. Jadi biarkan aku menunjukkan beberapa karakteristik lingkungan ini. 

Jadi di kiri atas layar, kami memiliki panggung Scratch ini, sehingga untuk berbicara. Scratch tidak hanya nama bahasa pemrograman ini; itu juga nama kucing yang Anda lihat secara default ada di orange. Dia adalah di atas panggung, jadi seperti yang saya jelaskan penyu sebelumnya sebagai dalam persegi panjang lingkungan papan putih. dunia ini kucing terbatas seluruhnya untuk yang persegi panjang di bagian atas ada. 

Sementara itu, di sebelah kanan sisi sini, itu hanya daerah script, sebuah batu tulis kosong jika Anda mau. Ini adalah di mana kita akan menulis program kami hanya dalam beberapa saat. Dan blok bangunan yang akan kita gunakan untuk menulis ini program-- teka-teki potongan, jika Anda will-- adalah mereka di sini, di tengah, dan mereka dikategorikan oleh fungsi. Jadi, misalnya, saya akan pergi ke depan dan menunjukkan setidaknya salah satu dari ini. Aku akan pergi ke depan dan klik kategori Kontrol atas. 

Jadi ini adalah kategori di bagian atas. Aku akan klik kategori Control. Sebaliknya, aku akan mengklik Acara kategori, pertama satu di bagian atas. Dan jika Anda ingin mengikuti bahkan seperti yang kita lakukan ini, Anda cukup dipersilakan untuk. Aku akan klik dan tarik ini pertama, "ketika bendera hijau diklik." Dan kemudian aku akan menjatuhkannya hanya kira-kira di atas papan tulis kosong saya. 

Dan apa yang baik tentang Scratch adalah bahwa potongan puzzle ini, ketika saling bertautan dengan puzzle lainnya potongan, yang akan dilakukan secara harfiah apa yang potongan-potongan puzzle mengatakan untuk melakukan. Jadi, misalnya, Scratch tepat sekarang di tengah dunianya. Aku akan pergi ke depan dan memilih sekarang, katakanlah, kategori Gerak, jika Anda ingin melakukan same-- kategori Motion. Dan sekarang melihat saya memiliki keseluruhan sekelompok potongan puzzle sini itu, sekali lagi, jenis melakukan apa yang mereka katakan. Dan aku akan pergi ke depan dan tarik dan drop blok langkah yang tepat di sini. 

Dan melihat bahwa segera setelah Anda mendapatkan dekat dengan bagian bawah "bendera hijau diklik "tombol, pemberitahuan bagaimana garis putih muncul, seolah-olah itu hampir magnetik, ia ingin pergi ke sana. Hanya membiarkan pergi, dan itu akan snap bersama-sama dan bentuk akan cocok. mungkin dan sekarang Anda bisa hampir menebak di mana kita akan dengan ini. 

Jika Anda melihat tahap Scratch di sini dan melihat ke atas itu, Anda akan melihat lampu merah, sebuah tanda berhenti, dan bendera hijau. Dan aku akan pergi ke depan dan menonton screen-- saya untuk sesaat, jika Anda bisa. Aku akan mengklik hijau bendera sekarang, dan ia pindah apa yang tampaknya menjadi 10 langkah atau 10 piksel, 10 titik, di layar. 

Dan jadi tidak menarik, tapi biarkan aku mengusulkan tanpa mengajar ini, hanya menggunakan sendiri membiarkan intuition-- Anda sendiri saya mengusulkan bahwa Anda tahu bagaimana membuat Scratch berjalan langsung dari panggung. Minta dia membuat jalan bagi sisi kanan layar, semua jalan ke kanan. Biarkan saya memberi Anda beberapa saat atau lebih bergulat dengan itu. Anda mungkin ingin lihat di kategori lain dari blok. Baiklah. Jadi hanya untuk rekap, ketika kita memiliki bendera hijau diklik di sini dan memindahkan 10 langkah adalah hanya instruksi, setiap kali saya klik bendera hijau, apa yang terjadi? Nah, yang menjalankan program saya. Jadi saya bisa melakukan ini mungkin 10 kali secara manual, tapi ini terasa sedikit bit hackish, sehingga untuk berbicara, dimana aku tidak benar-benar pemecahan masalah. Aku hanya berusaha lagi dan lagi dan lagi dan lagi sampai aku semacam sengaja mencapai direktif bahwa saya ditetapkan untuk mencapai sebelumnya. 

Tapi kita tahu dari kami pseudocode sebelumnya bahwa ada gagasan ini dalam pemrograman looping, melakukan sesuatu lagi dan lagi. Dan aku melihat bahwa sekelompok Anda meraih apa potongan puzzle? Ulangi sampai. Jadi kita bisa melakukan sesuatu seperti ulangi sampai. Dan apa yang Anda ulangi sampai tepat? 

BAIK. Dan biarkan aku pergi dengan satu yang agak sederhana untuk sesaat. Biarkan aku pergi ke depan dan melakukan hal ini. Perhatikan bahwa, karena Anda mungkin memiliki ditemukan di bawah Control, ada blok berulang ini, yang tidak terlihat seperti itu begitu besar. Tidak ada banyak ruang di antara dua garis kuning. Tapi karena beberapa dari Anda mungkin memiliki perhatikan, jika Anda drag dan drop, perhatikan bagaimana tumbuh untuk mengisi bentuk. 

Dan Anda bahkan dapat menjejalkan lebih. Itu hanya akan terus berkembang jika Anda drag dan membawa lebih dari itu. Dan aku tidak tahu apa yang terbaik di sini, jadi mari saya setidaknya mengulang lima kali, untuk Misalnya, dan kemudian kembali ke panggung dan klik bendera hijau. Dan sekarang melihat itu tidak cukup ada. 

Sekarang beberapa dari Anda yang diusulkan, sebagai Victoria hanya tidak, ulangi 10 kali. Dan yang umumnya tidak mendapatkan dia sepanjang jalan, tapi tidak akan ada menjadi lebih kuat cara dari sewenang-wenang mencari tahu berapa banyak bergerak untuk membuat? Apa yang mungkin menjadi blok yang lebih baik dari ulangi 10 kali menjadi? 

Ya, jadi mengapa tidak melakukan sesuatu selamanya? Dan sekarang biarkan aku bergerak potongan puzzle ini dalam sana dan menyingkirkan satu ini. Sekarang perhatikan di mana pun Scratch dimulai, dia pergi ke tepi. Dan untungnya MIT, yang membuat Scratch, hanya memastikan bahwa ia tidak pernah menghilang sepenuhnya. Anda selalu bisa ambil ekornya. 

Dan hanya intuitif, mengapa dia terus bergerak? Apa yang terjadi disini? Dia tampaknya telah berhenti, tetapi maka jika saya mengambil dan tarik ia terus ingin pergi ke sana. Mengapa demikian? Sesungguhnya, komputer secara harfiah akan melakukan apa yang Anda katakan untuk dilakukan. Jadi jika Anda mengatakan itu sebelumnya melakukan berikut hal selamanya, bergerak 10 langkah, itu akan terus dan pergi sampai aku memukul tanda berhenti merah dan menghentikan program sama sekali. 

Jadi bahkan jika Anda tidak melakukan hal ini, bagaimana mungkin saya membuat Scratch bergerak lebih cepat di layar? langkah lagi, kan? Jadi bukannya melakukan 10 pada suatu waktu, mengapa tidak kita pergi ke depan dan mengubahnya to-- apa yang akan Anda propose-- 50? Jadi sekarang aku akan mengklik hijau bendera, dan memang, dia pergi sangat cepat. 

Dan ini, tentu saja, hanya manifestasi dari animasi. Apa animasi? Itu hanya menunjukkan Anda seorang manusia sejumlah gambar masih benar-benar, benar-benar, benar-benar cepat. Dan jadi jika kita hanya mengatakan dia untuk pindah langkah lebih lanjut, kami hanya memiliki efek adalah untuk perubahan di mana dia berada di layar semua lebih cepat per satuan waktu. 

Sekarang tantangan berikutnya yang saya diusulkan adalah untuk memiliki dia bangkit dari tepi. Dan tanpa mengetahui apa puzzle potongan exist-- karena itu baik-baik saja jika Anda tidak mendapatkan ke tahap challenge-- apa Anda ingin melakukan intuitif? Bagaimana kita memiliki dia bangkit kembali dan sebagainya, antara kiri dan kanan? 

Ya. Jadi kita perlu semacam kondisi, dan kami tampaknya memiliki conditional, sehingga untuk berbicara, di bawah kategori Control. Manakah dari blok ini kita mungkin ingin? Ya, mungkin "jika, kemudian." Jadi perhatikan bahwa di antara blok kuning kita miliki di sini, ada ini "jika" atau ini "jika, lain" blok yang akan memungkinkan kita untuk membuat keputusan untuk melakukan hal ini atau untuk melakukan itu. bahkan dan Anda dapat sarang mereka untuk melakukan beberapa hal. Atau jika Anda sudah tidak pergi di sini belum, pergi ke depan untuk kategori Sensing dan- mari kita lihat apakah itu di sini. 

Jadi apa blok mungkin bisa membantu di sini untuk mendeteksi apakah dia dari panggung? Ya, melihat bahwa sebagian dari blok ini dapat parametrized, sehingga untuk berbicara. Mereka dapat semacam disesuaikan, tidak tidak seperti HTML kemarin dengan atribut, di mana atribut-atribut semacam menyesuaikan perilaku tag. Demikian pula di sini, bisa saya ambil menyentuh ini blok dan perubahan dan bertanya, yang Anda menyentuh mouse pointer seperti kursor atau Anda menyentuh tepi? 

Jadi biarkan aku pergi dan melakukan hal ini. Aku akan tampilannya keluar sejenak. Mari saya ambil potongan puzzle ini di sini, potongan puzzle ini ini, dan aku akan campur aduk mereka untuk sesaat. Aku akan pindah ini, mengubahnya ke tepi menyentuh, dan aku akan gerak melakukan hal ini. Jadi di sini adalah beberapa bahan. Saya pikir saya punya semua yang saya inginkan. 

Apakah seseorang ingin mengusulkan bagaimana saya dapat menghubungkan ini mungkin atas ke bawah dalam rangka memecahkan masalah memiliki Scratch bergerak dari kanan ke kiri ke kanan untuk kiri ke kanan ke kiri, masing-masing waktu hanya memantul dari dinding? Apa yang ingin saya lakukan? Yang blok harus saya terhubung ke "Bendera ketika hijau diklik pertama"? 

OK, jadi mari kita mulai dengan "selamanya." Apa yang terjadi di dalam berikutnya? Orang lain. OK, bergerak langkah. Baiklah. Lalu apa? Jadi jika. Dan perhatikan, meskipun tampak terjepit bersama-sama erat, itu hanya akan tumbuh untuk mengisi. Itu hanya akan melompat di mana saya menginginkannya. 

Dan apa yang saya menempatkan antara jika dan kemudian? Mungkin "jika menyentuh tepi." Dan pemberitahuan, sekali lagi, itu terlalu besar untuk itu, tetapi akan tumbuh untuk mengisi. Dan kemudian putar 15 derajat? Berapa derajat? Ya, jadi 180 akan berputar saya semua jalan di sekitar. Jadi mari kita lihat apakah saya punya hak ini. Mari saya zoom out. 

Mari saya tarik Scratch up. Jadi dia sedikit terdistorsi sekarang, tapi itu baik-baik saja. Bagaimana saya bisa mereset dia dengan mudah? Aku akan menipu sedikit. Jadi saya menambahkan lain blok, hanya harus jelas. Saya ingin dia menunjukkan 90 derajat ke kanan secara default, jadi aku hanya akan mengatakan kepadanya untuk melakukan itu pemrograman. Dan di sini kita pergi. Kita tampaknya telah melakukannya. Ini sedikit aneh, karena dia berjalan terbalik. Mari kita sebut bahwa bug. Itu kesalahan. Sebuah bug adalah kesalahan dalam program, sebuah kesalahan logis bahwa saya, manusia, membuat. Mengapa dia akan terbalik? Apakah MIT mengacaukan atau aku? 

Ya, maksud saya, itu tidak MIT kesalahan. Mereka memberiku potongan puzzle yang mengatakan mengubah beberapa jumlah derajat. Dan di saran Victoria, Aku berubah 180 derajat, yang merupakan intuisi yang tepat. Tapi berbalik 180 derajat harfiah berarti berputar 180 derajat, dan itu tidak benar-benar apa yang saya inginkan, rupanya. Karena setidaknya dia di dunia ini dua dimensi, jadi balik benar-benar akan flip dia terbalik. 

Saya mungkin ingin menggunakan apa block sebaliknya, berdasarkan apa yang Anda lihat di sini? Bagaimana mungkin kita memperbaiki ini? Ya, jadi kita bisa menunjukkan dalam arah yang berlawanan. Dan benar-benar bahkan itu tidak akan cukup, karena kita hanya bisa kode keras untuk menunjuk kiri atau kanan. 

Anda tahu apa yang bisa kita lakukan? Sepertinya kita memiliki kenyamanan blok di sini. Jika saya memperbesar, melihat sesuatu yang kita suka di sini? Jadi sepertinya MIT memiliki abstraksi dibangun di sini. Blok ini tampaknya menjadi setara yang blok lainnya, plural? 

satu blok ini tampaknya menjadi setara untuk seluruh trio ini blok yang kita miliki di sini. Jadi ternyata saya dapat menyederhanakan saya Program dengan menyingkirkan semua itu dan hanya menempatkan ini di sini. Dan sekarang dia masih sedikit kereta, dan itu bagus untuk saat ini. Kami akan memberikan yang ada. Tapi program saya bahkan sederhana, dan ini, juga, akan menjadi wakil dari tujuan di programming-- adalah idealnya membuat kode Anda sebagai sederhana, kompak mungkin, sementara masih sebagai dibaca mungkin. Anda tidak ingin membuatnya begitu singkat bahwa sulit untuk memahami. 

Tapi perhatikan aku sudah diganti tiga blok dengan satu, dan itu bisa dibilang hal yang baik. Aku sudah disarikan pergi gagasan memeriksa apakah Anda di tepi dengan hanya satu blok. Sekarang kita bisa bersenang-senang dengan ini, pada kenyataannya. Ini tidak menambahkan begitu banyak nilai intelektual tetapi nilai playful. Aku akan pergi ke depan dan ambil suara ini di sini. Jadi biarkan aku pergi ke depan, dan biarkan aku menghentikan program sejenak. Aku akan merekam berikut, memungkinkan akses ke mikrofon saya. 

Kita mulai. Aduh. Mari kita coba ini lagi. Kita mulai. OK, saya mencatat hal yang salah. Kita mulai. Aduh. Aduh. Baiklah. Sekarang saya perlu untuk menyingkirkan itu. Baiklah. 

Jadi sekarang aku punya perekaman hanya "Aduh." Jadi sekarang aku akan pergi depan dan menyebutnya "Aduh." Aku akan kembali script saya, dan sekarang pemberitahuan ada blok ini yang disebut memutar suara "meong" atau memutar suara "Aduh." Aku akan menyeret ini, dan di mana harus saya menempatkan ini untuk efek lucu? Ya, jadi sekarang itu jenis kereta, karena sekarang ini block-- perhatikan bagaimana ini "jika di tepi, bounce "adalah jenis mandiri. Jadi saya harus memperbaiki ini. Biarkan aku pergi ke depan dan melakukan hal ini. Biarkan aku menyingkirkan ini dan kembali untuk asli kami, lebih disengaja fungsionalitas. Jadi "jika menyentuh tepi, maka" Saya ingin untuk mengubah, sebagai Victoria diusulkan, 180 derajat. Dan apakah saya ingin bermain suara "Aduh" di sana? 

Ya, melihat itu luar blok kuning. Jadi ini juga, akan menjadi bug, tapi aku sudah melihat itu. Jadi aku akan seret di sini, dan pemberitahuan sekarang ini dalam "jika." Jadi "jika" adalah semacam ini seperti lengan-seperti blot yang hanya akan melakukan apa yang di dalamnya. Jadi sekarang jika saya zoom out di risiko annoying-- 

KOMPUTER: Aduh, aduh, aduh. 

DAVID Malan: Dan hanya akan berlangsung selamanya. Sekarang hanya untuk mempercepat hal-hal sini, biarkan aku pergi ke depan dan membuka, mari say-- biarkan aku pergi ke beberapa barang saya sendiri dari kelas. Dan biarkan aku membuka, katakanlah, ini satu yang dibuat oleh salah satu rekan mengajar kami beberapa tahun yang lalu. Jadi beberapa dari Anda mungkin ingat game ini dari masa lampau, dan itu benar-benar luar biasa. Meskipun kami sudah melakukan sederhana program sekarang, mari kita mempertimbangkan apa ini benar-benar tampak seperti. Mari saya tekan tombol play. 

Jadi dalam game ini, kita memiliki katak, dan menggunakan panah keys-- ia mengambil langkah besar daripada yang saya ingat-- Saya memiliki kontrol atas katak ini. Dan tujuannya adalah untuk mendapatkan seluruh sibuk jalan tanpa berlari ke mobil. Dan mari kita see-- jika saya pergi ke sini, saya harus menunggu log untuk menggulir dengan. Ini terasa seperti bug. Ini adalah jenis bug. Baiklah. Aku tentang ini di sini, ada, dan kemudian Anda tetap berjalan sampai Anda mendapatkan semua katak untuk bantalan lily. Sekarang ini mungkin terlihat semua lebih kompleks, tapi mari kita coba untuk memecahkan ini turun mental dan verbal menjadi blok-blok komponen. Jadi mungkin ada teka-teki sepotong bahwa kita belum melihat belum tapi itu menanggapi keystrokes, untuk hal-hal yang aku memukul pada keyboard. 

Jadi mungkin ada beberapa jenis blok yang mengatakan, jika kunci sama up, kemudian melakukan sesuatu dengan Scratch-- mungkin memindahkannya 10 langkah cara ini. Jika ditekan ditekan, bergerak 10 langkah cara ini, atau tombol kiri, bergerak 10 langkah cara ini, 10 langkah itu. Aku sudah jelas berubah kucing menjadi katak. Jadi itu hanya mana kostum, panggilan Scratch pengubah kami hanya mengimpor gambar katak. 

Tapi apa lagi yang terjadi? Apa baris lain dari kode, apa potongan puzzle lainnya melakukan Blake, mengajar sesama, digunakan dalam program ini, rupanya? Apa yang membuat segalanya move-- apa pemrograman membangun? 

Gerak, sure-- sehingga bergerak blok, pasti. Dan apa itu blok bergerak dalam, kemungkinan besar? Ya, semacam lingkaran, mungkin selamanya memblokir, mungkin mengulang block-- ulangi sampai blok. Dan itulah yang membuat log dan bantalan lily dan segala sesuatu yang lain bergerak bolak-balik. Ini hanya terjadi tanpa henti. 

Mengapa beberapa mobil bergerak lebih cepat dari yang lain? Apa yang berbeda tentang program-program tersebut? Ya, mungkin beberapa dari mereka mengambil langkah lagi sekaligus dan beberapa dari mereka langkah-langkah yang lebih sedikit sekaligus. Dan efek visual cepat dibandingkan lambat. 

Apa yang Anda pikir terjadi? Ketika aku katak saya semua jalan di seberang jalan dan sungai ke lily pad, sesuatu penting terjadi. Apa yang terjadi segera setelah saya melakukan itu? Itu berhenti. katak yang berhenti, dan Aku punya katak kedua. Jadi apa yang membangun harus digunakan di sana, fitur apa? 

Ya, jadi ada semacam "Jika" kondisi di sana, juga. Dan ternyata out-- kita tidak melihat ini-- tapi ada blok lain di sana yang bisa mengatakan, jika Anda menyentuh hal lain pada layar, jika Anda menyentuh pad lily, "kemudian." Dan kemudian saat itulah kita membuat katak kedua muncul. Jadi meskipun game ini tentu sangat tanggal, meskipun pada pandangan pertama ada begitu banyak terjadi Blake on-- dan tidak cambuk ini dalam dua menit, mungkin membawanya beberapa jam untuk membuat game ini berdasarkan memori atau video nya versi tahun kemarin itu. Tapi semua hal-hal kecil akan pada layar dalam isolasi mendidih ke ini sangat sederhana gerakan atau pernyataan constructs-- seperti yang sudah kita bahas, loop dan kondisi, dan itu saja. Ada beberapa fitur yang lebih menarik lainnya. Beberapa dari mereka adalah murni estetika atau akustik, seperti suara saya hanya bermain dengan. Tetapi untuk sebagian besar, Anda memiliki dalam bahasa ini, Scratch, semua fundamental bangunan blok yang Anda ada di C, Java, JavaScript, PHP, Ruby, Python, dan sejumlah bahasa lain. Pertanyaan tentang Scratch? Baiklah. Jadi kita tidak akan menyelam lebih dalam ke Scratch, meskipun kau selamat datang akhir pekan ini, terutama jika Anda memiliki anak-anak atau keponakan dan semacamnya, untuk memperkenalkan mereka kepada Scratch. Ini sebenarnya sangat lucu lingkungan dengan, sebagai penulisnya mengatakan, langit-langit yang sangat tinggi. Meskipun kami mulai dengan sangat detail tingkat rendah, Anda benar-benar dapat melakukan sedikit dengan itu, dan ini mungkin demonstrasi yang tepat. 

Tapi mari kita sekarang beralih ke beberapa lebih masalah canggih, jika Anda mau, dikenal sebagai "mencari" dan "Pemilahan," lebih umum. Kami memiliki buku telepon ini earlier-- inilah satu lagi hanya untuk discussion-- bahwa kita mampu untuk mencari lebih efisien karena dari asumsi yang signifikan. Dan hanya harus jelas, apa yang Asumsi itu saya membuat ketika mencari melalui buku telepon ini? Bahwa Mike Smith berada di buku telepon, meskipun saya akan mampu menangani skenario tanpa dia ada jika aku hanya berhenti sebelum waktunya. Buku ini abjad. Dan itu sangat murah hati asumsi, karena itu berarti someone-- Aku agak pemotongan sudut, seperti saya lebih cepat karena seseorang lain melakukan banyak kerja keras untuk saya. 

Tapi bagaimana jika telepon Buku yang unsorted? Mungkin Verizon punya malas, hanya melemparkan nama dan nomor semua orang di sana mungkin di urutan di mana mereka mendaftar untuk layanan telepon. Dan berapa banyak waktu yang dibutuhkan saya untuk menemukan seseorang seperti Mike Smith? 1.000 Halaman ponsel book-- berapa banyak halaman saya harus melihat melalui? 

Mereka semua. Anda semacam beruntung. Anda benar-benar harus melihat setiap Halaman jika buku telepon hanya acak diurutkan. Anda mungkin beruntung dan menemukan Mike pada halaman pertama, karena ia adalah pelanggan pertama untuk memesan layanan telepon. Tapi dia mungkin telah yang terakhir, juga. 

Jadi urutan acak tidak baik. Jadi misalkan kita harus mengurutkan buku telepon atau data semacam umum bahwa kita telah diberikan. Bagaimana kita bisa melakukan itu? 

Nah, biarkan aku hanya mencoba contoh sederhana di sini. Biarkan aku pergi ke depan dan melemparkan beberapa nomor di papan. Misalkan angka yang kita miliki adalah, katakanlah, empat, dua, satu, dan tiga. Dan, Ben, mengurutkan angka-angka ini bagi kita. 

Oke bagus. Bagaimana Anda melakukannya? Baiklah. Jadi mulai dengan yang terkecil nilai dan tertinggi, dan itu benar-benar intuisi yang baik. Dan menyadari kita bahwa manusia sebenarnya cukup pandai memecahkan masalah seperti ini, setidaknya ketika data yang relatif kecil. Segera setelah Anda mulai memiliki ratusan angka, ribuan nomor, jutaan nomor, Ben mungkin tidak bisa melakukannya cukup secepat itu, dengan asumsi bahwa ada kesenjangan dalam angka. Cukup mudah untuk menghitung satu juta jika tidak, memakan waktu hanya. 

Jadi algoritma kedengarannya seperti Ben digunakan sekarang adalah pencarian untuk nomor terkecil. Jadi meskipun kita manusia dapat mengambil di banyak informasi visual, komputer sebenarnya sedikit lebih terbatas. komputer hanya dapat melihat satu byte pada suatu waktu atau mungkin empat byte di time-- sebuah hari ini mungkin 8 byte pada time-- sebuah tetapi jumlah yang sangat kecil dari byte pada waktu tertentu. 

Jadi mengingat bahwa kita benar-benar memiliki empat nilai terpisah di sini- dan Anda bisa memikirkan Ben sebagai memiliki penutup mata jika ia adalah komputer seperti bahwa ia tidak bisa melihat apa-apa dari satu nomor di time-- sebuah sehingga kita umumnya akan menganggap, seperti di Bahasa Inggris, kami akan membaca dari kanan ke kiri. Jadi angka pertama Ben mungkin tampak di empat dan kemudian sangat cepat menyadari itu cukup besar number-- biarkan aku terus mencari. 

Ada dua. Tunggu sebentar. Dua lebih kecil dari empat. Aku akan ingat. Dua sekarang terkecil. Sekarang satu-- yang bahkan lebih baik. Itu bahkan lebih kecil. Aku akan melupakan dua dan hanya ingat satu sekarang. 

Dan dia bisa berhenti mencari? Yah, dia bisa berdasarkan informasi ini, tapi dia Sebaiknya pencarian yang lebih baik sisa daftar. Karena bagaimana jika nol berada dalam daftar? Bagaimana jika negatif satu berada di daftar? Dia hanya tahu bahwa jawabannya adalah benar jika dia secara mendalam memeriksa seluruh daftar. Jadi kita melihat sisa ini. Three-- itu membuang-buang waktu. Mendapat beruntung, tapi aku masih benar untuk melakukannya. Dan sekarang dia mungkin dipilih jumlah terkecil dan hanya menaruhnya di awal dari daftar, seperti yang saya akan lakukan di sini. Sekarang apa yang Anda lakukan selanjutnya, meskipun Anda tidak berpikir tentang hal itu hampir sejauh ini? Ulangi proses, jadi semacam lingkaran. Ada ide akrab. Jadi di sini adalah empat. Itulah saat yang terkecil. Itu kandidat. Tidak lagi. Sekarang aku sudah melihat dua. Itulah elemen terkecil berikutnya. Three-- itu tidak kecil, sehingga sekarang Ben dapat mencabut dua. 

Dan sekarang kita ulangi proses, dan tentu saja tiga akan ditarik keluar berikutnya. Ulangi proses. Empat akan ditarik keluar. Dan sekarang kita keluar dari nomor, sehingga daftar harus diurutkan. 

Dan memang, ini adalah algoritma formal. Seorang ilmuwan komputer akan menyebutnya "selection sort," ide menjadi semacam sebuah daftar iteratively-- lagi dan lagi dan lagi memilih jumlah terkecil. Dan apa yang baik tentang itu adalah itu hanya begitu darn intuitif. Ini sangat sederhana. Dan Anda dapat mengulangi hal yang sama operasi lagi dan lagi. Itu mudah. 

Dalam hal ini adalah cepat, tapi berapa lama waktu yang benar-benar mengambil? Mari kita membuatnya tampak dan merasa sedikit lebih membosankan. Jadi satu, dua, tiga, empat, lima enam, tujuh, delapan, sembilan, 10, 11, 12, 13, 14, 15, 16-- jumlah sewenang-wenang. Aku hanya ingin lebih ini waktu hanya empat. Jadi jika saya punya keseluruhan sekelompok angka sekarang-- itu bahkan tidak peduli apa yang mereka are-- mari berpikir tentang apa ini algoritma benar-benar seperti. 

Misalkan ada nomor di sana. Sekali lagi, tidak peduli apa mereka, tapi mereka secara acak. Saya menerapkan algoritma Ben. Saya harus memilih nomor terkecil. Apa yang saya lakukan? Dan aku akan secara fisik melakukannya kali ini untuk bertindak keluar. Melihat, mencari, mencari, mencari, mencari. Hanya pada saat saya sampai ke akhir daftar bisa Saya menyadari terkecil Jumlah itu dua kali ini. Salah satu yang tidak ada dalam daftar. Jadi saya meletakkan dua. 

Apa yang harus saya lakukan selanjutnya? Melihat, mencari, mencari, mencari. Sekarang saya menemukan nomor tujuh, karena ada kesenjangan dalam Numbers ini tapi hanya sewenang-wenang. Baiklah. Jadi sekarang aku bisa meletakkan tujuh. Mencari mencari, mencari. 

Sekarang Aku menduga, dari Tentu saja, yang Ben tidak memiliki RAM ekstra, ekstra memori, karena, tentu saja, Aku sedang melihat nomor yang sama. Tentunya saya bisa ingat semua angka-angka, dan itu benar-benar benar. Tapi jika Ben ingat semua nomor dia melihat, dia belum benar-benar membuat kemajuan mendasar karena dia sudah memiliki kemampuan untuk mencari melalui nomor di papan tulis. Mengingat semua nomor tidak membantu, karena ia masih bisa sebagai komputer hanya melihat, kita sudah mengatakan, satu nomor pada suatu waktu. Jadi tidak ada semacam curang ada yang Anda dapat memanfaatkan. 

Jadi dalam kenyataannya, seperti yang saya terus mencari daftar, Aku benar-benar harus hanya terus bolak-balik melalui itu, mencabut jumlah terkecil berikutnya. Dan seperti yang Anda jenis menyimpulkan dari gerakan-gerakan konyol saya, ini hanya akan sangat membosankan sangat cepat, dan saya tampaknya akan kembali dan balik, bolak-balik sedikit. Sekarang untuk menjadi adil, saya tidak harus pergi cukup, baik, mari kita see-- untuk menjadi adil, Saya tidak harus berjalan cukup karena banyak langkah setiap kali. Karena, tentu saja, seperti yang saya pilih nomor dari daftar, daftar tersisa semakin pendek. 

Dan mari kita berpikir tentang berapa banyak langkah Aku benar-benar traipsing melalui setiap kali. Dalam situasi pertama kami memiliki 16 angka, dan maximally-- mari kita melakukan ini untuk discussion-- sebuah Aku harus melihat melalui 16 nomor untuk menemukan terkecil. Tapi setelah saya dicabut jumlah terkecil, bagaimana panjang adalah daftar yang tersisa, tentu saja? Hanya 15. Jadi berapa banyak angka lakukan Ben atau saya harus untuk melihat melalui kedua kalinya? 15, hanya untuk pergi dan menemukan terkecil. Tapi sekarang, tentu saja, daftar ini, juga, lebih kecil daripada sebelumnya. Jadi berapa banyak langkah apakah saya harus mengambil waktu berikutnya? 14 dan kemudian 13 dan kemudian 12, ditambah dot, dot, dot, sampai aku pergi dengan hanya satu. Jadi sekarang seorang ilmuwan komputer akan bertanya, baik, apa yang semua sama? Ini sebenarnya sama dengan beberapa beton nomor yang kita bisa pasti melakukan deret hitung, tapi kami ingin berbicara tentang efisiensi algoritma sedikit lebih dirumuskan secara, independen dari berapa lama daftar adalah. 

Dan sehingga Anda tahu apa? Ini adalah 16, tapi seperti saya katakan sebelumnya, mari kita sebut ukuran masalah n, di mana n adalah beberapa nomor. Mungkin 16, mungkin itu tiga, mungkin itu satu juta. Saya tidak tahu. Saya tidak peduli. Apa yang saya inginkan adalah formula yang saya bisa gunakan untuk membandingkan algoritma ini terhadap algoritma lain bahwa seseorang mungkin mengklaim lebih baik atau lebih buruk. 

Jadi ternyata, dan saya hanya tahu ini dari sekolah dasar, bahwa ini benar-benar bekerja untuk sama Hal seperti n lebih n ditambah satu lebih dari dua. Dan ini terjadi untuk sama, dari Tentu saja, n kuadrat ditambah n lebih dari dua. Jadi jika saya ingin rumus untuk berapa banyak langkah terlibat dalam melihat semua dari angka-angka lagi dan lagi dan lagi dan lagi, saya akan mengatakan itu n kuadrat ditambah n lebih dari dua. Tapi kau tahu apa? Ini hanya tampak berantakan. Saya hanya benar-benar ingin pengertian umum dari hal. Dan Anda mungkin ingat dari SMA yang ada adalah gagasan dari istilah urutan tertinggi. Manakah dari istilah-istilah ini, n kuadrat, n, atau setengah, memiliki dampak yang paling dari waktu ke waktu? N lebih besar mendapat, yang dari hal-hal ini yang paling? 

Dengan kata lain, jika saya pasang dalam satu juta, n kuadrat akan menjadi yang paling mungkin faktor mendominasi, karena satu juta kali sendiri adalah jauh lebih besar dari ditambah satu tambahan juta. Sehingga Anda tahu apa? Ini darn seperti besar nomor jika Anda persegi nomor. Ini tidak benar-benar peduli. Kami hanya akan lintas yang keluar dan melupakannya. Dan seorang ilmuwan komputer akan mengatakan bahwa efisiensi algoritma ini adalah di urutan n squared-- Maksudku benar-benar perkiraan. Hal ini semacam kasar n kuadrat. Seiring waktu, semakin besar dan n lebih besar mendapat, ini adalah estimasi yang baik untuk apa efisiensi atau kurangnya efisiensi algoritma ini sebenarnya. Dan saya berasal itu, tentu saja, dari benar-benar melakukan matematika. Tapi sekarang aku hanya melambaikan tangan saya, karena saya hanya menginginkan sensasi umum algoritma ini. 

Jadi dengan menggunakan logika yang sama, sementara itu, mari kita pertimbangkan algoritma lain kita sudah melihat at-- pencarian linear. Ketika saya sedang mencari untuk book-- ponsel tidak menyortir itu, mencari melalui book-- ponsel kita terus mengatakan bahwa itu 1.000 langkah, atau 500 langkah. Tapi mari kita generalisasi itu. Jika ada n halaman di buku telepon, apa waktu berjalan atau efisiensi pencarian linear? Ini pada urutan berapa banyak langkah untuk menemukan Mike Smith menggunakan pencarian linear, yang algoritma pertama, atau bahkan kedua? 

Dalam kasus terburuk, Mike adalah pada akhir buku ini. Jadi jika buku telepon memiliki 1.000 halaman, kita mengatakan terakhir kali, dalam kasus terburuk, mungkin butuh kira-kira berapa banyak halaman untuk menemukan Mike? Seperti 1.000. Ini adalah batas atas. Ini adalah situasi yang paling buruk. Tapi sekali lagi, kita bergerak menjauh dari angka-angka seperti 1000 sekarang. Ini hanya n. 

Jadi apa kesimpulan logis? Menemukan Mike di telepon buku yang memiliki halaman n mungkin mengambil, dalam kasus terburuk, berapa banyak langkah pada urutan n? Dan memang komputer ilmuwan akan mengatakan bahwa waktu berjalan, atau kinerja atau efisiensi atau inefisiensi, dari sebuah algoritma seperti pencarian linear adalah di urutan n. Dan kita dapat menerapkan hal yang sama logika persimpangan sesuatu karena saya hanya melakukan yang kedua algoritma kami telah dengan buku telepon, di mana kami pergi dua halaman pada satu waktu. 

Jadi 1.000 halaman buku telepon mungkin membawa kita 500 halaman bergantian, ditambah satu jika kita melipatgandakan kembali sedikit. Jadi jika buku telepon memiliki halaman n, tapi kita lakukan dua halaman pada satu waktu, itulah kira-kira apa? N lebih dari dua, sehingga seperti n lebih dari dua. Tapi saya membuat klaim saat yang lalu bahwa n lebih two-- itulah jenis yang sama hanya n. Ini hanya faktor konstan, ilmuwan komputer akan mengatakan. Mari kita hanya fokus pada variabel, really-- variabel terbesar dalam persamaan. 

Jadi linear pencarian, baik yang dilakukan salah satu halaman pada satu waktu atau dua halaman pada satu waktu, adalah semacam dasarnya sama. Ini masih di urutan n. Tapi aku mengaku dengan gambar saya sebelumnya bahwa algoritma ketiga tidak linear. Itu bukan garis lurus. Itu garis melengkung, dan formula aljabar ada apa? Log dari n-- sehingga log basis dua dari n. Dan kita tidak perlu pergi ke terlalu banyak detail pada logaritma hari ini, tetapi kebanyakan ilmuwan komputer tidak akan bahkan memberitahu Anda apa dasar adalah. Karena itu semua hanya faktor konstan, sehingga untuk berbicara, hanya perbedaan numerik sedikit. Dan ini akan menjadi sangat umum Cara untuk komputer terutama resmi para ilmuwan di papan atau programmer di sebuah papan putih sebenarnya alasan yang algoritma mereka akan menggunakan atau apa efisiensi algoritma mereka. 

Dan ini belum tentu sesuatu Anda mendiskusikan secara rinci besar, tapi seorang programmer yang baik adalah seseorang yang memiliki solid, latar belakang formal. Dia mampu berbicara dengan Anda dalam jenis cara dan benar-benar membuat argumen kualitatif mengapa satu algoritma atau salah satu bagian dari perangkat lunak unggul dalam beberapa cara lain. Karena Anda bisa pasti hanya menjalankan program satu orang dan menghitung jumlah detik dibutuhkan untuk menyortir beberapa nomor, dan Anda dapat menjalankan beberapa Program orang lain dan menghitung jumlah detik dibutuhkan. Tapi ini adalah cara yang lebih umum yang Anda dapat menggunakan untuk menganalisis algoritma, jika Anda mau, hanya pada kertas atau hanya secara lisan. Tanpa menjalankannya, tanpa bahkan mencoba sampel input, Anda hanya dapat alasan melalui itu. Dan dengan mempekerjakan pengembang atau jika memiliki dia semacam berdebat untuk Anda mengapa algoritma mereka, rahasia mereka saus untuk mencari miliaran halaman web untuk Anda perusahaan lebih baik, ini adalah jenis argumen mereka idealnya harus mampu membuat. Atau setidaknya ini hal-hal yang yang akan datang dalam diskusi, di setidaknya dalam diskusi yang sangat formal. Baiklah. Jadi Ben diusulkan sesuatu disebut pilihan semacam. Tapi aku akan mengusulkan bahwa ada cara lain untuk melakukan hal ini, juga. Apa yang saya benar-benar tidak suka tentang algoritma Ben adalah bahwa ia terus berjalan, atau setelah saya berjalan, bolak-balik dan bolak-balik dan bolak-balik. Bagaimana jika sebaliknya saya melakukan sesuatu seperti angka-angka ini di sini dan saya hanya berurusan dengan masing-masing jumlah pada gilirannya karena saya diberikan itu? 

Dengan kata lain, inilah daftar nomor. Empat, satu, tiga, dua. Dan aku akan melakukan hal berikut. Aku akan memasukkan nomor di mana mereka berada agak dari memilih mereka satu per satu. Dengan kata lain, inilah nomor empat. 

Berikut daftar asli saya. Dan aku akan menjaga dasarnya daftar baru di sini. Jadi ini adalah daftar tua. Ini adalah daftar baru. Aku melihat nomor empat pertama. daftar baru saya awalnya kosong, sehingga sepele kasus bahwa empat kini daftar berbagai macam. Aku hanya mengambil jumlah aku diberi, dan aku memasukkannya dalam daftar baru saya. 

Apakah daftar baru ini diurutkan? Ya. Itu bodoh karena hanya ada satu elemen, tapi itu benar-benar diurutkan. Tidak ada yang keluar dari tempat. Ini lebih menarik, algoritma ini, ketika saya pindah ke langkah berikutnya. 

Sekarang aku punya satu. Jadi satu, tentu saja, termasuk di awal atau akhir daftar baru ini? Awal mula. Jadi saya harus melakukan beberapa pekerjaan sekarang. Saya telah mengambil beberapa kebebasan dengan spidol saya dengan hanya menggambar hal mana aku ingin mereka, tapi itu tidak benar-benar akurat dalam komputer. Sebuah komputer, seperti yang kita tahu, memiliki RAM, atau Random Access Memory, dan itu salah satu byte dan byte lain dan byte lain. Dan jika Anda memiliki gigabyte RAM, Anda memiliki satu miliar byte, tapi mereka secara fisik dalam satu lokasi. Anda tidak bisa hanya memindahkan barang di sekitar dengan menggambar di papan di mana pun Anda inginkan. Jadi jika daftar baru saya memiliki empat lokasi di memori, sayangnya empat adalah sudah di tempat yang salah. 

Jadi untuk memasukkan nomor satu Aku tidak bisa hanya menarik di sini. lokasi memori ini tidak ada. Itu akan kecurangan, dan saya telah kecurangan pictorially selama beberapa menit sini. Jadi benar-benar, jika saya ingin menempatkan satu di sini, Aku harus menyalin empat sementara dan kemudian menempatkan satu di sana. 

Itu baik-baik saja, itu benar, yang secara teknis mungkin, tapi menyadari itu bekerja ekstra. Aku tidak hanya menempatkan angka di tempat. Saya pertama kali harus memindahkan nomor, kemudian meletakkannya di tempat, jadi aku agak dua kali lipat jumlah saya bekerja. Jadi ingatlah bahwa dalam pikiran. 

Tapi sekarang saya sudah selesai dengan elemen ini. Sekarang saya ingin meraih nomor tiga. Di mana, tentu saja, apakah itu milik? Diantara. Saya tidak bisa menipu lagi dan hanya meletakkannya di sana, karena, sekali lagi, memori ini adalah di lokasi fisik. Jadi saya harus menyalin empat dan menempatkan tiga di sini. Bukan masalah besar. Ini hanya satu langkah ekstra again-- terasa sangat murah. 

Tapi sekarang aku pindah ke dua. Kedua, tentu saja, berada di sini. Sekarang Anda mulai melihat bagaimana pekerjaan dapat menumpuk. Sekarang apa yang harus saya lakukan? Ya, saya harus memindahkan empat, Saya kemudian harus menyalin tiga, dan sekarang saya bisa memasukkan dua. Dan menangkap dengan ini algoritma, cukup menarik, adalah bahwa misalkan kita memiliki lebih ekstrim kasus di mana itu katakanlah delapan, tujuh, enam, lima, empat, tiga, dua, satu. Hal ini, dalam banyak konteks, skenario terburuk, karena hal darn secara harfiah mundur. 

Ini tidak benar-benar mempengaruhi algoritma Ben, karena dalam pemilihan Ben semacam dia akan terus akan bolak-balik melalui daftar. Dan karena ia selalu mencari melalui daftar yang tersisa utuh, tidak apa-apa di mana unsur-unsur yang. Tapi dalam kasus ini dengan Memasukkan saya approach-- mari kita coba ini. 

Jadi satu, dua, tiga, empat, lima, enam, tujuh, delapan. Satu dua tiga empat, lima, enam, tujuh, delapan. Aku akan mengambil delapan, dan di mana saya menaruhnya? Nah, di awal daftar saya, karena daftar baru ini diurutkan. Dan saya coret. 

Di mana saya menempatkan tujuh? Darn it. Perlu pergi ke sana, jadi Aku harus melakukan beberapa menyalin. Dan sekarang tujuh goes here. Sekarang saya beralih ke enam. Sekarang bahkan lebih banyak pekerjaan. 

Delapan harus pergi di sini. Tujuh harus pergi di sini. Sekarang enam bisa pergi di sini. Sekarang saya ambil lima. Sekarang delapan harus pergi di sini, tujuh harus pergi di sini, enam harus pergi di sini, dan sekarang lima dan ulangi. Dan aku cukup banyak bergerak terus-menerus. 

Jadi pada akhirnya, algorithm-- ini kita akan menyebutnya penyisipan sort-- sebenarnya memiliki banyak pekerjaan, juga. Hanya saja yang berbeda jenis pekerjaan dari Ben. karya Ben telah saya akan bolak-balik sepanjang waktu, memilih berikutnya terkecil Unsur lagi dan lagi. Jadi itu semacam ini sangat visual pekerjaan. 

Algoritma ini lain, yang masih correct-- itu akan mendapatkan pekerjaan yang done-- hanya mengubah jumlah pekerjaan. Sepertinya awalnya Anda menghemat, karena Anda hanya berurusan dengan setiap elemen depan tanpa berjalan semua cara melalui daftar seperti Ben adalah. Tapi masalahnya adalah, terutama dalam kasus gila di mana itu semua mundur, Anda hanya jenis menunda kerja keras sampai Anda harus memperbaiki kesalahan-kesalahan Anda. 

Dan jadi jika Anda bisa membayangkan ini delapan dan tujuh dan enam dan lima dan kemudian empat dan tiga dan dua bergerak jalan melalui daftar, kami baru saja mengubah jenis pekerjaan yang kita lakukan. Alih-alih melakukan itu di mulai dari iterasi saya, Aku hanya melakukannya di akhir setiap iterasi. Jadi ternyata bahwa algoritma ini, juga, umumnya disebut insertion sort, juga di urutan n kuadrat. Ini sebenarnya tidak lebih baik, tidak lebih baik sama sekali. 

Namun, ada pendekatan ketiga Saya akan mendorong kita untuk mempertimbangkan, yang ini. Jadi misalkan daftar saya, untuk kesederhanaan lagi, empat, satu, tiga, two-- hanya empat angka. Ben memiliki intuisi yang baik, intuisi manusia yang baik sebelumnya, dimana kita tetap seluruh daftar eventually-- insertion sort. Aku membujuk kita bersama. Tapi mari kita mempertimbangkan Cara paling mudah untuk memperbaiki daftar ini. 

Daftar ini tidak diurutkan. Mengapa? Dalam bahasa Inggris, menjelaskan mengapa itu tidak benar-benar diurutkan. Apa artinya tidak akan diurutkan? 

SISWA: Ini tidak berurutan. 

DAVID Malan: Tidak berurutan. Berikan saya contoh. 

SISWA: Menempatkan mereka dalam rangka. 

DAVID Malan: OK. Memberi saya contoh yang lebih spesifik. 

SISWA: Ascending order. DAVID Malan: Tidak urutan menaik. Lebih tepat. Aku tidak tahu apa yang Anda maksud dengan naik. Apa yang salah? 

SISWA: The terkecil dari nomor tidak di ruang pertama. 

DAVID Malan: jumlah terkecil ini tidak di ruang pertama. Lebih spesifik. Aku mulai menangkap. Kami menghitung, tapi apa rusak di sini? 

SISWA: urutan numerik. DAVID Malan: urutan numerik. disukai setiap orang menjaga itu di sini-tingkat yang sangat tinggi. Hanya harfiah katakan padaku apa salah seperti kekuatan lima tahun. 

SISWA: Ditambah satu. 

DAVID Malan: Apa itu? 

SISWA: Ditambah satu. 

DAVID Malan: Apa maksudmu ditambah satu? Beri aku berusia lima tahun yang berbeda. Apa yang salah, ibu? Apa yang salah, ayah? Apa maksudmu ini tidak diurutkan? 

SISWA: Ini bukan tempat yang tepat. 

DAVID Malan: Apa tidak di tempat yang tepat? 

SISWA: Empat. DAVID Malan: OK, baik. Jadi empat tidak mana seharusnya. Secara khusus, apakah ini benar? Empat dan satu, yang pertama dua nomor yang saya lihat. Apakah ini benar? Tidak, mereka rusak, kan? Bahkan, pikir sekarang tentang komputer, juga. Hanya dapat melihat mungkin satu, mungkin dua hal di once-- dan benar-benar hanya satu hal pada suatu waktu, tetapi setidaknya bisa melihat satu hal maka Hal berikutnya tepat di sebelah itu. 

Jadi apakah ini dalam rangka? Tentu saja tidak. Sehingga Anda tahu apa? Mengapa kita tidak mengambil bayi langkah-langkah memperbaiki masalah ini bukannya melakukan mewah ini algoritma seperti Ben, di mana dia semacam memperbaikinya dengan perulangan melalui daftar bukannya melakukan apa yang saya lakukan, di mana Aku hanya jenis tetap sebagai kita pergi? Mari kita secara harfiah memecah Gagasan urutan numerik Comes urutan, menyebutnya apa pun yang Anda want-- ke dalam perbandingan berpasangan. 

Empat dan satu. Apakah ini urutan yang benar? Jadi mari kita memperbaikinya. Satu dan empat, dan kemudian kami hanya akan menyalin itu. Baiklah, baik. Saya tetap satu dan empat. Tiga dan dua? Tidak. Biarkan kata-kata saya cocok jari-jari saya. Empat dan tiga? 

Ini bukan dalam rangka, jadi aku akan untuk melakukan satu, tiga, empat, dua. Oke bagus. Sekarang empat dan dua? Kami harus memperbaiki ini, juga. Jadi satu, tiga, dua, empat. Jadi yang diurutkan? Tidak, tapi lebih dekat ke diurutkan? 

Hal ini, karena kita tetap ini kesalahan, kita tetap kesalahan ini, dan kami tetap kesalahan ini. Jadi kita tetap tiga kesalahan bisa dibilang. Masih tidak benar-benar terlihat diurutkan, tapi itu adalah obyektif lebih dekat dengan diurutkan karena kita tetap beberapa kesalahan-kesalahan. 

Sekarang apa yang harus saya lakukan selanjutnya? Aku agak mencapai akhir daftar. Saya tampaknya telah diperbaiki semua kesalahan, tapi tidak ada. Karena dalam kasus ini, beberapa nomor mungkin menggelegak lebih dekat ke nomor lain yang masih rusak. Jadi mari kita melakukannya lagi, dan aku akan hanya melakukannya di tempat saat ini. Satu dan tiga? Tidak apa-apa. Tiga dan dua? Tentu saja tidak ada, jadi mari kita mengubah itu. Jadi dua, tiga. Tiga dan empat? Dan sekarang mari kita hanya menjadi khususnya bertele-tele di sini. Apakah diurutkan? Anda manusia tahu itu diurutkan. 

Aku harus mencoba lagi. Jadi Olivia mengusulkan saya coba lagi. Mengapa? Karena komputer tidak memiliki kemewahan mata manusia hanya melirik back-- OK, aku sudah selesai. Bagaimana komputer menentukan bahwa daftar sekarang diurutkan? Mekanis. 

Aku harus pergi melalui sekali lagi, dan hanya jika saya tidak membuat / menemukan kesalahan yang bisa saya kemudian menyimpulkan sebagai komputer, ya, kami baik untuk pergi. Jadi satu dan dua, dua dan tiga, tiga dan empat. Sekarang saya pasti dapat mengatakan ini adalah diurutkan, karena saya tidak melakukan perubahan. Sekarang akan bug dan hanya bodoh jika saya, komputer, tanya pertanyaan-pertanyaan yang sama lagi mengharapkan jawaban yang berbeda. Seharusnya tidak terjadi. 

Dan jadi sekarang daftar diurutkan. Sayangnya, waktu berjalan dari algoritma ini juga n kuadrat. Mengapa? Karena Anda memiliki nomor n, dan di kasus terburuk Anda harus bergerak nomor n n kali karena Anda harus terus kembali untuk memeriksa dan berpotensi memperbaiki angka-angka ini. Dan kita bisa melakukan lebih analisis formal, juga. 

Jadi ini semua untuk mengatakan kami sudah tiga pendekatan yang berbeda, satu dari mereka segera intuitif dari kelelawar dari Ben penyisipan saya sarankan semacam untuk yang satu ini di mana Anda jenis melupakan hutan untuk pohon awalnya. Tapi kemudian jika Anda mengambil langkah mundur, voila, kami tetap gagasan penyortiran. Jadi ini, berani mengatakan, tingkat yang lebih rendah mungkin dari beberapa orang lain algoritma, tetapi mari kita melihat apakah kita tidak dapat membayangkan ini dengan cara ini. 

Jadi ini adalah beberapa bagus software bahwa seseorang menulis menggunakan warna-warni bar itu akan melakukan hal berikut untuk kita. Setiap bar ini mewakili angka. Taller bar, lebih besar nomor, kecil bar, semakin kecil angkanya. Jadi idealnya kita ingin piramida bagus di mana ia mulai kecil dan mendapat besar, dan itu berarti bahwa bar ini diurutkan. Jadi aku akan pergi ke depan dan memilih, misalnya, algoritma Ben first-- pilihan semacam. 

Dan perhatikan apa yang dilakukannya. Cara mereka telah memilih untuk memvisualisasikan algoritma ini adalah bahwa, seperti saya berjalan melalui daftar saya, Program ini berjalan melalui daftar nomor, menyoroti dalam warna pink setiap nomor yang itu melihat. Dan apa yang akan terjadi sekarang? 

Jumlah terkecil yang Saya atau Ben ditemukan tiba-tiba akan pindah ke awal daftar. Dan pemberitahuan mereka lakukan mengusir jumlah yang ada di sana, dan itu baik-baik saja. Aku tidak bisa masuk ke tingkat detail. Tapi kita perlu menempatkan jumlah itu di suatu tempat, jadi kami hanya pindah ke tempat terbuka yang telah dibuat. Jadi aku akan mempercepat ini up, karena jika tidak menjadi sangat membosankan cepat. Animasi speed-- ada kita pergi. Prinsip jadi sekarang sama Saya menerapkan, tetapi Anda bisa mulai merasakan algoritma, jika Anda akan, atau melihatnya sedikit lebih jelas. Dan algoritma ini memiliki efek memilih elemen terkecil berikutnya, sehingga Anda akan mulai melihatnya jalan sampai di sebelah kiri. Dan pada setiap iterasi, seperti yang saya diusulkan, itu tidak sedikit kerja kurang. Tidak perlu pergi jauh-jauh kembali ke ujung kiri daftar, karena sudah tahu mereka diurutkan. Jadi jenis rasanya seperti itu mempercepat, meskipun setiap langkah adalah mengambil jumlah waktu yang sama. Hanya ada sedikit langkah yang tersisa. Dan sekarang Anda dapat jenis merasakan algoritma membersihkan akhir itu, dan memang sekarang sudah diurutkan. 

Jadi insertion sort adalah semua dilakukan. Aku harus kembali mengacak array. Dan perhatikan aku hanya bisa terus mengacak itu, dan kita akan mendapatkan perkiraan pendekatan yang sama, insertion sort. Mari saya memperlambatnya di sini. Mari kita mulai yang lebih. Berhenti. 

Mari kita melewatkan empat. Di sana kami pergi. Mengacak array yang mereka. Dan di sini kita go-- insertion sort. Bermain. Perhatikan bahwa itu berurusan dengan masing-masing Unsur itu pertemuan langsung, tetapi jika itu milik di salah tempat pemberitahuan semua pekerjaan yang harus terjadi. Kami harus terus bergeser lebih dan lebih elemen untuk membuat ruang untuk satu kami ingin menempatkan di tempat. 

Jadi kita fokus pada ujung kiri dari daftar saja. Perhatikan kita bahkan belum tampak at-- kami belum disorot dalam apa pun warna pink ke kanan. Kami hanya berurusan dengan masalah seperti yang kita pergi, tapi kami menciptakan banyak bekerja untuk diri kita sendiri masih. Dan jadi jika kita mempercepat ini sekarang pergi ke selesai, itu memiliki rasa yang berbeda untuk itu memang. Ini hanya berfokus pada ujung kiri tapi melakukan lebih banyak pekerjaan sedikit sebagai needed-- jenis hal smoothing lebih, memperbaiki hal-hal, tapi berurusan akhirnya dengan setiap elemen satu per satu sampai kita mendapatkan the-- baik, kita semua tahu bagaimana ini akan berakhir, jadi sedikit underwhelming mungkin. 

Tapi daftar di end-- yang spoiler-- akan diurutkan. Jadi mari kita lihat satu yang terakhir. Kita tidak bisa hanya melewatkan sekarang. Kita sudah hampir sampai. Dua untuk pergi, satu untuk pergi. Dan voila. Sangat baik. 

Jadi sekarang mari kita lakukan satu yang terakhir, re-mengacak dengan bubble sort. Dan perhatikan di sini, terutama jika saya lambat bawah, hal ini terus menukik melalui. Tetapi melihat itu hanya membuat berpasangan semacam comparisons-- solusi lokal. Tapi begitu kita sampai akhir daftar dalam warna pink, apa yang akan harus terjadi lagi? Ya, itu akan harus mulai dari awal, karena hanya kesalahan berpasangan tetap. Dan yang mungkin telah mengungkapkan namun orang lain. Dan jadi jika Anda mempercepat hal ini, Anda akan melihat bahwa, banyak seperti namanya, lebih kecil elements-- atau lebih tepatnya, yang elements-- besar mulai gelembung ke atas, jika Anda mau. Dan unsur-unsur yang lebih kecil mulai gelembung ke kiri. Dan memang, itu semacam efek visual juga. Dan jadi ini akan berakhir menyelesaikan dalam cara yang sangat mirip, juga. 

Kami tidak perlu memikirkan pada satu ini. Mari saya buka ini sekarang juga. Ada beberapa algoritma pengurutan lainnya di dunia, beberapa di antaranya ditangkap di sini. Dan terutama untuk pelajar yang tidak tentu visual atau matematika, seperti yang kita lakukan sebelumnya, kita bisa juga melakukan ini audially jika kita kaitkan suara dengan ini. Dan hanya untuk bersenang-senang, di sini adalah beberapa algoritma yang berbeda, dan salah satu dari mereka secara khusus Anda akan melihat disebut "merge sort." 

Hal ini sebenarnya fundamental algoritma yang lebih baik, sehingga menggabungkan semacam, salah satu yang Anda lihat, tidak urutan n kuadrat. Ini pada urutan n kali log dari n, yang sebenarnya lebih kecil dan dengan demikian lebih cepat dari tiga lainnya. Dan ada beberapa lainnya yang konyol bahwa kita akan melihat. 

Jadi di sini kita pergi dengan beberapa suara. Ini adalah insertion sort, sehingga sekali lagi itu hanya berurusan dengan elemen karena mereka datang. Ini adalah semacam gelembung, sehingga mempertimbangkan mereka pasang pada suatu waktu. Dan lagi, elemen terbesar yang menggelegak ke atas. 

Selanjutnya pilihan semacam. Ini adalah algoritma Ben, di mana lagi dia memilih iteratif elemen terkecil berikutnya. Dan lagi, sekarang Anda dapat benar-benar mendengar bahwa itu mempercepat tetapi hanya sejauh seperti yang dilakukannya kurang dan kurang bekerja pada setiap iterasi. Ini adalah lebih cepat satu, menggabungkan semacam, yang menyortir cluster nomor bersama-sama dan kemudian menggabungkan mereka. Jadi look-- kiri setengah sudah diurutkan. 

Sekarang itu memilah bagian kanan, dan sekarang itu akan menggabungkan mereka menjadi satu. Ini adalah sesuatu yang disebut "Gnome macam." Dan Anda dapat jenis melihat bahwa itu akan bolak-balik, memperbaiki kerja sedikit di sini dan ada sebelum melanjutkan ke pekerjaan baru. Dan hanya itu. Ada semacam lain, yang benar-benar hanya untuk tujuan akademis, disebut "semacam bodoh," yang mengambil data Anda, memilah secara acak, dan kemudian memeriksa apakah itu disortir. Dan jika tidak, itu kembali macam itu acak, memeriksa apakah itu diurutkan, dan jika tidak mengulangi. Dan dalam teori, probabilistically ini akan menyelesaikan, tapi setelah sedikit waktu. Ini bukan yang paling efisien algoritma. Jadi pertanyaan pada mereka algoritma tertentu atau apapun terkait di sana, juga? 

Nah, sekarang mari kita menggoda terpisah apa semua garis ini bahwa saya telah menggambar dan apa yang saya mengasumsikan komputer dapat melakukan di bawah tenda. Saya berpendapat bahwa semua angka-angka ini Aku terus drawing-- mereka butuhkan untuk mendapatkan disimpan di suatu tempat di memori. Kami akan menyingkirkan orang ini sekarang juga. 

Jadi sepotong memori dalam computer-- sehingga RAM DIMM adalah apa yang kita mencari kemarin, dual inline memory module-- terlihat seperti ini. Dan masing-masing chip hitam kecil beberapa jumlah byte, biasanya. Dan kemudian pin emas seperti kabel yang terhubung ke komputer, dan papan hijau silikon hanya apa yang membuat segala sesuatu bersama-sama. Jadi, apa ini benar-benar berarti? Jika Aku agak menarik gambar yang sama ini, mari kita misalkan untuk kesederhanaan bahwa DIMM ini, dual inline memory module, adalah salah satu gigabyte RAM, satu gigabyte memori, yang adalah berapa banyak byte Total? Satu gigabyte adalah berapa banyak byte? Lebih dari itu. 1124 adalah kilo, 1000. Mega juta. Giga adalah miliar. 

Apakah saya berbohong? Dapatkah kita bahkan membaca label? Ini sebenarnya 128 gigabyte, sehingga lebih. Tapi kita akan berpura-pura ini adalah salah satu gigabyte. Jadi itu berarti ada satu miliar byte memori yang tersedia untuk saya atau 8 miliar bit, tapi kami akan berbicara dalam hal bytes sekarang, bergerak kedepan. 

Jadi apa itu artinya ini satu byte, ini adalah byte lain, ini adalah byte lain, dan jika kita benar-benar ingin untuk lebih spesifik kita harus menggambar miliar kotak kecil. Tapi apa artinya? Nah, biarkan aku hanya tampilannya di atas gambar ini. Jika saya punya sesuatu yang tampak seperti sekarang ini, yang empat byte. 

Dan jadi saya bisa menempatkan empat angka di sini. Satu dua tiga empat. Atau aku bisa meletakkan empat huruf atau simbol. "Hei!" bisa pergi di sana, karena masing-masing huruf, kita bahas sebelumnya, bisa diwakili dengan delapan bit atau ASCII atau byte. Jadi dengan kata lain, Anda bisa menempatkan 8 miliar hal dalam ini satu tongkat memori. Sekarang apa artinya untuk meletakkan segala sesuatu kembali untuk kembali ke belakang dalam memori seperti ini? Ini adalah apa yang seorang programmer sebut sebuah "array." Dalam program komputer, Anda tidak berpikir tentang hardware yang mendasari, per se. Anda hanya berpikir tentang diri Anda sebagai memiliki akses ke total miliar byte, dan Anda dapat apa pun yang Anda inginkan dengan itu. Tapi untuk kenyamanan akan sangat berguna untuk menjaga hak memori Anda di samping satu sama lain seperti ini. Jadi jika saya memperbesar ini-- karena kita pasti tidak akan menggambar miliar squares-- sedikit mari kita mengira bahwa forum ini merupakan tongkat memori sekarang. Dan aku hanya akan menarik sebanyak saya penanda akhirnya memberi saya di sini. Jadi sekarang kita memiliki tongkat memori di papan yang punya satu, dua, tiga, empat, lima, enam, satu, dua, tiga, empat, lima, enam, seven-- sehingga 42 byte memori pada total layar. Terima kasih. Ya, melakukan aritmatika saya benar. Jadi 42 byte memori di sini. Jadi, apa ini benar-benar berarti? Nah, seorang programmer komputer akan benar-benar umumnya memikirkan memori ini sebagai beralamat. Dengan kata lain, setiap satu dari ini lokasi di memori, di hardware, memiliki alamat yang unik. 

Ini tidak serumit Satu Brattle Square, Cambridge, Mass., 02138. Sebaliknya, itu hanya angka. Ini adalah byte angka nol, ini adalah satu, ini adalah dua, ini adalah tiga, dan ini adalah 41. Tunggu sebentar. Saya pikir saya mengatakan 42 saat yang lalu. Aku mulai menghitung dari nol, jadi itu benar-benar benar. Sekarang kita tidak harus benar-benar menarik itu sebagai kotak, dan jika Anda menggambar sebagai grid Saya pikir hal sebenarnya mendapatkan sedikit menyesatkan. Apa programmer akan, di pikirannya sendiri, umumnya menganggap ini memori adalah seperti tape, seperti sepotong selotip yang hanya berjalan dan selamanya atau sampai Anda kehabisan memori. Jadi cara yang lebih umum untuk menarik dan hanya berpikir tentang memori akan bahwa ini adalah byte nol, satu, dua, tiga, dan kemudian dot, dot, dot. Dan Anda memiliki 42 byte seperti total, bahkan meskipun secara fisik itu mungkin benar-benar menjadi sesuatu yang lebih seperti ini. 

Jadi jika Anda sekarang memikirkan Anda memori karena ini, seperti tape, ini adalah apa yang seorang programmer lagi akan memanggil array memori. Dan ketika Anda ingin benar-benar menyimpan sesuatu dalam memori komputer, biasanya Anda lakukan toko hal back-to-back to back-to-back. Jadi kita telah berbicara tentang angka. Dan ketika saya ingin memecahkan masalah seperti empat, satu, tiga, dua, meskipun saya hanya menggambar hanya nomor empat, satu, tiga, dua di papan, komputer akan benar-benar memiliki setup ini dalam memori. 

Dan apa yang akan di sebelah dua di memori komputer? Nah, tidak ada jawaban untuk itu. Kami tidak benar-benar tahu. Dan asalkan komputer tidak membutuhkannya, itu tidak harus peduli apa yang berikutnya ke nomor itu tidak peduli. Dan ketika saya mengatakan sebelumnya bahwa komputer hanya dapat melihat satu alamat pada satu waktu, ini adalah jenis sebabnya. 

Tidak seperti rekor player dan kepala membaca hanya mampu melihat tertentu alur dalam rekor lama-sekolah fisik pada suatu waktu, sama bisa komputer berkat untuk CPU dan nya Intel set instruksi, antara yang instruksi dibaca dari memori atau menyimpan ke memory-- sebuah komputer hanya dapat melihat di satu lokasi di time-- sebuah kadang-kadang kombinasi dari mereka, tapi benar-benar hanya satu lokasi pada satu waktu. Jadi ketika kita melakukan berbagai algoritma, Saya tidak hanya menulis dalam vacuum-- empat, satu, tiga, dua. angka-angka benar-benar milik suatu tempat fisik di memori. Jadi ada sedikit kecil transistor atau beberapa jenis elektronik di bawah hood menyimpan nilai-nilai ini. 

Dan total, berapa banyak bit yang terlibat sekarang, hanya harus jelas? Jadi ini adalah empat byte, atau sekarang itu 32 bit Total. Jadi sebenarnya ada 32 nol dan yang menyusun empat hal. Bahkan ada lebih di sini, tapi lagi kita tidak peduli tentang hal itu. 

Jadi sekarang mari kita bertanya lain Pertanyaan menggunakan memori, karena pada akhirnya hari ini di varians. Tidak peduli apa yang kita lakukan dengan komputer, pada akhir hari hardware masih sama di bawah tenda. Bagaimana saya akan menyimpan kata dalam sini? Nah, sebuah kata dalam komputer seperti "Hei!" akan disimpan seperti ini. Dan jika Anda ingin lebih lama kata, Anda hanya dapat menimpa itu dan mengatakan sesuatu seperti "halo" dan toko yang di sini. 

Dan jadi di sini, juga, contiguousness ini sebenarnya keuntungan, karena komputer hanya bisa dibaca dari kanan ke kiri. Tapi inilah pertanyaan. Dalam konteks kata ini, h-e-l-l-o, tanda seru, bagaimana mungkin komputer tahu di mana Kata dimulai dan di mana kata berakhir? Dalam konteks angka, bagaimana komputer tahu berapa lama urutan angka atau dari mana dimulai? Nah, ternyata out-- dan kami tidak akan pergi terlalu banyak ke tingkat detail-- komputer memindahkan barang-barang di dalam memori harfiah dengan cara alamat ini. Jadi di komputer, jika Anda menulis kode untuk menyimpan hal-hal seperti kata-kata, apa yang Anda benar-benar lakukan adalah mengetik ekspresi yang ingat di mana di memori komputer kata-kata ini. Jadi biarkan aku melakukan sangat, contoh yang sangat sederhana. 

Aku akan pergi ke depan dan membuka program teks sederhana, dan aku akan membuat file bernama hello.c. Sebagian besar informasi ini kami tidak akan masuk ke dalam detail, tapi aku akan menulis Program dalam bahasa yang sama, C. Ini jauh lebih menakutkan, Saya berpendapat, dari Scratch, tapi itu sangat mirip dalam roh. Bahkan, keriting ini braces-- Anda bisa jenis memikirkan apa yang baru saja saya lakukan karena ini. 

Mari kita lakukan ini, benar-benar. Ketika bendera hijau diklik, melakukan hal berikut. Saya ingin mencetak "halo." Jadi ini sekarang pseudocode. Aku agak mengaburkan garis. Dalam C, bahasa ini yang saya bicarakan tentang, cetak baris ini hello benar-benar menjadi "printf" dengan beberapa tanda kurung dan semi-colon. 

Tapi itu ide yang sama persis. Dan ini sangat user-friendly "Ketika bendera hijau diklik" menjadi jauh lebih misterius "void main int." Dan ini benar-benar tidak memiliki pemetaan, jadi aku hanya akan mengabaikan itu. Tapi kurung kurawal adalah seperti potongan puzzle melengkung seperti ini. 

Jadi Anda jenis dapat dari menebak. Bahkan jika Anda tidak pernah diprogram sebelumnya, apa program ini mungkin lakukan? Mungkin mencetak halo dengan tanda seru. 

Jadi mari kita coba itu. Aku akan menyimpannya. Dan ini, sekali lagi, sangat lingkungan sekolah tua. Saya tidak bisa klik, saya tidak dapat menarik. Saya harus perintah ketik. Jadi saya ingin menjalankan program saya, sehingga Saya mungkin melakukan hal ini, seperti hello.c. Itu file aku berlari. Tapi tunggu, aku kehilangan langkah. Apa yang kita katakan adalah diperlukan langkah untuk bahasa seperti C? Saya baru saja menulis sumber kode, tapi apa yang saya butuhkan? Ya, aku butuh compiler. Jadi pada Mac saya di sini, saya memiliki program yang disebut GCC, GNU C compiler, yang memungkinkan saya untuk melakukan turn ini-- kode sumber ke dalam, kita akan menyebutnya, kode mesin. 

Dan saya bisa melihat bahwa, lagi, sebagai berikut, ini adalah nol dan satu saya hanya dibuat dari kode sumber saya, semua nol dan satu. Dan jika saya ingin menjalankan saya program-- itu terjadi disebut a.out untuk reasons-- sejarah "halo." Saya dapat menjalankannya lagi. Halo halo halo. Dan tampaknya akan bekerja. 

Tapi itu berarti suatu tempat di saya memori komputer adalah kata-kata h-e-l-l-o, tanda seru. Dan ternyata, hanya sebagai samping, apa komputer akan biasanya lakukan sehingga ia tahu mana hal memulai dan end-- itu akan menempatkan simbol khusus di sini. Dan konvensi ini adalah untuk menempatkan angka nol pada akhir kata sehingga Anda tahu di mana itu benar-benar berakhir, sehingga Anda tidak menyimpan mencetak lebih banyak dan lebih karakter dari yang Anda benar-benar berniat. 

Tapi takeaway di sini, bahkan meskipun ini cukup misterius, adalah bahwa hal itu akhirnya relatif sederhana. Anda diberi semacam tape, kosong ruang di mana Anda dapat menulis surat. Anda hanya perlu memiliki simbol khusus, seperti sewenang-wenang angka nol, untuk menempatkan pada akhir kata-kata Anda sehingga komputer tahu, oh, saya harus berhenti mencetak setelah Aku melihat tanda seru. Karena hal berikutnya ada adalah nilai ASCII dari nol, atau karakter null sebagai seseorang akan menyebutnya. Tapi ada jenis masalah di sini, dan mari kita memulihkan kembali ke nomor sejenak. Misalkan yang saya lakukan, pada kenyataannya, memiliki sebuah array angka, dan anggaplah bahwa Program saya menulis adalah seperti buku kelas untuk guru dan guru kelas. Dan program ini memungkinkan dia mengetikkan skor siswa mereka ' pada kuis. Dan anggaplah bahwa siswa mendapat 100 pada kuis pertama mereka, mungkin seperti 80 pada berikutnya, maka 75, kemudian 90 pada kuis keempat. 

Jadi pada titik ini dalam cerita, array adalah ukuran empat. Ada benar-benar lebih banyak memori di komputer, tetapi array, sehingga untuk berbicara, adalah ukuran empat. Misalkan sekarang bahwa guru ingin untuk menetapkan kuis kelima kelas. Nah, salah satu hal yang ia atau dia akan harus melakukan sekarang menyimpan nilai tambahan di sini. Tetapi jika array guru memiliki dibuat dalam program ini adalah dari ukuran untuk, salah satu masalah dengan array adalah bahwa Anda tidak bisa hanya terus menambah memori. Karena bagaimana jika bagian lain dari Program memiliki kata "hey" di sana? 

Dengan kata lain, ingatan saya bisa digunakan untuk apa saja dalam sebuah program. Dan jika di muka saya mengetik di, hey, Saya ingin masukan empat skor kuis, mereka mungkin pergi di sini dan di sini. Dan jika Anda tiba-tiba berubah pikiran kemudian dan mengatakan saya ingin kuis kelima skor, Anda tidak bisa hanya meletakkannya di mana pun Anda inginkan, karena bagaimana jika ini memori yang digunakan sesuatu else-- program lain atau beberapa fitur lain dari program tersebut bahwa Anda menjalankan? Jadi Anda harus berpikir di muka bagaimana Anda ingin menyimpan data Anda, karena sekarang Anda sudah dicat diri ke sudut digital. 

Jadi seorang guru mungkin bukan mengatakan saat menulis program untuk menyimpan nya nilai, Anda tahu apa? Saya akan meminta, saat menulis program saya, yang ingin saya nol, satu, dua, tiga, empat, lima, enam, delapan nilai Total. Jadi satu, dua, tiga, empat, lima, enam, tujuh, delapan. guru hanya dapat over-mengalokasikan memori saat menulis nya Program dan berkata, kau tahu apa? Aku tidak akan pernah menetapkan lebih dari delapan kuis di semester. Itu hanya gila. Aku tidak akan pernah mengalokasikan itu. Sehingga dengan cara ini ia memiliki fleksibilitas untuk skor toko siswa, seperti 75, 90, dan mungkin salah satu ekstra di mana siswa mendapat kredit tambahan, 105. 

Tetapi jika guru tidak pernah menggunakan tiga ruang ini, ada sebuah takeaway intuitif sini. Dia hanya membuang-buang ruang. Jadi dengan kata lain, ada ini tradeoff umum dalam pemrograman di mana Anda dapat mengalokasikan persis seperti yang banyak memori yang Anda inginkan, terbalik dari yang adalah bahwa Anda super efficient-- Anda tidak menjadi boros di all-- tapi downside yang adalah bagaimana jika Anda berubah pikiran ketika menggunakan program yang ingin Anda untuk menyimpan lebih banyak data dari yang Anda awalnya ditujukan. 

Jadi mungkin solusinya adalah, kemudian, menulis program Anda sedemikian rupa bahwa mereka menggunakan lebih banyak memori dari yang mereka benar-benar perlu. Dengan cara ini Anda tidak akan untuk lari ke masalah itu, tapi kau menjadi boros. Dan semakin banyak memori program anda menggunakan, seperti yang kita bahas kemarin, kurang memori yang tersedia untuk program lain, semakin cepat komputer Anda mungkin memperlambat turun karena memori virtual. Dan solusi yang ideal mungkin apa? 

Under-pengalokasian tampaknya buruk. Over-pengalokasian tampaknya buruk. Jadi apa yang mungkin menjadi solusi yang lebih baik? Realokasi. Lebih dinamis. Jangan memaksakan diri untuk memilih apriori, di awal, apa yang Anda inginkan. Dan tentu saja tidak over-mengalokasikan, jangan sampai Anda menjadi boros. 

Dan untuk mencapai tujuan tersebut, kami perlu membuang struktur data ini, sehingga untuk berbicara, jauh. Dan jadi apa programmer biasanya akan menggunakan adalah sesuatu yang disebut tidak Array tapi linked list. Dengan kata lain, dia akan mulai berpikir memori mereka sebagai jenis bentuk bahwa mereka dapat menarik dengan cara berikut. Jika saya ingin menyimpan satu nomor di a program-- jadi September, Saya sudah memberikan siswa saya kuis; saya ingin untuk menyimpan kuis pertama siswa, dan mereka mendapat 100 pada itu-- I Saya akan meminta komputer saya, dengan cara program saya sudah ditulis, untuk satu sepotong memori. Dan aku akan menyimpan nomor 100 di dalamnya, dan hanya itu. 

Lalu beberapa minggu kemudian ketika saya mendapatkan kuis kedua saya, dan sudah waktunya untuk mengetik dalam 90%, saya akan untuk meminta komputer, hey, komputer, dapat saya memiliki potongan lain dari memori? Ini akan memberi saya ini sepotong kosong memori. Aku akan dimasukkan ke dalam jumlah 90, tetapi dalam program saya entah bagaimana atau other-- dan kami tidak akan khawatir tentang sintaks untuk ini-- saya perlu entah bagaimana rantai hal-hal ini bersama-sama. Dan aku akan rantai mereka bersama-sama dengan apa yang tampak seperti anak panah di sini. 

Kuis ketiga yang muncul, Aku akan mengatakan, hei, komputer, memberikan potongan memori yang lain. Dan aku akan meletakkan apa pun itu, seperti 75, dan saya harus rantai ini bersama-sama sekarang entah bagaimana. kuis keempat datang, dan mungkin itu menjelang akhir semester. Dan dengan itu program saya mungkin menggunakan memori seluruh tempat, seluruh fisik. Dan hanya untuk iseng, aku akan menarik ini sebagainya quiz-- saya lupa apa itu; saya pikir mungkin 80 atau something-- cara di atas sini. 

Tapi itu baik-baik saja, karena pictorially Aku akan menarik garis ini. Dengan kata lain, dalam kenyataannya, di hardware komputer Anda, skor pertama mungkin berakhir di sini karena itu tepat di awal semester. Yang berikutnya mungkin berakhir di sini karena sedikit waktu telah berlalu dan program terus berjalan. Skor berikutnya, yang 75, mungkin di sini. Dan skor terakhir mungkin 80, yang di sini. 

Jadi dalam kenyataannya, secara fisik, mungkin ini apa memori komputer Anda terlihat seperti. Tapi ini bukan mental yang berguna paradigma untuk programmer komputer. Mengapa Anda harus peduli di mana heck data Anda berakhir? Anda hanya ingin menyimpan data. 

Ini adalah jenis seperti diskusi kita sebelumnya menggambar kubus. Mengapa Anda peduli apa sudut adalah kubus dan bagaimana Anda harus mengubah menggambar itu? Anda hanya ingin kubus. Demikian pula di sini, Anda hanya ingin buku kelas. Anda hanya ingin memikirkan ini sebagai daftar nomor. Siapa yang peduli bagaimana itu diimplementasikan dalam perangkat keras? 

Jadi abstraksi sekarang adalah gambar ini di sini. Ini adalah daftar link, sebagai programmer akan menyebutnya, sejauh Anda memiliki daftar, jelas angka. Tapi itu terkait pictorially dengan cara panah tersebut, dan semua anak panah ini are-- bawahnya tenda, jika Anda penasaran, ingat bahwa hardware fisik kita memiliki alamat nol, satu, dua, tiga, empat. Semua anak panah ini adalah seperti peta atau arah, di mana jika 90 is-- sekarang Saya harus menghitung. 

Nol, satu, dua, tiga, empat, lima, enam, tujuh. Sepertinya 90 adalah di Jumlah alamat memori tujuh. Semua anak panah ini adalah seperti memo kertas kecil yang memberi arah ke Program yang mengatakan ikuti peta ini untuk sampai ke lokasi tujuh. Dan di sana Anda akan menemukan skor kuis kedua siswa. Sementara itu, 75-- jika saya terus ini, ini adalah tujuh, delapan, sembilan, 10, 11, 12, 13, 14, 15. 

panah lain ini hanya merupakan peta ke lokasi memori 15. Tapi sekali lagi, programmer umumnya tidak tidak peduli tentang tingkat detail. Dan dalam kebanyakan setiap pemrograman bahasa hari ini, programmer bahkan tidak akan tahu di mana dalam memori angka-angka ini sebenarnya. Semua ia harus peduli adalah bahwa mereka entah bagaimana terkait bersama-sama dalam struktur data seperti ini. 

Tapi ternyata tidak untuk mendapatkan terlalu teknis. Tapi hanya karena kita mungkin bisa mampu untuk memiliki diskusi ini di sini, misalkan kita kembali masalah ini di sini array. Mari kita lihat apakah kita menyesal akan di sini. Ini adalah 100, 90, 75, dan 80. 

Ijinkan saya membuat klaim ini. Ini adalah array, dan lagi, karakteristik yang menonjol dari array adalah bahwa semua data Anda kembali ke kembali ke belakang di memory-- harfiah satu byte atau mungkin empat byte, beberapa jumlah tetap byte pergi. Dalam daftar link, yang kita mungkin menarik seperti ini, di bawah tenda yang tahu di mana itu hal ini? Bahkan tidak perlu mengalir seperti ini. Beberapa data bisa kembali ke kiri di sana. Anda bahkan tidak tahu. 

Dan dengan sebuah array, Anda memiliki fitur yang dikenal sebagai akses acak. Dan apa akses acak berarti adalah bahwa komputer dapat melompat langsung untuk setiap lokasi dalam array. Mengapa? Karena komputer tahu bahwa lokasi pertama adalah nol, satu, dua, dan tiga. 

Dan jadi jika Anda ingin pergi dari elemen ini ke elemen berikutnya, Anda benar-benar, di pikiran komputer, hanya menambahkan satu. Jika Anda ingin pergi ke elemen ketiga, hanya menambahkan satu-- elemen berikutnya, hanya menambahkan satu. Namun, dalam versi ini cerita, kira komputer saat ini sedang mencari pada atau berurusan dengan nomor 100. Bagaimana Anda mendapatkan ke yang berikutnya kelas dalam buku kelas? 

Anda harus mengambil tujuh langkah, yang sewenang-wenang. Untuk mendapatkan ke yang berikutnya, Anda harus mengambil delapan langkah untuk 15. Dengan kata lain, itu bukan gap konstan antara angka-angka, dan sehingga hanya mengambil komputer lebih banyak waktu adalah titik. komputer harus mencari melalui memori agar untuk menemukan apa yang Anda cari. 

Jadi sedangkan array cenderung menjadi data yang cepat structure-- karena Anda dapat benar-benar hanya melakukan aritmatika sederhana dan di mana Anda inginkan dengan menambahkan satu, untuk instance-- sebuah linked list, Anda mengorbankan fitur itu. Anda tidak bisa hanya pergi dari pertama untuk kedua ketiga untuk keempat. Anda harus mengikuti peta. Anda harus mengambil langkah-langkah lebih untuk mendapatkan nilai-nilai yang tampaknya akan menjadi menambahkan biaya. Jadi kita membayar harga, tapi apa itu fitur yang Dan sedang mencari di sini? Apa linked list tampaknya memungkinkan kita untuk melakukan, yang merupakan asal-usul cerita khusus ini? 

Persis. Sebuah ukuran yang dinamis untuk itu. Kita dapat menambah daftar ini. Kita bahkan dapat mengecilkan daftar, sehingga bahwa kita hanya menggunakan sebanyak memori karena kami benar-benar ingin dan sebagainya kami tidak pernah over-mengalokasikan. 

Sekarang hanya harus benar-benar rewel, ada biaya tersembunyi. Jadi Anda tidak hanya harus membiarkan saya meyakinkan Anda bahwa ini adalah tradeoff menarik. Ada biaya lain yang tersembunyi di sini. Manfaatnya, harus jelas, adalah bahwa kita mendapatkan dinamisme. Jika saya ingin unsur lain, saya hanya bisa menggambar dan memasukkan nomor di sana. Dan kemudian saya bisa menghubungkannya dengan gambar di sini, sedangkan di sini, sekali lagi, jika saya sudah dicat sendiri ke sudut, jika sesuatu yang lain sudah menggunakan memori di sini, aku beruntung. Aku sudah dicat sendiri ke sudut. 

Tapi apa yang tersembunyi biaya dalam gambar ini? Ini bukan hanya jumlah yang waktu yang dibutuhkan untuk pergi dari sini ke sini, yang tujuh langkah, maka delapan langkah, yang lebih dari satu. Apa biaya lain yang tersembunyi? Bukan hanya waktu. Informasi tambahan diperlukan untuk mencapai gambar ini. 

Ya, itu peta, mereka memo kecil kertas, saya tetap menggambarkan mereka sebagai. Ini arrows-- mereka tidak bebas. Sebuah computer-- Anda tahu apa komputer memiliki. Ini memiliki nol dan satu. Jika Anda ingin mewakili panah atau map atau nomor, Anda memerlukan beberapa memori. Jadi harga lain Anda membayar untuk sebuah linked list, ilmu komputer umum sumber daya, juga ruang. 

Dan memang begitu, jadi sering, antara pengorbanan dalam merancang rekayasa perangkat lunak sistem adalah waktu dan space-- dua bahan Anda, dua dari bahan yang paling mahal Anda. Ini biaya saya lebih banyak waktu karena saya harus mengikuti peta ini, tapi itu juga biaya saya lebih banyak ruang karena saya harus menjaga peta ini sekitar. Jadi harapan, karena kami sudah jenis dibahas lebih kemarin dan hari ini, adalah bahwa manfaat akan lebih besar daripada biaya. 

Tapi tidak ada solusi yang jelas di sini. Mungkin itu adalah better-- a la cepat dan kotor, sebagai Kareem diusulkan earlier-- untuk membuang memori pada masalah. Hanya membeli lebih banyak memori, berpikir kurang keras tentang pemecahan masalah, dan menyelesaikannya dengan cara yang lebih mudah. Dan memang sebelumnya, ketika kita berbicara tentang pengorbanan, itu tidak ruang dalam komputer dan waktu. Itu waktu pengembang, yang belum sumber daya lain. 

Jadi sekali lagi, itu tindakan penyeimbangan ini mencoba untuk memutuskan mana dari hal-hal Anda bersedia untuk menghabiskan? Yang merupakan yang paling mahal? Yang menghasilkan hasil yang lebih baik? Ya? 

Memang. Dalam hal ini, jika Anda mewakili angka di maps-- yang ini disebut dalam banyak bahasa "Pointer" atau "alamat" - itu ganda ruang. Itu tidak perlu seburuk ganda jika sekarang kami hanya menyimpan nomor. Misalkan kita menyimpan catatan pasien di hospital-- sebuah sehingga nama Pierson ini, nomor telepon, nomor jaminan sosial, dokter sejarah. Kotak ini mungkin banyak, jauh lebih besar, dalam hal ini pointer kecil kecil, alamat berikutnya element-- itu bukan masalah besar. Ini pinggiran seperti biaya tidak masalah. Tapi dalam kasus ini, ya, itu dua kali lipat a. Pertanyaan bagus. 

Mari kita bicara tentang waktu sedikit lebih konkret. Apa waktu berjalan mencari daftar ini? Misalkan saya ingin mencari melalui semua nilai siswa, dan ada n nilai dalam struktur data ini. Di sini juga, kita bisa meminjam kosakata sebelumnya. Ini adalah struktur data linear. 

O besar n adalah apa yang diperlukan untuk mendapatkan sampai akhir struktur data ini, whereas-- dan kami belum melihat ini before-- array memberi Anda apa yang disebut konstanta waktu, yang berarti satu langkah atau dua langkah atau 10 steps-- tidak masalah. Ini adalah jumlah tetap. Ini tidak ada hubungannya dengan ukuran array. Dan alasan untuk itu, lagi, akses random. komputer bisa saja segera melompat ke lokasi lain, karena mereka semua sama jarak dari segala sesuatu yang lain. Tidak ada pemikiran yang terlibat. Baiklah. Jadi jika saya bisa, saya mencoba untuk melukis dua gambar akhir. Yang sangat umum dikenal sebagai tabel hash. Jadi untuk memotivasi diskusi ini, biarkan aku berpikir tentang bagaimana untuk melakukan hal ini. 

Jadi bagaimana ini? Misalkan masalah kami ingin memecahkan sekarang menerapkan di dictionary-- sebuah sehingga sejumlah besar kata-kata bahasa Inggris atau terserah. Dan tujuannya adalah untuk dapat menjawab pertanyaan dari formulir adalah ini sebuah kata? Jadi Anda ingin menerapkan pemeriksa ejaan, hanya seperti kamus fisik Anda dapat melihat hal-hal di. Bagaimana jika aku melakukan ini dengan array. Aku bisa melakukan ini. 

Dan kira kata-kata apple dan pisang dan melon. Dan saya tidak bisa memikirkan buah yang dimulai dengan d, jadi kami hanya akan memiliki tiga buah. Jadi ini adalah sebuah array, dan kami menyimpan semua kata-kata ini dalam kamus ini sebagai array. Pertanyaannya, kemudian, adalah bagaimana lagi Anda bisa menyimpan informasi ini? 

Yah, aku jenis kecurangan di sini, karena masing-masing surat-surat ini dalam kata benar-benar sebuah byte individu. Jadi jika saya benar-benar ingin menjadi rewel, saya harus benar-benar akan membagi ini menjadi lebih potongan yang lebih kecil dari memori, dan kita bisa melakukan hal itu. Tapi kita akan mengalami masalah yang sama seperti sebelumnya. Bagaimana jika, seperti Merriam Webster atau Oxford tidak setiap year-- mereka menambahkan kata-kata ke dictionary-- kita tidak selalu ingin melukis diri kita sendiri ke sudut dengan array? 

Jadi alih-alih, mungkin pendekatan yang lebih cerdas adalah untuk menempatkan apel di node atau kotak sendiri, seperti yang kita katakan, pisang, dan maka di sini kita memiliki blewah. Dan kami string yang hal-hal ini bersama-sama. Jadi ini adalah array, dan ini adalah linked list. Jika Anda tidak bisa melihat, itu hanya mengatakan "array," dan ini mengatakan "daftar." 

Jadi kita harus sama masalah persis seperti sebelumnya, dimana kita sekarang memiliki dinamisme dalam daftar kami terkait. Tapi kami memiliki kamus cukup lambat. Misalkan saya ingin mencari kata. Mungkin membawa saya O besar n langkah, karena kata mungkin menjadi semua jalan pada akhir daftar, seperti melon. Dan ternyata dalam pemrograman, semacam dari grail suci data struktur, adalah sesuatu yang memberikan konstan waktu seperti array tapi yang masih memberikan dinamisme. 

Jadi dapat kita memiliki yang terbaik dari kedua dunia? Dan memang, ada sesuatu disebut tabel hash yang memungkinkan Anda untuk melakukan hal bahwa, meskipun sekitar. Sebuah tabel hash adalah pengujian struktur data yang kita bisa memikirkan sebagai Kombinasi dari array-- dan aku akan menggambar seperti ini-- dan daftar terkait bahwa saya akan menggambar seperti ini di sini. 

Dan cara hal ini karya adalah sebagai berikut. Jika ini sekarang-- hash table-- adalah struktur data ketiga, dan saya ingin menyimpan kata-kata dalam ini, saya tidak ingin hanya menyimpan semua kata kembali untuk kembali ke belakang ke belakang. Saya ingin memanfaatkan beberapa sepotong informasi tentang kata-kata yang akan membiarkan saya mendapatkannya di mana itu lebih cepat. 

Jadi mengingat kata-kata apple dan pisang dan melon, Saya sengaja memilih kata-kata. Mengapa? Apa semacam fundamental yang berbeda tentang tiga? Apa yang jelas? Mereka mulai dengan huruf yang berbeda. 

Sehingga Anda tahu apa? Daripada menempatkan semua kata-kata saya di ember yang sama, sehingga untuk berbicara, seperti dalam satu daftar besar, mengapa tidak melakukan Saya setidaknya mencoba optimasi dan membuat daftar saya 1/26 lama. Sebuah optimasi menarik mungkin mengapa tidak melakukan Aku-- saat memasukkan kata ke dalam struktur data ini, ke dalam memori komputer, mengapa saya tidak meletakkan semua 'a' kata di sini, semua kata 'b' di sini, dan semua 'c' kata di sini? Jadi ini akhirnya menempatkan sebuah apel di sini, pisang sini, melon di sini, dan seterusnya. 

Dan jika saya memiliki tambahan kata like-- apa lagi? Apel, pisang, pir. Siapapun memikirkan buah yang dimulai dengan a, b, atau c? sempurna Blueberry--. Yang akan berakhir di sini. Dan jadi kita tampaknya memiliki sedikit solusi yang lebih baik, karena sekarang jika saya ingin untuk mencari apel, saya first-- saya tidak hanya menyelam ke dalam struktur data saya. Saya tidak menyelam ke dalam memori komputer saya. Saya pertama kali melihat huruf pertama. 

Dan ini adalah apa komputer ilmuwan akan mengatakan. Anda hash ke dalam struktur data Anda. Anda mengambil masukan Anda, yang pada hal ini adalah kata seperti apel. Anda menganalisis itu, melihat huruf pertama dalam kasus ini, demikian hashing. Hashing adalah dimana istilah umum Anda mengambil sesuatu sebagai masukan dan Anda menghasilkan beberapa output. Dan output dalam Kasus adalah lokasi Anda ingin mencari, pertama lokasi, lokasi kedua, ketiga. Jadi input apel, output adalah pertama. input adalah pisang, yang output harus kedua. input blewah, output harus ketiga. input adalah blueberry, yang output harus kembali menjadi yang kedua. Dan itulah yang membantu Anda mengambil pintas melalui memori Anda untuk mendapatkan kata-kata atau data secara lebih efektif. 

Sekarang ini menebang waktu kita berpotensi sebanyak satu dari 26, karena jika Anda berasumsi bahwa Anda memiliki banyak "a" kata-kata "z" kata-kata sebagai kata-kata "q", yang tidak benar-benar realistic-- Anda akan memiliki condong di huruf tertentu alphabet-- yang tapi ini akan menjadi tambahan Pendekatan yang tidak memungkinkan Anda untuk mendapatkan kata-kata jauh lebih cepat. Dan pada kenyataannya, canggih program, Googles dunia, yang Facebooks dari dunia-- mereka akan menggunakan tabel hash untuk banyak tujuan yang berbeda. Tapi mereka tidak akan begitu naif hanya melihat huruf pertama di apel atau pisang atau pir atau melon, karena seperti yang Anda lihat ini daftar masih bisa panjang. 

Dan jadi ini mungkin masih menjadi semacam dari linear-- sehingga semacam lambat, seperti dengan O besar n yang kita bahas sebelumnya. Jadi apa tabel hash nyata baik akan do-- itu akan memiliki array yang jauh lebih besar. Dan itu akan menggunakan lebih banyak fungsi hashing canggih, sehingga tidak hanya melihat "a." Mungkin terlihat di "a-p-p-l-e" dan entah bagaimana mengkonversi lima huruf ke lokasi di mana apel harus disimpan. Kami hanya naif menggunakan huruf 'a' saja, karena itu bagus dan sederhana. 

Tapi tabel hash, di akhirnya, Anda bisa memikirkan sebagai kombinasi array, yang masing-masing memiliki daftar link yang idealnya harus sesingkat mungkin. Dan ini bukan solusi yang jelas. Bahkan, banyak dari fine tuning yang berlangsung di bawah tenda saat melaksanakan jenis-jenis struktur data yang canggih adalah apa yang benar yang panjang array? Apa fungsi hash yang tepat? Bagaimana Anda menyimpan hal-hal dalam memori? 

Tapi menyadari betapa cepat diskusi semacam ini meningkat, baik sejauh bahwa itu semacam dari atas kepala seseorang pada saat ini, yang baik-baik saja. Tapi kita mulai, ingat, dengan benar-benar sesuatu tingkat rendah dan elektronik. Dan ini lagi adalah ini tema abstraksi, di mana setelah Anda mulai untuk mengambil untuk diberikan, OK, saya punya itu-- ada memori fisik, OK, mendapatkannya, setiap lokasi fisik memiliki alamat, OK, saya mendapatkannya, saya dapat mewakili alamat tersebut sebagai arrows-- Anda dapat dengan cepat mulai memiliki percakapan yang lebih canggih yang pada akhirnya tampaknya akan memungkinkan kita untuk memecahkan masalah seperti mencari dan menyortir lebih efektif. Dan yakinlah, too-- karena saya pikir ini adalah terdalam kita sudah ke beberapa topik CS ini proper-- kami telah dilakukan dalam satu hari dan setengah di ini menunjukkan apa yang mungkin Anda biasanya lakukan lebih kursus delapan minggu dalam satu semester. 

Pertanyaan ini? Tidak? Baiklah. Nah, kenapa tidak kita berhenti di sana, mulai siang beberapa menit lebih awal, melanjutkan hanya sekitar satu jam? Dan aku akan berlama-lama untuk sedikit dengan pertanyaan. Lalu aku akan harus pergi mengambil beberapa panggilan jika itu OK. Aku akan menyalakan musik sementara itu, tapi makan siang harus sekitar sudut.