Hai! Pelajaran hari ini akan berbeza sedikit daripada yang lain. Ia akan berbeza kerana ia hanya berkaitan secara tidak langsung dengan Java. 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
Algoritma apakah yang membolehkan anda mencapai hasil ini?
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.
Urutan tindakan ini pasti akan membolehkan anda mendapat hasil yang diingini. Dalam pengaturcaraan, kami sentiasa berusaha untuk menyelesaikan tugasan. Sebahagian besar daripada tugasan ini boleh dilakukan menggunakan algoritma yang telah diketahui. Sebagai contoh, katakan tugas anda ialah: mengisih senarai 100 nama dalam tatasusunan . Tugas ini agak mudah, tetapi ia boleh diselesaikan dengan cara yang berbeza. Berikut ialah satu penyelesaian yang mungkin: Algoritma untuk mengisih nama mengikut abjad:
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.
Adakah urutan tindakan sedemikian akan menyelesaikan tugas kita? Ya, ia pasti akan berlaku. Adakah penyelesaian ini cekap ? hampir tidak. Di sini kita sampai kepada satu lagi aspek algoritma yang sangat penting: kecekapannya . Terdapat beberapa cara untuk menyelesaikan tugas ini. Tetapi dalam pengaturcaraan dan dalam kehidupan biasa, kami mahu memilih cara yang paling berkesan. Jika tugas anda adalah membuat roti bakar yang disapu mentega, anda boleh mulakan dengan menyemai gandum dan memerah susu lembu. Tetapi itu akan menjadi tidak cekappenyelesaian — ia akan mengambil banyak masa dan akan menelan belanja yang banyak. Anda boleh menyelesaikan tugas mudah anda dengan hanya membeli roti dan mentega. Walaupun ia membenarkan anda menyelesaikan masalah, algoritma yang melibatkan gandum dan seekor lembu terlalu rumit untuk digunakan dalam amalan. Dalam pengaturcaraan, kami mempunyai notasi khas yang dipanggil notasi O besar untuk menilai kerumitan algoritma. Big O memungkinkan untuk menilai berapa banyak masa pelaksanaan algoritma bergantung pada saiz data input . Mari kita lihat contoh paling mudah: pemindahan data. Bayangkan anda perlu menghantar beberapa maklumat dalam bentuk fail dalam jarak yang jauh (contohnya, 5000 batu). Algoritma apakah yang paling berkesan? Ia bergantung pada data yang anda gunakan. Sebagai contoh, katakan kita mempunyai fail audio yang berukuran 10 MB. 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);
}
Apakah kerumitan algoritma ini? Linear, iaitu O(n). Bilangan tindakan yang mesti dilakukan oleh program bergantung pada bilangan nombor yang dihantar kepadanya. Jika terdapat 100 nombor dalam tatasusunan, akan ada 100 tindakan (pernyataan untuk memaparkan rentetan pada skrin). Jika terdapat 10,000 nombor dalam tatasusunan, maka 10,000 tindakan mesti dilakukan. Bolehkah algoritma kami dipertingkatkan dalam apa jua cara? Tidak. Tidak kira apa, kita perlu membuat N melalui tatasusunan dan melaksanakan penyataan N untuk memaparkan rentetan pada konsol. Pertimbangkan contoh lain.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Kami mempunyai kosong 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;
Apabila kami mengemas kini pautan, kami tidak kisah berapa banyak nombor yang sudah ada dalamLinkedList , 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! :)
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:
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 
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