Pendahuluan

Bayangkan Anda diminta membantu perpustakaan kampus membuat sistem peminjaman buku sederhana. Pada awalnya, masalah itu terdengar seperti masalah administrasi: ada mahasiswa, ada buku, ada tanggal pinjam, ada tanggal kembali. Namun begitu sistem mulai dirancang, muncul pertanyaan yang lebih teknis.

Jika seorang mahasiswa mengetik judul buku, bagaimana sistem mencarinya? Jika ada ribuan buku, apakah sistem harus memeriksa satu per satu dari awal sampai akhir? Jika daftar peminjaman harus selalu menampilkan buku yang paling lama dipinjam, bagaimana data itu sebaiknya disimpan? Jika dua mahasiswa mengembalikan buku pada waktu yang hampir bersamaan, bagaimana antreannya dikelola?

Pertanyaan-pertanyaan seperti itu adalah pintu masuk ke algoritma dan struktur data.

Secara sederhana, algoritma adalah prosedur komputasional yang menerima masukan, menjalankan langkah-langkah yang terdefinisi dengan jelas, lalu menghasilkan keluaran. Buku Introduction to Algorithms mendefinisikan algoritma sebagai prosedur komputasional yang mengambil suatu nilai atau sekumpulan nilai sebagai masukan dan menghasilkan suatu nilai atau sekumpulan nilai sebagai keluaran (Cormen et al., 2022). Misalnya, algoritma mencari nama mahasiswa dalam daftar dapat menerima masukan berupa nama_dicari dan daftar_mahasiswa, lalu menghasilkan keluaran berupa posisi nama tersebut jika ditemukan, atau pesan “tidak ditemukan” jika tidak ada.

Sementara itu, struktur data adalah cara mengorganisasi dan menyimpan data agar operasi tertentu dapat dilakukan secara efisien. Cormen et al. menjelaskan struktur data sebagai cara menyimpan dan mengorganisasi data untuk memudahkan akses dan modifikasi (Cormen et al., 2022). Contohnya, daftar kontak di ponsel dapat disimpan sebagai larik, tabel hash, atau pohon pencarian, tergantung operasi apa yang paling penting: menampilkan semua kontak, mencari nama dengan cepat, atau menjaga urutan alfabetis.

Buku ini membahas keduanya sekaligus karena dalam praktik, algoritma dan struktur data jarang benar-benar terpisah. Algoritma yang baik sering membutuhkan struktur data yang tepat. Sebaliknya, struktur data baru terasa berguna ketika kita memahami operasi apa yang ingin dilakukan di atasnya.

Mengapa ini penting?

Pada tahun pertama kuliah, banyak mahasiswa mengira bahwa belajar pemrograman terutama berarti belajar sintaks bahasa pemrograman: cara menulis if, for, fungsi, kelas, atau modul. Sintaks memang penting, tetapi sintaks hanyalah bentuk penulisan. Inti yang lebih dalam adalah kemampuan merancang proses berpikir yang dapat dijalankan oleh komputer.

Dua program dapat sama-sama benar, tetapi memiliki biaya komputasi yang sangat berbeda.

Misalnya, kita ingin mencari apakah angka 73 ada dalam daftar berikut:

[12, 18, 21, 35, 47, 58, 73, 91]

Cara pertama adalah memeriksa dari kiri ke kanan:

Periksa 12
Periksa 18
Periksa 21
...
Periksa 73

Cara ini disebut pencarian linear. Untuk daftar kecil, cara ini cukup baik. Tetapi jika daftar berisi satu juta data, pencarian linear dapat memerlukan pemeriksaan sangat banyak elemen.

Jika daftar sudah terurut, kita dapat memakai pencarian biner. Idenya adalah memeriksa elemen tengah, lalu membuang separuh ruang pencarian yang tidak mungkin berisi jawaban. Untuk data terurut yang dapat diakses langsung berdasarkan indeks, pencarian biner jauh lebih efisien daripada pencarian linear pada masukan besar. Analisis perbandingan seperti ini merupakan tema sentral dalam studi algoritma modern (Cormen et al., 2022).

Contoh ini mengajarkan tiga hal.

Pertama, kebenaran dan efisiensi adalah dua pertanyaan berbeda. Program benar jika menghasilkan keluaran yang sesuai spesifikasi. Program efisien jika menggunakan waktu dan memori secara hemat untuk ukuran masukan yang relevan.

Kedua, struktur data menentukan kemungkinan algoritma. Pencarian biner membutuhkan data yang terurut dan dapat diakses langsung berdasarkan posisi. Jika data disimpan dalam daftar berantai yang hanya bisa ditelusuri dari simpul ke simpul, manfaat pencarian biner tidak sama seperti pada larik.

Ketiga, tidak ada struktur data yang selalu terbaik. Larik baik untuk akses berdasarkan indeks. Daftar berantai baik untuk penyisipan atau penghapusan pada posisi yang sudah diketahui tanpa menggeser banyak elemen. Tumpukan baik untuk pola “yang terakhir masuk, pertama keluar”. Antrean baik untuk pola “yang pertama masuk, pertama keluar”. Tabel hash sering sangat cepat untuk pencarian berbasis kunci dalam kasus rata-rata, tetapi memerlukan perhatian terhadap collision dan load factor. Pohon dan graf cocok untuk relasi hierarkis dan relasi jaringan.

Belajar algoritma dan struktur data berarti belajar memilih alat yang sesuai dengan bentuk masalah.

Dari masalah sehari-hari ke masalah komputasional

Buku ini menggunakan sudut pandang berpikir komputasional. Istilah ini merujuk pada cara merumuskan masalah dan solusinya sehingga solusi tersebut dapat dijalankan oleh manusia, komputer, atau agen pemroses informasi lain. Jeannette Wing memopulerkan gagasan computational thinking sebagai keterampilan dasar untuk merumuskan masalah dan solusi dalam bentuk yang dapat diproses secara efektif (Wing, 2006).

Mari kita mulai dari contoh sederhana: mengatur antrean layanan akademik.

Dalam kehidupan sehari-hari, kita mungkin berkata:

“Mahasiswa yang datang lebih dulu harus dilayani lebih dulu.”

Kalimat itu dapat diterjemahkan menjadi gagasan komputasional:

• ada data mahasiswa yang datang,
• setiap mahasiswa masuk ke bagian belakang antrean,
• petugas selalu mengambil mahasiswa dari bagian depan antrean,
• urutan layanan mengikuti urutan kedatangan.

Struktur data yang cocok untuk pola ini adalah antrean. Antrean memiliki prinsip FIFO, singkatan dari first in, first out, yaitu data yang masuk lebih dulu akan keluar lebih dulu. Dalam bahasa sehari-hari, ini seperti antre di loket: orang yang datang paling awal seharusnya dilayani paling awal.

Sekarang bandingkan dengan tumpukan piring di kantin. Piring yang baru diletakkan biasanya berada di paling atas, dan piring yang paling atas itulah yang pertama diambil. Pola ini disebut LIFO, singkatan dari last in, first out. Struktur data yang cocok adalah tumpukan.

Dari dua contoh ini, kita melihat bahwa struktur data bukan sekadar “tempat menyimpan data”. Struktur data membawa aturan operasi. Jika aturan masalahnya FIFO, antrean alami digunakan. Jika aturan masalahnya LIFO, tumpukan alami digunakan.

Empat kebiasaan berpikir yang akan dilatih

Buku ini tidak hanya mengajarkan daftar algoritma. Tujuan utamanya adalah melatih cara berpikir. Ada empat kebiasaan yang akan sering muncul.

Pertama, dekomposisi masalah. Dekomposisi berarti memecah masalah besar menjadi bagian-bagian kecil yang lebih mudah dipahami. Misalnya, “membuat sistem pencarian buku” dapat dipecah menjadi: menyimpan data buku, menerima kata kunci, mencari kecocokan, menampilkan hasil, dan menangani kasus ketika buku tidak ditemukan.

Kedua, abstraksi. Abstraksi berarti memilih informasi penting dan mengabaikan rincian yang tidak relevan untuk tujuan tertentu. Ketika memodelkan antrean mahasiswa, kita mungkin hanya membutuhkan nomor_antrean, nama, dan waktu_datang. Kita tidak perlu memasukkan tinggi badan atau warna baju, karena informasi itu tidak memengaruhi urutan layanan.

Ketiga, pengenalan pola. Banyak masalah tampak berbeda di permukaan, tetapi memiliki bentuk komputasional yang sama. Antrean di bank, buffering data jaringan, dan penjadwalan tugas dapat sama-sama menggunakan gagasan antrean. Pencarian kontak, pencarian NIM, dan pencarian kode barang dapat sama-sama dilihat sebagai pencarian berbasis kunci.

Keempat, perancangan langkah algoritmik. Setelah masalah dipahami, kita menyusun langkah-langkah yang jelas. Langkah itu harus cukup tepat sehingga dapat ditelusuri, diuji, dan akhirnya diterjemahkan ke bahasa pemrograman.

Sebagai contoh, tugas “cari nilai terbesar dalam daftar” dapat ditulis sebagai algoritma:

Jika daftar kosong, laporkan bahwa tidak ada nilai terbesar.
Anggap elemen pertama sebagai nilai terbesar sementara.
Untuk setiap elemen berikutnya:
    Jika elemen itu lebih besar daripada nilai terbesar sementara:
        Ganti nilai terbesar sementara dengan elemen itu.
Setelah semua elemen diperiksa, keluarkan nilai terbesar sementara.

Langkah-langkah ini tidak bergantung pada bahasa pemrograman tertentu. Inilah salah satu alasan kita memakai pseudocode, yaitu penulisan algoritma yang mirip kode tetapi dirancang untuk dibaca manusia. Pseudocode membantu kita fokus pada ide sebelum tenggelam dalam detail sintaks.

Ukuran masukan dan biaya komputasi

Salah satu pertanyaan paling penting dalam buku ini adalah:

Apa yang terjadi ketika ukuran masukan membesar?

Jika daftar hanya berisi 10 elemen, hampir semua cara terasa cepat. Tetapi jika daftar berisi 10 juta elemen, perbedaan algoritma menjadi sangat nyata.

Ukuran masukan adalah ukuran data yang diproses oleh algoritma. Untuk algoritma pencarian dalam larik, ukuran masukan biasanya jumlah elemen, sering dilambangkan dengan n. Untuk graf, ukuran masukan dapat melibatkan jumlah simpul dan jumlah sisi. Untuk teks, ukuran masukan dapat berupa jumlah karakter atau jumlah kata.

Biaya komputasi adalah sumber daya yang digunakan algoritma. Dua biaya yang paling sering dianalisis adalah waktu dan ruang. Waktu berkaitan dengan jumlah operasi dasar yang dilakukan. Ruang berkaitan dengan jumlah memori tambahan yang dibutuhkan. Analisis algoritma biasanya mempelajari bagaimana kebutuhan sumber daya tumbuh ketika ukuran masukan bertambah (Cormen et al., 2022).

Misalnya, jika sebuah algoritma memeriksa setiap elemen satu kali, jumlah pemeriksaannya bertambah sebanding dengan jumlah elemen. Jika elemen bertambah dari 1.000 menjadi 2.000, pekerjaannya kira-kira ikut menjadi dua kali lipat. Ini disebut pertumbuhan linear.

Namun, jika sebuah algoritma membandingkan setiap pasangan elemen, jumlah pekerjaannya dapat tumbuh jauh lebih cepat. Untuk 1.000 elemen, jumlah pasangan jauh lebih besar daripada 1.000. Pola seperti ini akan dipelajari secara lebih tepat melalui notasi asimtotik, seperti Big-O, Big-Omega, dan Big-Theta.

Untuk saat ini, cukup pegang gagasan dasar berikut: kita tidak hanya bertanya “berapa detik program ini berjalan di laptop saya?”, tetapi juga “bagaimana jumlah langkahnya tumbuh ketika data menjadi lebih besar?”. Pertanyaan kedua lebih umum dan lebih berguna ketika kita membandingkan algoritma.

Kebenaran sebelum kecepatan

Efisiensi penting, tetapi algoritma cepat yang salah tetap tidak berguna. Karena itu, buku ini akan berkali-kali membedakan kebenaran algoritma dari efisiensi algoritma.

Algoritma benar jika memenuhi spesifikasi. Spesifikasi adalah pernyataan tentang apa yang harus diterima sebagai masukan dan apa yang harus dihasilkan sebagai keluaran. Misalnya, untuk pencarian nilai dalam daftar:

Masukan:
    daftar angka A
    angka x yang dicari

Keluaran:
    indeks i sehingga A[i] = x, jika x ditemukan
    atau -1 jika x tidak ditemukan

Dengan spesifikasi ini, kita dapat menguji algoritma pada beberapa kasus:

A = [4, 9, 2], x = 9      keluaran yang benar: 1
A = [4, 9, 2], x = 7      keluaran yang benar: -1
A = [], x = 5             keluaran yang benar: -1

Kasus terakhir, yaitu daftar kosong, disebut kasus tepi. Kasus tepi adalah situasi yang berada di batas kemungkinan masukan: data kosong, hanya satu elemen, nilai duplikat, indeks pertama, indeks terakhir, atau ukuran sangat besar. Banyak bug muncul karena program hanya diuji pada kasus “normal” dan melupakan kasus tepi.

Dalam bab-bab berikutnya, kita juga akan menggunakan gagasan invariant. Invariant adalah pernyataan yang tetap benar pada titik tertentu selama algoritma berjalan. Misalnya, dalam algoritma mencari nilai terbesar, setelah memeriksa beberapa elemen pertama, nilai terbesar sementara harus benar-benar merupakan nilai terbesar di antara elemen-elemen yang sudah diperiksa. Invariant membantu kita menjelaskan mengapa suatu algoritma benar, bukan hanya menunjukkan bahwa algoritma itu “terlihat bekerja” pada contoh tertentu.

Apa yang akan Anda kuasai setelah membaca buku ini?

Setelah menyelesaikan buku ini, Anda diharapkan mampu membaca masalah komputasional dengan lebih tenang. Ketika menghadapi sebuah tugas, Anda tidak langsung bertanya “pakai kode apa?”, tetapi mulai dari pertanyaan yang lebih mendasar:

• Apa masukannya?
• Apa keluarannya?
• Operasi apa yang paling sering dilakukan?
• Apakah data perlu terurut?
• Apakah perlu pencarian cepat?
• Apakah penyisipan dan penghapusan sering terjadi?
• Apakah ada relasi hierarkis seperti pohon?
• Apakah ada relasi jaringan seperti graf?
• Berapa biaya waktu dan ruang dari pilihan ini?

Pertanyaan-pertanyaan itu akan menuntun Anda memilih struktur data dan algoritma secara lebih rasional.

Jika masalah membutuhkan akses cepat berdasarkan indeks, larik mungkin cocok. Jika masalah membutuhkan pola pembatalan langkah terakhir, tumpukan mungkin cocok. Jika masalah berkaitan dengan layanan berdasarkan urutan kedatangan, antrean mungkin cocok. Jika masalah melibatkan relasi pertemanan, jalan, atau koneksi, graf mungkin diperlukan. Jika masalah meminta pencarian berdasarkan kunci, tabel hash atau pohon pencarian dapat dipertimbangkan.

Namun buku ini tidak akan mengajarkan hafalan kaku seperti “masalah X selalu pakai Y”. Dunia nyata lebih beragam. Buku ini akan mengajarkan cara menjelaskan trade-off: apa yang dibuat cepat, apa yang menjadi mahal, memori tambahan apa yang digunakan, dan asumsi apa yang harus dipenuhi.

Cara menggunakan buku ini

Setiap bab dibangun secara bertahap. Bab awal membahas cara merumuskan masalah, menulis algoritma, dan menghitung biaya. Setelah itu, kita mempelajari struktur data linear seperti larik, daftar berantai, tumpukan, dan antrean. Kemudian kita masuk ke rekursi, pencarian, pengurutan, tabel hash, pohon, graf, dan strategi perancangan algoritma.

Saat membaca, jangan hanya mengingat nama algoritma. Cobalah selalu menanyakan:

“Masalah apa yang diselesaikan oleh ide ini, dan operasi apa yang dibuat lebih murah?”

Misalnya, ketika belajar merge sort, jangan berhenti pada fakta bahwa ia adalah algoritma pengurutan. Perhatikan bahwa merge sort memakai strategi memecah masalah menjadi dua bagian, mengurutkan masing-masing bagian, lalu menggabungkannya. Ketika belajar heap, jangan hanya mengingat bentuk pohonnya. Perhatikan bahwa heap dirancang agar elemen dengan prioritas tertinggi atau terendah dapat diambil secara efisien.

Anda juga disarankan menelusuri contoh dengan tangan. Ambil kertas, tulis isi larik, gambar simpul daftar berantai, buat tumpukan panggilan rekursif, atau gambar graf kecil. Banyak konsep struktur data baru benar-benar terasa jelas setelah kita melihat bagaimana isinya berubah langkah demi langkah.

Sikap belajar yang tepat

Algoritma dan struktur data kadang terasa sulit bukan karena idenya terlalu jauh, tetapi karena beberapa lapisan dipelajari sekaligus: definisi, contoh, pseudocode, pembuktian kebenaran, dan analisis biaya. Jika suatu bagian terasa lambat, itu normal.

Belajarlah seperti seorang perancang, bukan seperti penghafal. Seorang penghafal bertanya, “Apa rumus kompleksitasnya?” Seorang perancang bertanya, “Mengapa kompleksitasnya demikian? Operasi mana yang paling sering terjadi? Bagian mana yang mendominasi biaya?”

Sebagai contoh, jika sebuah loop berjalan dari 1 sampai n, lalu di dalamnya ada loop lain yang juga dapat berjalan sampai n, kita tidak sekadar menghafal bahwa biayanya kuadratik. Kita memahami bahwa untuk setiap satu langkah loop luar, loop dalam dapat melakukan banyak langkah. Akibatnya, jumlah total operasi dapat tumbuh sebanding dengan n × n.

Pemahaman seperti ini membuat Anda lebih mandiri. Ketika nanti bertemu algoritma yang belum pernah dihafal, Anda tetap dapat menelusuri langkahnya, menemukan operasi dominan, dan memperkirakan biayanya.

Peta perjalanan

Buku ini dimulai dari fondasi: berpikir komputasional, algoritma, model biaya, dan notasi asimtotik. Setelah itu, kita membangun perbendaharaan struktur data: larik, daftar berantai, tumpukan, antrean, tabel hash, pohon, heap, dan graf. Di tengah perjalanan, kita mempelajari pencarian, pengurutan, rekursi, dan relasi rekurens. Pada bagian akhir, kita menyatukan semuanya melalui strategi perancangan algoritma dan studi kasus terpadu.

Tujuan akhirnya bukan sekadar agar Anda tahu bahwa quicksort biasanya cepat, BFS memakai antrean, atau Dijkstra mencari lintasan terpendek dengan bobot nonnegatif. Tujuan yang lebih penting adalah agar Anda dapat menjelaskan alasan di balik pilihan tersebut.

Ketika seseorang bertanya, “Mengapa memakai struktur data ini?”, Anda dapat menjawab secara teknis:

“Karena operasi dominannya adalah pencarian berdasarkan kunci. Dengan tabel hash dan fungsi hash yang baik, biaya rata-rata pencarian dapat dibuat sangat kecil. Namun jika kita perlu menjaga data tetap terurut, pohon pencarian seimbang mungkin lebih sesuai.”

Atau:

“Karena masalah ini membutuhkan eksplorasi simpul berdasarkan jarak jumlah sisi dari titik awal. BFS cocok untuk graf tak berbobot karena ia mengunjungi simpul lapis demi lapis.”

Kemampuan menjelaskan seperti itulah yang akan dibangun pelan-pelan dalam buku ini.

Kita mulai dari pertanyaan paling dasar: bagaimana mengubah masalah menjadi bentuk yang dapat diproses secara komputasional?

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.

Wing, J. M. (2006). Computational thinking. Communications of the ACM, 49(3), 33–35.