Logaritma dan Eksponen

Logaritma dan eksponen adalah dua operasi matematis yang sering muncul di analisis algoritma — binary search O(log n), merge sort O(n log n), pangkat cepat O(log k). Sayangnya, banyak pemula tidak menguasai sifat-sifat dasar logaritma, sehingga gagal menurunkan kompleksitas algoritma sendiri. Pada Chapter ini kita akan meninjau properti kunci logaritma dan eksponen, lalu menerapkannya untuk menjawab dua pertanyaan: mengapa binary search O(log n)? dan mengapa fast exponentiation O(log k)?

Properti Dasar Logaritma #

Aturan #

Untuk basis b > 0, b ≠ 1 dan argumen positif:

text
log_b(x · y) = log_b(x) + log_b(y)        (1) perkalian menjadi penjumlahan
log_b(x / y) = log_b(x) - log_b(y)        (2) pembagian menjadi pengurangan
log_b(x^y)   = y · log_b(x)                (3) pangkat menjadi perkalian
log_b(x)     = log_c(x) / log_c(b)         (4) perubahan basis
b^(log_b(x)) = x                            (5) invers: eksponen membatalkan log

Mekanisme: Mengapa Log Muncul di Algoritma #

Log muncul setiap kali kita membagi masalah menjadi dua bagian setara secara berulang. Jumlah pembagian yang diperlukan untuk mengecilkan n ke 1 adalah log₂(n).

Mengapa Binary Search O(log n)? #

Aturan #

Binary search membagi rentang pencarian menjadi dua di setiap iterasi. Setelah k iterasi, ukuran rentang menjadi n / 2^k. Pencarian berhenti saat n / 2^k = 1, yaitu 2^k = n, sehingga k = log₂(n).

Kode: Iterasi Binary Search #

cpp
#include <iostream>
#include <vector>

int binary_search_steps(int n) {
    // Simulasi binary search pada array [0..n-1], cari elemen terakhir
    int lo = 0, hi = n - 1;
    int steps = 0;
    while (lo <= hi) {
        ++steps;
        int mid = lo + (hi - lo) / 2;
        if (mid == n - 1) return steps;
        else if (mid < n - 1) lo = mid + 1;
        else hi = mid - 1;
    }
    return steps;
}

int main() {
    std::vector<int> sizes = {16, 1024, 1'048'576, 1'073'741'824};
    for (int n : sizes) {
        std::cout << "n=" << n << ", cari elemen terakhir:\n";
        std::cout << "  steps=" << binary_search_steps(n) << '\n';
        std::cout << "  log2(n) = " << (n > 0 ? 63 - __builtin_clzll((unsigned long long)n) : 0) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
n=16, cari elemen terakhir:
  steps=5
  log2(n) = 4
n=1024, cari elemen terakhir:
  steps=11
  log2(n) = 10
n=1048576, cari elemen terakhir:
  steps=21
  log2(n) = 20
n=1073741824, cari elemen terakhir:
  steps=31
  log2(n) = 30

Baris int mid = lo + (hi - lo) / 2;: hitung titik tengah tanpa overflow lo + hi.
Baris ++steps;: lacak jumlah iterasi. Untuk n elemen, jumlah iterasi mendekati log₂(n).
Baris 63 - __builtin_clzll((unsigned long long)n: trik GCC untuk hitung log₂(n) dengan instruksi CPU CLZ (count leading zeros).
Hasil n=1024 → steps=11: log₂(1024) = 10. Selisih 1 berasal dari iterasi awal dan batas lo <= hi. Konfirmasi: binary search melakukan sekitar log₂(n) iterasi.
Hasil n=1073741824 → steps=31: untuk milyaran elemen, hanya 31 iterasi. Inilah kekuatan log.

Properti Eksponen #

Aturan #

text
b^x · b^y = b^(x+y)                          (1) perkalian eksponen sebasis
b^x / b^y = b^(x-y)                          (2) pembagian eksponen sebasis
(b^x)^y   = b^(x·y)                          (3) eksponen berkalang
(b·c)^x   = b^x · c^x                        (4) distribusi ke perkalian
b^0       = 1                                 (5) basis apa pun pangkat 0 = 1
b^(-x)    = 1 / b^x                          (6) pangkat negatif = invers

Fast Exponentiation: Mengapa O(log k)? #

Aturan #

Hitung b^k mod m secara efisien. Naif: O(k) perkalian. Fast exponentiation (binary exponentiation): O(log k).

Mekanisme: Pecah k dalam Biner #

Kita ekspresikan k dalam biner: k = k_{t-1} · 2^(t-1) + ... + k_1 · 2 + k_0. Maka:

text

b^k = b^(k_{t-1}·2^(t-1)) · b^(k_{t-2}·2^(t-2)) · ... · b^k_0
     = (b^(2^(t-1)))^k_{t-1} · ... · b^k_0

Iterasi bit-by-bit: kuadratkan basis di setiap langkah (b → b² → b⁴ → b⁸ → ...), kalikan ke hasil hanya bila bit ke-i dari k menyala. Setiap langkah O(log m) untuk mod. Total O(log k · log m).

Kode: Fast Exponentiation (Iteratif) #

cpp
#include <iostream>

long long fast_pow(long long b, long long k, long long m) {
    long long result = 1;
    b %= m;
    while (k > 0) {
        if (k & 1) result = (result * b) % m;
        b = (b * b) % m;
        k >>= 1;
    }
    return result;
}

int main() {
    long long b = 2, m = 1'000'000'007;
    for (long long k : {0LL, 1LL, 10LL, 100LL, 1'000'000'000'000LL}) {
        std::cout << b << "^" << k << " mod " << m << " = "
                  << fast_pow(b, k, m) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
2^0 mod 1000000007 = 1
2^1 mod 1000000007 = 2
2^10 mod 1000000007 = 1024
2^100 mod 1000000007 = 976371285
2^1000000000000 mod 1000000007 = 959366170

Baris b %= m;: normalkan basis ke [0, m-1] di awal. Mencegah overflow saat b awal besar.
Baris if (k & 1) result = (result * b) % m;: bila bit terakhir k menyala, kalikan basis saat ini ke hasil.
Baris b = (b * b) % m;: kuadratkan basis. Sekuens: b → b² → b⁴ → b⁸ → ....
Baris k >>= 1;: geser k ke kanan — proses bit berikutnya.
Hasil 2^10 = 1024: 2^10 = 1024, tidak butuh mod.
Hasil 2^1000000000000 mod 1e9+7: hitung dalam ~40 iterasi (log₂(10^12) ≈ 40). Naif O(10^12) tidak mungkin.

Aplikasi: Hitung Geometri Modulo #

Aturan #

Hitung deret geometri 1 + r + r² + ... + r^(n-1) = (r^n - 1) / (r - 1) modulo m. Karena pembagian modulo tidak trivial (perlu modular inverse — lihat Chapter Modular Inverse ), pendekatan: ekspresikan sebagai r^n - 1 lalu kalikan dengan inverse r - 1.

Kode: Geometric Series Modulo #

cpp
#include <iostream>

long long fast_pow(long long b, long long k, long long m) {
    long long result = 1;
    b %= m;
    while (k > 0) {
        if (k & 1) result = (result * b) % m;
        b = (b * b) % m;
        k >>= 1;
    }
    return result;
}

long long mod_inverse(long long a, long long m) {
    // Fermat's little theorem: a^(-1) = a^(m-2) mod m (m prime)
    return fast_pow(a, m - 2, m);
}

long long geom_sum(long long r, long long n, long long m) {
    if (r == 1) return n % m;
    long long num = (fast_pow(r, n, m) - 1 + m) % m;
    long long den_inv = mod_inverse((r - 1 + m) % m, m);
    return (num * den_inv) % m;
}

int main() {
    long long m = 1'000'000'007;
    for (auto [r, n] : {std::pair<long long,long long>{2, 10}, {3, 5}, {10, 7}}) {
        std::cout << "1 + " << r << " + ... + " << r << "^" << (n-1)
                  << " mod " << m << " = " << geom_sum(r, n, m) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
+ 2 + ... + 2^9 mod 1000000007 = 1023
+ 3 + ... + 3^4 mod 1000000007 = 121
+ 10 + ... + 10^6 mod 1000000007 = 1111111

Baris if (r == 1) return n % m;: kasus khusus — bila r = 1, deret = n. Hindari pembagian dengan r - 1 = 0.
Baris long long num = (fast_pow(r, n, m) - 1 + m) % m;: hitung (r^n - 1) mod m. Tambah m sebelum mod agar hasil non-negatif.
Baris long long den_inv = mod_inverse((r - 1 + m) % m, m);: invers dari r - 1 modulo m. Memakai Fermat’s little theorem.
Baris return (num * den_inv) % m;: pembagian modulo = perkalian dengan invers.
Hasil 1 + 2 + ... + 2^9 = 1023: jumlah deret geometri 2^10 - 1 = 1023. Sesuai.
Hasil 1 + 10 + ... + 10^6 = 1111111: jumlah = (10^7 - 1)/9 = 1111111. Sesuai.

Ringkasan #

Properti log: log(xy) = log x + log y, log(x^y) = y · log x, perubahan basis adalah konstanta.
Binary search O(log n) karena di setiap iterasi rentang dibagi 2 — butuh log₂ n iterasi.
Properti eksponen: b^x · b^y = b^(x+y), (b^x)^y = b^(xy).
Fast exponentiation O(log k) memanfaatkan representasi biner k — kuadratkan basis setiap langkah, kalikan ke hasil bila bit k menyala.
Aplikasi: deret geometri modulo via fast pow + modular inverse.