Menganalisis kompleksitas waktu Big-O, merancang fungsi rekursif dengan base case presisi, dan menerapkan paradigma divide and conquer pada merge sort dan binary search.
Strategi algoritmik merupakan inti dari pemecahan masalah komputasi berskala besar. Pada jenjang SMA Kelas 12, peserta didik beralih dari sekadar menulis kode sintaksis sederhana menuju analisis matematis efisiensi algoritma melalui notasi asimptotik Big-O. Peserta didik memahami bagaimana pemilihan algoritma yang tepat mampu membedakan program yang berjalan dalam hitungan milidetik dengan program yang memerlukan waktu berjam-jam untuk memproses jutaan data.
Konsep rekursi dieksplorasi secara mendalam dengan membedah mekanisme kerja tumpukan pemanggilan memori (*call stack*), bahaya *stack overflow*, dan penentuan kondisi terminasi (*base case*). Peserta didik menerapkan rekursi pada struktur data hierarkis dan masalah klasik seperti Menara Hanoi, faktorial, dan penjelajahan pohon biner (*tree traversal*).
Pembelajaran berlanjut pada paradigma desain *Divide and Conquer*, di mana masalah besar dipecah (*divide*) menjadi submasalah independen yang lebih kecil, diselesaikan (*conquer*), dan digabungkan (*combine*) kembali. Algoritma seperti *Merge Sort* dan *Binary Search* diimplementasikan dan diuji secara komparatif terhadap algoritma *brute force* untuk membuktikan efisiensinya secara empiris.
Pengukuran efisiensi waktu eksekusi terhadap ukuran input data ($n$), skenario *best case*, *average case*, dan *worst case*.
Prinsip pemanggilan fungsi mandiri, eksekusi memori *stack frame*, *tail recursion*, dan pencegahan *infinite loop*.
Tahapan divide, conquer, combine, implementasi Merge Sort ($O(n \log n)$) dan pencarian logaritmik Binary Search ($O(\log n)$).
5 butir instrumen soal pilihan ganda berbasis HOTS untuk mengukur pemahaman konsep pada bab ini. Dilengkapi kunci jawaban dan uraian pembahasan analitis.
Jika suatu algoritma pencarian memiliki kompleksitas waktu $O(\log n)$ untuk memproses data berukuran $n = 1.000.000$, kira-kira berapa operasi perbandingan maksimum yang diperlukan dalam skenario terburuk?
Pembahasan: Pada algoritma logaritmik basis 2 seperti Binary Search, $\log_2(1.000.000) \approx 19,93$, sehingga hanya dibutuhkan maksimal 20 perbandingan untuk menemukan elemen di antara 1 juta data terurut.
Perhatikan fungsi rekursif Python berikut: ```python def hitung(n): if n == 0: return 1 return n * hitung(n - 1) ``` Apa nilai yang dikembalikan saat `hitung(4)` dipanggil?
Pembahasan: Fungsi ini menghitung faktorial: hitung(4) = 4 * hitung(3) = 4 * 3 * hitung(2) = 4 * 3 * 2 * hitung(1) = 4 * 3 * 2 * 1 * 1 = 24.
Apa konsekuensi fatal yang terjadi pada sistem komputer jika sebuah fungsi rekursif ditulis tanpa menyertakan 'base case' yang tepat?
Pembahasan: Tanpa base case, fungsi akan terus memanggil dirinya sendiri dan mengalokasikan stack frame baru di memori hingga batas alokasi stack habis (Stack Overflow).
Manakah pernyataan yang paling tepat mengenai perbandingan efisiensi antara algoritma Bubble Sort ($O(n^2)$) dan Merge Sort ($O(n \log n)$) ketika mengurutkan data besar ($n = 100.000$)?
Pembahasan: Untuk $n = 100.000$, $n^2 = 10.000.000.000$ operasi pada Bubble Sort, sedangkan Merge Sort hanya butuh sekitar $100.000 \times 17 \approx 1.700.000$ operasi, ribuan kali lebih cepat.
Dalam algoritma pencarian biner (Binary Search), syarat mutlak yang harus dipenuhi oleh struktur data array sebelum proses pencarian dilakukan adalah...
Pembahasan: Binary Search bekerja dengan membagi dua ruang pencarian berdasarkan perbandingan dengan nilai tengah; hal ini hanya valid jika elemen array berada dalam kondisi terurut (sorted).
Setelah mengunduh berkas perangkat ajar, ikuti langkah berikut untuk menggunakannya secara optimal:
Tidak ada bahan ajar yang cocok dengan kriteria pencarian.
