Hai! Pelajaran hari ini akan sedikit berbeda dari yang lain. Ini akan berbeda karena hanya terkait secara tidak langsung dengan Jawa. Konon, topik ini sangat penting bagi setiap programmer. Kita akan berbicara tentang algoritma . Apa itu algoritma? Secara sederhana, itu adalah beberapa urutan tindakan yang harus diselesaikan untuk mencapai hasil yang diinginkan . Kami sering menggunakan algoritma dalam kehidupan sehari-hari. Misalnya, setiap pagi Anda memiliki tugas tertentu: pergi ke sekolah atau bekerja, dan pada saat yang sama menjadi:
Berpakaian
Membersihkan
Diberi makan
Algoritme apa yang memungkinkan Anda mencapai hasil ini?
Bangun menggunakan jam alarm.
Mandi dan bersihkan dirimu.
Buat sarapan dan kopi atau teh.
Makan.
Jika Anda tidak menyetrika pakaian Anda pada malam sebelumnya, maka setrikalah.
Berpakaian.
Meninggalkan rumah.
Urutan tindakan ini pasti akan membuat Anda mendapatkan hasil yang diinginkan. Dalam pemrograman, kami terus bekerja untuk menyelesaikan tugas. Sebagian besar tugas ini dapat dilakukan dengan menggunakan algoritme yang sudah dikenal. Misalnya, tugas Anda adalah untuk ini: mengurutkan daftar 100 nama dalam sebuah array . Tugas ini cukup sederhana, tetapi dapat diselesaikan dengan berbagai cara. Berikut adalah salah satu solusi yang mungkin: Algoritma untuk mengurutkan nama menurut abjad:
Beli atau unduh Kamus Internasional Baru Ketiga Webster edisi 1961.
Temukan setiap nama dari daftar kami di kamus ini.
Di selembar kertas, tulis halaman kamus tempat nama itu berada.
Gunakan potongan kertas untuk mengurutkan nama.
Akankah urutan tindakan seperti itu menyelesaikan tugas kita? Ya, tentu saja. Apakah solusi ini efisien ? Hampir tidak. Di sini kita sampai pada aspek lain yang sangat penting dari algoritme: efisiensinya . Ada beberapa cara untuk menyelesaikan tugas ini. Namun baik dalam pemrograman maupun dalam kehidupan biasa, kami ingin memilih cara yang paling efisien. Jika tugas Anda adalah membuat roti panggang yang diolesi mentega, Anda bisa mulai dengan menabur gandum dan memerah susu sapi. Tapi itu akan menjadi tidak efisiensolusi — itu akan memakan banyak waktu dan akan menghabiskan banyak uang. Anda dapat menyelesaikan tugas sederhana Anda hanya dengan membeli roti dan mentega. Meskipun memungkinkan Anda memecahkan masalah, algoritme yang melibatkan gandum dan sapi terlalu rumit untuk digunakan dalam praktik. Dalam pemrograman, kami memiliki notasi khusus yang disebut notasi O besar untuk menilai kompleksitas algoritma. Big O memungkinkan untuk menilai berapa banyak waktu eksekusi suatu algoritma bergantung pada ukuran data input . Mari kita lihat contoh paling sederhana: transfer data. Bayangkan Anda perlu mengirim beberapa informasi dalam bentuk file dalam jarak jauh (misalnya, 5.000 mil). Algoritma apa yang paling efisien? Itu tergantung pada data yang Anda kerjakan. Misalnya, misalkan kita memiliki file audio berukuran 10 MB. Dalam hal ini, algoritme yang paling efisien adalah mengirim file melalui Internet. Tidak perlu lebih dari beberapa menit! Mari nyatakan kembali algoritme kami: "Jika Anda ingin mentransfer informasi dalam bentuk file dengan jarak 5.000 mil, Anda harus mengirim data melalui Internet". Bagus sekali. Sekarang mari kita menganalisisnya. Apakah itu menyelesaikan tugas kita?Ya, benar. Tapi apa yang bisa kita katakan tentang kerumitannya? Hmm, sekarang hal-hal menjadi lebih menarik. Faktanya adalah algoritme kami sangat bergantung pada data input, yaitu ukuran file. Jika kami memiliki 10 megabita, maka semuanya baik-baik saja. Tetapi bagaimana jika kita perlu mengirim 500 megabita? 20 gigabyte? 500 terabyte? 30 petabyte? Apakah algoritme kami akan berhenti berfungsi? Tidak, semua jumlah data ini memang bisa ditransfer. Apakah akan memakan waktu lebih lama? Ya, tentu saja! Sekarang kami mengetahui fitur penting dari algoritme kami: semakin besar jumlah data yang dikirim, semakin lama waktu yang diperlukan untuk menjalankan algoritme. Namun kami ingin memiliki pemahaman yang lebih tepat tentang hubungan ini (antara ukuran data input dan waktu yang diperlukan untuk mengirimkannya). Dalam kasus kami, kompleksitas algoritmiknya adalah linear . "Linear" berarti bahwa dengan bertambahnya jumlah input data, waktu yang diperlukan untuk mengirimkannya akan meningkat secara proporsional. Jika jumlah data berlipat ganda, maka waktu yang dibutuhkan untuk mengirimkannya akan menjadi dua kali lipat. Jika data bertambah 10 kali lipat, maka waktu transmisi akan bertambah 10 kali lipat. Menggunakan notasi O besar, kompleksitas algoritme kami dinyatakan sebagai O(n). Anda harus mengingat notasi ini untuk masa depan — notasi ini selalu digunakan untuk algoritme dengan kompleksitas linier. Perhatikan bahwa kita tidak membicarakan beberapa hal yang mungkin berbeda di sini: kecepatan internet, daya komputasi komputer kita, dan sebagainya. Saat menilai kerumitan algoritme, tidak masuk akal untuk mempertimbangkan faktor-faktor ini — bagaimanapun juga, faktor-faktor tersebut berada di luar kendali kami. Notasi Big O mengungkapkan kompleksitas algoritme itu sendiri, bukan "lingkungan" tempat algoritme dijalankan. Mari kita lanjutkan dengan contoh kita. Misalkan kita akhirnya mengetahui bahwa kita perlu mengirim file dengan total 800 terabyte. Kami tentu saja dapat menyelesaikan tugas kami dengan mengirimkannya melalui Internet. Hanya ada satu masalah: dengan kecepatan transmisi data rumah tangga standar (100 megabit per detik), ini akan memakan waktu sekitar 708 hari. Hampir 2 tahun! : O Algoritme kami jelas tidak cocok di sini. Kami membutuhkan solusi lain! Tanpa diduga, raksasa TI Amazon datang menyelamatkan kita! Layanan Snowmobile Amazon memungkinkan kami mengunggah sejumlah besar data ke penyimpanan seluler dan kemudian mengirimkannya ke alamat yang diinginkan dengan truk! Jadi, kami memiliki algoritme baru! "Jika Anda ingin mentransfer informasi dalam bentuk file dengan jarak lebih dari 5.000 mil dan membutuhkan waktu lebih dari 14 hari untuk dikirim melalui Internet, Anda harus mengirimkan data tersebut dengan truk Amazon." Kami memilih 14 hari secara sewenang-wenang di sini. Katakanlah ini adalah periode terlama yang bisa kita tunggu. Mari kita analisis algoritme kita. Bagaimana dengan kecepatannya? Bahkan jika truk itu melaju hanya dengan kecepatan 50 mph, itu akan menempuh jarak 5.000 mil hanya dalam 100 jam. Ini sedikit lebih dari empat hari! Ini jauh lebih baik daripada opsi pengiriman data melalui Internet. Dan bagaimana dengan kerumitan algoritma ini? Apakah ini juga linier, yaitu O(n)? Tidak, bukan itu. Lagi pula, truk tidak peduli seberapa berat Anda memuatnya — truk akan tetap melaju dengan kecepatan yang sama dan tiba tepat waktu. Apakah kita memiliki 800 terabyte, atau 10 kali lipatnya, truk akan tetap mencapai tujuannya dalam waktu 5 hari. Dengan kata lain, algoritma transfer data berbasis truk memiliki kompleksitas yang konstan. Di sini, "konstan" berarti tidak bergantung pada ukuran data masukan. Masukkan flash drive 1GB ke dalam truk, itu akan tiba dalam 5 hari. Masukkan ke dalam disk yang berisi 800 terabyte data, itu akan tiba dalam 5 hari. Saat menggunakan notasi O besar, kompleksitas konstan dilambangkan dengan O(1) . Kita sudah terbiasa dengan O(n) dan O(1) , jadi sekarang mari kita lihat lebih banyak contoh di dunia pemrograman :) Misalkan Anda diberi array berisi 100 angka, dan tugasnya adalah menampilkan masing-masing di konsol. Anda menulis loop biasa foryang melakukan tugas ini
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Apa kompleksitas dari algoritma ini? Linear, yaitu O(n). Jumlah tindakan yang harus dilakukan program bergantung pada berapa banyak angka yang diteruskan ke program tersebut. Jika ada 100 angka dalam larik, akan ada 100 tindakan (pernyataan untuk menampilkan string di layar). Jika ada 10.000 angka dalam larik, maka 10.000 tindakan harus dilakukan. Bisakah algoritme kami ditingkatkan dengan cara apa pun? Tidak. Apa pun yang terjadi, kita harus membuat N melewati array dan menjalankan pernyataan N untuk menampilkan string di 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 memiliki ruang kosong LinkedListtempat kami memasukkan beberapa angka. Kita perlu mengevaluasi kompleksitas algoritmik dalam memasukkan satu angka ke dalam LinkedListcontoh kita, dan bagaimana hal itu bergantung pada jumlah elemen dalam daftar. Jawabannya adalah O(1), yaitu kompleksitas konstan . Mengapa? Perhatikan bahwa kami memasukkan setiap nomor di awal daftar. Selain itu, Anda akan mengingat bahwa saat Anda memasukkan angka ke dalam a LinkedList, elemen tidak berpindah ke mana pun. Tautan (atau referensi) diperbarui (jika Anda lupa cara kerja LinkedList, lihat salah satu pelajaran lama kami ). Jika angka pertama dalam daftar kita adalah x, dan kita menyisipkan angka y di depan daftar, maka yang perlu kita lakukan hanyalah ini:
x.previous = y;
y.previous = null;
y.next = x;
Saat kami memperbarui tautan, kami tidak peduli berapa angka yang sudah ada diLinkedList , apakah satu atau satu miliar. Kompleksitas algoritma adalah konstan, yaitu O(1).
Kompleksitas logaritmik
Jangan panik! :) Jika kata "logaritmik" membuat Anda ingin menutup pelajaran ini dan berhenti membaca, tunggu beberapa menit. Tidak akan ada matematika gila di sini (ada banyak penjelasan seperti itu di tempat lain), dan kami akan memisahkan setiap contoh. Bayangkan tugas Anda adalah menemukan satu angka tertentu dalam larik berisi 100 angka. Lebih tepatnya, Anda perlu memeriksa apakah itu ada atau tidak. Segera setelah nomor yang diperlukan ditemukan, pencarian berakhir, dan Anda menampilkan yang berikut di konsol: "Nomor yang diperlukan ditemukan! Indeksnya dalam array = ...." Bagaimana Anda menyelesaikan tugas ini? Di sini solusinya jelas: Anda perlu mengulangi elemen-elemen array satu per satu, mulai dari yang pertama (atau dari yang terakhir) dan memeriksa apakah nomor saat ini cocok dengan yang Anda cari. Demikian, jumlah tindakan secara langsung bergantung pada jumlah elemen dalam larik. Jika kita memiliki 100 angka, maka kita berpotensi perlu pergi ke elemen berikutnya 100 kali dan melakukan 100 perbandingan. Jika ada 1000 angka, maka bisa ada 1000 perbandingan. Ini jelas kompleksitas linier, yaituO(n) . Dan sekarang kami akan menambahkan satu penyempurnaan ke contoh kami: larik tempat Anda perlu menemukan nomor diurutkan dalam urutan menaik . Apakah ini mengubah sesuatu sehubungan dengan tugas kita? Kami masih dapat melakukan pencarian kasar untuk nomor yang diinginkan. Tapi alternatifnya, kita bisa menggunakan algoritma pencarian biner yang terkenal . Di baris atas pada gambar, kita melihat array yang diurutkan. Kita perlu menemukan angka 23 di dalamnya. Alih-alih mengulangi angka, kami hanya membagi larik menjadi 2 bagian dan memeriksa angka tengah dalam larik. Temukan nomor yang terletak di sel 4 dan periksa (baris kedua pada gambar). Angka ini 16, dan kami mencari 23. Angka saat ini kurang dari yang kami cari. Maksudnya itu apa? Itu artinyasemua angka sebelumnya (yang terletak sebelum angka 16) tidak perlu dicentang : dijamin lebih kecil dari yang kita cari, karena array kita sudah diurutkan! Kami melanjutkan pencarian di antara 5 elemen yang tersisa. Catatan:kami hanya melakukan satu perbandingan, tetapi kami telah menghilangkan setengah dari opsi yang memungkinkan. Kami hanya memiliki 5 elemen tersisa. Kami akan mengulangi langkah kami sebelumnya dengan sekali lagi membagi subarray yang tersisa menjadi dua dan kembali mengambil elemen tengah (baris ke-3 pada gambar). Jumlahnya 56, dan lebih besar dari yang kita cari. Maksudnya itu apa? Ini berarti bahwa kita telah menghilangkan 3 kemungkinan lainnya: angka 56 itu sendiri serta dua angka setelahnya (karena dijamin lebih besar dari 23, karena array diurutkan). Kami hanya memiliki 2 nomor tersisa untuk diperiksa (baris terakhir pada gambar) — nomor dengan indeks array 5 dan 6. Kami memeriksa yang pertama, dan menemukan apa yang kami cari — nomor 23! Indeksnya adalah 5! Mari kita lihat hasil algoritme kita, lalu kita akan menganalisis kompleksitasnya. Omong-omong, sekarang Anda mengerti mengapa ini disebut pencarian biner: ini bergantung pada pembagian data menjadi dua berulang kali. Hasilnya mengesankan! Jika kita menggunakan pencarian linier untuk mencari angka, kita memerlukan hingga 10 perbandingan, tetapi dengan pencarian biner, kita menyelesaikan tugas hanya dengan 3! Dalam kasus terburuk, akan ada 4 perbandingan (jika pada langkah terakhir angka yang kita inginkan adalah yang kedua dari kemungkinan yang tersisa, bukan yang pertama. Lalu bagaimana dengan kerumitannya? Ini poin yang sangat menarik :) Algoritma pencarian biner jauh lebih tidak bergantung pada jumlah elemen dalam array daripada algoritma pencarian linier (yaitu, iterasi sederhana). Dengan 10 elemen dalam array, pencarian linier akan membutuhkan maksimal 10 perbandingan, tetapi pencarian biner akan membutuhkan maksimal 4 perbandingan. Itu perbedaan dengan faktor 2,5. Tetapi untuk larik 1000 elemen , pencarian linier akan membutuhkan hingga 1000 perbandingan, tetapi pencarian biner hanya membutuhkan 10 ! Perbedaannya sekarang 100 kali lipat! Catatan:jumlah elemen dalam larik telah meningkat 100 kali lipat (dari 10 menjadi 1000), tetapi jumlah perbandingan yang diperlukan untuk pencarian biner hanya meningkat dengan faktor 2,5 (dari 4 menjadi 10). Jika kita mendapatkan 10.000 elemen , perbedaannya akan semakin mengesankan: 10.000 perbandingan untuk pencarian linier, dan total 14 perbandingan untuk pencarian biner. Dan lagi, jika jumlah elemen bertambah 1000 kali (dari 10 menjadi 10.000), maka jumlah perbandingan bertambah dengan faktor hanya 3,5 (dari 4 menjadi 14). Kompleksitas algoritma pencarian biner adalah logaritmik , atau, jika kita menggunakan notasi O besar, O(log n). Mengapa disebut demikian? Logaritma seperti kebalikan dari eksponensial. Logaritma biner adalah kekuatan yang angka 2 harus dinaikkan untuk mendapatkan angka. Misalnya, kami memiliki 10.000 elemen yang perlu dicari menggunakan algoritma pencarian biner. Saat ini, Anda dapat melihat tabel nilai untuk mengetahui bahwa melakukan ini akan membutuhkan maksimal 14 perbandingan. Tetapi bagaimana jika tidak ada yang menyediakan tabel seperti itu dan Anda perlu menghitung jumlah perbandingan maksimum yang tepat? Anda hanya perlu menjawab pertanyaan sederhana: pangkat berapa yang Anda perlukan untuk menaikkan angka 2 agar hasilnya lebih besar atau sama dengan jumlah elemen yang akan diperiksa? Untuk 10.000, itu adalah kekuatan ke-14. 2 pangkat 13 terlalu kecil (8192), tetapi 2 pangkat 14 = 16384, dan angka ini memenuhi kondisi kita (lebih besar dari atau sama dengan jumlah elemen dalam larik). Kami menemukan logaritma: 14. Itulah berapa banyak perbandingan yang mungkin kami butuhkan! :) Algoritma dan kompleksitas algoritmik adalah topik yang terlalu luas untuk dimasukkan ke dalam satu pelajaran. Tetapi mengetahuinya sangat penting: banyak wawancara kerja akan melibatkan pertanyaan yang melibatkan algoritme. Untuk teori, saya dapat merekomendasikan beberapa buku untuk Anda. Anda bisa mulai dengan " Algoritma Grokking ". Contoh dalam buku ini ditulis dengan Python, tetapi buku ini menggunakan bahasa dan contoh yang sangat sederhana. Itu pilihan terbaik untuk pemula dan, terlebih lagi, itu tidak terlalu besar. Di antara bacaan yang lebih serius, kami memiliki buku karya Robert Lafore dan Robert Sedgewick. Keduanya ditulis dalam Java, yang akan membuat belajar sedikit lebih mudah bagi Anda. Lagi pula, Anda cukup familiar dengan bahasa ini! :) Untuk siswa dengan kemampuan matematika yang baik, pilihan terbaik adalah buku Thomas Cormen . Tapi teori saja tidak akan mengisi perut Anda! Pengetahuan != Kemampuan . Anda dapat berlatih memecahkan masalah yang melibatkan algoritme di HackerRank dan LeetCode . Tugas dari website ini sering digunakan bahkan saat wawancara di Google dan Facebook, jadi pasti tidak akan bosan :) Untuk memperkuat materi pelajaran ini, saya sarankan Anda menonton video bagus tentang notasi O besar di YouTube. Sampai jumpa di pelajaran selanjutnya! :)
Konon, topik ini sangat penting bagi setiap programmer. Kita akan berbicara tentang algoritma . Apa itu algoritma? Secara sederhana, itu adalah beberapa urutan tindakan yang harus diselesaikan untuk mencapai hasil yang diinginkan . Kami sering menggunakan algoritma dalam kehidupan sehari-hari. Misalnya, setiap pagi Anda memiliki tugas tertentu: pergi ke sekolah atau bekerja, dan pada saat yang sama menjadi:
Dalam hal ini, algoritme yang paling efisien adalah mengirim file melalui Internet. Tidak perlu lebih dari beberapa menit! Mari nyatakan kembali algoritme kami: "Jika Anda ingin mentransfer informasi dalam bentuk file dengan jarak 5.000 mil, Anda harus mengirim data melalui Internet". Bagus sekali. Sekarang mari kita menganalisisnya. Apakah itu menyelesaikan tugas kita?Ya, benar. Tapi apa yang bisa kita katakan tentang kerumitannya? Hmm, sekarang hal-hal menjadi lebih menarik. Faktanya adalah algoritme kami sangat bergantung pada data input, yaitu ukuran file. Jika kami memiliki 10 megabita, maka semuanya baik-baik saja. Tetapi bagaimana jika kita perlu mengirim 500 megabita? 20 gigabyte? 500 terabyte? 30 petabyte? Apakah algoritme kami akan berhenti berfungsi? Tidak, semua jumlah data ini memang bisa ditransfer. Apakah akan memakan waktu lebih lama? Ya, tentu saja! Sekarang kami mengetahui fitur penting dari algoritme kami: semakin besar jumlah data yang dikirim, semakin lama waktu yang diperlukan untuk menjalankan algoritme. Namun kami ingin memiliki pemahaman yang lebih tepat tentang hubungan ini (antara ukuran data input dan waktu yang diperlukan untuk mengirimkannya). Dalam kasus kami, kompleksitas algoritmiknya adalah linear . "Linear" berarti bahwa dengan bertambahnya jumlah input data, waktu yang diperlukan untuk mengirimkannya akan meningkat secara proporsional. Jika jumlah data berlipat ganda, maka waktu yang dibutuhkan untuk mengirimkannya akan menjadi dua kali lipat. Jika data bertambah 10 kali lipat, maka waktu transmisi akan bertambah 10 kali lipat. Menggunakan notasi O besar, kompleksitas algoritme kami dinyatakan sebagai O(n). Anda harus mengingat notasi ini untuk masa depan — notasi ini selalu digunakan untuk algoritme dengan kompleksitas linier. Perhatikan bahwa kita tidak membicarakan beberapa hal yang mungkin berbeda di sini: kecepatan internet, daya komputasi komputer kita, dan sebagainya. Saat menilai kerumitan algoritme, tidak masuk akal untuk mempertimbangkan faktor-faktor ini — bagaimanapun juga, faktor-faktor tersebut berada di luar kendali kami. Notasi Big O mengungkapkan kompleksitas algoritme itu sendiri, bukan "lingkungan" tempat algoritme dijalankan. Mari kita lanjutkan dengan contoh kita. Misalkan kita akhirnya mengetahui bahwa kita perlu mengirim file dengan total 800 terabyte. Kami tentu saja dapat menyelesaikan tugas kami dengan mengirimkannya melalui Internet. Hanya ada satu masalah: dengan kecepatan transmisi data rumah tangga standar (100 megabit per detik), ini akan memakan waktu sekitar 708 hari. Hampir 2 tahun! : O Algoritme kami jelas tidak cocok di sini. Kami membutuhkan solusi lain! Tanpa diduga, raksasa TI Amazon datang menyelamatkan kita! Layanan Snowmobile Amazon memungkinkan kami mengunggah sejumlah besar data ke penyimpanan seluler dan kemudian mengirimkannya ke alamat yang diinginkan dengan truk! 
Jadi, kami memiliki algoritme baru! "Jika Anda ingin mentransfer informasi dalam bentuk file dengan jarak lebih dari 5.000 mil dan membutuhkan waktu lebih dari 14 hari untuk dikirim melalui Internet, Anda harus mengirimkan data tersebut dengan truk Amazon." Kami memilih 14 hari secara sewenang-wenang di sini. Katakanlah ini adalah periode terlama yang bisa kita tunggu. Mari kita analisis algoritme kita. Bagaimana dengan kecepatannya? Bahkan jika truk itu melaju hanya dengan kecepatan 50 mph, itu akan menempuh jarak 5.000 mil hanya dalam 100 jam. Ini sedikit lebih dari empat hari! Ini jauh lebih baik daripada opsi pengiriman data melalui Internet. Dan bagaimana dengan kerumitan algoritma ini? Apakah ini juga linier, yaitu O(n)? Tidak, bukan itu. Lagi pula, truk tidak peduli seberapa berat Anda memuatnya — truk akan tetap melaju dengan kecepatan yang sama dan tiba tepat waktu. Apakah kita memiliki 800 terabyte, atau 10 kali lipatnya, truk akan tetap mencapai tujuannya dalam waktu 5 hari. Dengan kata lain, algoritma transfer data berbasis truk memiliki kompleksitas yang konstan. Di sini, "konstan" berarti tidak bergantung pada ukuran data masukan. Masukkan flash drive 1GB ke dalam truk, itu akan tiba dalam 5 hari. Masukkan ke dalam disk yang berisi 800 terabyte data, itu akan tiba dalam 5 hari. Saat menggunakan notasi O besar, kompleksitas konstan dilambangkan dengan O(1) . Kita sudah terbiasa dengan O(n) dan O(1) , jadi sekarang mari kita lihat lebih banyak contoh di dunia pemrograman :) Misalkan Anda diberi array berisi 100 angka, dan tugasnya adalah menampilkan masing-masing di konsol. Anda menulis loop biasa 
Di baris atas pada gambar, kita melihat array yang diurutkan. Kita perlu menemukan angka 23 di dalamnya. Alih-alih mengulangi angka, kami hanya membagi larik menjadi 2 bagian dan memeriksa angka tengah dalam larik. Temukan nomor yang terletak di sel 4 dan periksa (baris kedua pada gambar). Angka ini 16, dan kami mencari 23. Angka saat ini kurang dari yang kami cari. Maksudnya itu apa? Itu artinyasemua angka sebelumnya (yang terletak sebelum angka 16) tidak perlu dicentang : dijamin lebih kecil dari yang kita cari, karena array kita sudah diurutkan! Kami melanjutkan pencarian di antara 5 elemen yang tersisa. Catatan:kami hanya melakukan satu perbandingan, tetapi kami telah menghilangkan setengah dari opsi yang memungkinkan. Kami hanya memiliki 5 elemen tersisa. Kami akan mengulangi langkah kami sebelumnya dengan sekali lagi membagi subarray yang tersisa menjadi dua dan kembali mengambil elemen tengah (baris ke-3 pada gambar). Jumlahnya 56, dan lebih besar dari yang kita cari. Maksudnya itu apa? Ini berarti bahwa kita telah menghilangkan 3 kemungkinan lainnya: angka 56 itu sendiri serta dua angka setelahnya (karena dijamin lebih besar dari 23, karena array diurutkan). Kami hanya memiliki 2 nomor tersisa untuk diperiksa (baris terakhir pada gambar) — nomor dengan indeks array 5 dan 6. Kami memeriksa yang pertama, dan menemukan apa yang kami cari — nomor 23! Indeksnya adalah 5! Mari kita lihat hasil algoritme kita, lalu kita akan menganalisis kompleksitasnya. Omong-omong, sekarang Anda mengerti mengapa ini disebut pencarian biner: ini bergantung pada pembagian data menjadi dua berulang kali. Hasilnya mengesankan! Jika kita menggunakan pencarian linier untuk mencari angka, kita memerlukan hingga 10 perbandingan, tetapi dengan pencarian biner, kita menyelesaikan tugas hanya dengan 3! Dalam kasus terburuk, akan ada 4 perbandingan (jika pada langkah terakhir angka yang kita inginkan adalah yang kedua dari kemungkinan yang tersisa, bukan yang pertama. Lalu bagaimana dengan kerumitannya? Ini poin yang sangat menarik :) Algoritma pencarian biner jauh lebih tidak bergantung pada jumlah elemen dalam array daripada algoritma pencarian linier (yaitu, iterasi sederhana). Dengan 10 elemen dalam array, pencarian linier akan membutuhkan maksimal 10 perbandingan, tetapi pencarian biner akan membutuhkan maksimal 4 perbandingan. Itu perbedaan dengan faktor 2,5. Tetapi untuk larik 1000 elemen , pencarian linier akan membutuhkan hingga 1000 perbandingan, tetapi pencarian biner hanya membutuhkan 10 ! Perbedaannya sekarang 100 kali lipat! Catatan:jumlah elemen dalam larik telah meningkat 100 kali lipat (dari 10 menjadi 1000), tetapi jumlah perbandingan yang diperlukan untuk pencarian biner hanya meningkat dengan faktor 2,5 (dari 4 menjadi 10). Jika kita mendapatkan 10.000 elemen , perbedaannya akan semakin mengesankan: 10.000 perbandingan untuk pencarian linier, dan total 14 perbandingan untuk pencarian biner. Dan lagi, jika jumlah elemen bertambah 1000 kali (dari 10 menjadi 10.000), maka jumlah perbandingan bertambah dengan faktor hanya 3,5 (dari 4 menjadi 14). Kompleksitas algoritma pencarian biner adalah logaritmik , atau, jika kita menggunakan notasi O besar, O(log n). Mengapa disebut demikian? Logaritma seperti kebalikan dari eksponensial. Logaritma biner adalah kekuatan yang angka 2 harus dinaikkan untuk mendapatkan angka. Misalnya, kami memiliki 10.000 elemen yang perlu dicari menggunakan algoritma pencarian biner. 
Saat ini, Anda dapat melihat tabel nilai untuk mengetahui bahwa melakukan ini akan membutuhkan maksimal 14 perbandingan. Tetapi bagaimana jika tidak ada yang menyediakan tabel seperti itu dan Anda perlu menghitung jumlah perbandingan maksimum yang tepat? Anda hanya perlu menjawab pertanyaan sederhana: pangkat berapa yang Anda perlukan untuk menaikkan angka 2 agar hasilnya lebih besar atau sama dengan jumlah elemen yang akan diperiksa? Untuk 10.000, itu adalah kekuatan ke-14. 2 pangkat 13 terlalu kecil (8192), tetapi 2 pangkat 14 = 16384, dan angka ini memenuhi kondisi kita (lebih besar dari atau sama dengan jumlah elemen dalam larik). Kami menemukan logaritma: 14. Itulah berapa banyak perbandingan yang mungkin kami butuhkan! :) Algoritma dan kompleksitas algoritmik adalah topik yang terlalu luas untuk dimasukkan ke dalam satu pelajaran. Tetapi mengetahuinya sangat penting: banyak wawancara kerja akan melibatkan pertanyaan yang melibatkan algoritme. Untuk teori, saya dapat merekomendasikan beberapa buku untuk Anda. Anda bisa mulai dengan " Algoritma Grokking ". Contoh dalam buku ini ditulis dengan Python, tetapi buku ini menggunakan bahasa dan contoh yang sangat sederhana. Itu pilihan terbaik untuk pemula dan, terlebih lagi, itu tidak terlalu besar. Di antara bacaan yang lebih serius, kami memiliki buku karya Robert Lafore dan Robert Sedgewick. Keduanya ditulis dalam Java, yang akan membuat belajar sedikit lebih mudah bagi Anda. Lagi pula, Anda cukup familiar dengan bahasa ini! :) Untuk siswa dengan kemampuan matematika yang baik, pilihan terbaik adalah buku Thomas Cormen . Tapi teori saja tidak akan mengisi perut Anda! Pengetahuan != Kemampuan . Anda dapat berlatih memecahkan masalah yang melibatkan algoritme di HackerRank dan LeetCode . Tugas dari website ini sering digunakan bahkan saat wawancara di Google dan Facebook, jadi pasti tidak akan bosan :) Untuk memperkuat materi pelajaran ini, saya sarankan Anda menonton video bagus tentang notasi O besar di YouTube. Sampai jumpa di pelajaran selanjutnya! :)
GO TO FULL VERSION