Kompleksitas Matematis

Kompleksitas asimptotik (Big-O, Big-Ω, Big-Θ) sering dipakai untuk membandingkan algoritma, tetapi definisi formalnya jarang diajarkan. Tanpa fondasi matematis, kita sulit membuktikan bahwa O(n log n) benar-benar lebih cepat dari O(n^1.0001) untuk n besar. Pada Chapter ini kita akan menurunkan Big-O dari konsep limit, melihat bagaimana L’Hôpital memberi intuisi, dan memperlakukan Big-O sebagai himpunan fungsi dengan operasi aljabar. Pemahaman formal ini berguna saat membuktikan kompleksitas algoritma rekursif via Master Theorem atau Akra-Bazzi.

Definisi Formal Big-O #

Aturan #

Diberikan dua fungsi f(n) dan g(n), kita menyatakan f(n) = O(g(n)) jika dan hanya jika ada konstanta positif c dan n_0 sehingga untuk semua n ≥ n_0:

|f(n)| ≤ c · g(n)

Ekivalen dalam limit:

f(n) = O(g(n))  ⟺  lim (n→∞) |f(n)| / g(n)  <  ∞

Bila limit berhingga (termasuk 0), maka f = O(g). Bila limit = 0, kita tulis f = o(g) (little-o, pertumbuhan lebih lambat).

Mekanisme: Limit sebagai Banding #

Limit f(n)/g(n) mengukur rasio pertumbuhan. Bila rasio → 0, f jauh lebih lambat dari g. Bila rasio → ∞, f jauh lebih cepat dari g. Bila rasio → konstanta, keduanya tumbuh pada laju yang sebanding.

L’Hôpital sebagai Intuisi #

Aturan #

Bentuk tak tentu 0/0 atau ∞/∞ dapat diselesaikan dengan L’Hôpital: limit f/g = limit f'/g' (turunan), bila turunan keduanya ada dan limit turunan ada.

Contoh: log n vs n #

lim (n→∞) log n / n   =  lim (n→∞) (1/n) / 1   =  lim (n→∞) 1/n   =  0

Turunan log n adalah 1/n (untuk log natural). Turunan n adalah 1. Setelah L’Hôpital, limit = 0, sehingga log n = o(n) — log tumbuh jauh lebih lambat dari n.

Contoh: n² vs n³ #

lim (n→∞) n² / n³  =  lim (n→∞) 1/n  =  0

Tidak perlu L’Hôpital. n² = o(n³). Konsisten dengan intuisi kita.

Big-O sebagai Himpunan Fungsi #

Aturan #

O(g) adalah himpunan:

O(g) = { f : ∃ c > 0, n_0 > 0, ∀n ≥ n_0, |f(n)| ≤ c·g(n) }

Operasi himpunan:

Mekanisme: Loop Bersarang #

Loop bersarang memberi perkalian kompleksitas. Loop berurutan memberi penjumlahan (diambil maksimum).

for (int i = 0; i < n; ++i)       // O(n)
    for (int j = 0; j < n; ++j)   // O(n)
        /* konstan */;            // O(1) per iterasi
// total: O(n · n · 1) = O(n²)

for (int i = 0; i < n; ++i)       // O(n)
    /* A */;
for (int i = 0; i < n; ++i)       // O(n)
    /* B */;
// total: O(n) + O(n) = O(n) (penjumlahan, ambil maksimum)

Hierarki Pertumbuhan #

Tabel Laju Pertumbuhan (urutan naik) #

Kode: Perbandingan Numerik #

#include <iostream>
#include <cmath>

double ops_constant(int n)    { return 1.0; }
double ops_log(int n)         { return std::log2(n); }
double ops_linear(int n)      { return n; }
double ops_nlogn(int n)       { return n * std::log2(n); }
double ops_quadratic(int n)   { return 1.0 * n * n; }
double ops_exponential(int n) { return std::pow(2.0, n); }

int main() {
    int sizes[] = {10, 100, 1000, 10000};
    std::cout << "n\tO(1)\tO(log n)\tO(n)\tO(n log n)\tO(n^2)\n";
    for (int n : sizes) {
        std::cout << n << '\t'
                  << ops_constant(n) << '\t'
                  << ops_log(n) << '\t'
                  << ops_linear(n) << '\t'
                  << ops_nlogn(n) << '\t'
                  << ops_quadratic(n) << '\n';
    }
    std::cout << "\nUntuk 2^n (eksponensial):\n";
    for (int n : {10, 20, 30, 40}) {
        std::cout << "2^" << n << " = " << ops_exponential(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

n	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)
10	1	3.32193	10	33.2193	100
100	1	6.64386	100	664.386	10000
1000	1	9.96578	1000	9965.78	1e+06
10000	1	13.2877	10000	132877	1e+08

Untuk 2^n (eksponensial):
2^10 = 1024
2^20 = 1.04858e+06
2^30 = 1.07374e+09
2^40 = 1.09951e+12

1. Baris double ops_constant(int n) { return 1.0; }: O(1) — konstan, tidak bergantung n.
2. Baris double ops_log(int n) { return std::log2(n); }: O(log n) — pertumbuhan sangat lambat. Untuk n = 10000, hanya 13.
3. Baris double ops_nlogn(int n) { return n * std::log2(n); }: O(n log n) — pertumbuhan “hampir linier”. Untuk n = 10000, ~133 ribu.
4. Baris double ops_quadratic(int n) { return 1.0 * n * n; }: O(n²) — untuk n = 10000, 100 juta. Mendekati batas 1 detik.
5. Baris std::pow(2.0, n): O(2^n) — eksponensial. Untuk n = 40, sudah 10^12 — jelas TLE.

Big-Ω dan Big-Θ #

Aturan #

• f = Ω(g): f tumbuh tidak lebih lambat dari g. Formal: lim f/g > 0 (boleh ∞).
• f = Θ(g): f = O(g) dan f = Ω(g) — tumbuh pada laju yang sama.
• f = o(g): f = O(g) tetapi bukan Ω(g) — tumbuh lebih lambat.

Contoh #

• 3n + 5 = Θ(n): limit 3n+5 / n = 3 (konstanta), sehingga O(n) dan Ω(n) keduanya benar.
• log n = o(n): limit = 0, sehingga O(n) tetapi bukan Ω(n).
• n² = Ω(n log n): limit n² / (n log n) = n/log n → ∞, sehingga Ω tetapi bukan O.

Ringkasan #

• Big-O formal: f = O(g) ⟺ ∃ c, n_0 > 0, ∀n ≥ n_0, |f(n)| ≤ c·g(n). Ekivalen dengan lim f/g < ∞.
• L’Hôpital membantu menentukan limit bentuk 0/0 atau ∞/∞ — misal membuktikan log n = o(n).
• O(g) adalah himpunan fungsi. Tanda = adalah kependekan dari ∈.
• Hierarki pertumbuhan: 1 < log log n < log n < sqrt(n) < n < n log n < n² < n³ < 2^n < n!.
• f = Θ(g) iff f = O(g) dan f = Ω(g) — tumbuh pada laju yang sama (rasio → konstanta).