Baiklah, jadi, kompleksitas komputasi. Hanya sedikit peringatan sebelum kita menyelam terlalu far-- ini mungkin akan menjadi salah hal yang paling matematika-berat kita berbicara tentang di CS50. Mudah-mudahan itu tidak akan terlalu besar dan kami akan mencoba dan membimbing Anda melalui proses, tapi hanya sedikit peringatan yang adil. Ada sedikit matematika terlibat di sini. Baiklah, jadi untuk membuat penggunaan sumber daya komputasi kami di dunia-- nyata itu benar-benar penting untuk memahami algoritma dan bagaimana mereka memproses data. Jika kita benar-benar memiliki algoritma yang efisien, kami dapat meminimalkan jumlah sumber daya kita harus tersedia untuk menghadapinya. Jika kita memiliki sebuah algoritma yang akan mengambil banyak pekerjaan memproses benar set besar data, itu akan memerlukan lebih banyak dan lebih banyak sumber daya, yang adalah uang, RAM, semua hal semacam itu. 

Jadi, bisa menganalisis sebuah algoritma menggunakan tool set ini, pada dasarnya, meminta question-- yang bagaimana skala algoritma ini seperti yang kita membuang lebih banyak dan lebih banyak data itu? Dalam CS50, jumlah data kami bekerja dengan cukup kecil. Umumnya, program kami akan untuk menjalankan dalam kedua atau less-- mungkin banyak kurang terutama sejak dini. 

Tetapi berpikir tentang sebuah perusahaan yang penawaran dengan ratusan juta pelanggan. Dan mereka perlu proses bahwa data pelanggan. Karena jumlah pelanggan mereka memiliki akan lebih besar dan lebih besar, itu akan membutuhkan lebih dan lebih banyak sumber daya. Berapa banyak sumber? Yah, itu tergantung pada bagaimana kita menganalisis algoritma, menggunakan alat-alat dalam toolbox ini. Ketika kita berbicara tentang kompleksitas sebuah algorithm-- yang kadang-kadang Anda akan mendengarnya disebut sebagai waktu kompleksitas atau ruang kompleksitas tapi kami hanya akan untuk memanggil complexity-- kita umumnya berbicara tentang skenario terburuk. Mengingat tumpukan terburuk mutlak Data yang kita dapat melemparkan di itu, bagaimana algoritma ini akan memproses atau berurusan dengan data itu? Kita umumnya memanggil-kasus terburuk runtime dari suatu algoritma besar-O. Jadi algoritma bisa dikatakan berjalan dalam O n O atau n kuadrat. Dan lebih lanjut tentang apa yang mereka berarti dalam satu detik. 

Kadang-kadang, meskipun, kita lakukan perawatan tentang skenario kasus terbaik. Jika data apapun yang kami inginkan hal itu terjadi dan itu benar-benar sempurna dan kami mengirimkan ini sempurna mengatur data melalui algoritma kami. Bagaimana hal itu akan menangani dalam situasi itu? Kita kadang-kadang menyebut bahwa sebagai besar-Omega, sehingga kontras dengan besar-O, kita memiliki besar-Omega. Big-Omega untuk skenario kasus terbaik. Big-O untuk skenario terburuk. Umumnya, ketika kita berbicara tentang kompleksitas algoritma, kita berbicara tentang skenario terburuk. Jadi ingatlah bahwa dalam pikiran. 

Dan di kelas ini, kita umumnya akan meninggalkan analisis ketat samping. Ada ilmu dan bidang dikhususkan untuk hal semacam ini. Ketika kita berbicara tentang penalaran melalui algoritma, yang akan kita lakukan sepotong demi sepotong untuk banyak algoritma kita berbicara tentang di kelas. Kami benar-benar hanya berbicara tentang penalaran melalui itu dengan akal sehat, tidak dengan formula, atau bukti, atau sesuatu seperti itu. Jadi jangan khawatir, kami tidak akan berubah menjadi kelas matematika besar. 

Jadi aku berkata kita peduli kompleksitas karena mengajukan pertanyaan, bagaimana jangan algoritma kami menangani lebih besar dan set data yang lebih besar yang dilemparkan pada mereka. Nah, apa yang merupakan kumpulan data? Apa yang saya maksud ketika saya mengatakan bahwa? Artinya apa pun yang membuat paling akal dalam konteks, jujur. Jika kita memiliki sebuah algoritma, yang Proses Strings-- kami mungkin berbicara tentang ukuran string. Itu data set-- ukuran, jumlah karakter yang membentuk string. Jika kita berbicara tentang algoritma yang memproses file, kita mungkin akan berbicara tentang bagaimana banyak kilobyte terdiri file itu. Dan itulah kumpulan data. Jika kita berbicara tentang sebuah algoritma yang menangani array lebih umum, seperti algoritma pengurutan atau algoritma pencarian, kita mungkin berbicara tentang jumlah elemen yang terdiri dari array. 

Sekarang, kita dapat mengukur algorithm-- khususnya, ketika saya mengatakan kita bisa mengukur suatu algoritma, saya berarti kita dapat mengukur seberapa banyak sumber daya tidak memakan. Apakah sumber daya, berapa banyak byte RAM-- atau megabyte RAM menggunakan. Atau berapa banyak waktu yang diperlukan untuk menjalankan. Dan kita bisa menyebutnya mengukur, sewenang-wenang, f n. Di mana n adalah jumlah elemen dalam kumpulan data. Dan f n adalah berapa banyak somethings. Berapa banyak unit sumberdaya melakukan itu perlu memproses data tersebut. 

Sekarang, kita benar-benar tidak peduli tentang apa f n adalah persis. Bahkan, kami sangat jarang will-- tentu tidak akan pernah di saya class-- ini menyelam ke setiap benar-benar mendalam analisis apa yang f n adalah. Kami hanya akan berbicara tentang apa yang f n adalah sekitar atau apa itu cenderung. Dan kecenderungan algoritma adalah didikte oleh jangka tertinggi order. Dan kita bisa melihat apa yang saya maksud dengan itu dengan mengambil a lihat contoh yang lebih konkret. 

Jadi mari kita mengatakan bahwa kita memiliki tiga algoritma yang berbeda. Yang pertama mengambil n potong dadu, beberapa unit sumberdaya untuk memproses set data berukuran n. Kami memiliki algoritma kedua yang mengambil n potong dadu ditambah sumber n kuadrat untuk memproses set data berukuran n. Dan kami memiliki sepertiga algoritma yang berjalan in-- yang mengambil n dikurangi potong dadu 8N kuadrat ditambah 20 n unit sumberdaya untuk memproses algoritma dengan data set ukuran n. 

Sekarang lagi, kami benar-benar tidak akan untuk masuk ke tingkat detail. Aku benar-benar hanya memiliki ini up di sini sebagai ilustrasi titik bahwa aku akan menjadi membuat dalam satu detik, yang adalah bahwa kita hanya benar-benar peduli tentang kecenderungan hal sebagai data set menjadi lebih besar. Jadi jika kumpulan data kecil, ada sebenarnya perbedaan yang cukup besar dalam algoritma ini. Algoritma ketiga ada Dibutuhkan 13 kali lebih lama, 13 kali jumlah sumber daya untuk menjalankan relatif terhadap yang pertama. 

Jika set data kami adalah ukuran 10, yang lebih besar, tetapi tidak harus besar, kita dapat melihat bahwa ada sebenarnya sedikit perbedaan. Algoritma ketiga menjadi lebih efisien. Ini tentang sebenarnya 40% - atau 60% lebih efisien. Dibutuhkan 40% jumlah waktu. Hal ini dapat run-- dapat mengambil 400 unit sumberdaya untuk memproses data set ukuran 10. Sedangkan yang pertama algoritma, sebaliknya, Dibutuhkan 1.000 unit sumberdaya untuk memproses data set ukuran 10. Tapi lihat apa yang terjadi sebagai nomor kami mendapatkan bahkan lebih besar. 

Sekarang, perbedaan antara algoritma ini mulai menjadi sedikit kurang jelas. Dan fakta bahwa ada rendah-order terms-- atau lebih tepatnya, berdamai dengan exponents-- rendah mulai menjadi tidak relevan. Jika satu set data ukuran 1.000 dan algoritma pertama berjalan dalam satu miliar langkah. Dan algoritma kedua berjalan dalam satu miliar dan satu juta langkah. Dan algoritma ketiga berjalan hanya malu dari satu miliar langkah. Hal ini cukup banyak satu miliar langkah. Istilah-istilah yang lebih rendah-order mulai untuk menjadi benar-benar tidak relevan. Dan hanya untuk benar-benar palu rumah point-- yang jika input data dari ukuran million-- ketiga ini cukup banyak mengambil satu quintillion-- jika matematika saya adalah langkah correct-- untuk memproses data input ukuran satu juta. Itu banyak langkah-langkah. Dan fakta bahwa salah satu dari mereka mungkin mengambil beberapa 100.000, atau beberapa 100 juta bahkan kurang ketika kita sedang berbicara tentang angka bahwa big-- itu semacam tidak relevan. Mereka semua cenderung untuk mengambil sekitar n potong dadu, dan jadi kita benar-benar akan merujuk untuk semua algoritma ini sebagai pada urutan n potong dadu atau besar-O dari n potong dadu. 

Berikut adalah daftar dari beberapa yang lebih umum kelas kompleksitas komputasi bahwa kita akan menemukan di algoritma, umumnya. Dan juga secara khusus di CS50. Ini dipesan dari umumnya tercepat di atas, untuk umum paling lambat di bagian bawah. Jadi algoritma waktu yang konstan cenderung menjadi yang tercepat, terlepas dari ukuran masukan data yang lulus dalam. Mereka selalu mengambil satu operasi atau satu unit sumber daya untuk menangani. Mungkin 2, itu mungkin menjadi 3, mungkin 4. Tapi itu sejumlah konstan. Itu tidak bervariasi. 

Algoritma waktu logaritmik yang sedikit lebih baik. Dan contoh yang benar-benar baik algoritma waktu logaritmik Anda sudah pasti melihat sekarang adalah merobek dari buku telepon untuk menemukan Mike Smith dalam buku telepon. Kami memotong masalah di setengah. Dan sehingga n akan lebih besar dan lebih besar dan larger-- pada kenyataannya, setiap kali Anda dua kali lipat n, hanya membutuhkan satu langkah lagi. Jadi itu jauh lebih baik dari, katakanlah, waktu linier. Yang jika Anda dua kali lipat n, itu mengambil dua kali lipat jumlah langkah. Jika Anda tiga kali lipat n, dibutuhkan tiga kali lipat jumlah langkah. Salah satu langkah per unit. 

Maka hal-hal mendapatkan sedikit more-- sedikit kurang bagus dari sana. Anda punya waktu berirama linier, kadang-kadang disebut log waktu linier atau hanya n log n. Dan kita akan sebuah contoh dari suatu algoritma yang berjalan di n log n, yang masih lebih baik dari kuadrat time-- n kuadrat. Atau waktu polinomial, n dua sejumlah besar dari dua. Atau waktu eksponensial, yang bahkan worse-- C untuk n. Jadi beberapa nomor konstan diangkat ke kekuatan ukuran input. Jadi jika ada 1,000-- jika masukan data dari ukuran 1.000, itu akan mengambil C dengan daya 1000. Ini jauh lebih buruk dari waktu polinomial. 

Waktu faktorial bahkan lebih buruk. Dan pada kenyataannya, ada benar-benar melakukan ada algoritma waktu yang tak terbatas, seperti, disebut sort-- bodoh yang pekerjaan adalah untuk secara acak mengocok array dan kemudian memeriksa untuk melihat apakah itu diurutkan. Dan jika tidak, secara acak mengocok array lagi dan memeriksa untuk melihat apakah itu diurutkan. Dan karena Anda mungkin dapat imagine-- Anda bisa membayangkan situasi di mana dalam kasus terburuk, akan yang pernah benar-benar mulai dengan array. Algoritma yang akan menjalankan selamanya. Dan sehingga akan menjadi algoritma waktu yang tak terbatas. Mudah-mudahan Anda tidak akan menulis setiap saat faktorial atau tak terbatas algoritma di CS50. 

Jadi, mari kita sedikit lebih Penampilan beton di beberapa sederhana kelas kompleksitas komputasi. Jadi kita memiliki example-- atau dua contoh di sini- algoritma waktu yang konstan, yang selalu mengambil satu operasi dalam kasus terburuk. Jadi example-- pertama kita memiliki fungsi disebut 4 untuk Anda, yang mengambil array ukuran 1.000. Tapi kemudian ternyata tidak benar-benar melihat di itu-- tidak benar-benar peduli apa di dalamnya, array itu. Selalu hanya mengembalikan empat. Jadi, algoritma yang, meskipun fakta bahwa itu Dibutuhkan 1.000 elemen tidak melakukan apa-apa dengan mereka. Hanya mengembalikan empat. Itu selalu satu langkah. 

Bahkan, tambahkan 2 nums-- yang kita lihat sebelumnya seperti baik hanya memproses dua bilangan bulat. Ini bukan satu langkah. Ini sebenarnya beberapa langkah. Anda mendapatkan, Anda mendapatkan b, Anda menambahkannya bersama-sama, dan Anda output hasil. Jadi 84 langkah. Tapi selalu konstan, terlepas dari atau b. Anda harus mendapatkan, dapatkan b, tambahkan mereka bersama-sama, output hasil. Jadi itulah algoritma waktu yang konstan. 

Berikut ini adalah contoh dari linear waktu algorithm-- algoritma yang gets-- yang mengambil satu langkah tambahan, mungkin, sebagai masukan Anda tumbuh dengan 1. Jadi, katakanlah kita sedang mencari jumlah 5 dalam sebuah array. Anda mungkin memiliki situasi di mana Anda dapat menemukannya cukup awal. Tapi Anda juga bisa memiliki situasi di mana mungkin elemen terakhir dari array. Dalam berbagai ukuran 5, jika kami sedang mencari nomor 5. Ini akan mengambil 5 langkah. Dan pada kenyataannya, bayangkan bahwa ada tidak 5 di mana saja di array ini. Kami masih benar-benar harus melihat setiap elemen dari array untuk menentukan apakah 5 ada. 

Jadi dalam kasus terburuk, yaitu bahwa Unsur adalah terakhir dalam array atau tidak ada sama sekali. Kami masih harus melihat semua elemen n. Dan algoritma ini berjalan dalam waktu linier. Anda dapat mengkonfirmasi bahwa dengan ekstrapolasi sedikit dengan mengatakan, jika kita memiliki array 6-elemen dan kita cari nomor 5, mungkin butuh 6 langkah. Jika kita memiliki array 7-elemen dan kami sedang mencari nomor 5. Mungkin butuh 7 langkah. Seperti kita menambahkan satu elemen lebih untuk kami array, dibutuhkan satu langkah lagi. Itu algoritma linear dalam kasus terburuk. 

Pasangan pertanyaan cepat untuk Anda. Apa runtime-- apa terburuk-kasus runtime dari potongan tertentu dari kode? Jadi saya memiliki 4 lingkaran di sini yang berjalan dari j sama dengan 0, semua jalan sampai ke m. Dan apa yang saya lihat di sini, adalah bahwa tubuh loop berjalan dalam waktu yang konstan. Jadi menggunakan terminologi yang kita sudah bicara about-- apa akan menjadi kasus terburuk runtime dari algoritma ini? Mengambil kedua. Bagian dalam loop berjalan dalam waktu yang konstan. Dan bagian luar dari loop akan dijalankan m kali. Jadi apa runtime terburuk di sini? Apakah Anda menebak besar-O dari m? Anda akan benar. 

Bagaimana tentang satu sama lain? Kali ini kami memiliki lingkaran dalam lingkaran. Kami memiliki loop luar yang berjalan dari nol sampai p. Dan kami memiliki loop batin yang berjalan dari nol sampai p, dan di dalam itu, Saya menyatakan bahwa tubuh yang loop berjalan dalam waktu yang konstan. Jadi apa runtime terburuk dari potongan tertentu dari kode? Nah, sekali lagi, kita memiliki lingkaran luar yang berjalan p kali. Dan setiap iterasi time-- loop itu, bukan. Kami memiliki loop batin yang juga menjalankan p kali. Dan kemudian di dalam itu, ada konstan time-- potongan kecil di sana. 

Jadi jika kita memiliki lingkaran luar yang menjalankan p kali dalam yang loop batin yang menjalankan p times-- apa terburuk-kasus runtime dari potongan kode ini? Apakah Anda menebak besar-O dari p kuadrat? 

Aku Doug Lloyd. Ini adalah CS50.