Pengenalan Visual tentang Notasi Big O

(samwho.dev)

2 poin oleh GN⁺ 2025-08-26 | 1 komentar | Bagikan ke WhatsApp

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

1 komentar

GN⁺ 2025-08-26

Komentar Hacker News

Artikel ini, beserta komentar-komentar di HN, tampaknya melanjutkan tradisi menjelaskan Big O Notation sambil memperdebatkan penggunaan nyata dan detail teknisnya. Sebagai contoh yang layak dirujuk, ada artikel penjelasan ini dan tulisan tentang sikap para ahli
- Jika melihat komentar di tulisan sebelumnya, ada pengguna bernama Pyon yang menunjukkan sikap tajam dan kaku. Namun, bantahan Ned juga tidak terlalu bagus. Ia tidak menjelaskan detail teknisnya dengan tepat, dan hanya terkesan berputar-putar dengan terus menyebut “detail tertentu”. Disayangkan juga karena tidak dijelaskan mengapa kritiknya hanya sekadar mencari-cari kesalahan, atau mengapa isi pembahasannya sendiri sampai ditolak. Ned memang menunjukkan arah yang benar soal komunikasi dan empati di internet. Tetap saja, kalau seorang pendidik, rasanya ia seharusnya setidaknya sekali menjelaskan mengapa poin teknis itu terlalu remeh atau sekadar nitpicking. Ned sendiri hanya bilang bahwa ia “baru tahu setelah puluhan tahun”, dan itu terasa belum cukup. Lalu setelah melihat lagi thread komentar aslinya, ternyata Ned sebenarnya berdebat dengan cukup diplomatis dan serius. Jadi saya heran mengapa analisis itu hilang dari tulisan blognya. Secara pribadi saya juga tidak benar-benar tahu apa detail teknis yang dimaksud, jadi saya berharap setidaknya ada ringkasan penjelasan singkat sekali saja
- Saya cenderung termasuk ahli yang kritis. Setiap kali melihat upaya mengajarkan topik kompleks lewat blog, saya hampir selalu kecewa, karena biasanya non-ahli yang menjelaskan sambil mengorbankan akurasi. Akibatnya, 1) informasi yang tidak akurat disalin-tempel ke seluruh internet, dan 2) pembaca hanya berhenti di level blog lalu enggan belajar lebih jauh, sehingga ketidaktahuan mereka justru mengeras. Selain itu, saya juga tidak suka tata letak halamannya. Dari pengalaman saya sebagai orang dengan ADHD dan daya ingat yang kurang baik, saya butuh pemecahan yang rapi dengan format yang tepat—subjudul/tebal/warna pemisah/bullet dan semacamnya—agar bisa mengikuti. Artikel ini terasa seperti dinding teks. Semakin lama waktu yang dibutuhkan untuk menangkap poin utamanya, semakin hilang fokus saya. Penjelasan Big O di Simple Wikipedia jauh lebih lugas. Sementara halaman Wikipedia biasa tiba-tiba masuk ke matematika, dan ketika melihatnya langsung, jadi terasa bahwa Big O ternyata topik yang jauh lebih rumit dari yang dibayangkan, sehingga saya sampai pada kesimpulan bahwa “menyederhanakannya justru mungkin tidak baik”
- Tautan kedua bukan tentang Big-O, dan sikap seperti itu memang tidak perlu ditiru
- Ned mengirimi saya email beberapa hari lalu, dan dengan senang hati saya juga ikut berkontribusi dalam diskusi seperti ini
- Saat melihat tulisan seperti ini, pelajaran yang sebenarnya adalah bukan “kalau ada penjelasan yang salah atau menyesatkan, berhentilah mengoreksi”, melainkan bahwa di internet ada sebagian “ahli” yang hanya ingin menang debat. Dari sikap Pyon, ia terlihat cukup agresif dan seperti troll internet. Kita sama sekali tidak boleh menarik kesimpulan bahwa “berarti detail teknis tidak penting dan tidak akurat pun tidak masalah”
O(1) pada praktiknya sebenarnya memakai fungsi hashing, yang meskipun tidak sederhana tetap memerlukan biaya operasi yang konstan. Jika datanya sangat sedikit, algoritma terburuk seperti O(n^2) justru bisa lebih cepat dalam waktu nyata
- Itu benar, tetapi sebaiknya jangan terlalu dibesar-besarkan. Di dunia kerja, membuat orang memahami bahwa n^2 saja sudah bisa membuat komputer terasa macet pun sudah sulit. Lagi pula, dalam beberapa kasus kita juga bisa memakai fungsi hash sempurna seperti mod
Saya merasa pentingnya Big-O di era modern tidak sebesar dulu. Perangkat keras sekarang punya multithreading, pipeline, NUMA, caching yang kompleks, dan sebagainya, sehingga ada operasi yang selesai dalam kurang dari satu siklus, sementara yang lain justru memakan ratusan atau ribuan siklus. Jika kita mencoba menjelaskan algoritma hanya lewat jumlah iterasi innermost loop, kita malah mendistorsi kenyataan. Dan kalau membahas Big-O, notasi lain seperti Big-Omega juga wajib disebut. (Sebagai catatan, saya juga menikmati animasi bertema Big-O itu)
- Teori Big-O lahir justru untuk mendefinisikan jumlah operasi tanpa bergantung pada faktor-faktor yang terikat pada mesin seperti itu. Dalam arti itu, ini adalah alat yang tidak lekang oleh zaman. (Presenter yang baik biasanya juga pasti menyebut bahwa “konstanta seperti C menjadi faktor yang sangat penting saat N kecil”)
Yang benar-benar menarik adalah bahwa dalam komputasi kuantum, ada operasi tertentu yang tumbuh terhadap jumlah atom sebesar O(n^7), tetapi para ilmuwan tidak takut benar-benar menjalankan perhitungan itu. Karena N-nya cukup kecil, komputer dan memori terus menjadi lebih cepat, dan nilai hasilnya sangat besar. (Saya bukan spesialis ilmu komputer, jadi mohon maklum kalau saya salah memakai notasi O())
- Cukup bilang saja “bertambah sebanding dengan n^7”. Jika menulis O(n^7), kebanyakan orang memang paham maksudnya, tetapi secara matematis O hanya menunjukkan ‘batas atas’, jadi itu tidak sepenuhnya akurat kalau mau ketat. Kalau mau benar-benar tepat, penulisannya seharusnya seperti Ω(n^7)
Saya sangat suka visualisasinya. Bahkan sebagai orang yang dulu pernah belajar algoritma, melihatnya secara visual tetap sangat membantu
Mungkin karena saya mengambil teknik elektro, Big O Notation selalu terasa seperti konsep yang entah bagaimana dilewati begitu saja. Selalu diperlakukan seolah-olah semua orang sudah pasti tahu, jadi saya rasa saya belum pernah melihat penjelasan yang benar-benar ramah. Saya penasaran di tingkat matematika atau ilmu komputer seperti apa konsep ini pertama kali diperkenalkan
- Saya belajar Big-O paling sistematis saat kuliah Discrete Math di jurusan ilmu komputer
- Di kampus saya, Big-O dan berbagai metode pembuktian diajarkan di Algorithm Analysis (mata kuliah wajib). Tapi mata kuliah ini hampir selalu diambil saat tahun ke-3 atau ke-4, dan sebenarnya ada asumsi tersirat bahwa pada tahun pertama mahasiswa sudah menyerap konsepnya sampai taraf tertentu (mungkin lebih karena terbiasa mendengarnya di sekitar)
- Secara matematis, fungsi f(x) adalah O(g(x)) berarti f(x)/g(x) memenuhi “untuk suatu konstanta C, untuk semua x berlaku f(x)/g(x) < C”. Di ilmu komputer, f(x) sering berarti kompleksitas seperti jumlah operasi dari suatu algoritma tertentu
- Perancangan Big-O Notation bisa ditafsirkan dengan beberapa cara. Misalnya jika suatu algoritma didefinisikan berdasarkan jumlah langkah pada Turing Machine, maka algoritma waktu log tidak mungkin ada dan O(log n) diperlakukan sebagai O(1)
- Saya mempelajarinya di mata kuliah wajib tahun pertama ilmu komputer. Sebenarnya tidak rumit: ini hanya konsep yang menjelaskan bagaimana jumlah operasi bertambah saat data masukan membesar. Kelihatannya sulit, tetapi pada praktiknya sangat sederhana dan jelas
Visualisasi dinamisnya sangat membantu pemahaman. Saya harap akan dibuat lebih banyak pelajaran/materi seperti ini
- Senang sekali mendengar respons seperti itu
Setiap kali thread tentang Big-O Notation muncul, saya selalu berharap ada yang menjelaskan bagaimana konsep ini terhubung dengan anime The Big O. Sampai sekarang saya masih tidak benar-benar paham anime itu soal apa
- (menenggak 4 kaleng bir)Oke dengar ya. Anime itu rasanya seperti Pacific Rim, Dark City, dan The Matrix dicampur berurutan jadi satu
Menurut saya pribadi, cara paling efektif memahami Big O Notation adalah dengan mengaitkannya ke keseharian lewat analogi
Menurut saya ini materi yang indah. Saya sudah mengirim sinyal, semoga tersampaikan, dan rasanya seperti mendapat sesendok dopamin tanpa alasan
- Sudah sampai. Terima kasih