Time Complexity

Time complexity adalah deskripsi matematis tentang bagaimana jumlah operasi sebuah algoritma tumbuh ketika ukuran input n membesar. Dengan mengetahui time complexity, kita bisa memprediksi apakah sebuah algoritma akan tetap praktis saat inputnya naik 10× atau 1000× lipat. Pada Chapter ini kita akan mempelajari cara menghitung time complexity dengan model Random Access Machine (RAM), menghitung operasi pada berbagai konstruksi bahasa, dan membandingkan time complexity beberapa algoritma pencarian yang setara.

Model Komputasi: Random Access Machine #

Untuk menghitung time complexity secara konsisten, kita menggunakan model komputasi sederhana bernama Random Access Machine (RAM). Pada model ini:

Setiap operasi primitif (penugasan, pembandingan, akses array, operasi aritmetika dasar) dianggap memerlukan waktu konstan O(1).
Memori diakses secara acak: akses ke indeks arr[0] dan arr[1000000] dianggap sama-sama O(1).
Tidak ada operasi paralel: instruksi dijalankan satu per satu secara berurutan.

Operasi Primitif yang Berharga O(1) #

Operasi berikut dianggap konstan dalam model RAM:

Operasi	Contoh di C++	Biaya
Penugasan	`a = 5;`	`O(1)`
Aritmetika dasar	`a + b * c`	`O(1)`
Pembandingan	`a < b`, `a == b`	`O(1)`
Akses elemen array	`arr[i]`	`O(1)`
Akses field struct/class	`obj.field`	`O(1)`
Fungsi `std::swap(a,b)` untuk tipe primitif	`std::swap(x,y)`	`O(1)`
Method `.size()` pada `std::vector`	`v.size()`	`O(1)`

Operasi berikut bukan O(1) walau terlihat sederhana:

Operasi	Contoh di C++	Biaya
Konstruktor `std::vector` dari initializer besar	`std::vector<int>{1,2,...,n}`	`O(n)`
Method `.push_back` saat realokasi	`v.push_back(x)` (amortisasi)	`O(1)` amortized
Fungsi `std::sort`	`std::sort(v.begin(), v.end())`	`O(n log n)`
Method `.insert` pada `std::vector` di tengah	`v.insert(v.begin()+i, x)`	`O(n)`
Method `.find` pada `std::unordered_set` (kasus buruk)	`s.find(x)`	`O(n)` worst case

Cara Menghitung Time Complexity #

Aturan Penjumlahan #

Bila dua blok kode dijalankan secara berurutan, time complexity total adalah penjumlahan keduanya:

text

T_total(n) = T_blok_1(n) + T_blok_2(n)

Untuk ordo asimptotik, kita ambil suku yang dominan. Misal T1 = n² + 3n dan T2 = 5n, maka T_total = n² + 8n, dan ordo asimptotiknya O(n²).

Aturan Perkalian #

Bila dua blok kode bersarang (loop dalam loop), time complexity total adalah perkalian:

text

T_total(n) = T_luar(n) × T_dalam(n)

Loop luar n kali yang berisi loop dalam n kali menghasilkan O(n²).

Kode: Menghitung Operasi Secara Eksplisit #

cpp
#include <iostream>
#include <vector>

long long jumlahOperasi = 0;

int cariMaks(const std::vector<int>& v) {
    int maks = v[0];          jumlahOperasi += 1;   // penugasan
    for (std::size_t i = 1; i < v.size(); ++i) {
        jumlahOperasi += 2;   // pembandingan loop + increment
        ++jumlahOperasi;       // pembandingan v[i] > maks
        if (v[i] > maks) {
            ++jumlahOperasi;  // penugasan baru
            maks = v[i];
        }
    }
    return maks;
}

int main() {
    for (int n : {10, 100, 1000}) {
        std::vector<int> data(n);
        for (int i = 0; i < n; ++i) data[i] = i * 2;

        jumlahOperasi = 0;
        cariMaks(data);
        std::cout << "n=" << n << " -> operasi = " << jumlahOperasi << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
n=10 -> operasi = 37
n=100 -> operasi = 397
n=1000 -> operasi = 3997

Bedah Kode Baris-per-Baris #

Mari kita telaah bagian-bagian penting program di atas:

Baris long long jumlahOperasi = 0;: variabel global sebagai penghitung operasi. Global dipilih agar tidak perlu diteruskan sebagai parameter.
Baris int maks = v[0];: satu penugasan dihitung sebagai 1 operasi.
Baris jumlahOperasi += 2;: setiap iterasi loop melakukan pembandingan i < v.size() dan ++i, masing-masing dihitung sebagai 1 operasi.
Baris ++jumlahOperasi; setelah pembandingan: pembandingan v[i] > maks dihitung sebagai 1 operasi, terlepas dari cabang mana yang diambil.
Baris di dalam if: penugasan maks = v[i] hanya terjadi jika kondisi terpenuhi. Pada contoh di atas dengan data terurut naik, kondisi ini selalu benar.
Output n=10 -> operasi = 37: formula yang terbentuk adalah 1 + (n-1)×4 = 4n - 3. Untuk n=10: 4×10 - 3 = 37. Rasio operasi/n mendekati konstan (~4) saat n besar, menandakan time complexity O(n).

Tiga Kasus: Best, Worst, dan Average #

Time complexity sebuah algoritma bisa berbeda tergantung input. Kita biasanya mempertimbangkan tiga kasus:

Best case — input yang memberi jumlah operasi paling sedikit. Misal linear search menemukan target di elemen pertama: O(1).
Worst case — input yang memberi jumlah operasi paling banyak. Misal linear search menemukan target di elemen terakhir atau tidak ketemu: O(n).
Average case — rata-rata operasi pada seluruh input yang mungkin, dengan asumsi distribusi seragam. Untuk linear search pada array acak: O(n).

flowchart LR A[Input n] --> B{Distribusi?} B -- Best --> C[Operasi minimum] B -- Worst --> D[Operasi maksimum] B -- Average --> E[Rata-rata seluruh input]

Contoh: Linear vs Binary Search #

Mekanisme Kedua Algoritma #

Linear search membandingkan target dengan setiap elemen array satu per satu mulai dari indeks 0. Pada array tak terurut, algoritma ini adalah satu-satunya pilihan. Binary search memanfaatkan array yang sudah terurut: pada setiap langkah, algoritma membandingkan target dengan elemen tengah, lalu membuang setengah dari ruang pencarian. Inilah yang membuat binary search jauh lebih cepat untuk n besar.

Kode Program #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int linearSearch(const std::vector<int>& v, int target, long long& op) {
    op = 0;
    for (std::size_t i = 0; i < v.size(); ++i) {
        ++op;
        if (v[i] == target) return static_cast<int>(i);
    }
    return -1;
}

int binarySearch(const std::vector<int>& v, int target, long long& op) {
    op = 0;
    int lo = 0, hi = static_cast<int>(v.size()) - 1;
    while (lo <= hi) {
        ++op;
        int mid = lo + (hi - lo) / 2;
        if (v[mid] == target) return mid;
        else if (v[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    for (int n : {1000, 1000000}) {
        std::vector<int> data(n);
        for (int i = 0; i < n; ++i) data[i] = i;

        long long opLin = 0, opBin = 0;
        linearSearch(data, -1, opLin);     // worst case: tidak ketemu
        binarySearch(data, -1, opBin);
        std::cout << "n=" << n
                  << " | linear ops=" << opLin
                  << ", binary ops=" << opBin << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text

n=1000 | linear ops=1000, binary ops=9
n=1000000 | linear ops=1000000, binary ops=19

Bedah Kode Baris-per-Baris #

Baris for (std::size_t i = 0; i < v.size(); ++i): linear search menjelajah setiap elemen. std::size_t dipakai karena v.size() mengembalikan tipe tak bertanda.
Baris int mid = lo + (hi - lo) / 2;: kita menggunakan lo + (hi - lo) / 2, bukan (lo + hi) / 2, untuk menghindari integer overflow saat lo + hi melebihi INT_MAX.
Baris else if (v[mid] < target) lo = mid + 1;: jika target lebih besar dari elemen tengah, ruang pencarian dipindahkan ke paruh kanan. mid + 1 penting agar loop berakhir, karena mid sendiri sudah diperiksa.
Pemanggilan dengan target -1: target sengaja tidak ada di array, sehingga kedua algoritma menjelajah seluruh ruang pencarian. Inilah kondisi worst case.
Output: saat n naik 1000× (dari 1.000 ke 1.000.000), linear search ops naik 1000× (dari 1.000 ke 1.000.000), tetapi binary search ops hanya naik ~2× (dari 9 ke 19, kira-kira ⌊log2 n⌋). Pola O(n) vs O(log n) terbukti.

Beberapa Time Complexity Umum #

Berikut daftar kelas time complexity yang sering kita jumpai, diurutkan dari paling efisien ke paling lambat:

Kelas	Nama	Contoh Algoritma
`O(1)`	Konstan	Akses elemen array `arr[i]`
`O(log n)`	Logaritmik	Binary search
`O(n)`	Linier	Linear search, traversal array
`O(n log n)`	Linieritmik	Merge sort, heap sort, FFT
`O(n²)`	Kuadratik	Bubble sort, selection sort
`O(n³)`	Kubik	Perkalian matriks naive
`O(2ⁿ)`	Eksponensial	Subset generation
`O(n!)`	Faktorial	Permutasi semua (brute force TSP)

Ringkasan #

Time complexity mengukur bagaimana jumlah operasi tumbuh sebagai fungsi dari n, dengan model komputasi RAM.
Operasi primitif (penugasan, pembandingan, akses array) dianggap O(1); sebaliknya, fungsi STL seperti std::sort atau vector::insert punya biaya asimptotik sendiri.
Aturan penjumlahan untuk kode berurutan, aturan perkalian untuk loop bersarang.
Tiga kasus analisis: best case, worst case, dan average case. Kita paling sering memakai worst case untuk jaminan batas atas.
Contoh linear search vs binary search menunjukkan perbedaan dramatis antara O(n) dan O(log n) saat n membesar.

Pada Chapter berikutnya kita akan membahas dimensi kedua kompleksitas: space complexity, yang mengukur pemakaian memori tambahan oleh algoritma.