Pengenalan Visual tentang Notasi Big O

• Notasi Big O mengekspresikan performa fungsi sebagai pola pertumbuhan terhadap perubahan ukuran input
• Artikel ini menjelaskan Big O yang representatif untuk konstan, logaritmik, linear, dan kuadratik beserta contohnya
• Bergantung pada struktur data dan algoritme, kompleksitas waktu bisa berbeda, termasuk pada pengurutan dan pencarian dalam array
• Untuk benar-benar meningkatkan performa kode, kuncinya adalah memilih struktur data yang tepat dan menghapus operasi yang tidak perlu di dalam loop
• Big O selalu menyederhanakan hubungan antara input dan waktu eksekusi ke bentuk paling sederhana, dan saat mengoptimalkan performa penting untuk mengukur kode secara langsung

---

Gambaran umum notasi Big O

• Notasi Big O adalah cara menjelaskan pola pertumbuhan waktu eksekusi berdasarkan ukuran input (n) alih-alih mengukur waktu secara langsung
• Waktu eksekusi fungsi diklasifikasikan berdasarkan ukuran input, dan bentuk yang umum dianalisis adalah konstan (O(1)), logaritmik (O(log n)), linear (O(n)), dan kuadratik (O(n²))
• Artikel ini menjelaskannya agar mudah dipahami pemula melalui konsep tiap kategori, contoh visual, dan contoh kode nyata

Perulangan (Iterating) dan algoritme linear

• Fungsi sum(n) adalah contoh struktur perulangan untuk menjumlahkan dari 1 sampai n, dan ketika nilai input n membesar, waktu eksekusi juga bertambah secara proporsional
• Dalam praktiknya, sum(1e9) memerlukan sekitar 1 detik, sum(2e9) sekitar 2 detik, sehingga wall-clock time bertumbuh dengan pola O(n)
• Kompleksitas waktu adalah hubungan antara input fungsi dan waktu eksekusinya, dan ini dinyatakan dengan notasi Big O (O(n) — sebanding dengan n)
• Alih-alih perulangan, memakai rumus matematika sum(n) = (n*(n+1))/2 membuat waktu eksekusi tetap konstan tanpa bergantung pada nilai input n
• Fungsi seperti ini disebut memiliki kompleksitas waktu konstan O(1), dengan ciri tidak ada pertumbuhan waktu eksekusi saat input berubah

Sintaks notasi Big O

• Huruf O pada Big O berasal dari “Order”, dan hanya menunjukkan bentuk pertumbuhannya saja
• Yang ditulis secara ringkas bukan nilai absolut waktu eksekusi, melainkan hanya 'pola' pertumbuhan terhadap input
• Misalnya, meski sebuah fungsi bisa ditulis sebagai O(2n) atau O(n+1), bentuk seperti itu tidak dipakai; yang dipilih adalah suku paling sederhana

Mempercepat waktu dengan memanfaatkan struktur input

• Seperti contoh rumus sum(n), perbaikan algoritme dapat mengubah kompleksitas waktu dari O(n) menjadi O(1)
• Namun, kompleksitas waktu konstan tidak selalu berarti pasti lebih cepat, karena total waktu eksekusi tetap bergantung pada jenis operasinya
• Pada input tertentu, algoritme O(n) bisa lebih cepat daripada O(1), tetapi ketika ukuran input membesar, pendekatan O(1) akan selalu lebih unggul

Pengurutan (Sorting) dan algoritme kuadratik: contoh bubble sort

• Bubble Sort adalah contoh dasar pengurutan array dengan menukar elemen yang bersebelahan berulang kali
• Jika array sudah terurut, cukup 1 kali iterasi (O(n)); jika urut terbalik, perlu menelusuri hingga n kali berulang → jumlah operasi total pada kasus terburuk adalah n²
• Algoritme O(n²) mengalami kenaikan waktu eksekusi yang sangat besar dalam bentuk kuadrat saat input membesar
• Dalam penggunaan nyata, Big O selalu didasarkan pada kasus terburuk (worst-case), meskipun kadang kasus rata-rata/terbaik juga dituliskan
• Jumlah iterasi bisa berkurang tergantung kondisi awal array, tetapi karena mempertimbangkan kasus terburuk, ia tetap diklasifikasikan sebagai kompleksitas waktu kuadratik

Pencarian (Searching) dan algoritme logaritmik: contoh binary search

• Binary Search memperkirakan nilai tengah dari rentang yang sudah terurut, lalu menghapus setengah area kandidat pada setiap langkah
• Misalnya, untuk menebak angka tertentu antara 1–100 dibutuhkan paling banyak 7 kali, dan untuk 1 hingga 1 miliar pun bisa dilakukan dalam kurang dari 31 percobaan
• Karena daftar kandidat berkurang setengah pada tiap langkah, waktu eksekusinya adalah O(log n) (kompleksitas waktu logaritmik)
• Algoritme logaritmik bertambah sangat lambat ketika n membesar, sehingga jauh lebih efisien dibanding linear atau kuadratik
• Saat dibandingkan dalam grafik, perbedaan pertumbuhan log n, n, dan n² terlihat sangat jelas

Penerapan nyata: tips meningkatkan kompleksitas waktu

Mencari item dalam list

• Secara dasar, fungsi untuk mencari nilai dalam array termasuk O(n)
• Jika pencarian dilakukan sering, memakai struktur data seperti Set dapat meningkatkannya menjadi O(1)
• Namun, proses konversi itu sendiri dengan new Set(array) adalah O(n), jadi ini hanya cocok untuk pencarian yang sering dilakukan (biaya konversi harus dipertimbangkan)
• Contoh: items.has("banana") memberikan kompleksitas waktu konstan

Menulis loop dengan memanfaatkan indeks

• Kode yang menggunakan .indexOf di dalam loop seperti di bawah ini sering menjadi penyebab masalah performa

  function buildList(items) {
    const output = [];
    for (const item of items) {
      const index = items.indexOf(item);
      output.push(`Item ${index + 1}: ${item}`);
    }
    return output.join("\n");
  }
  

• Karena .indexOf adalah operasi O(n) di dalam loop, secara keseluruhan polanya menjadi O(n^2)

• Jika memakai iterasi berbasis indeks atau forEach((item, index) => ...), ini dapat diperbaiki menjadi O(n)

  function buildList(items) {
    const output = [];
    for (let i = 0; i < items.length; i++) {
      output.push(`Item ${i + 1}: ${items[i]}`);
    }
    return output.join("\n");
  }
  

Memanfaatkan memoization

• Struktur seperti faktorial yang menghitung ulang nilai saat dipanggil berulang bisa ditingkatkan performanya dengan cache hasil (menggunakan Map)

• Pencarian pada Map termasuk O(1) sehingga perhitungan ulang yang tidak perlu dapat diminimalkan

• Namun, caching berkontribusi pada peningkatan waktu rata-rata, dan meski kompleksitas waktu terburuknya tidak berubah, performa tetap bisa meningkat secara efisien

  const cache = new Map();
  function factorial(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }
    if (n === 0) {
      return 1;
    }
    const result = n * factorial(n - 1);
    cache.set(n, result);
    return result;
  }
  

Evaluasi performa dan kesimpulan

• Saat meningkatkan performa kode, selain kompleksitas waktu secara teori, kita juga perlu menguji eksekusi secara langsung untuk memastikan apakah benar ada peningkatan
• Big O mengekspresikan hubungan dan pola pertumbuhan antara input dan waktu eksekusi dengan penyederhanaan yang paling esensial
• Dengan memilih algoritme yang baik dan mengoptimalkan struktur data, efisiensi kode dapat dimaksimalkan

Ringkasan

• Notasi Big O mengekspresikan hubungan antara nilai input fungsi dan waktu eksekusi
• Kategori performa utama: O(1) (konstan), O(log n) (logaritmik), O(n) (linear), O(n^2) (kuadratik)
• Untuk menulis kode yang efisien, algoritme yang tepat dan optimasi loop sangat penting
• Performa nyata perlu diukur langsung untuk memverifikasi hasil optimasi
• Grafik perbandingan pola pertumbuhan membantu memahami karakteristik kompleksitas waktu secara sekilas