📖 1. Mengapa Analisis Algoritma Penting?

🎖️ Contoh: Database Personel Militer

Dua algoritma untuk mencari data dari 1 juta personel:

Faktor yang Mempengaruhi Waktu Eksekusi

1. Kecepatan hardware (CPU, RAM, storage)
2. Bahasa pemrograman dan compiler
3. Kualitas implementasi (coding style)
4. Ukuran input (n)
5. Algoritma yang digunakan ← Fokus analisis!

Empiris vs Teoritis

📖 2. Menghitung Operasi Dasar

• Operasi aritmatika: +, -, *, /, %
• Operasi perbandingan: <, >, ==, !=
• Assignment: =
• Akses elemen array dengan indeks

💻 Contoh Penghitungan Operasi

int findMax(int arr[], int n) {
    int max = arr[0];           // 2 operasi
    for (int i = 1; i < n; i++) { // 1 + (n-1) + (n-1) operasi
        if (arr[i] > max) {     // 2 operasi per iterasi
            max = arr[i];       // 2 operasi (worst case)
        }
    }
    return max;                 // 1 operasi
}
                    

🧠 Quiz: Hitung Operasi

int sum = 0;
for (int i = 0; i < n; i++) {
    sum = sum + arr[i];
}
                        

📖 3. Notasi Asimptotik

Konsep Pertumbuhan Fungsi

Untuk n sangat besar, hanya suku dengan pangkat tertinggi yang dominan:

Big-O (Upper Bound)

Gambar 2.1: Visualisasi Big-O — f(n) dibatasi oleh c·g(n) untuk n ≥ n₀

Perbandingan Notasi

🧠 Quiz: Buktikan Big-O

📖 4. Aturan Penyederhanaan Big-O

Aturan Penjumlahan (Sum Rule)

Untuk dua segmen kode berurutan:

// Segmen 1: O(n)
for (int i = 0; i < n; i++) { /* ... */ }

// Segmen 2: O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { /* ... */ }
}
// Total: O(n + n²) = O(n²)
                    

Aturan Perkalian (Product Rule)

Untuk loop bersarang:

// Loop luar: n kali
for (int i = 0; i < n; i++) {
    // Loop dalam: n kali per iterasi
    for (int j = 0; j < n; j++) {
        /* O(1) operation */
    }
}
// Total: O(n × n) = O(n²)
                    

🧠 Quiz: Sederhanakan

📖 5. Kelas-Kelas Kompleksitas Umum

Perbandingan Pertumbuhan

Gambar 2.2: Perbandingan pertumbuhan berbagai kelas kompleksitas

Dampak Praktis (10⁹ ops/sec)

Untuk n besar, algoritma eksponensial praktis tidak dapat diselesaikan!

🎖️ Analogi Militer

📖 6. Best, Worst, Average Case

Untuk input berukuran n yang sama, waktu eksekusi bisa berbeda tergantung konfigurasi input.

Contoh: Linear Search

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;  // Ditemukan
    }
    return -1;  // Tidak ditemukan
}
                    

Mana yang Paling Penting?

Average case berguna untuk algoritma yang worst case-nya jarang terjadi (seperti Quick Sort).

📖 7. Analisis Algoritma Iteratif

Pola Loop Tunggal

// Pola 1: Loop linear
for (int i = 0; i < n; i++) { ... }     // O(n)

// Pola 2: Loop dengan increment konstan
for (int i = 0; i < n; i += 2) { ... }  // O(n/2) = O(n)

// Pola 3: Loop dengan pengali
for (int i = 1; i < n; i *= 2) { ... }  // O(log n)

// Pola 4: Loop dengan pembagi
for (int i = n; i > 0; i /= 2) { ... }  // O(log n)
                    

Pola Loop Bersarang

// Pola 1: Nested linear → O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { ... }
}

// Pola 2: Loop dalam bergantung pada i → O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) { ... }
}
// Total: 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)

// Pola 3: Loop luar logaritmik → O(n log n)
for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < n; j++) { ... }
}
                    

🧠 Quiz: Kompleksitas Mystery

void mystery(int n) {
    for (int i = 1; i < n; i = i * 2) {
        for (int j = 0; j < n; j++) {
            cout << i << " " << j << endl;
        }
    }
}
                        

📖 8. Analisis Algoritma Rekursif

Recurrence Relation

void printN(int n) {
    if (n <= 0) return;        // Base case
    cout << n << endl;         // O(1)
    printN(n - 1);             // T(n-1)
}
                    

Metode Substitusi

Selesaikan T(n) = T(n-1) + 1, T(0) = 1:

Fibonacci Rekursif (Naive)

long fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Dua pemanggilan rekursif!
}
                    

Pohon Rekursi Fibonacci

Gambar 2.3: Pohon rekursi Fibonacci — banyak perhitungan redundan

Contoh: Binary Search Rekursif

📖 9. Master Theorem

Untuk relasi rekurens divide-and-conquer:

Kasus Master Theorem

Contoh Penerapan

🧠 Quiz: Master Theorem