hello! Kuliah hari ini akan berbeza sedikit daripada yang lain. Ia akan berbeza kerana ia hanya berkaitan secara tidak langsung dengan Java. Walau bagaimanapun, topik ini sangat penting untuk setiap pengaturcara. Kita akan bercakap tentang algoritma . Apakah algoritma? Secara ringkas, ini ialah urutan tindakan tertentu yang mesti dilakukan untuk mencapai hasil yang diinginkan . Kami sering menggunakan algoritma dalam kehidupan seharian. Sebagai contoh, setiap pagi anda dihadapkan dengan tugas: datang ke sekolah atau bekerja, dan pada masa yang sama:
Berpakaian
Bersih
cukup makan
Algoritma apakah yang akan membolehkan anda mencapai keputusan ini?
Bangun dengan jam penggera.
Mandi, cuci muka.
Sediakan sarapan pagi, buat kopi/teh.
makan.
Jika anda belum menyeterika pakaian anda sejak petang, gosokkannya.
Berpakaian.
Tinggalkan rumah.
Urutan tindakan ini pasti akan membolehkan anda mendapatkan hasil yang diinginkan. Dalam pengaturcaraan, intipati kerja kami adalah untuk sentiasa menyelesaikan masalah. Sebahagian penting daripada tugasan ini boleh dilakukan menggunakan algoritma yang telah diketahui. Sebagai contoh, anda berhadapan dengan tugas: mengisih senarai 100 nama dalam tatasusunan . Masalah ini agak mudah, tetapi ia boleh diselesaikan dengan cara yang berbeza. Berikut ialah satu penyelesaian: Algoritma untuk mengisih nama mengikut abjad:
Beli atau muat turun di Internet "Kamus Nama Peribadi Rusia" edisi 1966.
Cari setiap nama dalam senarai kami dalam kamus ini.
Tulis pada sehelai kertas di mana halaman kamus nama itu.
Susun nama mengikut urutan menggunakan nota pada sekeping kertas.
Adakah urutan tindakan sedemikian membolehkan kita menyelesaikan masalah kita? Ya, ia akan membenarkannya sepenuhnya. Adakah penyelesaian ini berkesan ? hampir tidak. Di sini kita sampai kepada satu lagi sifat algoritma yang sangat penting - kecekapannya . Masalah boleh diselesaikan dengan cara yang berbeza. Tetapi dalam pengaturcaraan dan dalam kehidupan seharian, kami memilih kaedah yang paling berkesan. Jika tugas anda adalah untuk membuat sandwic dengan mentega, anda boleh, sudah tentu, mulakan dengan menyemai gandum dan memerah susu lembu. Tetapi ini akan menjadi penyelesaian yang tidak berkesan - ia akan mengambil banyak masa dan memerlukan banyak wang. Untuk menyelesaikan masalah mudah anda, anda hanya boleh membeli roti dan mentega. Dan algoritma dengan gandum dan lembu, walaupun ia membolehkan anda menyelesaikan masalah, terlalu rumit untuk menerapkannya dalam amalan. Untuk menilai kerumitan algoritma dalam pengaturcaraan, notasi khas telah dicipta dipanggil Big-O ("big O") . Big-O membolehkan anda menganggarkan berapa banyak masa pelaksanaan algoritma bergantung pada data yang dihantar ke dalamnya . Mari kita lihat contoh paling mudah - pemindahan data. Bayangkan anda perlu menghantar beberapa maklumat dalam bentuk fail pada jarak yang jauh (contohnya, 5000 kilometer). Algoritma manakah yang paling berkesan? Ia bergantung pada data yang dia perlu bekerjasama. Sebagai contoh, kami mempunyai fail audio bersaiz 10 megabait. Dalam kes ini, algoritma yang paling cekap ialah memindahkan fail melalui Internet. Ia hanya akan mengambil masa beberapa minit! Jadi, mari kita suarakan algoritma kami sekali lagi: "Jika anda perlu memindahkan maklumat dalam bentuk fail pada jarak 5000 kilometer, anda perlu menggunakan penghantaran data melalui Internet." Hebat. Sekarang mari kita menganalisisnya. Adakah ia menyelesaikan masalah kita? Secara umum, ya, ia menyelesaikannya sepenuhnya. Tetapi apa yang boleh anda katakan tentang kerumitannya? Hmm, sekarang di sinilah perkara menjadi menarik. Hakikatnya ialah algoritma kami sangat bergantung pada data yang masuk, iaitu saiz fail. Kini kami mempunyai 10 megabait dan semuanya baik-baik saja. Bagaimana jika kita perlu memindahkan 500 megabait? 20 gigabait? 500 terabait? 30 petabait? Adakah algoritma kami akan berhenti berfungsi? Tidak, semua jumlah data ini masih boleh dipindahkan. Adakah ia akan mengambil masa yang lebih lama untuk disiapkan? Ya ia akan! Kini kami mengetahui ciri penting algoritma kami: lebih besar saiz data yang akan dipindahkan, lebih lama algoritma akan mengambil masa untuk menyelesaikan . Tetapi kami ingin memahami dengan lebih tepat rupa hubungan ini (antara saiz data dan masa yang diperlukan untuk memindahkannya). Dalam kes kami, kerumitan algoritma akan menjadi linear. "Linear" bermaksud bahawa apabila volum data meningkat, masa untuk penghantarannya akan meningkat lebih kurang berkadar. Jika terdapat 2 kali lebih banyak data, dan ia akan mengambil 2 kali lebih masa untuk memindahkannya. Jika terdapat 10 kali lebih banyak data, masa pemindahan akan meningkat 10 kali ganda. Menggunakan tatatanda Big-O, kerumitan algoritma kami ditakrifkan sebagai O(N) . Notasi ini paling diingati untuk rujukan masa hadapan; ia sentiasa digunakan untuk algoritma dengan kerumitan linear. Sila ambil perhatian: kami tidak bercakap di sini sama sekali tentang pelbagai perkara "pembolehubah": kelajuan Internet, kuasa komputer kami, dan sebagainya. Apabila menilai kerumitan algoritma, ini tidak masuk akal - kami tidak mempunyai kawalan ke atasnya. Big-O menilai algoritma itu sendiri, tanpa mengira "persekitaran" di mana ia perlu berfungsi. Mari kita teruskan dengan contoh kita. Katakan akhirnya ternyata saiz fail yang akan dipindahkan ialah 800 terabait. Jika kita menghantarnya melalui Internet, masalahnya, sudah tentu, akan diselesaikan. Hanya ada satu masalah: penghantaran melalui pautan moden standard (pada 100 megabit sesaat) yang kebanyakan kita gunakan di rumah kita akan mengambil masa kira-kira 708 hari. Hampir 2 tahun! :O Jadi, algoritma kami jelas tidak sesuai di sini. Kami memerlukan penyelesaian lain! Tiba-tiba, Amazon gergasi IT datang membantu kami! Perkhidmatan Amazon Snowmobile membolehkan anda memuatkan sejumlah besar data ke dalam unit storan mudah alih dan menghantarnya ke alamat yang dikehendaki dengan trak! Jadi kami mempunyai algoritma baharu! "Jika anda perlu memindahkan maklumat dalam bentuk fail dalam jarak 5,000 kilometer, dan prosesnya akan mengambil masa lebih daripada 14 hari apabila dipindahkan melalui Internet, anda perlu menggunakan pengangkutan trak Amazon." Angka 14 hari dipilih di sini secara rawak: katakan ini adalah tempoh maksimum yang kita mampu. Mari analisa algoritma kami. Bagaimana pula dengan kelajuan? Walaupun trak itu bergerak pada kelajuan hanya 50 km/j, ia akan menempuh 5,000 kilometer dalam masa 100 jam sahaja. Itu baru lebih empat hari! Ini jauh lebih baik daripada pilihan penghantaran Internet. Bagaimana pula dengan kerumitan algoritma ini? Adakah ia juga linear, O(N)? Tidak, ia tidak akan. Lagipun, trak itu tidak peduli berapa banyak anda memuatkannya - ia masih akan memandu pada kelajuan yang lebih kurang sama dan tiba tepat pada masanya. Sama ada kita mempunyai 800 terabait, atau 10 kali lebih banyak data, trak itu masih akan sampai ke sana dalam masa 5 hari. Dalam erti kata lain, algoritma untuk menghantar data melalui trak mempunyai kerumitan yang berterusan . "Malar" bermakna ia tidak bergantung pada data yang dihantar kepada algoritma. Letakkan pemacu kilat 1GB dalam trak dan ia akan sampai dalam 5 hari. Letakkan cakera dengan 800 terabait data di sana dan ia akan tiba dalam masa 5 hari. Apabila menggunakan Big-O, kerumitan malar dilambangkan sebagai O(1) . Sejak kita telah berkenalan dengan O(N) danO(1) , mari kita lihat lebih banyak contoh "pengaturcara" :) Katakan anda diberi tatasusunan 100 nombor, dan tugasnya adalah untuk mencetak setiap satu daripadanya ke konsol. Anda menulis gelung biasa foryang melaksanakan tugas ini
Apakah kerumitan algoritma bertulis? Linear, O(N). Bilangan tindakan yang mesti dilakukan oleh program bergantung pada jumlah nombor yang dihantar ke dalamnya. Jika terdapat 100 nombor dalam tatasusunan, akan ada 100 tindakan (output pada skrin). Jika terdapat 10,000 nombor dalam tatasusunan, 10,000 tindakan perlu dilakukan. Bolehkah algoritma kami dipertingkatkan? Tidak. Walau apa pun, kita perlu membuat N melalui tatasusunan dan melaksanakan N output ke konsol. Mari kita lihat contoh lain.
Kami mempunyai satu yang kosong LinkedListdi mana kami memasukkan beberapa nombor. Kami perlu menganggarkan kerumitan algoritma untuk memasukkan nombor tunggal ke dalam LinkedListcontoh kami, dan bagaimana ia bergantung pada bilangan elemen dalam senarai. Jawapannya ialah O(1) - kerumitan malar . kenapa? Sila ambil perhatian: setiap kali kami memasukkan nombor pada permulaan senarai. Di samping itu, seperti yang anda ingat, apabila memasukkan nombor ke dalam LinkedListelemen, ia tidak dialihkan ke mana-mana - pautan ditakrifkan semula (jika anda tiba-tiba terlupa cara LinkedList berfungsi, lihat salah satu kuliah lama kami ). Jika sekarang nombor pertama dalam senarai kami ialah nombor х, dan kami memasukkan nombor y pada permulaan senarai, semua yang diperlukan ialah:
x.previous = y;
y.previous =null;
y.next = x;
Untuk takrifan semula rujukan ini, kami tidak kisah berapa banyak nombor yang ada sekarangLinkedList - sekurang-kurangnya satu, sekurang-kurangnya satu bilion. Kerumitan algoritma akan tetap - O(1).
Kerumitan logaritma
Jangan panik! :) Jika perkataan "logaritma" membuatkan anda ingin menutup kuliah dan tidak membaca lebih lanjut, tunggu beberapa minit. Tidak akan ada kesukaran matematik di sini (terdapat banyak penjelasan sedemikian di tempat lain), dan kami akan menganalisis semua contoh "di jari". Bayangkan bahawa tugas anda adalah untuk mencari satu nombor tertentu dalam tatasusunan 100 nombor. Lebih tepat lagi, semak sama ada ia ada sama sekali. Sebaik sahaja nombor yang diperlukan ditemui, carian mesti dihentikan, dan entri "Nombor yang diperlukan telah dijumpai!" hendaklah dipaparkan dalam konsol. Indeksnya dalam tatasusunan = ....” Bagaimana anda akan menyelesaikan masalah sedemikian? Di sini penyelesaiannya jelas: anda perlu mengulangi elemen tatasusunan satu demi satu, bermula dengan yang pertama (atau yang terakhir) dan semak sama ada nombor semasa bertepatan dengan yang dikehendaki. Sehubungan itu, bilangan tindakan secara langsung bergantung pada bilangan elemen dalam tatasusunan. Jika kita mempunyai 100 nombor, maka kita perlu pergi ke elemen seterusnya 100 kali dan menyemak nombor untuk perlawanan 100 kali. Jika terdapat 1000 nombor, maka akan ada 1000 langkah semak. Ini jelas merupakan kerumitan linear, O(N) . Sekarang kami akan menambah satu penjelasan kepada contoh kami: tatasusunan yang anda perlukan untuk mencari nombor diisih mengikut tertib menaik . Adakah ini mengubah apa-apa untuk tugas kita? Kita masih boleh mencari nombor yang dikehendaki dengan kekerasan. Tetapi kita boleh menggunakan algoritma carian binari yang terkenal sebaliknya . Di baris atas imej kita melihat tatasusunan yang diisih. Di dalamnya kita perlu mencari nombor 23. Daripada mengulangi nombor, kita hanya membahagikan tatasusunan kepada 2 bahagian dan menyemak nombor purata dalam tatasusunan. Kami mencari nombor yang terletak dalam sel 4 dan menyemaknya (baris kedua dalam gambar). Nombor ini ialah 16, dan kami sedang mencari 23. Nombor semasa adalah kurang. Apakah maksud ini? Bahawa semua nombor sebelumnya (yang terletak sehingga nombor 16) tidak perlu diperiksa : mereka pasti akan kurang daripada yang kita cari, kerana tatasusunan kita disusun! Mari teruskan pencarian di antara 5 elemen yang tinggal. Beri perhatian:Kami hanya melakukan satu pemeriksaan, tetapi kami telah menghapuskan separuh daripada pilihan yang mungkin. Kami hanya mempunyai 5 elemen lagi. Kami akan mengulangi langkah kami - sekali lagi bahagikan tatasusunan yang tinggal dengan 2 dan sekali lagi ambil elemen tengah (baris 3 dalam rajah). Nombor ini ialah 56, dan ia lebih besar daripada yang kami cari. Apakah maksud ini? Bahawa kita membuang 3 lagi pilihan - nombor 56 itu sendiri, dan dua nombor selepasnya (ia pasti lebih besar daripada 23, kerana tatasusunan diisih). Kami hanya mempunyai 2 nombor lagi untuk diperiksa (baris terakhir dalam rajah) - nombor dengan indeks tatasusunan 5 dan 6. Kami menyemak nombor pertama, dan inilah yang kami cari - nombor 23! Indeksnya = 5! Mari lihat hasil algoritma kami, dan kemudian kami akan memahami kerumitannya. (Dengan cara ini, kini anda memahami mengapa ia dipanggil binari: intipatinya adalah untuk sentiasa membahagikan data dengan 2). Hasilnya sangat mengagumkan! Jika kami mencari nombor yang dikehendaki menggunakan carian linear, kami memerlukan 10 semakan, tetapi dengan carian binari kami melakukannya dalam 3! Dalam kes yang paling teruk, akan ada 4 daripadanya, jika pada langkah terakhir nombor yang kami perlukan ternyata yang kedua, dan bukan yang pertama. Bagaimana pula dengan kerumitannya? Ini adalah perkara yang sangat menarik :) Algoritma carian binari bergantung lebih sedikit pada bilangan elemen dalam tatasusunan berbanding algoritma carian linear (iaitu, penghitungan mudah). Dengan 10 elemen dalam tatasusunan, carian linear memerlukan maksimum 10 semakan dan carian binari memerlukan maksimum 4 semakan. Perbezaannya ialah 2.5 kali ganda. Tetapi untuk tatasusunan 1000 elemen, carian linear memerlukan 1000 semakan, dan carian binari hanya memerlukan 10 ! Perbezaannya sudah 100 kali ganda! Beri perhatian:bilangan elemen dalam tatasusunan meningkat 100 kali ganda (dari 10 hingga 1000), dan bilangan semakan yang diperlukan untuk carian binari meningkat hanya 2.5 kali ganda - daripada 4 hingga 10. Jika kita mencapai 10,000 elemen , perbezaannya lebih mengagumkan: 10,000 semakan untuk carian linear, dan sejumlah 14 semakan untuk binari. Dan sekali lagi: bilangan elemen meningkat 1000 kali (dari 10 hingga 10000), tetapi bilangan cek meningkat hanya 3.5 kali (dari 4 hingga 14). Kerumitan algoritma carian binari adalah logaritma , atau, dalam tatatanda Big-O, O(log n) . Mengapa ia dipanggil begitu? Logaritma ialah songsangan bagi eksponen. Logaritma binari digunakan untuk mengira kuasa 2. Sebagai contoh, kita mempunyai 10,000 elemen yang perlu kita lalui menggunakan carian binari. Kini anda mempunyai gambar di hadapan mata anda, dan anda tahu bahawa ini memerlukan maksimum 14 pemeriksaan. Tetapi bagaimana jika tidak ada gambar di depan mata anda, dan anda perlu mengira bilangan tepat pemeriksaan yang diperlukan? Cukuplah untuk menjawab soalan mudah: pada kuasa apakah angka 2 harus dinaikkan supaya hasil yang diperoleh ialah >= bilangan elemen yang diperiksa? Untuk 10000 ia akan menjadi kuasa ke-14. 2 kepada kuasa ke-13 adalah terlalu kecil (8192) Tetapi 2 kepada kuasa ke-14 = 16384 , nombor ini memenuhi keadaan kami (ia adalah >= bilangan elemen dalam tatasusunan). Kami menjumpai logaritma - 14. Itulah jumlah semakan yang kami perlukan! :) Algoritma dan kerumitannya adalah topik yang terlalu luas untuk dimasukkan dalam satu kuliah. Tetapi mengetahuinya adalah sangat penting: dalam banyak temu bual anda akan menerima masalah algoritma. Untuk teori, saya boleh mengesyorkan anda beberapa buku. Tempat yang baik untuk bermula ialah " Algoritma Grocking ": walaupun contoh dalam buku ditulis dalam Python, bahasa dan contoh buku itu sangat mudah. Pilihan terbaik untuk pemula, dan ia juga kecil dalam jumlah. Pembacaan yang lebih serius: buku oleh Robert Laforet dan Robert Sedgwick . Kedua-duanya ditulis dalam Java, yang akan menjadikan pembelajaran lebih mudah untuk anda. Lagipun, anda sudah biasa dengan bahasa ini! :) Bagi pelajar yang mempunyai latar belakang matematik yang baik, pilihan terbaik ialah buku oleh Thomas Corman . Tetapi anda tidak akan berpuas hati dengan hanya teori! “Tahu” != “dapat” Anda boleh berlatih menyelesaikan masalah algoritma pada HackerRank dan Leetcode . Masalah dari sana sering digunakan walaupun semasa temuduga di Google dan Facebook, jadi anda pasti tidak akan bosan :) Untuk mengukuhkan bahan kuliah, saya menasihati anda untuk menonton video yang sangat baik tentang Big-O di YouTube. Jumpa anda di kuliah seterusnya! :)
Dalam kes ini, algoritma yang paling cekap ialah memindahkan fail melalui Internet. Ia hanya akan mengambil masa beberapa minit! Jadi, mari kita suarakan algoritma kami sekali lagi: "Jika anda perlu memindahkan maklumat dalam bentuk fail pada jarak 5000 kilometer, anda perlu menggunakan penghantaran data melalui Internet." Hebat. Sekarang mari kita menganalisisnya. Adakah ia menyelesaikan masalah kita? Secara umum, ya, ia menyelesaikannya sepenuhnya. Tetapi apa yang boleh anda katakan tentang kerumitannya? Hmm, sekarang di sinilah perkara menjadi menarik. Hakikatnya ialah algoritma kami sangat bergantung pada data yang masuk, iaitu saiz fail. Kini kami mempunyai 10 megabait dan semuanya baik-baik saja. Bagaimana jika kita perlu memindahkan 500 megabait? 20 gigabait? 500 terabait? 30 petabait? Adakah algoritma kami akan berhenti berfungsi? Tidak, semua jumlah data ini masih boleh dipindahkan. Adakah ia akan mengambil masa yang lebih lama untuk disiapkan? Ya ia akan! Kini kami mengetahui ciri penting algoritma kami: lebih besar saiz data yang akan dipindahkan, lebih lama algoritma akan mengambil masa untuk menyelesaikan . Tetapi kami ingin memahami dengan lebih tepat rupa hubungan ini (antara saiz data dan masa yang diperlukan untuk memindahkannya). Dalam kes kami, kerumitan algoritma akan menjadi linear. "Linear" bermaksud bahawa apabila volum data meningkat, masa untuk penghantarannya akan meningkat lebih kurang berkadar. Jika terdapat 2 kali lebih banyak data, dan ia akan mengambil 2 kali lebih masa untuk memindahkannya. Jika terdapat 10 kali lebih banyak data, masa pemindahan akan meningkat 10 kali ganda. Menggunakan tatatanda Big-O, kerumitan algoritma kami ditakrifkan sebagai O(N) . Notasi ini paling diingati untuk rujukan masa hadapan; ia sentiasa digunakan untuk algoritma dengan kerumitan linear. Sila ambil perhatian: kami tidak bercakap di sini sama sekali tentang pelbagai perkara "pembolehubah": kelajuan Internet, kuasa komputer kami, dan sebagainya. Apabila menilai kerumitan algoritma, ini tidak masuk akal - kami tidak mempunyai kawalan ke atasnya. Big-O menilai algoritma itu sendiri, tanpa mengira "persekitaran" di mana ia perlu berfungsi. Mari kita teruskan dengan contoh kita. Katakan akhirnya ternyata saiz fail yang akan dipindahkan ialah 800 terabait. Jika kita menghantarnya melalui Internet, masalahnya, sudah tentu, akan diselesaikan. Hanya ada satu masalah: penghantaran melalui pautan moden standard (pada 100 megabit sesaat) yang kebanyakan kita gunakan di rumah kita akan mengambil masa kira-kira 708 hari. Hampir 2 tahun! :O Jadi, algoritma kami jelas tidak sesuai di sini. Kami memerlukan penyelesaian lain! Tiba-tiba, Amazon gergasi IT datang membantu kami! Perkhidmatan Amazon Snowmobile membolehkan anda memuatkan sejumlah besar data ke dalam unit storan mudah alih dan menghantarnya ke alamat yang dikehendaki dengan trak! 
Jadi kami mempunyai algoritma baharu! "Jika anda perlu memindahkan maklumat dalam bentuk fail dalam jarak 5,000 kilometer, dan prosesnya akan mengambil masa lebih daripada 14 hari apabila dipindahkan melalui Internet, anda perlu menggunakan pengangkutan trak Amazon." Angka 14 hari dipilih di sini secara rawak: katakan ini adalah tempoh maksimum yang kita mampu. Mari analisa algoritma kami. Bagaimana pula dengan kelajuan? Walaupun trak itu bergerak pada kelajuan hanya 50 km/j, ia akan menempuh 5,000 kilometer dalam masa 100 jam sahaja. Itu baru lebih empat hari! Ini jauh lebih baik daripada pilihan penghantaran Internet. Bagaimana pula dengan kerumitan algoritma ini? Adakah ia juga linear, O(N)? Tidak, ia tidak akan. Lagipun, trak itu tidak peduli berapa banyak anda memuatkannya - ia masih akan memandu pada kelajuan yang lebih kurang sama dan tiba tepat pada masanya. Sama ada kita mempunyai 800 terabait, atau 10 kali lebih banyak data, trak itu masih akan sampai ke sana dalam masa 5 hari. Dalam erti kata lain, algoritma untuk menghantar data melalui trak mempunyai kerumitan yang berterusan . "Malar" bermakna ia tidak bergantung pada data yang dihantar kepada algoritma. Letakkan pemacu kilat 1GB dalam trak dan ia akan sampai dalam 5 hari. Letakkan cakera dengan 800 terabait data di sana dan ia akan tiba dalam masa 5 hari. Apabila menggunakan Big-O, kerumitan malar dilambangkan sebagai O(1) . Sejak kita telah berkenalan dengan O(N) danO(1) , mari kita lihat lebih banyak contoh "pengaturcara" :) Katakan anda diberi tatasusunan 100 nombor, dan tugasnya adalah untuk mencetak setiap satu daripadanya ke konsol. Anda menulis gelung biasa 
Di baris atas imej kita melihat tatasusunan yang diisih. Di dalamnya kita perlu mencari nombor 23. Daripada mengulangi nombor, kita hanya membahagikan tatasusunan kepada 2 bahagian dan menyemak nombor purata dalam tatasusunan. Kami mencari nombor yang terletak dalam sel 4 dan menyemaknya (baris kedua dalam gambar). Nombor ini ialah 16, dan kami sedang mencari 23. Nombor semasa adalah kurang. Apakah maksud ini? Bahawa semua nombor sebelumnya (yang terletak sehingga nombor 16) tidak perlu diperiksa : mereka pasti akan kurang daripada yang kita cari, kerana tatasusunan kita disusun! Mari teruskan pencarian di antara 5 elemen yang tinggal. Beri perhatian:Kami hanya melakukan satu pemeriksaan, tetapi kami telah menghapuskan separuh daripada pilihan yang mungkin. Kami hanya mempunyai 5 elemen lagi. Kami akan mengulangi langkah kami - sekali lagi bahagikan tatasusunan yang tinggal dengan 2 dan sekali lagi ambil elemen tengah (baris 3 dalam rajah). Nombor ini ialah 56, dan ia lebih besar daripada yang kami cari. Apakah maksud ini? Bahawa kita membuang 3 lagi pilihan - nombor 56 itu sendiri, dan dua nombor selepasnya (ia pasti lebih besar daripada 23, kerana tatasusunan diisih). Kami hanya mempunyai 2 nombor lagi untuk diperiksa (baris terakhir dalam rajah) - nombor dengan indeks tatasusunan 5 dan 6. Kami menyemak nombor pertama, dan inilah yang kami cari - nombor 23! Indeksnya = 5! Mari lihat hasil algoritma kami, dan kemudian kami akan memahami kerumitannya. (Dengan cara ini, kini anda memahami mengapa ia dipanggil binari: intipatinya adalah untuk sentiasa membahagikan data dengan 2). Hasilnya sangat mengagumkan! Jika kami mencari nombor yang dikehendaki menggunakan carian linear, kami memerlukan 10 semakan, tetapi dengan carian binari kami melakukannya dalam 3! Dalam kes yang paling teruk, akan ada 4 daripadanya, jika pada langkah terakhir nombor yang kami perlukan ternyata yang kedua, dan bukan yang pertama. Bagaimana pula dengan kerumitannya? Ini adalah perkara yang sangat menarik :) Algoritma carian binari bergantung lebih sedikit pada bilangan elemen dalam tatasusunan berbanding algoritma carian linear (iaitu, penghitungan mudah). Dengan 10 elemen dalam tatasusunan, carian linear memerlukan maksimum 10 semakan dan carian binari memerlukan maksimum 4 semakan. Perbezaannya ialah 2.5 kali ganda. Tetapi untuk tatasusunan 1000 elemen, carian linear memerlukan 1000 semakan, dan carian binari hanya memerlukan 10 ! Perbezaannya sudah 100 kali ganda! Beri perhatian:bilangan elemen dalam tatasusunan meningkat 100 kali ganda (dari 10 hingga 1000), dan bilangan semakan yang diperlukan untuk carian binari meningkat hanya 2.5 kali ganda - daripada 4 hingga 10. Jika kita mencapai 10,000 elemen , perbezaannya lebih mengagumkan: 10,000 semakan untuk carian linear, dan sejumlah 14 semakan untuk binari. Dan sekali lagi: bilangan elemen meningkat 1000 kali (dari 10 hingga 10000), tetapi bilangan cek meningkat hanya 3.5 kali (dari 4 hingga 14). Kerumitan algoritma carian binari adalah logaritma , atau, dalam tatatanda Big-O, O(log n) . Mengapa ia dipanggil begitu? Logaritma ialah songsangan bagi eksponen. Logaritma binari digunakan untuk mengira kuasa 2. Sebagai contoh, kita mempunyai 10,000 elemen yang perlu kita lalui menggunakan carian binari. 
Kini anda mempunyai gambar di hadapan mata anda, dan anda tahu bahawa ini memerlukan maksimum 14 pemeriksaan. Tetapi bagaimana jika tidak ada gambar di depan mata anda, dan anda perlu mengira bilangan tepat pemeriksaan yang diperlukan? Cukuplah untuk menjawab soalan mudah: pada kuasa apakah angka 2 harus dinaikkan supaya hasil yang diperoleh ialah >= bilangan elemen yang diperiksa? Untuk 10000 ia akan menjadi kuasa ke-14. 2 kepada kuasa ke-13 adalah terlalu kecil (8192) Tetapi 2 kepada kuasa ke-14 = 16384 , nombor ini memenuhi keadaan kami (ia adalah >= bilangan elemen dalam tatasusunan). Kami menjumpai logaritma - 14. Itulah jumlah semakan yang kami perlukan! :) Algoritma dan kerumitannya adalah topik yang terlalu luas untuk dimasukkan dalam satu kuliah. Tetapi mengetahuinya adalah sangat penting: dalam banyak temu bual anda akan menerima masalah algoritma. Untuk teori, saya boleh mengesyorkan anda beberapa buku. Tempat yang baik untuk bermula ialah " Algoritma Grocking ": walaupun contoh dalam buku ditulis dalam Python, bahasa dan contoh buku itu sangat mudah. Pilihan terbaik untuk pemula, dan ia juga kecil dalam jumlah. Pembacaan yang lebih serius: buku oleh Robert Laforet dan Robert Sedgwick . Kedua-duanya ditulis dalam Java, yang akan menjadikan pembelajaran lebih mudah untuk anda. Lagipun, anda sudah biasa dengan bahasa ini! :) Bagi pelajar yang mempunyai latar belakang matematik yang baik, pilihan terbaik ialah buku oleh Thomas Corman . Tetapi anda tidak akan berpuas hati dengan hanya teori! “Tahu” != “dapat” Anda boleh berlatih menyelesaikan masalah algoritma pada HackerRank dan Leetcode . Masalah dari sana sering digunakan walaupun semasa temuduga di Google dan Facebook, jadi anda pasti tidak akan bosan :) Untuk mengukuhkan bahan kuliah, saya menasihati anda untuk menonton video yang sangat baik tentang Big-O di YouTube. Jumpa anda di kuliah seterusnya! :)
GO TO FULL VERSION