Overview
Materi ini membahas kompleksitas algoritma dalam penyusunan kembali string (string reconstruction), membandingkan pendekatan brute-force, greedy, dan dynamic programming serta pentingnya teknik memoization untuk efisiensi waktu dan memori.
Permasalahan String Reconstruction
- String reconstruction bertujuan membagi urutan karakter menjadi kata-kata bermakna berdasarkan kamus.
- Komputer harus secara sistematis mencoba kemungkinan peletakan spasi, berbeda dengan manusia yang intuitif.
- Algoritma brute-force mengetes setiap kemungkinan peletakan spasi, tetapi sangat tidak efisien.
- Greedy approach memilih kata terpanjang yang valid pada setiap langkah, namun belum tentu mendapatkan hasil optimal.
- Keduanya dapat menyebabkan computational cost yang tinggi dan hasil yang kurang akurat.
Kompleksitas Algoritma & Dynamic Programming
- Brute-force dan greedy cenderung menghasilkan time complexity eksponensial (O(2^n)) pada jumlah karakter besar.
- Dynamic programming memecah masalah besar menjadi subproblem kecil yang hasilnya disimpan untuk menghindari kalkulasi ulang.
- Teknik ini disebut memoization, digunakan untuk mengurangi repetisi proses komputasi yang sama di subproblem yang overlap.
- Dengan menyimpan hasil sementara di cache/tabel, efisiensi waktu dan ruang dapat dicapai.
- Prinsip bottom-up: selesaikan masalah kecil, lalu gunakan hasilnya untuk masalah yang lebih besar.
Contoh Penerapan
- Pada string “applepie” dengan kamus {apple, pie}, dynamic programming membagi string dan mengecek setiap substring pada kamus, menyimpan hasil intermediate.
- Teknik memoization sangat membantu bila jumlah kemungkinan pecahan string sangat banyak (n besar).
- Untuk kasus kecil, perbedaan tanpa memoization tidak terlalu signifikan, tetapi untuk input besar sangatlah penting.
Catatan Implementasi Memoization
- Gunakan cache untuk menyimpan hasil sementara perhitungan subproblem.
- Perhatikan penggunaan memori, cache hanya digunakan bila hasil sering dipakai kembali.
- Sesuaikan dimensi penyimpanan (1D, 2D, 3D) sesuai kebutuhan masalah.
- Pastikan melakukan benchmark waktu eksekusi masing-masing subproblem.
Kesimpulan dan Aplikasi
- Algoritma efisien diperlukan agar komputer dapat menyelesaikan masalah yang tampak mudah bagi manusia.
- Dynamic programming terbukti jauh lebih efisien dibanding brute-force dan greedy approach untuk kasus string reconstruction.
- Paradigma penyelesaian masalah kecil (subproblem) relevan untuk berbagai aplikasi praktis, seperti spell checker atau autocorrect di AI/NLP.
Key Terms & Definitions
- String Reconstruction — Proses menyusun kembali karakter acak menjadi kalimat bermakna menggunakan referensi kamus.
- Brute-force — Pendekatan mencoba semua kemungkinan solusi, sangat tidak efisien.
- Greedy Approach — Memilih solusi lokal terbaik di setiap langkah, kadang menghasilkan hasil suboptimal.
- Dynamic Programming — Teknik memecah masalah besar menjadi subproblem kecil yang hasilnya disimpan (memoization).
- Memoization — Penyimpanan hasil komputasi subproblem agar tidak dihitung ulang.
- Time Complexity — Ukuran waktu eksekusi algoritma sehubungan dengan input.
- Cache — Tempat sementara menyimpan hasil komputasi.
Action Items / Next Steps
- Latihan membagi string dan implementasi dynamic programming dengan memoization.
- Evaluasi efisiensi algoritma dengan mengukur time complexity pada berbagai ukuran input.
- Pelajari lebih lanjut penerapan dynamic programming untuk kasus lain seperti scheduling dan simulasi di berbagai bidang.