Mengapa DSA penting

Topik ini menyajikan bukti konkret bahwa pemilihan struktur data dan algoritma mengubah kinerja program, bukan sekadar klaim teoretis. Setelah membacanya, perbedaan pencarian linear dan pencarian biner dapat dijelaskan lewat jumlah langkah yang benar-benar dihitung oleh sebuah program. Kosakata inti yang dipakai sepanjang jalur, mulai dari array, hash, stack, antrian, rekursi, hingga kompleksitas, juga dipetakan sebagai bekal menyelesaikan masalah. Bagian akhir merangkum peran kemampuan ini dalam wawancara teknis secara faktual.

Bukti nyata dari penghitungan langkah#

Meyakinkan orang tentang pentingnya algoritma tidak memerlukan teori yang rumit, melainkan angka yang dapat dihitung ulang. Perhatikan sebuah daftar berisi 1.000.000 angka yang sudah terurut dari yang terkecil sampai terbesar, serta satu angka yang harus dicari posisinya. Pendekatan pertama adalah linear search, yakni pencarian dengan memeriksa angka satu per satu dari kiri. Pendekatan kedua adalah binary search, yakni pencarian yang memeriksa angka di tengah dahulu, lalu membuang separuh daftar yang tidak mungkin memuat angka tersebut. Kedua pendekatan diterapkan pada daftar yang sama, sehingga perbedaan kerjanya dapat dibandingkan secara adil.

Program berikut menghitung dan mencetak jumlah langkah kedua pendekatan pada daftar 1.000.000 angka, bukan mengukur waktu. Angka yang dicari sengaja dipilih paling belakang, yaitu 999999, supaya pencarian linear bekerja pada kondisi terburuknya. Setiap perbandingan satu angka dihitung sebagai satu langkah.

def cari_linear(data, target):
    langkah = 0
    for i in range(len(data)):
        langkah += 1
        if data[i] == target:
            return langkah
    return langkah

def cari_biner(data, target):
    kiri, kanan = 0, len(data) - 1
    langkah = 0
    while kiri <= kanan:
        langkah += 1
        tengah = (kiri + kanan) // 2
        if data[tengah] == target:
            return langkah
        elif data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return langkah

data = list(range(1000000))
target = 999999
print("jumlah data    :", len(data))
print("langkah linear :", cari_linear(data, target))
print("langkah biner  :", cari_biner(data, target))

jumlah data    : 1000000
langkah linear : 1000000
langkah biner  : 20

Hasilnya kontras. Pencarian linear menuntut 1.000.000 langkah karena angka yang dicari berada di posisi paling akhir, sedangkan pencarian biner menyelesaikan tugas yang sama dalam 20 langkah. Selisihnya mencapai sekitar 50.000 kali lipat untuk daftar seukuran ini. Selisih semacam itu bukan keajaiban, melainkan akibat langsung dari cara kedua algoritma memangkas pekerjaannya.

Intuisi kinerja dari hasil penghitungan#

Angka 20 pada keluaran di atas muncul karena pencarian biner membelah dua ruang pencariannya di setiap langkah. Berawal dari 1.000.000 angka, ruangnya menyusut menjadi 500.000, lalu 250.000, lalu 125.000, dan seterusnya sampai tersisa satu kandidat. Diagram berikut menggambarkan penyusutan itu dari kiri ke kanan.

Perhitungan di balik angka 20 itu sederhana. Karena $2^{20} = 1048576$ sudah melebihi 1.000.000, paling banyak 20 pembelahan diperlukan sebelum ruang pencarian habis. Hubungan umumnya, jumlah langkah pencarian biner tumbuh sebanding dengan $\log_2 n$, sedangkan jumlah langkah pencarian linear tumbuh sebanding dengan $n$. Kedua hubungan ini dirangkum oleh notasi Big-O, yakni cara menuliskan laju pertumbuhan pekerjaan terhadap ukuran masukan dengan mengabaikan konstanta dan suku kecil. Dengan notasi tersebut, pencarian linear ditulis $O(n)$ dan pencarian biner ditulis $O(\log n)$.

Tabel di atas menunjukkan pola yang sama pada ukuran yang lebih besar. Menggandakan jumlah data dari 1.000.000 menjadi 2.000.000 angka menggandakan langkah pencarian linear, tetapi hanya menambah satu langkah pencarian biner. Inilah intuisi kinerja yang perlu terbawa sejak awal, yaitu pemilihan algoritma mengubah jumlah pekerjaan itu sendiri, bukan sekadar kecepatan komputer yang menjalankannya. Keuntungan sebesar ini tidak dapat ditandingi dengan mengganti mesin atau menyetel ulang konfigurasi.

Kosakata inti sepanjang jalur#

Setiap struktur data dan algoritma pada jalur ini menyumbang satu kata ke dalam kosakata penyelesaian masalah. Kosakata yang sama dipakai untuk membaca soal, memilih strategi, dan menjelaskan jawaban. Tujuh istilah berikut paling sering muncul, dan pada tahap ini cukup dikenali secara garis besar karena pemahamannya mendalam secara bertahap seiring praktik. Istilah di luar daftar tetap muncul sesekali, tetapi ketujuhnya menjadi tulang punggung pengungkapan ide.

Ketujuh istilah itu bekerja seperti kotak peralatan yang isinya saling melengkapi. Soal mencari dua angka yang jumlahnya cocok mudah diceritakan dengan array dan hash. Soal memeriksa tanda kurung seimbang terasa alami dengan stack, sedangkan penelusuran berlapis dipahami lewat rekursi. Sisanya menyusul pada soal lain, karena satu soal jarang menuntut seluruh kotak sekaligus. Dengan kosakata ini, strategi dapat disebut dengan namanya alih-alih dideskripsikan panjang lebar, sehingga proses berpikir tersusun lebih cepat.

Hubungan dengan wawancara teknis#

Banyak perusahaan teknis menyertakan sesi coding, yakni penulisan program secara langsung, dalam proses wawancaranya. Pada sesi semacam itu, kandidat diminta menyelesaikan soal pemrograman sambil menjelaskan pendekatannya, biasanya dengan menulis kode yang dapat dijalankan. Pertanyaan lanjutan yang sering muncul menyentuh kompleksitas, misalnya berapa langkah yang dikerjakan solusi pada masukan terburuk dan apakah ada cara yang lebih hemat memori. Jawaban atas pertanyaan semacam ini persis seperti penghitungan langkah pada bagian pertama topik.

Judge daring, yakni situs yang menilai kode secara otomatis, menyediakan bank soal dengan kasus uji sehingga latihan dapat dinilai tanpa menunggu orang lain. LeetCode adalah salah satu judge yang lazim dipakai untuk keperluan ini. Notasi Big-O menjadi bahasa bersama antara kandidat dan pewawancara ketika membahas trade-off, yaitu pertukaran antara dua sumber daya seperti waktu dan memori. Kedua pihak berargumen dengan angka dan notasi yang baku, bukan dengan kesan. Kemampuan berargumen semacam itulah yang dilatih sepanjang jalur ini, sedangkan hafalan solusi tidak pernah menjadi tujuannya.

Ringkasan#

• Pencarian linear memeriksa data satu per satu, sehingga jumlah langkahnya sebanding dengan ukuran data, sedangkan pencarian biner membuang separuh data di setiap langkah.
• Pada daftar 1.000.000 angka terurut, program di topik ini menghitung 1.000.000 langkah untuk pencarian linear dan 20 langkah untuk pencarian biner.
• Notasi Big-O merangkum laju pertumbuhan tersebut, misalnya $O(n)$ untuk pencarian linear dan $O(\log n)$ untuk pencarian biner.
• Istilah array, hash, stack, antrian, rekursi, dan kompleksitas menjadi kosakata bersama untuk membaca soal dan menjelaskan solusi.

Referensi#

• Big O notation — Wikipedia — Definisi notasi Big-O beserta contoh kelas pertumbuhan yang umum.
• NeetCode Roadmap — NeetCode — Peta jalan soal latihan yang dikelompokkan menurut pola dan struktur data.
• LeetCode problemset — LeetCode — Kumpulan soal pemrograman dengan kasus uji yang diperiksa otomatis.