Konsep Dasar DSA

Sebuah program komputer pada dasarnya mengambil data, mengolahnya, lalu menghasilkan keluaran. Tanpa pemilihan struktur data dan algoritma yang tepat, program yang sama bisa berjalan lambat, menghabiskan memori berlebih, atau bahkan tidak mampu menyelesaikan masalah ketika ukuran data membesar. Pada Chapter ini kita akan memahami dua konsep inti yang menjadi tulang punggung seluruh Course: struktur data sebagai cara penyimpanan, dan algoritma sebagai cara pengolahan. Kedua konsep tersebut tidak berdiri sendiri, melainkan saling melengkapi dan menentukan kualitas solusi yang kita bangun.

Apa itu Struktur Data #

Struktur data adalah cara terorganisir untuk menyimpan, mengelola, dan mengakses sekumpulan data di dalam memori komputer. Pemilihan struktur data menentukan operasi apa yang bisa dilakukan dengan cepat dan operasi apa yang menjadi mahal. Sebagai contoh, array memungkinkan akses ke elemen ke-i secara langsung, sementanta linked list mempermudah penyisipan elemen di tengah tanpa menggeser elemen lain.

Beberapa contoh struktur data yang sering kita jumpai:

Apa itu Algoritma #

Algoritma adalah urutan langkah terdefinisi yang menjelaskan bagaimana sebuah masalah dipecahkan secara komputasi. Sebuah algoritma menerima input, memproses data melalui langkah-langkah yang terbatas, dan menghasilkan output yang sesuai dengan spesifikasi masalah.

Sebuah algoritma yang baik umumnya memenuhi kriteria berikut:

• Tepat (correct): menghasilkan output yang benar untuk seluruh input yang valid.
• Terbatas (finite): berhenti setelah sejumlah langkah yang dapat dihitung.
• Tentu (deterministic): untuk input yang sama, langkah yang ditempuh dapat diprediksi.
• Efisien (efficient): menggunakan waktu dan memori yang wajar terhadap ukuran input.

Dua algoritma yang menghasilkan output sama bisa memiliki perbedaan dramatis pada kecepatan dan pemakaian memori. Perbedaan inilah yang menjadi fokus utama saat kita memilih algoritma untuk masalah nyata.

Hubungan Struktur Data dan Algoritma #

Struktur data dan algoritma saling membentuk satu sama lain. Struktur data yang dipilih menentukan operasi yang efisien, dan algoritma yang dirancang biasanya mengasumsikan struktur data tertentu. Sebagai contoh, algoritma binary search hanya bekerja pada data terurut yang mendukung akses acak seperti std::vector atau std::array. Pada linked list, algoritma yang sama menjadi tidak efisien karena tidak ada akses langsung ke indeks.

Pada diagram di atas, panah putus-putus menunjukkan bahwa pilihan struktur data membatasi algoritma yang bisa dipakai, sementara pilihan algoritma sering kali menuntut struktur data tertentu. Dalam praktik, kita memilih pasangan keduanya secara bersamaan.

Contoh Konkret: Menjumlahkan Elemen 1 sampai N #

Sekarang kita akan melihat bagaimana dua algoritma berbeda dapat menyelesaikan masalah yang sama dengan hasil identik tetapi karakteristik berbeda. Masalahnya sederhana: jumlahkan seluruh bilangan bulat dari 1 sampai n. Kita akan membandingkan pendekatan linier yang menjumlahkan satu per satu dengan pendekatan berbasis rumus matematis Gauss.

Mekanisme Kedua Pendekatan #

Pendekatan linier membentuk kumpulan data 1, 2, 3, ..., n, lalu menjelajah seluruh elemen sambil menambahkannya ke akumulator. Banyaknya operasi penjumlahan tumbuh seiring nilai n. Pendekatan rumus memanfaatkan identitas deret aritmetika 1 + 2 + ... + n = n*(n+1)/2, yang hanya membutuhkan satu operasi perkalian, satu penambahan, dan satu pembagian, terlepas dari nilai n.

Kode Program #

#include <iostream>
#include <vector>

// Pendekatan 1: penjumlahan langsung satu per satu
int jumlahLinear(const std::vector<int>& data) {
    int total = 0;
    for (int nilai : data) {
        total += nilai;
    }
    return total;
}

// Pendekatan 2: penjumlahan dengan rumus deret aritmetika
// Hanya berlaku bila data berisi bilangan bulat 1..n secara berurutan
int jumlahRumus(int n) {
    return n * (n + 1) / 2;
}

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int hasilLinear = jumlahLinear(data);
    int hasilRumus  = jumlahRumus(10);

    std::cout << "Hasil penjumlahan linear : " << hasilLinear << "\n";
    std::cout << "Hasil penjumlahan rumus  : " << hasilRumus  << "\n";
    std::cout << "Kedua hasil sama?         : "
              << (hasilLinear == hasilRumus ? "ya" : "tidak") << "\n";

    return 0;
}

Output yang Dihasilkan:

Hasil penjumlahan linear : 55
Hasil penjumlahan rumus  : 55
Kedua hasil sama?         : ya

Bedah Kode Baris-per-Baris #

Mari kita telaah bagian-bagian penting dari program di atas:

1. Baris 1 (#include <iostream>): menyediakan objek std::cout untuk menulis keluaran ke terminal.
2. Baris 2 (#include <vector>): menyertakan definisi std::vector, struktur data array dinamis yang dipakai sebagai kontainer data.
3. Baris 5 (int jumlahLinear(const std::vector<int>& data)): mendeklarasikan fungsi yang menerima reference ke std::vector agar tidak terjadi penyalinan elemen. Kata kunci const menjamin isi data tidak diubah.
4. Baris 7 (for (int nilai : data)): range-based for loop yang menjelajah tiap elemen data dari awal sampai akhir.
5. Baris 13 (int jumlahRumus(int n)): menerima nilai n saja, tanpa perlu menyimpan elemen individual. Inilah inti perbedaan struktur data: pendekatan rumus tidak menyimpan array sama sekali.
6. Baris 14 (return n * (n + 1) / 2;): menerapkan rumus deret Gauss. Banyaknya operasi konstan, tidak bergantung pada n.
7. Baris 21 (std::vector<int> data = {...}): membuat std::vector berisi sepuluh elemen pada stack frame main.
8. Baris 26 ((hasilLinear == hasilRumus ? "ya" : "tidak")): operator ternary yang membandingkan kedua hasil lalu mengembalikan string yang sesuai.

Perbedaan Karakteristik Kedua Algoritma #

Walaupun output kedua fungsi identik, karakteristik keduanya sangat berbeda. Tabel berikut merangkum perbedaan utama yang akan kita pelajari lebih dalam pada Section analisis-kompleksitas.

Perhatikan baris terakhir tabel: algoritma yang lebih cepat sering kali memiliki batasan input yang lebih ketat. Pemilihan algoritma selalu merupakan hasil pertukaran antara kecepatan, memori, dan fleksibilitas input. Inilah yang membuat pemahaman mendalam terhadap DSA menjadi keterampilan penting bagi setiap pengembang perangkat lunak.

Ringkasan #

Pada Chapter ini kita telah membangun pemahaman dasar tentang dua konsep inti Course:

• Struktur data adalah cara penyimpanan data yang menentukan operasi yang efisien.
• Algoritma adalah urutan langkah terbatas untuk menyelesaikan masalah komputasi.
• Keduanya saling melengkapi: pilihan struktur data membatasi algoritma yang bisa dipakai, demikian pula sebaliknya.
• Dua algoritma yang menghasilkan output sama dapat memiliki perbedaan dramatis pada kecepatan dan penggunaan memori.

Pada Chapter berikutnya kita akan melihat lebih jauh bagaimana pemilihan struktur data dan algoritma memengaruhi kualitas solusi perangkat lunak secara nyata.