Analisis Algoritma

Sebuah algoritma dapat diimplementasikan dalam banyak cara, tetapi tidak semua implementasi sama efisiennya. Analisis algoritma memberi kita kerangka untuk memprediksi bagaimana waktu eksekusi dan penggunaan memori bertumbuh ketika ukuran masukan bertambah. Tanpa analisis ini, kita hanya bisa menebak apakah kode akan tetap cepat saat data naik dari ratusan menjadi jutaan elemen. Pada chapter ini kita akan belajar cara menghitung operasi dasar yang dilakukan sebuah fungsi, lalu mengamati bagaimana jumlah operasi tersebut bertumbuh seiring ukuran input. Analisis ini menjadi dasar sebelum kita masuk ke notasi Big O pada chapter berikutnya.

Mengapa Analisis Algoritma Penting #

Ketika kita menulis sebuah fungsi jumlah_array() yang menjumlahkan seluruh elemen array, intuitif kita mengatakan: “bila array berukuran 100, fungsi melakukan 100 penjumlahan”. Hal itu benar untuk kasus sederhana, tetapi pada algoritma yang lebih kompleks (sorting, searching, struktur data rekursif) kita perlu membedah operasi yang dilakukan baris per baris. Analisis algoritma memberi kita tiga pertanyaan kunci:

• Berapa banyak operasi dasar yang dilakukan sebagai fungsi dari n (ukuran input)?
• Berapa banyak memori tambahan yang dialokasikan?
• Bagaimana pertumbuhan tersebut bila n membesar?

Kita akan mulai dengan menghitung operasi dasar dari sebuah loop sederhana, lalu melihat pertumbuhan waktu eksekusi pada algoritma ber-nested loop.

Menghitung Operasi Dasar #

Kita akan menulis dua versi fungsi penjumlahan array. Versi pertama hanya menghitung hasil; versi kedua mencatat berapa kali operasi penjumlahan dan perbandingan dilakukan.

#include <stdio.h>

/* Versi sederhana: jumlahkan semua elemen array */
long long jumlah_v1(const int *a, int n) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += a[i];
    }
    return total;
}

/* Versi yang menghitung jumlah operasi dasar */
long long jumlah_v2(const int *a, int n,
                    long long *jumlah_penjumlahan,
                    long long *jumlah_perbandingan) {
    long long total = 0;
    *jumlah_penjumlahan = 0;
    *jumlah_perbandingan = 0;
    for (int i = 0; i < n; i++) {
        (*jumlah_perbandingan)++;      /* i < n */
        total += a[i];
        (*jumlah_penjumlahan)++;       /* total += a[i] */
    }
    (*jumlah_perbandingan)++;          /* tes akhir i==n yang false */
    return total;
}

int main(void) {
    int a[] = {10, 20, 30, 40, 50};
    int n = sizeof(a) / sizeof(a[0]);

    long long hasil1 = jumlah_v1(a, n);
    printf("jumlah_v1 = %lld\n", hasil1);

    long long jp, jb;
    long long hasil2 = jumlah_v2(a, n, &jp, &jb);
    printf("jumlah_v2 = %lld (penjumlahan: %lld, perbandingan: %lld)\n",
           hasil2, jp, jb);
    printf("n = %d, total operasi dasar = %lld\n", n, jp + jb);

    printf("\nUkuran n -> total operasi dasar:\n");
    for (int uk = 1; uk <= 5; uk++) {
        long long dummy_p, dummy_b;
        jumlah_v2(a, uk, &dummy_p, &dummy_b);
        printf("  n=%d -> %lld\n", uk, dummy_p + dummy_b);
    }
    return 0;
}

Output yang Dihasilkan:

jumlah_v1 = 150
jumlah_v2 = 150 (penjumlahan: 5, perbandingan: 6)
n = 5, total operasi dasar = 11

Ukuran n -> total operasi dasar:
  n=1 -> 3
  n=2 -> 5
  n=3 -> 7
  n=4 -> 9
  n=5 -> 11

Hasil di atas menunjukkan pola linear: setiap kali n bertambah 1, total operasi bertambah 2. Rumusnya adalah 2n + 1. Konstanta 2 dan 1 tidak mengubah bentuk pertumbuhan—yang penting adalah pertumbuhan linear terhadap n.

Mari kita telaah baris-baris kode di atas:

1. Baris 4-9 (jumlah_v1): implementasi ringkas yang fokus pada hasil. Loop for dari i=0 sampai i<n, tiap iterasi menambahkan a[i] ke total.
2. Baris 12-26 (jumlah_v2): sama logikanya dengan jumlah_v1, tetapi setiap operasi dasar dicatat ke counter. Parameter keluaran jumlah_penjumlahan dan jumlah_perbandingan adalah output parameter berbentuk pointer ke long long.
3. Baris 16 ((*jumlah_perbandingan)++): di dalam loop, satu operasi perbandingan i < n dicatat per iterasi yang berhasil.
4. Baris 18 ((*jumlah_penjumlahan)++): penjumlahan total += a[i] dicatat per iterasi.
5. Baris 20 ((*jumlah_perbandingan)++): di luar loop, satu perbandingan akhir yang menghasilkan false dan menyebabkan loop berhenti.
6. Baris 39-43 (for (int uk = 1; uk <= 5; uk++)): pemanggilan jumlah_v2 dengan n berbeda untuk memetakan pertumbuhan operasi.

Mengukur Waktu Eksekusi Nyata #

Selain menghitung operasi, kita dapat mengukur waktu eksekusi secara empiris dengan clock() dari <time.h>. Bila algoritma memiliki kompleksitas kuadratik (nested loop), waktu tumbuh jauh lebih cepat dibanding linear.

#include <stdio.h>
#include <time.h>

/* Fungsi O(n^2): jumlah semua pasangan */
long long jumlah_pasangan(int n) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += 1;
        }
    }
    return total;
}

int main(void) {
    int ukuran[] = {10, 50, 100, 200, 400};
    int k = sizeof(ukuran) / sizeof(ukuran[0]);

    printf("n      operasi      waktu (detik)\n");
    for (int i = 0; i < k; i++) {
        int n = ukuran[i];
        clock_t mulai = clock();
        long long op = jumlah_pasangan(n);
        clock_t akhir = clock();
        double detik = (double)(akhir - mulai) / CLOCKS_PER_SEC;
        printf("%-7d%-13lld%.6f\n", n, op, detik);
    }
    return 0;
}

Output yang Dihasilkan:

n      operasi      waktu (detik)
10     100          0.000001
50     2500         0.000006
100    10000        0.000022
200    40000        0.000088
400    160000       0.000362

Ketika n berlipat dari 200 ke 400 (dua kali lipat), jumlah operasi naik dari 40.000 ke 160.000—yaitu empat kali lipat. Ini adalah ciri khas kompleksitas kuadratik O(n^2): penggandaan n mengkuadratkan operasi. Untuk n kecil perbedaan ini tampak sepele, tetapi pada n = 10.000 algoritma yang sama akan melakukan 100 juta operasi dan mulai terasa lambat.

Analisis Kompleksitas Ruang #

Selain waktu, kita juga harus memperhatikan space complexity—berapa memori tambahan yang dialokasikan algoritma relatif terhadap n. Tabel berikut merangkum perbedaan yang umum dijumpai:

Algoritma dengan ruang O(1) hanya memakai beberapa variabel skalar terlepas dari n. Algoritma rekursif yang dalam memakai call stack hingga kedalaman n menyebabkan space complexity menjadi O(n) walaupun tidak ada malloc eksplisit. Inilah mengapa iteratif biasanya lebih hemat memori dibanding rekursif untuk masalah yang sederhana.

Ringkasan Pertumbuhan #

Dari dua contoh di atas kita melihat dua pola pertumbuhan berbeda. Pada jumlah_v2, pertumbuhan operasi adalah 2n + 1—linear terhadap n. Pada jumlah_pasangan, pertumbuhannya n^2—kuadratik. Pada chapter berikutnya kita akan memformalkan pengamatan ini ke dalam notasi Big O, yang memberi kita cara standar untuk menulis kompleksitas tanpa peduli konstanta.