Algoritma & kompleksitas: latihan soal dengan penjelasan

1Apa yang diukur kompleksitas

Algoritma adalah daftar langkah yang berhingga dan tepat untuk menyelesaikan suatu masalah, seperti mengurutkan daftar atau mencari nama di buku telepon.

Dua algoritma dapat menyelesaikan masalah yang sama tetapi memerlukan waktu yang sangat berbeda. Kompleksitas menjelaskan bagaimana pekerjaan bertumbuh ketika masukan membesar.

Ukuran masukan disebut n: jumlah item yang diurutkan, panjang daftar, jumlah simpul dalam graf.

Bayangkan mencari nama di buku telepon setebal 1000 halaman. Membaca setiap halaman memerlukan hingga 1000 langkah. Membukanya di tengah dan membagi dua setiap kali memerlukan sekitar 10 langkah.

Kompleksitas waktu menghitung langkah. Kompleksitas ruang menghitung memori tambahan. Keduanya ditulis sebagai fungsi n.

Biasanya Anda meninjau kasus terburuk: pekerjaan paling banyak dari semua masukan berukuran n. Kadang yang ditanyakan adalah kasus rata-rata atau kasus terbaik.

2Big O dan kelas pertumbuhan

Notasi Big O hanya menyimpan yang penting untuk n besar. Anda membuang faktor konstanta dan hanya menyimpan suku yang tumbuh paling cepat.

Untuk n = 1000 suku n² adalah 3 000 000, sedangkan 5n hanya 5000. Suku yang lebih kecil hampir tidak mengubah totalnya.

Kelas-kelas ini muncul berulang kali, dari pertumbuhan paling lambat hingga paling cepat:

• O(1), konstan: membaca elemen larik berdasarkan indeksnya.
• O(log n), logaritmik: pencarian biner, yang membagi dua masalah pada setiap langkah.
• O(n), linear: satu kali lewat atas semua item, seperti mencari nilai terbesar.
• O(n log n): algoritma pengurutan yang baik seperti merge sort.
• O(n²), kuadratik: dua loop bersarang atas item, seperti bubble sort.
• O(2ⁿ), eksponensial: mencoba setiap himpunan bagian. Cepat menjadi tidak dapat dipakai.

Big O adalah batas atas: pekerjaan tumbuh paling cepat sebesar ini. Ω (Big Omega) adalah batas bawah, dan Θ (Theta) adalah batas ketat, baik atas maupun bawah.

Basis logaritma tidak berpengaruh pada Big O, karena logaritma dengan basis berbeda hanya berselisih faktor konstanta.

3Pencarian, pengurutan, dan rekursi

Beberapa algoritma muncul di hampir setiap mata kuliah. Pelajari kompleksitasnya sebagai fakta.

• Pencarian linear memeriksa item satu per satu: O(n). Pencarian biner memerlukan larik yang terurut dan membagi dua rentang pada setiap langkah: O(log n).
• Bubble, insertion, dan selection sort membandingkan dan menukar item dalam loop bersarang: O(n²). Insertion sort adalah O(n) pada larik yang sudah terurut.
• Merge sort membagi larik menjadi dua bagian, mengurutkannya, lalu menggabungkannya: O(n log n) dalam setiap kasus, dengan memori tambahan O(n).
• Quicksort membagi di sekitar pivot: O(n log n) rata-rata, tetapi O(n²) pada kasus terburuk, misalnya larik terurut dengan elemen pertama sebagai pivot.
• Tidak ada pengurutan yang hanya membandingkan item yang bisa mengalahkan Ω(n log n) pada kasus terburuk. Counting sort lebih cepat karena tidak membandingkan.

Fungsi rekursif memanggil dirinya sendiri pada masukan yang lebih kecil sampai mencapai kasus dasar yang dijawabnya langsung. Waktu jalannya ditulis sebagai relasi rekurensi:

• T(n) = T(n/2) + O(1) menghasilkan O(log n), seperti pencarian biner.
• T(n) = 2T(n/2) + O(n) menghasilkan O(n log n), seperti merge sort.
• T(n) = T(n − 1) + O(n) menghasilkan O(n²).
• T(n) = 2T(n − 1) + O(1) menghasilkan O(2ⁿ).

Tiga gagasan rancangan perlu diketahui. Divide and conquer (bagi dan taklukkan) membagi, menyelesaikan, dan menggabungkan. Greedy (serakah) mengambil pilihan terbaik secara lokal pada setiap langkah. Pemrograman dinamis menyimpan jawaban submasalah yang tumpang tindih agar dihitung sekali saja.

4Metode ini selangkah demi selangkah

Untuk mencari kompleksitas waktu sepotong kode:

1. Tentukan apa n itu: ukuran masukan.
2. Hitung berapa kali setiap loop berjalan. Loop yang menambah 1 setiap kali berjalan sekitar n kali. Loop yang menggandakan atau membagi dua berjalan sekitar log₂ n kali.
3. Loop di dalam loop dikalikan. Loop yang berurutan dijumlahkan.
4. Untuk fungsi rekursif, tulis rekurensinya: berapa banyak panggilan, pada ukuran berapa, ditambah pekerjaan per panggilan.
5. Simpan suku yang tumbuh paling cepat dan buang konstanta.
6. Periksa dengan bilangan kecil, misalnya n = 8 atau n = 1024.

Untuk soal teori, sebutkan dulu algoritma atau gagasan yang dijelaskannya, lalu ingat kompleksitas dan syaratnya (masukan terurut, bobot tak negatif, submasalah yang tumpang tindih).

5Contoh soal lengkap

Ikuti setiap langkah. Cobalah menebak langkah berikutnya sebelum membukanya.

6Kesalahan umum

• Mengalikan loop yang berjalan berurutan. n + n = 2n tetap O(n).
• Mempertahankan konstanta, seperti O(2n) atau O(n/2). Keduanya O(n).
• Menghitung loop penggandaan sebagai n putaran. Ia berjalan sekitar log₂ n kali.
• Memakai pencarian biner pada data tak terurut, atau pada linked list yang bagian tengahnya tidak dapat dicapai dalam satu langkah.
• Memberikan kasus rata-rata quicksort padahal yang ditanyakan kasus terburuk.
• Mengira Big O berarti “tepat”. O(n²) adalah batas atas; Θ(n²) adalah pertumbuhan yang tepat.

7Seperti apa soal ujiannya

• Mudah: istilah dan fakta kunci. Kompleksitas pencarian biner, merge sort, atau akses larik, arti O, Ω, dan Θ, apa itu rekursi.
• Sedang: menerapkan konsep. Kompleksitas sebuah potongan kode, rekurensi yang harus diselesaikan, bagaimana waktu berubah ketika n digandakan, algoritma mana yang cocok untuk suatu tugas.
• Sulit: kasus dan analisis. Teorema master, kasus terburuk quicksort, greedy versus pemrograman dinamis, dan kelas P, NP, dan NP-complete.

P memuat masalah yang dapat diselesaikan dalam waktu polinomial. NP memuat masalah yang solusinya dapat diperiksa dalam waktu polinomial. Setiap masalah di P berada di NP; apakah P = NP masih belum diketahui.