Sebagian besar algoritma imperatif terdiri atas loop — for, while, atau range-based for. Memahami pola loop dan jumlah iterasi yang dilakukan adalah keterampilan dasar untuk menentukan time complexity. Pada Chapter ini kita akan membedah berbagai pola loop yang sering muncul di DSA, mulai dari loop tunggal linier hingga loop bersarang dengan pertambahan geometris, dan melihat bagaimana pola tersebut menentukan Big-Theta algoritma.

Loop Tunggal Linier #

Loop paling sederhana menjelajah elemen satu per satu dengan indeks bertambah konstan.

cpp 
for (int i = 0; i < n; ++i) {
    // body: O(1)
}

Jumlah iterasi: n. Kompleksitas: Θ(n).

Variasi Pertambahan #

Bila pertambahan bukan +1 melainkan +k, jumlah iterasi menjadi ⌈n/k⌉:

cpp 
for (int i = 0; i < n; i += 3) {
    // body: O(1)
}

Jumlah iterasi: ⌈n/3⌉ ≈ n/3. Kompleksitas: Θ(n). Konstanta 3 diabaikan dalam Big-Theta.

Loop Logaritmik #

Saat indeks dikalikan dengan konstanta (misal i *= 2), jumlah iterasi tumbuh logaritmik terhadap n.

cpp 
for (int i = 1; i < n; i *= 2) {
    // body: O(1)
}

Jumlah iterasi: ⌊log₂ n⌋ + 1. Kompleksitas: Θ(log n).

Loop Akar #

Saat indeks bertambah dengan konstanta, tetapi batas loop berubah mengikuti i²:

cpp 
for (int i = 1; i * i <= n; ++i) {
    // body: O(1)
}

Jumlah iterasi: ⌊√n⌋. Kompleksitas: Θ(√n).

Loop Bersarang (Nested Loops) #

Saat loop dalam berada di dalam loop luar, jumlah iterasi total adalah perkalian keduanya — namun dengan catatan: batas loop dalam bisa bergantung pada variabel loop luar.

Pola 1: Loop Dalam Independen #

cpp 
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        // body: O(1)
    }
}

Iterasi total: n × n = n². Kompleksitas: Θ(n²).

Pola 2: Loop Dalam Bergantung pada Loop Luar #

cpp 
for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
        // body: O(1)
    }
}

Iterasi total: 1 + 2 + 3 + ... + n = n(n+1)/2. Kompleksitas: Θ(n²).

Pola 3: Loop Dalam dengan Batas Konstan #

cpp 
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 10; ++j) {
        // body: O(1)
    }
}

Iterasi total: n × 10 = 10n. Kompleksitas: Θ(n). Loop dalam berkonstanta tidak mengubah kelas asimptotik.

Kode: Verifikasi Empat Pola Loop #

cpp 
#include <iostream>

int main() {
    long long iter;
    int n = 1000;

    // Pola 1: n × n
    iter = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) ++iter;
    std::cout << "Pola 1 (n*n)       : " << iter << " (n^2 = " << 1LL*n*n << ")\n";

    // Pola 2: segitiga 1+2+...+n
    iter = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j) ++iter;
    std::cout << "Pola 2 (segitiga)  : " << iter
              << " (n(n+1)/2 = " << 1LL*n*(n+1)/2 << ")\n";

    // Pola 3: loop dalam konstan
    iter = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 10; ++j) ++iter;
    std::cout << "Pola 3 (10n)       : " << iter << " (10n = " << 10*n << ")\n";

    // Pola 4: logaritmik
    iter = 0;
    for (int i = 1; i < n; i *= 2) ++iter;
    std::cout << "Pola 4 (log n)     : " << iter
              << " (log2 n = ~10 untuk n=1000)\n";
    return 0;
}

Output yang Dihasilkan:

text 
Pola 1 (n*n)       : 1000000 (n^2 = 1000000)
Pola 2 (segitiga)  : 500500 (n(n+1)/2 = 500500)
Pola 3 (10n)       : 10000 (10n = 10000)
Pola 4 (log n)     : 10 (log2 n = ~10 untuk n=1000)

Bedah Kode Baris-per-Baris #

  1. Pola 1: loop dalam menjelajah seluruh n untuk setiap i. Total tepat n² iterasi.
  2. Pola 2: loop dalam menjelajah dari 0 sampai i inklusif, sehingga jumlah iterasi adalah deret aritmetika 1 + 2 + ... + n = n(n+1)/2. Untuk n = 1000, hasilnya 500.500.
  3. Pola 3: loop dalam berkonstan 10, sehingga total iterasi 10n. Konstanta 10 diabaikan dalam Big-Theta; kompleksitas tetap Θ(n).
  4. Pola 4: indeks i berubah 1, 2, 4, 8, 16, 32, 64, 128, 256, 512. Iterasi ke-11 akan membuat i = 1024 > n, sehingga loop berhenti. Total 10 iterasi, sesuai dengan ⌊log₂ 1000⌋ + 1 = 9 + 1 = 10.
  5. Implikasi: ketika batas loop dalam bergantung pada variabel loop luar, kita perlu menghitung jumlah iterasi secara eksplisit (sering kali sebagai deret), bukan sekadar perkalian n × m.

Loop dengan Variabel Loop Dimodifikasi di Dalam #

Kadang variabel loop dimodifikasi di dalam body, sehingga analisis menjadi lebih rumit:

cpp 
int i = 0;
while (i < n) {
    if (kondisi) i *= 2;
    else         ++i;
}

Loop seperti ini sulit dianalisis tanpa mengetahui distribusi kondisi. Untuk analisis worst case, kita mengasumsikan cabang yang memberi paling banyak iterasi.

Loop Berdasar Deret #

Beberapa pola loop menghasilkan deret matematika yang dapat dijumlahkan:

PolaDeretJumlahBig-Theta
for (i=1; i<=n; ++i) linier1+1+...+1 (n kali)nΘ(n)
for (i=1; i<=n; ++i) total += i1+2+...+nn(n+1)/2Θ(n²)
for (i=1; i<=n; ++i) for (j=1; j<=i; ++j) for (k=1; k<=j; ++k)ΣΣΣ1n(n+1)(n+2)/6Θ(n³)
for (i=1; i<n; i*=2) logaritmik1+1+...+1 (log n kali)log₂ nΘ(log n)
for (i=1; i<=n; i*=2) for (j=0; j<i; ++j)1+2+4+...+2^k2n-1Θ(n)
for (i=n; i>=1; i/=2) for (j=0; j<i; ++j)n+n/2+n/4+...+12nΘ(n)

Binary search memiliki loop khas yang membagi ruang pencarian dua pada setiap iterasi:

cpp 
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[mid] == target) return mid;
    else if (v[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Loop ini berjalan paling banyak ⌊log₂ n⌋ + 1 kali. Kompleksitas: Θ(log n).

Pola Loop dengan std::vector::push_back #

Bila loop melakukan push_back pada std::vector di dalam, perlu diperhatikan bahwa push_back sendiri memiliki kompleksitas amortized O(1):

cpp 
std::vector<int> v;
for (int i = 0; i < n; ++i) {
    v.push_back(i);   // amortized O(1)
}

Total: O(n) amortized. Bab Kompleksitas Amortisasi akan membahas ini secara detail.

Loop dengan Kondisi Kompleks #

Beberapa loop memiliki kondisi yang melibatkan fungsi non-trivial. Contoh:

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

Loop berhenti saat i² ≥ n, yaitu saat i ≥ √n. Jumlah iterasi: ⌈√n⌉. Kompleksitas: Θ(√n).

Ringkasan #

  • Loop tunggal linier: Θ(n); loop logaritmik (i *= 2): Θ(log n); loop akar (i*i ≤ n): Θ(√n).
  • Loop bersarang dengan batas independen menghasilkan perkalian; dengan batas bergantung menghasilkan deret.
  • Loop dalam dengan batas konstan tidak mengubah kelas asimptotik.
  • Beberapa pola menghasilkan deret matematika yang dapat dijumlahkan; koefisiennya berbeda-beda tetapi ordo asimptotiknya bisa Θ(n), Θ(n²), atau Θ(n³).
  • Loop dengan push_back pada std::vector memiliki biaya amortized O(1) per operasi.

Pada Chapter berikutnya kita akan naik ke level berikutnya: analisis fungsi rekursif, di mana kompleksitas ditentukan oleh kedalaman rekursi dan recurrence relation.