Baiklah, jadi, kerumitan pengiraan. Hanya sedikit amaran sebelum kita menyelam dalam terlalu far-- ini mungkin akan menjadi antara perkara yang paling matematik-berat kita bercakap kira-kira dalam CS50. Mudah-mudahan ia tidak akan menjadi terlalu besar dan kami akan cuba dan membimbing anda melalui proses itu, tetapi hanya sedikit amaran yang adil. Ada sedikit sedikit matematik terlibat di sini. Baiklah, jadi untuk membuat penggunaan sumber pengiraan kami dalam world-- sebenar ia benar-benar penting untuk memahami algoritma dan bagaimana mereka memproses data. Jika kita mempunyai benar-benar algoritma yang cekap, boleh mengurangkan jumlah sumber kita ada untuk menanganinya. Jika kita mempunyai algoritma yang akan mengambil banyak kerja memproses benar-benar set data yang besar, ia adalah akan memerlukan lebih banyak dan lebih banyak sumber, yang adalah wang, RAM, semua jenis barangan. 

Jadi, dapat menganalisis satu algoritma menggunakan set alat ini, pada dasarnya, soal question-- yang bagaimana skala algoritma ini seperti yang kita membuang lebih dan lebih banyak data pada itu? Dalam CS50, jumlah data kami bekerja dengan agak kecil. Secara umumnya, program kami akan berjalan di kedua atau less-- mungkin banyak yang kurang terutama sejak awal. 

Tetapi berfikir tentang sebuah syarikat yang tawaran dengan beratus-ratus berjuta-juta pelanggan. Dan mereka perlu memproses bahawa data pelanggan. Oleh kerana bilangan pelanggan mereka ada mendapat lebih besar dan lebih besar, ia akan memerlukan lebih dan lebih banyak sumber. Berapa banyak lagi sumber? Nah, itu bergantung kepada bagaimana kita menganalisis algoritma, menggunakan alat-alat dalam toolbox ini. Apabila kita bercakap mengenai kerumitan algorithm-- yang yang kadang-kadang anda akan mendengar ia disebut sebagai masa kerumitan atau ruang kerumitan tetapi kami hanya akan untuk memanggil complexity-- kita secara umumnya bercakap tentang senario kes terburuk. Memandangkan timbunan terburuk mutlak data yang kita boleh membuang ia, bagaimana algoritma ini akan memproses atau berurusan dengan data itu? Kita biasanya memanggil kes terburuk yang runtime daripada algoritma besar-O. Jadi algoritma mungkin dikatakan berjalan di O n atau O n kuasa dua. Dan lebih lanjut mengenai apa yang yang bermakna dalam satu saat. 

Kadang-kadang, walaupun, kita mengambil berat tentang senario kes terbaik. Jika data adalah segala-galanya yang kita mahu ia menjadi dan ia adalah benar-benar sempurna dan kami telah menghantar ini sempurna set data melalui algoritma kami. Bagaimana ia akan mengendalikan dalam keadaan itu? Kita kadang-kadang merujuk kepada bahawa sebagai besar Omega, supaya berbeza dengan besar-O, kami mempunyai besar Omega. Big-Omega untuk senario kes terbaik. Big-O untuk senario kes terburuk. Secara umumnya, apabila kita bercakap mengenai kerumitan algoritma, kita bercakap tentang senario kes terburuk. Jadi menyimpan bahawa dalam fikiran. 

Dan di dalam kelas ini, kita biasanya akan untuk meninggalkan analisis yang ketat diketepikan. Terdapat sains dan bidang-bidang ditumpukan kepada jenis barangan. Apabila kita bercakap mengenai penaakulan melalui algoritma, yang kita akan lakukan sekeping demi sekeping untuk banyak algoritma kita bercakap tentang di dalam kelas. Kami benar-benar hanya bercakap tentang pemikiran melaluinya dengan akal, bukan dengan formula, atau bukti-bukti, atau apa-apa seperti itu. Jadi jangan bimbang, Kami tidak akan bertukar menjadi kelas matematik besar. 

Jadi, saya berkata kita mengambil berat tentang kerumitan kerana bertanya soalan, bagaimana jangan algoritma kami mengendalikan lebih besar dan set data yang lebih besar yang dilemparkan kepada mereka. Nah, apa adalah satu set data? Apa yang saya maksudkan apabila saya berkata demikian? Ini bermakna apa sahaja yang membuat paling rasa dalam konteks, untuk bersikap jujur. Jika kita mempunyai algoritma, yang Proses Strings-- kami mungkin bercakap tentang saiz tali. Itulah data set-- saiz, bilangan watak-watak yang membentuk tali. Jika kita bercakap tentang algoritma yang memproses fail, kita mungkin bercakap tentang bagaimana banyak kilobait terdiri daripada fail itu. Dan itu set data. Jika kita berbicara tentang algoritma yang mengendalikan tatasusunan lebih umum, seperti menyusun algoritma atau mencari algoritma, kita mungkin bercakap mengenai bilangan unsur-unsur yang terdiri daripada pelbagai. 

Sekarang, kita boleh mengukur yang algorithm-- khususnya, apabila saya mengatakan kita boleh mengukur algoritma, saya bermakna kita boleh mengukur berapa banyak sumber ia mengambil masa sehingga. Sama ada sumber-sumber, bagaimana banyak bait RAM-- atau megabait RAM ia menggunakan. Atau berapa banyak masa yang diperlukan untuk menjalankan. Dan kita boleh memanggil ini mengukur, sewenang-wenangnya, f n. Di mana n adalah bilangan unsur-unsur dalam set data. Dan f n berapa banyak somethings. Berapa unit sumber tidak ia memerlukan untuk memproses data tersebut. 

Sekarang, kita benar-benar tidak peduli tentang f n apa yang betul-betul. Malah, kita jarang sekali will-- pasti ia tidak akan di I class-- ini menyelam ke dalam apa-apa yang benar-benar mendalam analisis apa f n adalah. Kami hanya akan bercakap tentang apa f daripada n adalah lebih kurang atau apa yang ia cenderung untuk. Dan kecenderungan algoritma adalah ditentukan oleh jangka perintahnya tertinggi. Dan kita boleh melihat apa yang saya maksudkan dengan itu dengan mengambil yang melihat contoh yang lebih konkrit. 

Jadi mari kita mengatakan bahawa kita mempunyai tiga algoritma yang berbeza. Pertama yang mengambil n cubed, beberapa unit sumber untuk memproses satu set data bersaiz n. Kami mempunyai algoritma kedua yang mengambil n cubed ditambah sumber n kuasa untuk memproses satu set data bersaiz n. Dan kita mempunyai satu pertiga algoritma yang berjalan dalam- yang mengambil n tolak cubed 8n kuasa dua ditambah 20 n unit sumber untuk memproses algoritma dengan set data bersaiz n. 

Kini sekali lagi, kita benar-benar tidak akan untuk masuk ke tahap ini terperinci. Saya benar-benar hanya mempunyai ini sehingga di sini sebagai contoh tauladan mata bahawa saya akan menjadi membuat dalam satu saat, yang adalah bahawa kita hanya peduli tentang kecenderungan perkara sebagai set data menjadi lebih besar. Jadi, jika set data adalah kecil, ada sebenarnya perbezaan yang cukup besar dalam algoritma ini. Algoritma ketiga ada mengambil 13 kali lebih lama, 13 kali jumlah sumber untuk menjalankan berbanding dengan yang pertama. 

Jika set data kami adalah saiz 10, yang adalah lebih besar, tetapi tidak semestinya besar, kita dapat melihat bahawa ada sebenarnya sedikit perbezaan. Algoritma ketiga menjadi lebih cekap. Ia kira-kira sebenarnya 40% - atau 60% lebih cekap. Ia mengambil masa 40% jumlah masa. Ia boleh run-- ia boleh mengambil 400 unit sumber untuk memproses satu set data saiz 10. Sedangkan yang pertama algoritma, sebaliknya, mengambil 1,000 unit sumber untuk memproses satu set data saiz 10. Tetapi melihat apa yang berlaku sebagai nombor kami mendapatkan lebih besar. 

Sekarang, perbezaan antara algoritma ini mula menjadi sedikit kurang jelas. Dan hakikat bahawa terdapat lebih rendah pesanan terms-- atau sebaliknya, terma dengan exponents-- lebih rendah mula menjadi tidak relevan. Jika set data adalah saiz 1000 dan algoritma pertama berjalan dalam satu bilion langkah. Dan algoritma kedua berjalan dalam satu bilion dan sejuta langkah. Dan algoritma yang ketiga berjalan dalam hanya malu satu bilion langkah. Ia cukup banyak satu bilion langkah. Istilah yang lebih rendah pesanan mula untuk menjadi benar-benar tidak relevan. Dan hanya untuk benar-benar tukul rumah point-- yang jika input data adalah saiz yang million-- ketiga-tiga ini cukup banyak mengambil satu quintillion-- jika matematik saya hanya beberapa langkah correct-- memproses input data saiz satu juta. Itu banyak langkah. Dan hakikat bahawa salah seorang daripada mereka mungkin mengambil masa beberapa 100,000, atau pasangan 100 juta lebih sedikit apabila kita berbicara tentang sebilangan yang big-- ia adalah jenis yang tidak relevan. Mereka semua cenderung untuk mengambil kira-kira n cubed, dan supaya kita benar-benar akan merujuk kepada semua algoritma ini sebagai atas perintah n cubed atau besar O-n cubed. 

Berikut adalah senarai beberapa yang lebih biasa kelas kerumitan pengiraan yang kita akan hadapi dalam algoritma, amnya. Dan juga secara khusus dalam CS50. Ini dipesan dari umumnya paling cepat di bahagian atas, untuk secara amnya paling perlahan di bahagian bawah. Jadi algoritma masa yang berterusan cenderung menjadi yang paling cepat, tidak kira daripada saiz input data yang anda lulus. Mereka sentiasa mengambil satu operasi atau satu unit sumber untuk menangani. Ia mungkin menjadi 2, ia mungkin menjadi 3, ia mungkin 4. Tetapi ia adalah satu jumlah yang tetap. Ia tidak berbeza-beza. 

Algoritma masa logaritma adalah lebih baik sedikit. Dan contoh yang benar-benar baik algoritma masa logaritma anda pasti dilihat sekarang ialah mengoyak selain buku telefon untuk mencari Mike Smith dalam buku telefon. Kami memotong masalah pada separuh. Dan supaya n mendapat yang lebih besar dan lebih besar dan larger-- sebenarnya, setiap kali anda dua kali ganda n, ia hanya mengambil satu lagi langkah. Jadi, itu lebih baik daripada, katakan, masa linear. Iaitu jika anda menggandakan n, ia mengambil dua kali ganda bilangan langkah. Jika anda tiga kali ganda n, ia mengambil masa tiga kali ganda bilangan langkah. Satu langkah seunit. 

Kemudian perkara mendapatkan sedikit more-- sedikit kurang hebat di sana. Anda mempunyai masa berirama linear, kadang-kadang dipanggil log masa linear atau hanya n log n. Dan kita akan contoh algoritma yang yang berjalan dalam n log n, yang masih lebih baik daripada time-- kuadratik n kuasa dua. Atau masa polinomial, n dua mana-mana nombor yang lebih besar daripada dua orang. Atau masa eksponen, yang adalah lebih worse-- C hingga n. Jadi beberapa angka tetap dinaikkan kepada kuasa saiz input. Jadi, jika ada 1,000-- jika input data adalah saiz 1,000, ia akan mengambil C kepada kuasa 1000. Ia lebih buruk daripada masa polinomial. 

Masa faktorial adalah lebih buruk lagi. Dan sebenarnya, ada benar-benar melakukan wujud algoritma masa terhingga, seperti sort-- kerana, apa yang dipanggil bodoh yang tugasnya adalah untuk rawak shuffle array dan kemudian semak untuk melihat sama ada ia disusun. Dan jika tidak, secara rawak shuffle array lagi dan memeriksa untuk melihat sama ada ia disusun. Dan seperti yang anda mungkin boleh imagine-- anda boleh bayangkan keadaan di mana dalam kes terburuk, kehendak yang pernah benar-benar bermula dengan array. Algoritma yang akan berlangsung selama-lamanya. Dan sebagainya yang akan menjadi algoritma masa tak terhingga. Mudah-mudahan anda tidak akan menulis bila-bila masa faktorial atau tak terhingga algoritma dalam CS50. 

Jadi, mari kita mengambil lebih sedikit rupa konkrit di beberapa lebih mudah kelas kerumitan pengiraan. Jadi kita mempunyai example-- yang atau dua contoh sini-- algoritma masa yang berterusan, yang sentiasa mengambil satu operasi dalam kes terburuk itu. Jadi example-- pertama kita mempunyai fungsi yang dipanggil 4 untuk anda, yang mengambil pelbagai saiz 1,000. Tetapi nampaknya sebenarnya tidak melihat pada kitab itu tidak benar-benar mengambil berat apa yang di dalamnya, array itu. Sentiasa hanya mengembalikan empat. Jadi, algoritma yang, walaupun pada hakikatnya ia mengambil 1000 unsur-unsur tidak berbuat apa-apa dengan mereka. Hanya mengembalikan empat. Ia sentiasa satu langkah. 

Malah, tambah 2 nums-- yang kita lihat sebelum ini sebagai well-- hanya memproses dua integer. Ia bukan satu langkah. Ini sebenarnya pasangan langkah. Daftar untuk kadar terkini, anda akan mendapat b, anda menambah mereka bersama-sama, dan anda output keputusan. Jadi ia adalah 84 langkah. Tetapi ia sentiasa berterusan, tanpa mengira atau b. Anda perlu mendapatkan, mendapatkan b, tambah mereka bersama-sama, output keputusan. Jadi itulah algoritma masa yang berterusan. 

Berikut adalah satu contoh masa algorithm-- linear algoritma yang gets-- yang mengambil satu langkah tambahan, mungkin, sebagai input anda tumbuh dengan 1. Jadi, katakan kita cari di dalam nombor 5 array. Anda mungkin mempunyai situasi di mana anda boleh merasa agak awal. Tetapi anda juga boleh mempunyai keadaan di mana ia mungkin elemen terakhir array. Dalam pelbagai saiz 5, jika yang kami cari nombor 5. Ia akan mengambil masa 5 langkah. Dan sebenarnya, bayangkan bahawa ada tidak 5 mana-mana sahaja dalam pelbagai ini. Kita masih sebenarnya perlu melihat setiap elemen tunggal array untuk menentukan sama ada atau tidak 5 ada. 

Jadi dalam kes terburuk, iaitu bahawa elemen adalah yang terakhir dalam array atau tidak wujud sama sekali. Kita masih perlu melihat semua n unsur-unsur. Dan sebagainya algoritma ini berjalan dalam masa linear. Anda boleh mengesahkan dengan menentuluar sedikit dengan berkata, jika kita mempunyai pelbagai 6-elemen dan kita cari nombor 5, ia mungkin mengambil masa 6 langkah. Jika kita mempunyai pelbagai 7-unsur dan yang kami cari nombor 5. Ia mungkin mengambil masa 7 langkah. Seperti yang kita menambah satu elemen yang lebih kepada kami pelbagai, ia mengambil satu lagi langkah. Itulah algoritma yang linear dalam kes terburuk itu. 

Pasangan soalan pantas untuk anda. Apa yang runtime-- apa yang yang terburuk runtime ini coretan tertentu kod? Jadi saya mempunyai gelung 4 di sini yang berjalan dari j sama dengan 0, sepanjang jalan sehingga m. Dan apa yang saya lihat di sini, adalah bahawa badan gelung berjalan dalam masa yang berterusan. Jadi menggunakan istilah yang kita sudah bercakap about-- apa akan menjadi kes terburuk yang runtime algoritma ini? Mengambil kedua. Bahagian dalam gelung berjalan dalam masa yang berterusan. Dan yang luar daripada gelung akan berjalan m kali. Jadi apa yang runtime terburuk di sini? Adakah anda rasa besar O-m? Anda akan menjadi betul. 

Bagaimana pula dengan satu sama lain? Kali ini kita mempunyai gelung di dalam gelung. Kami mempunyai gelung luar yang berjalan dari sifar hingga h. Dan kita mempunyai gelung dalaman yang berjalan dari sifar hingga p, dan di dalam itu, Saya menyatakan bahawa badan itu gelung berjalan dalam masa yang berterusan. Jadi apa yang runtime kes terburuk ini coretan tertentu kod? Nah, sekali lagi, kita mempunyai gelung luar yang berjalan p masa. Dan setiap lelaran time-- gelung itu, agak. Kami mempunyai gelung dalaman yang juga menjalankan p masa. Dan kemudian di dalam itu, ada yang berterusan coretan sedikit time-- sana. 

Jadi, jika kita mempunyai gelung luar yang berjalan p kali di dalam yang adalah gelung dalaman yang berjalan p times-- apa yang yang terburuk runtime coretan kod ini? Adakah anda rasa besar O-p kuasa dua? 

Saya Doug Lloyd. Ini adalah CS50.