Hai! Pelajaran hari ini akan berbeza sedikit daripada yang lain. Ia akan berbeza kerana ia hanya berkaitan secara tidak langsung dengan Java. ![Kerumitan algoritma - 1]()
Yang berkata, topik ini sangat penting untuk setiap pengaturcara. Kita akan bercakap tentang algoritma . Apakah algoritma? Secara ringkas, ini adalah beberapa urutan tindakan yang mesti diselesaikan untuk mencapai hasil yang diinginkan . Kami sering menggunakan algoritma dalam kehidupan seharian. Sebagai contoh, setiap pagi anda mempunyai tugas tertentu: pergi ke sekolah atau kerja, dan pada masa yang sama:
![Kerumitan algoritma - 2]()
Dalam kes ini, algoritma yang paling cekap ialah menghantar fail melalui Internet. Ia tidak boleh mengambil lebih daripada beberapa minit! Mari nyatakan semula algoritma kami: "Jika anda ingin memindahkan maklumat dalam bentuk fail pada jarak 5000 batu, anda harus menghantar data melalui Internet". Cemerlang. Sekarang mari kita menganalisisnya. Adakah ia menyelesaikan tugas kita?Ya, memang begitu. Tetapi apa yang boleh kita katakan tentang kerumitannya? Hmm, sekarang keadaan semakin menarik. Hakikatnya ialah algoritma kami sangat bergantung pada data input, iaitu saiz fail. Jika kita mempunyai 10 megabait, maka semuanya baik-baik saja. Tetapi bagaimana jika kita perlu menghantar 500 megabait? 20 gigabait? 500 terabait? 30 petabait? Adakah algoritma kami akan berhenti berfungsi? Tidak, semua jumlah data ini sememangnya boleh dipindahkan. Adakah ia akan mengambil masa yang lebih lama? Ya ia akan! Kini kami mengetahui ciri penting algoritma kami: lebih besar jumlah data untuk dihantar, lebih lama masa yang diperlukan untuk menjalankan algoritma. Tetapi kami ingin mempunyai pemahaman yang lebih tepat tentang hubungan ini (antara saiz data input dan masa yang diperlukan untuk menghantarnya). Dalam kes kami, kerumitan algoritma adalah linear . "Linear" bermaksud bahawa apabila jumlah data input meningkat, masa yang diperlukan untuk menghantarnya akan meningkat lebih kurang secara berkadar. Jika jumlah data berganda, maka masa yang diperlukan untuk menghantarnya akan menjadi dua kali ganda. Jika data meningkat sebanyak 10 kali, maka masa penghantaran akan meningkat 10 kali ganda. Menggunakan notasi O besar, kerumitan algoritma kami dinyatakan sebagai O(n). Anda harus ingat tatatanda ini untuk masa hadapan — ia sentiasa digunakan untuk algoritma dengan kerumitan linear. Ambil perhatian bahawa kita tidak bercakap tentang beberapa perkara yang mungkin berbeza-beza di sini: kelajuan Internet, kuasa pengiraan komputer kita dan sebagainya. Apabila menilai kerumitan algoritma, adalah tidak masuk akal untuk mempertimbangkan faktor-faktor ini — dalam apa jua keadaan, ia berada di luar kawalan kami. Notasi Big O menyatakan kerumitan algoritma itu sendiri, bukan "persekitaran" yang dijalankannya. Mari kita teruskan dengan contoh kita. Katakan bahawa kita akhirnya mengetahui bahawa kita perlu menghantar fail berjumlah 800 terabait. Kita boleh, sudah tentu, menyelesaikan tugas kita dengan menghantarnya melalui Internet. Hanya ada satu masalah: pada kadar penghantaran data isi rumah standard (100 megabit sesaat), ia akan mengambil masa kira-kira 708 hari. Hampir 2 tahun! :O Algoritma kami jelas tidak sesuai di sini. Kami memerlukan penyelesaian lain! Tanpa diduga, Amazon gergasi IT datang untuk menyelamatkan kami! Perkhidmatan Snowmobile Amazon membolehkan kami memuat naik sejumlah besar data ke storan mudah alih dan kemudian menghantarnya ke alamat yang dikehendaki dengan trak! ![Kerumitan algoritma - 3]()
Jadi, kami mempunyai algoritma baharu! "Jika anda ingin memindahkan maklumat dalam bentuk fail dalam jarak 5000 batu dan berbuat demikian akan mengambil masa lebih daripada 14 hari untuk dihantar melalui Internet, anda harus menghantar data pada trak Amazon." Kami memilih 14 hari sewenang-wenangnya di sini. Katakan ini adalah tempoh paling lama yang boleh kita tunggu. Mari analisa algoritma kami. Bagaimana dengan kelajuannya? Walaupun trak itu bergerak pada 50 mph sahaja, ia akan meliputi 5000 batu dalam masa 100 jam sahaja. Ini adalah lebih kurang empat hari! Ini jauh lebih baik daripada pilihan menghantar data melalui Internet. Dan bagaimana pula dengan kerumitan algoritma ini? Adakah ia juga linear, iaitu O(n)? Tidak, ia bukan. Lagipun, trak itu tidak peduli seberapa berat anda memuatkannya — ia masih akan memandu pada kelajuan yang sama dan tiba tepat pada masanya. Sama ada kita mempunyai 800 terabait, atau 10 kali ganda itu, trak itu masih akan sampai ke destinasinya dalam masa 5 hari. Dengan kata lain, algoritma pemindahan data berasaskan trak mempunyai kerumitan yang berterusan. Di sini, "malar" bermakna ia tidak bergantung pada saiz data input. Letakkan pemacu kilat 1GB dalam trak, ia akan sampai dalam masa 5 hari. Letakkan dalam cakera yang mengandungi 800 terabait data, ia akan tiba dalam masa 5 hari. Apabila menggunakan tatatanda O besar, kerumitan malar dilambangkan dengan O(1) . Kami telah menjadi biasa dengan O(n) dan O(1) , jadi sekarang mari kita lihat lebih banyak contoh dalam dunia pengaturcaraan :) Katakan anda diberi tatasusunan 100 nombor, dan tugasnya adalah untuk memaparkan setiap satu daripadanya pada konsol itu. Anda menulis gelung biasa ![Kerumitan algoritma - 5]()
Di baris atas dalam imej, kita melihat tatasusunan yang diisih. Kita perlu mencari nombor 23 di dalamnya. Daripada mengulangi nombor, kami hanya membahagikan tatasusunan kepada 2 bahagian dan semak nombor tengah dalam tatasusunan. Cari nombor yang terletak dalam sel 4 dan semaknya (baris kedua dalam imej). Nombor ini ialah 16, dan kami sedang mencari 23. Nombor semasa adalah kurang daripada apa yang kami cari. Apakah maksudnya? Maksudnya begitusemua nombor sebelumnya (yang terletak sebelum nombor 16) tidak perlu diperiksa : ia dijamin kurang daripada yang kita cari, kerana tatasusunan kita disusun! Kami meneruskan pencarian di antara 5 elemen yang tinggal. Catatan:kami telah melakukan hanya satu perbandingan, tetapi kami telah menghapuskan separuh daripada pilihan yang mungkin. Kami hanya mempunyai 5 elemen lagi. Kami akan mengulangi langkah sebelumnya dengan sekali lagi membahagikan subarray yang tinggal kepada separuh dan sekali lagi mengambil elemen tengah (baris ke-3 dalam imej). Nombornya ialah 56, dan ia lebih besar daripada yang kami cari. Apakah maksudnya? Ini bermakna kami telah menghapuskan 3 lagi kemungkinan: nombor 56 itu sendiri serta dua nombor selepasnya (kerana ia dijamin lebih besar daripada 23, kerana tatasusunan disusun). Kami hanya mempunyai 2 nombor yang tinggal untuk diperiksa (baris terakhir dalam imej) — nombor dengan indeks tatasusunan 5 dan 6. Kami menyemak nombor pertama dan mencari apa yang kami cari — nombor 23! Indeksnya ialah 5! Mari kita lihat hasil algoritma kami, dan kemudian kami' akan menganalisis kerumitannya. Ngomong-ngomong, kini anda faham mengapa ini dipanggil carian binari: ia bergantung pada membahagikan data berulang kali kepada separuh. Hasilnya sangat mengagumkan! Jika kami menggunakan carian linear untuk mencari nombor, kami memerlukan sehingga 10 perbandingan, tetapi dengan carian binari, kami menyelesaikan tugas dengan hanya 3! Dalam kes yang paling teruk, akan ada 4 perbandingan (jika dalam langkah terakhir nombor yang kita inginkan adalah yang kedua daripada kemungkinan yang tinggal, bukannya yang pertama. Jadi bagaimana pula dengan kerumitannya? Ini adalah perkara yang sangat menarik :) Algoritma carian binari adalah kurang bergantung kepada bilangan elemen dalam tatasusunan berbanding algoritma carian linear (iaitu, lelaran mudah). Dengan 10 elemen dalam tatasusunan, carian linear memerlukan maksimum 10 perbandingan, tetapi carian binari memerlukan maksimum 4 perbandingan. Itu perbezaan dengan faktor 2.5. Tetapi untuk tatasusunan 1000 elemen , carian linear memerlukan sehingga 1000 perbandingan, tetapi carian binari hanya memerlukan 10 ! Perbezaannya kini 100 kali ganda! Catatan:bilangan elemen dalam tatasusunan telah meningkat 100 kali ganda (dari 10 hingga 1000), tetapi bilangan perbandingan yang diperlukan untuk carian binari telah meningkat dengan faktor hanya 2.5 (dari 4 hingga 10). Jika kita sampai kepada 10,000 elemen , perbezaannya akan menjadi lebih mengagumkan: 10,000 perbandingan untuk carian linear, dan sejumlah 14 perbandingan untuk carian binari. Dan sekali lagi, jika bilangan elemen meningkat sebanyak 1000 kali (dari 10 hingga 10000), maka bilangan perbandingan meningkat dengan faktor hanya 3.5 (dari 4 hingga 14). Kerumitan algoritma carian binari adalah logaritma , atau, jika kita menggunakan notasi O besar, O(log n). Mengapa ia dipanggil begitu? Logaritma adalah seperti lawan eksponen. Logaritma binari ialah kuasa yang nombor 2 mesti dinaikkan untuk mendapatkan nombor. Sebagai contoh, kami mempunyai 10,000 elemen yang kami perlukan untuk mencari menggunakan algoritma carian binari. ![Kerumitan algoritma - 6]()
Pada masa ini, anda boleh melihat jadual nilai untuk mengetahui bahawa melakukan ini memerlukan maksimum 14 perbandingan. Tetapi bagaimana jika tiada siapa yang menyediakan jadual sedemikian dan anda perlu mengira bilangan perbandingan maksimum yang tepat? Anda hanya perlu menjawab soalan mudah: kuasa apa yang anda perlukan untuk menaikkan nombor 2 supaya hasilnya lebih besar daripada atau sama dengan bilangan elemen yang akan diperiksa? Untuk 10,000, ia adalah kuasa ke-14. 2 hingga kuasa ke-13 terlalu kecil (8192), tetapi 2 hingga kuasa ke-14 = 16384, dan nombor ini memenuhi keadaan kami (ia lebih besar daripada atau sama dengan bilangan elemen dalam tatasusunan). Kami mendapati logaritma: 14. Itulah berapa banyak perbandingan yang mungkin kami perlukan! :) Algoritma dan kerumitan algoritma adalah topik yang terlalu luas untuk dimuatkan ke dalam satu pelajaran. Tetapi mengetahuinya adalah sangat penting: banyak temu duga kerja akan melibatkan soalan yang melibatkan algoritma. Untuk teori, saya boleh mengesyorkan beberapa buku untuk anda. Anda boleh mulakan dengan " Algoritma Grokking ". Contoh dalam buku ini ditulis dalam Python, tetapi buku ini menggunakan bahasa dan contoh yang sangat mudah. Ia adalah pilihan terbaik untuk pemula dan, lebih-lebih lagi, ia tidak terlalu besar. Antara bacaan yang lebih serius, kami mempunyai buku oleh Robert Lafore dan Robert Sedgewick. Kedua-duanya ditulis dalam Java, yang akan menjadikan pembelajaran lebih mudah untuk anda. Lagipun, anda sudah biasa dengan bahasa ini! :) Bagi pelajar yang mempunyai kemahiran matematik yang baik, pilihan terbaik ialah buku Thomas Cormen . Tetapi teori sahaja tidak akan mengisi perut anda! Pengetahuan != Kebolehan . Anda boleh berlatih menyelesaikan masalah yang melibatkan algoritma pada HackerRank dan LeetCode . Tugasan daripada tapak web ini sering digunakan walaupun semasa temu duga di Google dan Facebook, jadi anda pasti tidak akan bosan :) Untuk mengukuhkan bahan pelajaran ini, saya syorkan anda menonton video yang sangat baik ini tentang notasi O besar di YouTube. Jumpa anda dalam pelajaran seterusnya! :)
Yang berkata, topik ini sangat penting untuk setiap pengaturcara. Kita akan bercakap tentang algoritma . Apakah algoritma? Secara ringkas, ini adalah beberapa urutan tindakan yang mesti diselesaikan untuk mencapai hasil yang diinginkan . Kami sering menggunakan algoritma dalam kehidupan seharian. Sebagai contoh, setiap pagi anda mempunyai tugas tertentu: pergi ke sekolah atau kerja, dan pada masa yang sama:
- Berpakaian
- Bersih
- makan
- Bangun tidur menggunakan jam penggera.
- Mandi dan basuh diri.
- Sediakan sarapan pagi dan kopi atau teh.
- makan.
- Jika anda tidak menyeterika pakaian anda pada petang sebelumnya, maka seterikanya.
- Berpakaian.
- Tinggalkan rumah.
- Beli atau muat turun Kamus Antarabangsa Baharu Webster edisi 1961.
- Cari setiap nama daripada senarai kami dalam kamus ini.
- Pada sehelai kertas, tulis halaman kamus di mana nama itu terletak.
- Gunakan kepingan kertas untuk mengisih nama.
Dalam kes ini, algoritma yang paling cekap ialah menghantar fail melalui Internet. Ia tidak boleh mengambil lebih daripada beberapa minit! Mari nyatakan semula algoritma kami: "Jika anda ingin memindahkan maklumat dalam bentuk fail pada jarak 5000 batu, anda harus menghantar data melalui Internet". Cemerlang. Sekarang mari kita menganalisisnya. Adakah ia menyelesaikan tugas kita?Ya, memang begitu. Tetapi apa yang boleh kita katakan tentang kerumitannya? Hmm, sekarang keadaan semakin menarik. Hakikatnya ialah algoritma kami sangat bergantung pada data input, iaitu saiz fail. Jika kita mempunyai 10 megabait, maka semuanya baik-baik saja. Tetapi bagaimana jika kita perlu menghantar 500 megabait? 20 gigabait? 500 terabait? 30 petabait? Adakah algoritma kami akan berhenti berfungsi? Tidak, semua jumlah data ini sememangnya boleh dipindahkan. Adakah ia akan mengambil masa yang lebih lama? Ya ia akan! Kini kami mengetahui ciri penting algoritma kami: lebih besar jumlah data untuk dihantar, lebih lama masa yang diperlukan untuk menjalankan algoritma. Tetapi kami ingin mempunyai pemahaman yang lebih tepat tentang hubungan ini (antara saiz data input dan masa yang diperlukan untuk menghantarnya). Dalam kes kami, kerumitan algoritma adalah linear . "Linear" bermaksud bahawa apabila jumlah data input meningkat, masa yang diperlukan untuk menghantarnya akan meningkat lebih kurang secara berkadar. Jika jumlah data berganda, maka masa yang diperlukan untuk menghantarnya akan menjadi dua kali ganda. Jika data meningkat sebanyak 10 kali, maka masa penghantaran akan meningkat 10 kali ganda. Menggunakan notasi O besar, kerumitan algoritma kami dinyatakan sebagai O(n). Anda harus ingat tatatanda ini untuk masa hadapan — ia sentiasa digunakan untuk algoritma dengan kerumitan linear. Ambil perhatian bahawa kita tidak bercakap tentang beberapa perkara yang mungkin berbeza-beza di sini: kelajuan Internet, kuasa pengiraan komputer kita dan sebagainya. Apabila menilai kerumitan algoritma, adalah tidak masuk akal untuk mempertimbangkan faktor-faktor ini — dalam apa jua keadaan, ia berada di luar kawalan kami. Notasi Big O menyatakan kerumitan algoritma itu sendiri, bukan "persekitaran" yang dijalankannya. Mari kita teruskan dengan contoh kita. Katakan bahawa kita akhirnya mengetahui bahawa kita perlu menghantar fail berjumlah 800 terabait. Kita boleh, sudah tentu, menyelesaikan tugas kita dengan menghantarnya melalui Internet. Hanya ada satu masalah: pada kadar penghantaran data isi rumah standard (100 megabit sesaat), ia akan mengambil masa kira-kira 708 hari. Hampir 2 tahun! :O Algoritma kami jelas tidak sesuai di sini. Kami memerlukan penyelesaian lain! Tanpa diduga, Amazon gergasi IT datang untuk menyelamatkan kami! Perkhidmatan Snowmobile Amazon membolehkan kami memuat naik sejumlah besar data ke storan mudah alih dan kemudian menghantarnya ke alamat yang dikehendaki dengan trak! 
Jadi, kami mempunyai algoritma baharu! "Jika anda ingin memindahkan maklumat dalam bentuk fail dalam jarak 5000 batu dan berbuat demikian akan mengambil masa lebih daripada 14 hari untuk dihantar melalui Internet, anda harus menghantar data pada trak Amazon." Kami memilih 14 hari sewenang-wenangnya di sini. Katakan ini adalah tempoh paling lama yang boleh kita tunggu. Mari analisa algoritma kami. Bagaimana dengan kelajuannya? Walaupun trak itu bergerak pada 50 mph sahaja, ia akan meliputi 5000 batu dalam masa 100 jam sahaja. Ini adalah lebih kurang empat hari! Ini jauh lebih baik daripada pilihan menghantar data melalui Internet. Dan bagaimana pula dengan kerumitan algoritma ini? Adakah ia juga linear, iaitu O(n)? Tidak, ia bukan. Lagipun, trak itu tidak peduli seberapa berat anda memuatkannya — ia masih akan memandu pada kelajuan yang sama dan tiba tepat pada masanya. Sama ada kita mempunyai 800 terabait, atau 10 kali ganda itu, trak itu masih akan sampai ke destinasinya dalam masa 5 hari. Dengan kata lain, algoritma pemindahan data berasaskan trak mempunyai kerumitan yang berterusan. Di sini, "malar" bermakna ia tidak bergantung pada saiz data input. Letakkan pemacu kilat 1GB dalam trak, ia akan sampai dalam masa 5 hari. Letakkan dalam cakera yang mengandungi 800 terabait data, ia akan tiba dalam masa 5 hari. Apabila menggunakan tatatanda O besar, kerumitan malar dilambangkan dengan O(1) . Kami telah menjadi biasa dengan O(n) dan O(1) , jadi sekarang mari kita lihat lebih banyak contoh dalam dunia pengaturcaraan :) Katakan anda diberi tatasusunan 100 nombor, dan tugasnya adalah untuk memaparkan setiap satu daripadanya pada konsol itu. Anda menulis gelung biasa foryang melaksanakan tugas ini
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
LinkedListdi mana kami memasukkan beberapa nombor. Kita perlu menilai kerumitan algoritma untuk memasukkan nombor tunggal ke dalam LinkedListcontoh kita, dan bagaimana ia bergantung pada bilangan elemen dalam senarai. Jawapannya ialah O(1), iaitu kerumitan malar . kenapa? Ambil perhatian bahawa kami memasukkan setiap nombor pada permulaan senarai. Di samping itu, anda akan ingat bahawa apabila anda memasukkan nombor ke dalam LinkedList, unsur-unsur tidak bergerak ke mana-mana. Pautan (atau rujukan) dikemas kini (jika anda terlupa cara LinkedList berfungsi, lihat salah satu pelajaran lama kami ). Jika nombor pertama dalam senarai kami ialah x, dan kami memasukkan nombor y di hadapan senarai, maka apa yang perlu kami lakukan ialah ini:
x.previous = y;
y.previous = null;
y.next = x;
LinkedList , sama ada satu atau satu bilion. Kerumitan algoritma adalah malar, iaitu O(1).
Kerumitan logaritma
Jangan panik! :) Jika perkataan "logaritma" membuatkan anda ingin menutup pelajaran ini dan berhenti membaca, hanya tahan selama beberapa minit. Tidak akan ada matematik gila di sini (terdapat banyak penjelasan seperti itu di tempat lain), dan kami akan memilih setiap contoh. Bayangkan bahawa tugas anda adalah untuk mencari satu nombor tertentu dalam tatasusunan 100 nombor. Lebih tepat lagi, anda perlu menyemak sama ada ia ada atau tidak. Sebaik sahaja nombor yang diperlukan ditemui, carian tamat, dan anda memaparkan perkara berikut dalam konsol: "Nombor yang diperlukan ditemui! Indeksnya dalam tatasusunan = ...." Bagaimana anda akan menyelesaikan tugas ini? Di sini penyelesaiannya adalah jelas: anda perlu mengulangi elemen tatasusunan satu demi satu, bermula dari yang pertama (atau dari yang terakhir) dan semak sama ada nombor semasa sepadan dengan yang anda cari. Sehubungan itu, bilangan tindakan secara langsung bergantung pada bilangan elemen dalam tatasusunan. Jika kita mempunyai 100 nombor, maka kita mungkin perlu pergi ke elemen seterusnya 100 kali dan melakukan 100 perbandingan. Jika terdapat 1000 nombor, maka mungkin terdapat 1000 perbandingan. Ini jelas merupakan kerumitan linear, iaituO(n) . Dan sekarang kami akan menambah satu penghalusan pada contoh kami: tatasusunan yang anda perlukan untuk mencari nombor diisih mengikut tertib menaik . Adakah ini mengubah apa-apa berkaitan tugas kita? Kami masih boleh melakukan carian kekerasan untuk nombor yang dikehendaki. Tetapi sebagai alternatif, kita boleh menggunakan algoritma carian binari yang terkenal .
Di baris atas dalam imej, kita melihat tatasusunan yang diisih. Kita perlu mencari nombor 23 di dalamnya. Daripada mengulangi nombor, kami hanya membahagikan tatasusunan kepada 2 bahagian dan semak nombor tengah dalam tatasusunan. Cari nombor yang terletak dalam sel 4 dan semaknya (baris kedua dalam imej). Nombor ini ialah 16, dan kami sedang mencari 23. Nombor semasa adalah kurang daripada apa yang kami cari. Apakah maksudnya? Maksudnya begitusemua nombor sebelumnya (yang terletak sebelum nombor 16) tidak perlu diperiksa : ia dijamin kurang daripada yang kita cari, kerana tatasusunan kita disusun! Kami meneruskan pencarian di antara 5 elemen yang tinggal. Catatan:kami telah melakukan hanya satu perbandingan, tetapi kami telah menghapuskan separuh daripada pilihan yang mungkin. Kami hanya mempunyai 5 elemen lagi. Kami akan mengulangi langkah sebelumnya dengan sekali lagi membahagikan subarray yang tinggal kepada separuh dan sekali lagi mengambil elemen tengah (baris ke-3 dalam imej). Nombornya ialah 56, dan ia lebih besar daripada yang kami cari. Apakah maksudnya? Ini bermakna kami telah menghapuskan 3 lagi kemungkinan: nombor 56 itu sendiri serta dua nombor selepasnya (kerana ia dijamin lebih besar daripada 23, kerana tatasusunan disusun). Kami hanya mempunyai 2 nombor yang tinggal untuk diperiksa (baris terakhir dalam imej) — nombor dengan indeks tatasusunan 5 dan 6. Kami menyemak nombor pertama dan mencari apa yang kami cari — nombor 23! Indeksnya ialah 5! Mari kita lihat hasil algoritma kami, dan kemudian kami' akan menganalisis kerumitannya. Ngomong-ngomong, kini anda faham mengapa ini dipanggil carian binari: ia bergantung pada membahagikan data berulang kali kepada separuh. Hasilnya sangat mengagumkan! Jika kami menggunakan carian linear untuk mencari nombor, kami memerlukan sehingga 10 perbandingan, tetapi dengan carian binari, kami menyelesaikan tugas dengan hanya 3! Dalam kes yang paling teruk, akan ada 4 perbandingan (jika dalam langkah terakhir nombor yang kita inginkan adalah yang kedua daripada kemungkinan yang tinggal, bukannya yang pertama. Jadi bagaimana pula dengan kerumitannya? Ini adalah perkara yang sangat menarik :) Algoritma carian binari adalah kurang bergantung kepada bilangan elemen dalam tatasusunan berbanding algoritma carian linear (iaitu, lelaran mudah). Dengan 10 elemen dalam tatasusunan, carian linear memerlukan maksimum 10 perbandingan, tetapi carian binari memerlukan maksimum 4 perbandingan. Itu perbezaan dengan faktor 2.5. Tetapi untuk tatasusunan 1000 elemen , carian linear memerlukan sehingga 1000 perbandingan, tetapi carian binari hanya memerlukan 10 ! Perbezaannya kini 100 kali ganda! Catatan:bilangan elemen dalam tatasusunan telah meningkat 100 kali ganda (dari 10 hingga 1000), tetapi bilangan perbandingan yang diperlukan untuk carian binari telah meningkat dengan faktor hanya 2.5 (dari 4 hingga 10). Jika kita sampai kepada 10,000 elemen , perbezaannya akan menjadi lebih mengagumkan: 10,000 perbandingan untuk carian linear, dan sejumlah 14 perbandingan untuk carian binari. Dan sekali lagi, jika bilangan elemen meningkat sebanyak 1000 kali (dari 10 hingga 10000), maka bilangan perbandingan meningkat dengan faktor hanya 3.5 (dari 4 hingga 14). Kerumitan algoritma carian binari adalah logaritma , atau, jika kita menggunakan notasi O besar, O(log n). Mengapa ia dipanggil begitu? Logaritma adalah seperti lawan eksponen. Logaritma binari ialah kuasa yang nombor 2 mesti dinaikkan untuk mendapatkan nombor. Sebagai contoh, kami mempunyai 10,000 elemen yang kami perlukan untuk mencari menggunakan algoritma carian binari. 
Pada masa ini, anda boleh melihat jadual nilai untuk mengetahui bahawa melakukan ini memerlukan maksimum 14 perbandingan. Tetapi bagaimana jika tiada siapa yang menyediakan jadual sedemikian dan anda perlu mengira bilangan perbandingan maksimum yang tepat? Anda hanya perlu menjawab soalan mudah: kuasa apa yang anda perlukan untuk menaikkan nombor 2 supaya hasilnya lebih besar daripada atau sama dengan bilangan elemen yang akan diperiksa? Untuk 10,000, ia adalah kuasa ke-14. 2 hingga kuasa ke-13 terlalu kecil (8192), tetapi 2 hingga kuasa ke-14 = 16384, dan nombor ini memenuhi keadaan kami (ia lebih besar daripada atau sama dengan bilangan elemen dalam tatasusunan). Kami mendapati logaritma: 14. Itulah berapa banyak perbandingan yang mungkin kami perlukan! :) Algoritma dan kerumitan algoritma adalah topik yang terlalu luas untuk dimuatkan ke dalam satu pelajaran. Tetapi mengetahuinya adalah sangat penting: banyak temu duga kerja akan melibatkan soalan yang melibatkan algoritma. Untuk teori, saya boleh mengesyorkan beberapa buku untuk anda. Anda boleh mulakan dengan " Algoritma Grokking ". Contoh dalam buku ini ditulis dalam Python, tetapi buku ini menggunakan bahasa dan contoh yang sangat mudah. Ia adalah pilihan terbaik untuk pemula dan, lebih-lebih lagi, ia tidak terlalu besar. Antara bacaan yang lebih serius, kami mempunyai buku oleh Robert Lafore dan Robert Sedgewick. Kedua-duanya ditulis dalam Java, yang akan menjadikan pembelajaran lebih mudah untuk anda. Lagipun, anda sudah biasa dengan bahasa ini! :) Bagi pelajar yang mempunyai kemahiran matematik yang baik, pilihan terbaik ialah buku Thomas Cormen . Tetapi teori sahaja tidak akan mengisi perut anda! Pengetahuan != Kebolehan . Anda boleh berlatih menyelesaikan masalah yang melibatkan algoritma pada HackerRank dan LeetCode . Tugasan daripada tapak web ini sering digunakan walaupun semasa temu duga di Google dan Facebook, jadi anda pasti tidak akan bosan :) Untuk mengukuhkan bahan pelajaran ini, saya syorkan anda menonton video yang sangat baik ini tentang notasi O besar di YouTube. Jumpa anda dalam pelajaran seterusnya! :)
GO TO FULL VERSION