Halo! Kuliah hari ini akan sedikit berbeda dari kuliah lainnya. Bedanya, ini hanya terkait secara tidak langsung dengan Java. Namun topik ini sangat penting bagi setiap programmer. Kami akan berbicara tentang algoritma . Apa itu algoritma? Secara sederhana, ini adalah serangkaian tindakan tertentu yang harus dilakukan untuk mencapai hasil yang diinginkan . Kita sering menggunakan algoritma dalam kehidupan sehari-hari. Misalnya, setiap pagi Anda dihadapkan pada tugas: datang ke sekolah atau bekerja, sekaligus menjadi:
Berpakaian
Membersihkan
Cukup makan
Algoritma apa yang memungkinkan Anda mencapai hasil ini?
Bangun karena jam alarm.
Mandi, cuci muka.
Menyiapkan sarapan, membuat kopi/teh.
Makan.
Jika Anda belum menyetrika pakaian sejak malam hari, setrikalah.
Berpakaian.
Meninggalkan rumah.
Urutan tindakan ini pasti akan memungkinkan Anda mendapatkan hasil yang diinginkan. Dalam pemrograman, inti dari pekerjaan kami adalah untuk terus memecahkan masalah. Sebagian besar tugas ini dapat dilakukan dengan menggunakan algoritma yang sudah diketahui. Misalnya, Anda dihadapkan pada tugas: mengurutkan daftar 100 nama dalam sebuah array . Masalah ini cukup sederhana, namun dapat diselesaikan dengan berbagai cara. Berikut salah satu solusinya: Algoritma untuk mengurutkan nama berdasarkan abjad:
Beli atau unduh di Internet “Kamus Nama Pribadi Rusia” edisi 1966.
Temukan setiap nama di daftar kami di kamus ini.
Tuliskan di selembar kertas di halaman kamus mana nama tersebut berada.
Susunlah nama-nama tersebut secara berurutan menggunakan catatan di selembar kertas.
Akankah rangkaian tindakan ini memungkinkan kita memecahkan masalah kita? Ya, itu akan sepenuhnya mengizinkannya. Akankah solusi ini efektif ? Hampir tidak. Di sini kita sampai pada properti lain yang sangat penting dari algoritma - efisiensinya . Masalahnya dapat diselesaikan dengan berbagai cara. Namun baik dalam pemrograman maupun kehidupan sehari-hari, kami memilih metode yang paling efektif. Jika tugas Anda adalah membuat sandwich dengan mentega, tentu saja Anda bisa memulainya dengan menabur gandum dan memerah susu sapi. Namun ini akan menjadi solusi yang tidak efektif - akan memakan banyak waktu dan menghabiskan banyak uang. Untuk mengatasi masalah sederhana Anda, Anda cukup membeli roti dan mentega. Dan algoritme dengan gandum dan sapi, meskipun memungkinkan Anda memecahkan masalah, terlalu rumit untuk diterapkan dalam praktik. Untuk menilai kompleksitas algoritma dalam pemrograman, diciptakan notasi khusus yang disebut Big-O (“big O”) . Big-O memungkinkan Anda memperkirakan seberapa besar waktu eksekusi suatu algoritme bergantung pada data yang dimasukkan ke dalamnya . Mari kita lihat contoh paling sederhana - transfer data. Bayangkan Anda perlu mengirimkan beberapa informasi dalam bentuk file dalam jarak jauh (misalnya 5000 kilometer). Algoritma mana yang paling efisien? Itu tergantung pada data yang harus dia kerjakan. Misalnya, kami memiliki file audio berukuran 10 megabyte. Dalam hal ini, algoritma yang paling efisien adalah mentransfer file melalui Internet. Hanya perlu beberapa menit! Jadi, mari kita nyatakan kembali algoritma kita: “Jika Anda perlu mentransfer informasi dalam bentuk file melalui jarak 5000 kilometer, Anda perlu menggunakan transmisi data melalui Internet.” Besar. Sekarang mari kita menganalisisnya. Apakah ini menyelesaikan masalah kita? Secara umum, ya, itu menyelesaikannya sepenuhnya. Namun apa yang dapat Anda katakan tentang kompleksitasnya? Hmm, sekarang di sinilah segalanya menjadi menarik. Faktanya algoritma kami sangat bergantung pada data yang masuk, yaitu ukuran file. Sekarang kami memiliki 10 megabita dan semuanya baik-baik saja. Bagaimana jika kita perlu mentransfer 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Akankah algoritme kami berhenti bekerja? Tidak, seluruh jumlah data ini masih dapat ditransfer. Apakah akan memakan waktu lebih lama untuk menyelesaikannya? Ya, tentu saja! Sekarang kami mengetahui fitur penting dari algoritme kami: semakin besar ukuran data yang akan ditransfer, semakin lama waktu yang dibutuhkan algoritme untuk menyelesaikannya . Namun kami ingin memahami lebih tepat seperti apa hubungan ini (antara ukuran data dan waktu yang diperlukan untuk mentransfernya). Dalam kasus kami, kompleksitas algoritme akan linier. “Linear” berarti seiring bertambahnya volume data, waktu transmisinya akan meningkat kira-kira secara proporsional. Jika datanya 2 kali lebih banyak, dan perlu waktu 2 kali lebih lama untuk mentransfernya. Jika datanya 10 kali lebih banyak, waktu transfer akan bertambah 10 kali lipat. Menggunakan notasi Big-O, kompleksitas algoritma kami didefinisikan sebagai O(N) . Notasi ini paling baik diingat untuk referensi di masa mendatang; notasi ini selalu digunakan untuk algoritma dengan kompleksitas linier. Harap diperhatikan: di sini kita sama sekali tidak membicarakan berbagai hal “variabel”: kecepatan internet, kekuatan komputer kita, dan sebagainya. Saat menilai kompleksitas suatu algoritme, hal ini tidak masuk akal - kami tidak memiliki kendali atas algoritme tersebut. Big-O mengevaluasi algoritme itu sendiri, terlepas dari “lingkungan” di mana algoritme tersebut harus bekerja. Mari kita lanjutkan dengan contoh kita. Katakanlah ternyata ukuran file yang akan ditransfer adalah 800 terabyte. Jika kita mengirimkannya melalui Internet, masalahnya tentu saja akan teratasi. Hanya ada satu masalah: transmisi melalui tautan modern standar (dengan kecepatan 100 megabit per detik) yang sebagian besar dari kita gunakan di rumah akan memakan waktu sekitar 708 hari. Hampir 2 tahun! :O Jadi, algoritma kami jelas tidak cocok di sini. Kami membutuhkan solusi lain! Tiba-tiba, raksasa IT Amazon datang membantu kita! Layanan Amazon Snowmobile memungkinkan Anda memuat data dalam jumlah besar ke dalam unit penyimpanan seluler dan mengirimkannya ke alamat yang diinginkan dengan truk! Jadi kami memiliki algoritma baru! “Jika Anda perlu mentransfer informasi dalam bentuk file dengan jarak 5.000 kilometer, dan prosesnya akan memakan waktu lebih dari 14 hari jika ditransfer melalui Internet, Anda perlu menggunakan transportasi truk Amazon.” Angka 14 hari dipilih secara acak di sini: katakanlah ini adalah jangka waktu maksimum yang mampu kita bayar. Mari kita menganalisis algoritma kita. Bagaimana dengan kecepatan? Sekalipun truk tersebut melaju dengan kecepatan hanya 50 km/jam, ia dapat menempuh jarak 5.000 kilometer hanya dalam waktu 100 jam. Itu baru empat hari! Ini jauh lebih baik daripada opsi transmisi Internet. Bagaimana dengan kompleksitas algoritma ini? Apakah juga akan linier, O(N)? Tidak, itu tidak akan terjadi. Lagi pula, truk tidak peduli berapa banyak Anda memuatnya - truk akan tetap melaju dengan kecepatan yang kira-kira sama dan tiba tepat waktu. Apakah kita memiliki 800 terabyte, atau data 10 kali lebih banyak, truk akan tetap sampai di sana dalam 5 hari. Dengan kata lain, algoritma pengiriman data melalui truk memiliki kompleksitas yang konstan . “Konstan” berarti tidak bergantung pada data yang diteruskan ke algoritme. Masukkan flash drive 1GB ke dalam truk dan akan tiba dalam 5 hari. Letakkan disk dengan data 800 terabyte di sana dan itu akan tiba dalam 5 hari. Saat menggunakan Big-O, kompleksitas konstan dilambangkan sebagai O(1) . Sejak kita berkenalan dengan O(N) danO(1) , sekarang mari kita lihat lebih banyak contoh “programmer” :) Katakanlah Anda diberikan array yang terdiri dari 100 angka, dan tugasnya adalah mencetak masing-masing angka tersebut ke konsol. Anda menulis loop reguler foryang melakukan tugas ini
Apa kompleksitas dari algoritma tertulis? Linier, PADA(N). Jumlah tindakan yang harus dilakukan program bergantung pada berapa banyak angka yang dimasukkan ke dalamnya. Jika ada 100 angka dalam array, akan ada 100 tindakan (output di layar). Jika ada 10.000 angka dalam array, 10.000 tindakan perlu dilakukan. Bisakah algoritme kami ditingkatkan? TIDAK. Bagaimanapun, kita harus membuat N melewati array dan melakukan N keluaran ke konsol. Mari kita lihat contoh lainnya.
Kami memiliki yang kosong LinkedListdi mana kami memasukkan beberapa nomor. Kita perlu memperkirakan kompleksitas algoritma untuk memasukkan satu nomor ke dalam LinkedListcontoh kita, dan bagaimana hal itu bergantung pada jumlah elemen dalam daftar. Jawabannya adalah O(1) - kompleksitas konstan . Mengapa? Harap diperhatikan: setiap kali kami memasukkan nomor di awal daftar. Selain itu, seperti yang Anda ingat, saat memasukkan angka ke dalam LinkedListelemen, angka tersebut tidak digeser ke mana pun - tautan didefinisikan ulang (jika Anda tiba-tiba lupa cara kerja LinkedList, lihat salah satu kuliah lama kami ). Jika sekarang angka pertama dalam daftar kita adalah angka х, dan kita memasukkan angka y di awal daftar, yang diperlukan hanyalah:
x.previous = y;
y.previous =null;
y.next = x;
Untuk redefinisi referensi ini, tidak menjadi masalah bagi kita berapa banyak angka yang ada sekarangLinkedList - setidaknya satu, setidaknya satu miliar. Kompleksitas algoritma akan konstan - O(1).
Kompleksitas logaritmik
Jangan panik! :) Jika kata “logaritma” membuat Anda ingin menutup kuliah dan tidak membaca lebih lanjut, tunggu beberapa menit. Tidak akan ada kesulitan matematika di sini (ada banyak penjelasan seperti itu di tempat lain), dan kami akan menganalisis semua contoh “dengan jari”. Bayangkan tugas Anda adalah menemukan satu angka tertentu dalam deretan 100 angka. Lebih tepatnya, periksa apakah itu ada. Segera setelah nomor yang diperlukan ditemukan, pencarian harus dihentikan, dan entri “Nomor yang diperlukan telah ditemukan!” harus ditampilkan di konsol. Indeksnya dalam array = ....” Bagaimana Anda mengatasi masalah seperti itu? Di sini solusinya jelas: Anda perlu mengulangi elemen array satu per satu, dimulai dengan yang pertama (atau terakhir) dan memeriksa apakah nomor saat ini sesuai dengan yang diinginkan. Oleh karena itu, jumlah tindakan secara langsung bergantung pada jumlah elemen dalam array. Jika kita memiliki 100 angka, maka kita perlu pergi ke elemen berikutnya sebanyak 100 kali dan memeriksa kecocokan nomor tersebut sebanyak 100 kali. Jika ada 1000 angka, maka akan ada 1000 langkah pemeriksaan, ini jelas merupakan kompleksitas linier, O(N) . Sekarang kita akan menambahkan satu klarifikasi pada contoh kita: array di mana Anda perlu menemukan nomornya diurutkan dalam urutan menaik . Apakah ini mengubah sesuatu untuk tugas kita? Kita masih bisa mencari nomor yang diinginkan dengan cara brute force. Tapi kita bisa menggunakan algoritma pencarian biner yang terkenal . Di baris atas gambar kita melihat array yang diurutkan. Di dalamnya kita perlu mencari angka 23. Daripada mengulangi angka-angka tersebut, kita cukup membagi array menjadi 2 bagian dan memeriksa angka rata-rata dalam array. Kami menemukan nomor yang terletak di sel 4 dan memeriksanya (baris kedua pada gambar). Angka ini 16, dan kita mencari 23. Angka saat ini lebih sedikit. Apa artinya ini? Bahwa semua bilangan sebelumnya (yang letaknya sampai dengan bilangan 16) tidak perlu dicentang : pasti lebih kecil dari bilangan yang kita cari, karena larik kita sudah terurut! Mari lanjutkan pencarian di antara 5 elemen yang tersisa. Perhatian:Kami hanya melakukan satu pemeriksaan, tetapi kami telah menghilangkan setengah dari opsi yang mungkin. Kami hanya memiliki 5 elemen tersisa. Kami akan mengulangi langkah kami - lagi membagi array yang tersisa dengan 2 dan sekali lagi mengambil elemen tengah (baris 3 pada gambar). Angka ini 56, dan lebih besar dari yang kita cari. Apa artinya ini? Bahwa kita membuang 3 opsi lagi - angka 56 itu sendiri, dan dua angka setelahnya (pastinya lebih besar dari 23, karena arraynya sudah diurutkan). Kami hanya memiliki 2 angka tersisa untuk diperiksa (baris terakhir pada gambar) - angka dengan indeks array 5 dan 6. Kami memeriksa yang pertama, dan inilah yang kami cari - angka 23! Indeksnya = 5! Mari kita lihat hasil algoritma kita, dan kemudian kita akan memahami kompleksitasnya. (Omong-omong, sekarang Anda mengerti mengapa ini disebut biner: intinya adalah membagi data secara konstan dengan 2). Hasilnya sungguh mengesankan! Jika kita mencari angka yang diinginkan menggunakan pencarian linier, kita memerlukan 10 pemeriksaan, tetapi dengan pencarian biner kita melakukannya dalam 3! Dalam kasus terburuk, akan ada 4, jika pada langkah terakhir nomor yang kita butuhkan ternyata yang kedua, dan bukan yang pertama. Bagaimana dengan kompleksitasnya? Ini adalah poin yang sangat menarik :) Algoritma pencarian biner tidak terlalu bergantung pada jumlah elemen dalam array dibandingkan algoritma pencarian linier (yaitu, enumerasi sederhana). Dengan 10 elemen dalam array, pencarian linier memerlukan maksimal 10 pemeriksaan, dan pencarian biner memerlukan maksimal 4 pemeriksaan. Perbedaannya 2,5 kali lipat. Namun untuk array yang terdiri dari 1000 elemen, penelusuran linier memerlukan 1000 pemeriksaan, dan penelusuran biner hanya memerlukan 10 ! Perbedaannya sudah 100 kali lipat! Perhatian:jumlah elemen dalam array meningkat 100 kali lipat (dari 10 menjadi 1000), dan jumlah pemeriksaan yang diperlukan untuk pencarian biner hanya meningkat 2,5 kali lipat - dari 4 menjadi 10. Jika kita mencapai 10.000 elemen , perbedaannya bahkan lebih mengesankan: 10.000 memeriksa pencarian linier, dan total 14 pemeriksaan untuk biner. Dan lagi: jumlah elemen meningkat 1000 kali lipat (dari 10 menjadi 10.000), tetapi jumlah pemeriksaan hanya meningkat 3,5 kali lipat (dari 4 menjadi 14). Kompleksitas algoritma pencarian biner adalah logaritmik , atau, dalam notasi Big-O, O(log n) . Mengapa disebut demikian? Logaritma adalah kebalikan dari eksponensial. Logaritma biner digunakan untuk menghitung pangkat 2. Misalnya, kita memiliki 10.000 elemen yang harus kita lalui menggunakan pencarian biner. Sekarang Anda memiliki gambaran di depan mata Anda, dan Anda tahu bahwa ini memerlukan maksimal 14 pemeriksaan. Tetapi bagaimana jika tidak ada gambaran di depan mata Anda, dan Anda perlu menghitung jumlah pasti pemeriksaan yang diperlukan? Cukup dengan menjawab pertanyaan sederhana: berapa pangkat 2 yang harus dipangkatkan agar hasil yang didapat >= banyaknya elemen yang diperiksa? Untuk 10.000 itu akan menjadi pangkat ke-14. 2 pangkat 13 terlalu kecil (8192) Tapi 2 pangkat 14 = 16384 , angka ini memenuhi kondisi kita (>= jumlah elemen dalam array). Kami menemukan logaritma - 14. Itulah jumlah cek yang kami perlukan! :) Algoritma dan kompleksitasnya merupakan topik yang terlalu luas untuk dimasukkan dalam satu kuliah. Namun mengetahuinya sangatlah penting: dalam banyak wawancara Anda akan menerima masalah algoritmik. Untuk teori, saya dapat merekomendasikan Anda beberapa buku. Tempat yang baik untuk memulai adalah “ Algoritma Grocking ”: meskipun contoh dalam buku ini ditulis dengan Python, bahasa dan contoh buku ini sangat sederhana. Pilihan terbaik untuk pemula, dan volumenya juga kecil. Bacaan yang lebih serius: buku karya Robert Laforet dan Robert Sedgwick . Keduanya ditulis dalam Java, yang akan membuat pembelajaran Anda sedikit lebih mudah. Lagi pula, Anda cukup familiar dengan bahasa ini! :) Untuk siswa dengan latar belakang matematika yang baik, pilihan terbaik adalah buku karya Thomas Corman . Namun Anda tidak akan puas hanya dengan teori! “Tahu” != “mampu” Anda dapat berlatih menyelesaikan masalah algoritma di HackerRank dan Leetcode . Soal-soal dari sana sering digunakan bahkan saat wawancara di Google dan Facebook, jadi pasti tidak akan bosan :) Untuk memperkuat materi perkuliahan, saya menyarankan Anda untuk menonton video bagus tentang Big-O di YouTube. Sampai jumpa di perkuliahan selanjutnya! :)
Dalam hal ini, algoritma yang paling efisien adalah mentransfer file melalui Internet. Hanya perlu beberapa menit! Jadi, mari kita nyatakan kembali algoritma kita: “Jika Anda perlu mentransfer informasi dalam bentuk file melalui jarak 5000 kilometer, Anda perlu menggunakan transmisi data melalui Internet.” Besar. Sekarang mari kita menganalisisnya. Apakah ini menyelesaikan masalah kita? Secara umum, ya, itu menyelesaikannya sepenuhnya. Namun apa yang dapat Anda katakan tentang kompleksitasnya? Hmm, sekarang di sinilah segalanya menjadi menarik. Faktanya algoritma kami sangat bergantung pada data yang masuk, yaitu ukuran file. Sekarang kami memiliki 10 megabita dan semuanya baik-baik saja. Bagaimana jika kita perlu mentransfer 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Akankah algoritme kami berhenti bekerja? Tidak, seluruh jumlah data ini masih dapat ditransfer. Apakah akan memakan waktu lebih lama untuk menyelesaikannya? Ya, tentu saja! Sekarang kami mengetahui fitur penting dari algoritme kami: semakin besar ukuran data yang akan ditransfer, semakin lama waktu yang dibutuhkan algoritme untuk menyelesaikannya . Namun kami ingin memahami lebih tepat seperti apa hubungan ini (antara ukuran data dan waktu yang diperlukan untuk mentransfernya). Dalam kasus kami, kompleksitas algoritme akan linier. “Linear” berarti seiring bertambahnya volume data, waktu transmisinya akan meningkat kira-kira secara proporsional. Jika datanya 2 kali lebih banyak, dan perlu waktu 2 kali lebih lama untuk mentransfernya. Jika datanya 10 kali lebih banyak, waktu transfer akan bertambah 10 kali lipat. Menggunakan notasi Big-O, kompleksitas algoritma kami didefinisikan sebagai O(N) . Notasi ini paling baik diingat untuk referensi di masa mendatang; notasi ini selalu digunakan untuk algoritma dengan kompleksitas linier. Harap diperhatikan: di sini kita sama sekali tidak membicarakan berbagai hal “variabel”: kecepatan internet, kekuatan komputer kita, dan sebagainya. Saat menilai kompleksitas suatu algoritme, hal ini tidak masuk akal - kami tidak memiliki kendali atas algoritme tersebut. Big-O mengevaluasi algoritme itu sendiri, terlepas dari “lingkungan” di mana algoritme tersebut harus bekerja. Mari kita lanjutkan dengan contoh kita. Katakanlah ternyata ukuran file yang akan ditransfer adalah 800 terabyte. Jika kita mengirimkannya melalui Internet, masalahnya tentu saja akan teratasi. Hanya ada satu masalah: transmisi melalui tautan modern standar (dengan kecepatan 100 megabit per detik) yang sebagian besar dari kita gunakan di rumah akan memakan waktu sekitar 708 hari. Hampir 2 tahun! :O Jadi, algoritma kami jelas tidak cocok di sini. Kami membutuhkan solusi lain! Tiba-tiba, raksasa IT Amazon datang membantu kita! Layanan Amazon Snowmobile memungkinkan Anda memuat data dalam jumlah besar ke dalam unit penyimpanan seluler dan mengirimkannya ke alamat yang diinginkan dengan truk! 
Jadi kami memiliki algoritma baru! “Jika Anda perlu mentransfer informasi dalam bentuk file dengan jarak 5.000 kilometer, dan prosesnya akan memakan waktu lebih dari 14 hari jika ditransfer melalui Internet, Anda perlu menggunakan transportasi truk Amazon.” Angka 14 hari dipilih secara acak di sini: katakanlah ini adalah jangka waktu maksimum yang mampu kita bayar. Mari kita menganalisis algoritma kita. Bagaimana dengan kecepatan? Sekalipun truk tersebut melaju dengan kecepatan hanya 50 km/jam, ia dapat menempuh jarak 5.000 kilometer hanya dalam waktu 100 jam. Itu baru empat hari! Ini jauh lebih baik daripada opsi transmisi Internet. Bagaimana dengan kompleksitas algoritma ini? Apakah juga akan linier, O(N)? Tidak, itu tidak akan terjadi. Lagi pula, truk tidak peduli berapa banyak Anda memuatnya - truk akan tetap melaju dengan kecepatan yang kira-kira sama dan tiba tepat waktu. Apakah kita memiliki 800 terabyte, atau data 10 kali lebih banyak, truk akan tetap sampai di sana dalam 5 hari. Dengan kata lain, algoritma pengiriman data melalui truk memiliki kompleksitas yang konstan . “Konstan” berarti tidak bergantung pada data yang diteruskan ke algoritme. Masukkan flash drive 1GB ke dalam truk dan akan tiba dalam 5 hari. Letakkan disk dengan data 800 terabyte di sana dan itu akan tiba dalam 5 hari. Saat menggunakan Big-O, kompleksitas konstan dilambangkan sebagai O(1) . Sejak kita berkenalan dengan O(N) danO(1) , sekarang mari kita lihat lebih banyak contoh “programmer” :) Katakanlah Anda diberikan array yang terdiri dari 100 angka, dan tugasnya adalah mencetak masing-masing angka tersebut ke konsol. Anda menulis loop reguler 
Di baris atas gambar kita melihat array yang diurutkan. Di dalamnya kita perlu mencari angka 23. Daripada mengulangi angka-angka tersebut, kita cukup membagi array menjadi 2 bagian dan memeriksa angka rata-rata dalam array. Kami menemukan nomor yang terletak di sel 4 dan memeriksanya (baris kedua pada gambar). Angka ini 16, dan kita mencari 23. Angka saat ini lebih sedikit. Apa artinya ini? Bahwa semua bilangan sebelumnya (yang letaknya sampai dengan bilangan 16) tidak perlu dicentang : pasti lebih kecil dari bilangan yang kita cari, karena larik kita sudah terurut! Mari lanjutkan pencarian di antara 5 elemen yang tersisa. Perhatian:Kami hanya melakukan satu pemeriksaan, tetapi kami telah menghilangkan setengah dari opsi yang mungkin. Kami hanya memiliki 5 elemen tersisa. Kami akan mengulangi langkah kami - lagi membagi array yang tersisa dengan 2 dan sekali lagi mengambil elemen tengah (baris 3 pada gambar). Angka ini 56, dan lebih besar dari yang kita cari. Apa artinya ini? Bahwa kita membuang 3 opsi lagi - angka 56 itu sendiri, dan dua angka setelahnya (pastinya lebih besar dari 23, karena arraynya sudah diurutkan). Kami hanya memiliki 2 angka tersisa untuk diperiksa (baris terakhir pada gambar) - angka dengan indeks array 5 dan 6. Kami memeriksa yang pertama, dan inilah yang kami cari - angka 23! Indeksnya = 5! Mari kita lihat hasil algoritma kita, dan kemudian kita akan memahami kompleksitasnya. (Omong-omong, sekarang Anda mengerti mengapa ini disebut biner: intinya adalah membagi data secara konstan dengan 2). Hasilnya sungguh mengesankan! Jika kita mencari angka yang diinginkan menggunakan pencarian linier, kita memerlukan 10 pemeriksaan, tetapi dengan pencarian biner kita melakukannya dalam 3! Dalam kasus terburuk, akan ada 4, jika pada langkah terakhir nomor yang kita butuhkan ternyata yang kedua, dan bukan yang pertama. Bagaimana dengan kompleksitasnya? Ini adalah poin yang sangat menarik :) Algoritma pencarian biner tidak terlalu bergantung pada jumlah elemen dalam array dibandingkan algoritma pencarian linier (yaitu, enumerasi sederhana). Dengan 10 elemen dalam array, pencarian linier memerlukan maksimal 10 pemeriksaan, dan pencarian biner memerlukan maksimal 4 pemeriksaan. Perbedaannya 2,5 kali lipat. Namun untuk array yang terdiri dari 1000 elemen, penelusuran linier memerlukan 1000 pemeriksaan, dan penelusuran biner hanya memerlukan 10 ! Perbedaannya sudah 100 kali lipat! Perhatian:jumlah elemen dalam array meningkat 100 kali lipat (dari 10 menjadi 1000), dan jumlah pemeriksaan yang diperlukan untuk pencarian biner hanya meningkat 2,5 kali lipat - dari 4 menjadi 10. Jika kita mencapai 10.000 elemen , perbedaannya bahkan lebih mengesankan: 10.000 memeriksa pencarian linier, dan total 14 pemeriksaan untuk biner. Dan lagi: jumlah elemen meningkat 1000 kali lipat (dari 10 menjadi 10.000), tetapi jumlah pemeriksaan hanya meningkat 3,5 kali lipat (dari 4 menjadi 14). Kompleksitas algoritma pencarian biner adalah logaritmik , atau, dalam notasi Big-O, O(log n) . Mengapa disebut demikian? Logaritma adalah kebalikan dari eksponensial. Logaritma biner digunakan untuk menghitung pangkat 2. Misalnya, kita memiliki 10.000 elemen yang harus kita lalui menggunakan pencarian biner. 
Sekarang Anda memiliki gambaran di depan mata Anda, dan Anda tahu bahwa ini memerlukan maksimal 14 pemeriksaan. Tetapi bagaimana jika tidak ada gambaran di depan mata Anda, dan Anda perlu menghitung jumlah pasti pemeriksaan yang diperlukan? Cukup dengan menjawab pertanyaan sederhana: berapa pangkat 2 yang harus dipangkatkan agar hasil yang didapat >= banyaknya elemen yang diperiksa? Untuk 10.000 itu akan menjadi pangkat ke-14. 2 pangkat 13 terlalu kecil (8192) Tapi 2 pangkat 14 = 16384 , angka ini memenuhi kondisi kita (>= jumlah elemen dalam array). Kami menemukan logaritma - 14. Itulah jumlah cek yang kami perlukan! :) Algoritma dan kompleksitasnya merupakan topik yang terlalu luas untuk dimasukkan dalam satu kuliah. Namun mengetahuinya sangatlah penting: dalam banyak wawancara Anda akan menerima masalah algoritmik. Untuk teori, saya dapat merekomendasikan Anda beberapa buku. Tempat yang baik untuk memulai adalah “ Algoritma Grocking ”: meskipun contoh dalam buku ini ditulis dengan Python, bahasa dan contoh buku ini sangat sederhana. Pilihan terbaik untuk pemula, dan volumenya juga kecil. Bacaan yang lebih serius: buku karya Robert Laforet dan Robert Sedgwick . Keduanya ditulis dalam Java, yang akan membuat pembelajaran Anda sedikit lebih mudah. Lagi pula, Anda cukup familiar dengan bahasa ini! :) Untuk siswa dengan latar belakang matematika yang baik, pilihan terbaik adalah buku karya Thomas Corman . Namun Anda tidak akan puas hanya dengan teori! “Tahu” != “mampu” Anda dapat berlatih menyelesaikan masalah algoritma di HackerRank dan Leetcode . Soal-soal dari sana sering digunakan bahkan saat wawancara di Google dan Facebook, jadi pasti tidak akan bosan :) Untuk memperkuat materi perkuliahan, saya menyarankan Anda untuk menonton video bagus tentang Big-O di YouTube. Sampai jumpa di perkuliahan selanjutnya! :)
GO TO FULL VERSION