Pendekatan Analisis Algoritma

Mengetahui bahwa sebuah algoritma “berjalan cepat” belum cukup untuk memutuskan apakah algoritma tersebut layak dipakai. Pertanyaan yang lebih tajam adalah: cepat dalam kondisi seperti apa? Pada kasus terbaik? Kasus terburuk? Rata-rata? Setelah sekumpulan operasi? Empat pendekatan analisis — worst case, best case, average case, dan amortized — memberi sudut pandang berbeda untuk menjawab pertanyaan ini. Pada Chapter ini kita akan membandingkan keempat pendekatan tersebut, melihat kapan masing-masing relevan, dan menentukan pendekatan mana yang tepat untuk situasi tertentu.

Empat Pendekatan Analisis #

Worst Case Analysis #

Worst case memberi jaminan batas atas: algoritma tidak akan pernah lebih lambat dari T_worst(n) pada input berukuran n. Inilah mengapa sebagian besar literatur DSA menyatakan kompleksitas dalam worst case.

Karakteristik Worst Case #

• Memberi garansi kinerja paling tidak.
• Tidak memerlukan asumsi distribusi input.
• Mudah dihitung untuk sebagian besar algoritma.
• Cenderung pesimistik: pada praktik, rata-rata operasi sering jauh lebih kecil.

Contoh: Quick Sort #

Quick sort memiliki worst case O(n²) (terjadi saat pivot selalu elemen terkecil/terbesar), tetapi average case O(n log n). Bila kita hanya melihat worst case, kita akan menyimpulkan quick sort lebih buruk dari merge sort — padahal di praktik, quick sort biasanya lebih cepat karena konstanta kecil.

Best Case Analysis #

Best case memberi gambaran kinerja maksimum yang bisa dicapai algoritma, biasanya pada input yang ideal.

Karakteristik Best Case #

• Memberi batas bawah kinerja algoritma.
• Jarang dipakai sebagai satu-satunya metrik karena jarang representatif.
• Berguna untuk verifikasi: bila best case masih lambat, algoritma jelas tidak layak.
• Sering menjadi lower bound masalah.

Contoh: Insertion Sort #

Insertion sort pada array sudah terurut hanya memerlukan n - 1 pembandingan (Θ(n) best case). Best case ini membuat insertion sort sangat efisien untuk data hampir terurut — karakteristik yang dimanfaatkan banyak library std::sort sebagai fallback untuk sub-array kecil.

Average Case Analysis #

Average case mengasumsikan distribusi probabilistik tertentu pada input (biasanya distribusi seragam acak), lalu menghitung ekspektasi jumlah operasi.

Karakteristik Average Case #

• Memberi prediksi paling realistis untuk input acak.
• Memerlukan asumsi distribusi yang mungkin tidak cocok untuk data realistis.
• Lebih sulit dihitung dibanding worst case.
• Berguna saat input diasumsikan acak (misal data ujian).

Contoh: Quick Sort Average Case #

Asumsikan pivot dipilih secara acak seragam. Ekspektasi jumlah pembandingan pada quick sort adalah 2n ln n ≈ 1,39 n log₂ n. Inilah yang membuat quick sort average case O(n log n) dengan konstanta ~1,39 — sedikit lebih baik dari merge sort (konstanta ~1,00 untuk operasi, tetapi dengan biaya salin yang lebih besar).

Amortized Analysis #

Amortized analysis menghitung rata-rata biaya per operasi pada urutan n operasi. Berbeda dari average case, amortisasi tidak mengasumsikan distribusi probabilistik — jaminannya berlaku untuk setiap urutan operasi yang valid.

Karakteristik Amortized #

• Memberi rata-rata yang terjamin, bukan ekspektasi probabilistik.
• Cocok untuk struktur data dengan operasi yang kadang mahal (push_back, hash table rehash).
• Tidak menghapus worst case per operasi.
• Tiga metode: aggregate, accounting, potential (lihat Chapter Kompleksitas Amortisasi).

Contoh: Dynamic Array push_back #

std::vector::push_back memiliki worst case O(n) (saat realokasi), tetapi amortized O(1). Bila kita memilih berdasarkan worst case saja, kita akan menghindari push_back — padahal rata-rata biayanya sangat murah.

Kode: Membandingkan Empat Pendekatan pada Insertion Sort #

Mekanisme Empat Kasus #

Kita akan mengukur jumlah pembandingan insertion sort pada empat tipe input: (1) array acak (average case), (2) array sudah terurut (best case), (3) array terurut terbalik (worst case), (4) urutan operasi amortized pada struktur lain.

Kode Program #

#include <iostream>
#include <vector>
#include <random>

long long cmp = 0;

void insertionSort(std::vector<int>& v) {
    cmp = 0;
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0) {
            ++cmp;
            if (v[j] > key) { v[j + 1] = v[j]; --j; }
            else break;
        }
        v[j + 1] = key;
    }
}

std::vector<int> buatAcak(int n) {
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(1, 1000000);
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = dist(rng);
    return v;
}

std::vector<int> buatTerurut(int n) {
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i + 1;
    return v;
}

std::vector<int> buatTerbalik(int n) {
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = n - i;
    return v;
}

int main() {
    int n = 1000;
    long long teoritisWorst = 1LL * n * (n - 1) / 2;   // n(n-1)/2
    long long teoritisBest  = n - 1;                   // n-1

    auto acak = buatAcak(n);
    auto terurut = buatTerurut(n);
    auto terbalik = buatTerbalik(n);

    insertionSort(terurut);
    std::cout << "Best case (terurut)    : " << cmp
              << " (teoritis " << teoritisBest << ")\n";

    insertionSort(terbalik);
    std::cout << "Worst case (terbalik)  : " << cmp
              << " (teoritis " << teoritisWorst << ")\n";

    insertionSort(acak);
    std::cout << "Average case (acak)    : " << cmp
              << " (estimasi n^2/4 = " << 1LL * n * n / 4 << ")\n";
    return 0;
}

Output yang Dihasilkan:

Best case (terurut)    : 999 (teoritis 999)
Worst case (terbalik)  : 499500 (teoritis 499500)
Average case (acak)    : 244208 (estimasi n^2/4 = 250000)

Bedah Kode Baris-per-Baris #

1. Fungsi buatAcak: menghasilkan array acak dengan std::mt19937 (PRNG Mersenne Twister). Seed tetap (42) memastikan reproducibility.
2. Fungsi buatTerurut dan buatTerbalik: menghasilkan array terurut naik dan turun untuk kasus best dan worst.
3. Baris teoritisWorst = n(n-1)/2: rumus jumlah pembandingan pada worst case insertion sort: 1 + 2 + ... + (n-1) = n(n-1)/2.
4. Baris teoritisBest = n-1: pada best case, setiap elemen hanya memerlukan satu pembandingan (untuk menyimpulkan v[j] <= key).
5. Output: best case 999 pembandingan tepat sesuai rumus; worst case 499.500 sesuai rumus; average case 244.208 mendekati estimasi n²/4 = 250.000. Estimasi n²/4 berasal dari ekspektasi: rata-rata elemen baru perlu dibandingkan dengan i/2 elemen sebelumnya.
6. Implikasi: pemilihan pendekatan analisis sangat memengaruhi kesimpulan. Insertion sort tampak buruk dari worst case (O(n²)), tetapi menarik dari best case (O(n)), dan realistis dari average case.

Memilih Pendekatan yang Tepat #

Hubungan dengan Notasi #

Empat pendekatan analisis ini dapat dipadukan dengan tiga notasi asimptotik:

Ringkasan #

• Empat pendekatan analisis: worst case (jaminan atas), best case (batas bawah), average case (ekspektasi probabilistik), amortized (rata-rata urutan operasi).
• Worst case paling sering dipakai karena memberi jaminan paling kuat tanpa asumsi distribusi.
• Average case realistis untuk input acak tetapi memerlukan asumsi distribusi.
• Best case bermanfaat untuk verifikasi kasus ideal.
• Amortized cocok untuk struktur data dengan operasi kadang mahal (dynamic array, hash table).

Pada Chapter berikutnya kita akan mempelajari loop invariant — teknik formal untuk membuktikan kebenaran algoritma iteratif.