Apa Itu Big O Notation? Penjelasan Lengkap untuk Memahami Efisiensi Algoritma

Masalah yang Sebenarnya Diselesaikan oleh Big O Notation

Sebelum membahas notasi itu sendiri, ada baiknya memahami masalah spesifik yang ingin diatasi oleh notasi ini. Bayangkan kita telah menulis dua kode berbeda yang keduanya dengan benar menyelesaikan masalah yang sama — misalnya, menemukan apakah angka tertentu ada dalam sebuah daftar. Bagaimana kita memutuskan mana yang sebenarnya lebih baik? Kita dapat menjalankan keduanya di komputer kita sendiri dan mengukur waktunya, tetapi pengukuran itu akan terkait dengan berbagai faktor yang tidak ada hubungannya dengan algoritma itu sendiri, yaitu seberapa cepat prosesor spesifik kita, apa lagi yang sedang dilakukan komputer kita pada saat yang sama, bagaimana bahasa pemrograman spesifik yang kita gunakan diimplementasikan, dan seberapa besar daftar tertentu yang kita uji.

Tidak satu pun dari faktor-faktor tersebut memberi tahu kita sesuatu yang pasti tentang algoritma itu sendiri. Yang sebenarnya ingin kita ketahui adalah pertanyaan yang lebih mendasar, yaitu seiring bertambahnya ukuran input — dari seratus item menjadi satu juta hingga satu miliar — bagaimana jumlah pekerjaan yang harus dilakukan setiap algoritma juga bertambah? Big O notation menjawab pertanyaan itu, dan hanya pertanyaan itu. Algoritma ini sengaja mengabaikan kecepatan perangkat keras, bahasa pemrograman, dan detail implementasi, dan hanya berfokus pada tingkat pertumbuhan yang mendasarinya, yaitu bagaimana penggunaan sumber daya algoritma meningkat seiring dengan bertambahnya ukuran input, yang dinyatakan sebagai fungsi dari ukuran input, yang secara konvensional diberi label n.

Apa Arti Big O Notation Sebenarnya

Secara formal, Big O notation menggambarkan batas atas bagaimana waktu eksekusi atau penggunaan memori suatu algoritma tumbuh relatif terhadap ukuran inputnya, dalam kasus terburuk, ketika ukuran input tersebut mendekati tak terhingga. Itu adalah definisi matematis yang tepat, tetapi intuisi praktisnya lebih sederhana daripada kedengarannya, yaitu Big O menjawab pertanyaan "jika saya menggandakan ukuran input saya, kira-kira berapa banyak pekerjaan tambahan yang perlu dilakukan algoritma ini?"

Notasi itu sendiri ditulis sebagai O diikuti oleh fungsi n dalam tanda kurung — O(n), O(n²), O(log n), dan seterusnya — dan masing-masing mewakili kategori yang berbeda, yang disebut kelas kompleksitas, yang menggambarkan bentuk pertumbuhan tertentu. Yang terpenting, Big O notation sengaja mengabaikan faktor konstanta dan suku-suku tingkat rendah. Algoritma yang melakukan tepat 5n operasi dan algoritma yang melakukan tepat 500n operasi keduanya digambarkan sebagai O(n), karena Big O memperhatikan bentuk kurva pertumbuhan ketika n menjadi besar, bukan jumlah operasi yang tepat pada nilai n tertentu. Awalnya ini mungkin tampak seperti membuang informasi yang berguna, dan dalam arti sempit memang demikian — tetapi inti dari notasi ini adalah untuk menangkap properti yang sebenarnya paling penting saat masalah meningkat, yaitu beban kerja algoritma mana yang tumbuh lebih cepat, bukan algoritma mana yang kebetulan lebih cepat pada input spesifik dengan ukuran tetap saat ini.

Kelas Kompleksitas Umum, Dijelaskan dengan Intuisi Nyata

Memahami Big O secara abstrak jauh kurang bermanfaat daripada memahami seperti apa sebenarnya setiap kelas kompleksitas umum dalam praktiknya, dan membangun intuisi yang tulus tentang bagaimana kelas-kelas ini berperilaku berbeda seiring bertambahnya ukuran input.

O(1): Waktu Konstan

Suatu algoritma adalah O(1), atau waktu konstan, ketika jumlah pekerjaan yang dilakukannya sama sekali tidak bergantung pada ukuran input. Mencari nilai dalam array ketika kita sudah mengetahui indeks pastinya adalah contoh kanonik, yaitu apakah array tersebut memiliki sepuluh elemen atau sepuluh juta, mengambil array[5] membutuhkan langkah tunggal yang sama. Ini adalah kelas kompleksitas tercepat yang mungkin, justru karena ukuran masalah sama sekali tidak berpengaruh pada seberapa banyak pekerjaan yang perlu dilakukan.

O(log n): Waktu Logaritmik

Ini adalah contoh buku telepon dari pengantar, yang diformalkan. Suatu algoritma adalah O(log n) ketika algoritma tersebut dapat berulang kali membagi ruang masalah yang tersisa menjadi dua (atau dengan faktor konstan lainnya) pada setiap langkah, daripada perlu memeriksa setiap elemen secara individual. Pencarian biner adalah contoh klasik, yaitu dengan memeriksa elemen tengah dan menghilangkan setengah dari kemungkinan yang tersisa setiap kali, pencarian biner melalui satu juta item yang diurutkan membutuhkan paling banyak sekitar dua puluh perbandingan, bukan satu juta. Sifat pertumbuhan logaritmik yang benar-benar mencolok adalah betapa lambatnya pertumbuhannya ketika ukuran input meledak — beralih dari seribu item ke satu miliar item hampir tidak mengubah jumlah langkah yang diperlukan, itulah sebabnya kelas kompleksitas ini sangat dihargai setiap kali dapat dicapai.

O(n): Waktu Linier

Suatu algoritma adalah O(n), atau waktu linier, ketika jumlah pekerjaan tumbuh secara langsung, proporsional, dengan ukuran input. Pencari buku telepon pertama kita, memeriksa setiap entri satu per satu hingga menemukan nama yang tepat, adalah O(n), yaitu menggandakan ukuran buku telepon akan menggandakan, kira-kira, jumlah entri yang mungkin perlu diperiksa. Operasi sederhana satu kali jalan seperti mencari nilai maksimum dalam daftar yang tidak terurut, atau menjumlahkan setiap angka dalam sebuah array, adalah operasi O(n) klasik, yaitu kita benar-benar harus melihat setiap elemen setidaknya sekali, dan pekerjaan tersebut berbanding lurus dengan jumlah elemen yang ada.

O(n log n): Waktu Linearithmik

Kelas kompleksitas ini terus muncul dalam algoritma pengurutan yang efisien, dan mewakili semacam jalan tengah, yaitu lebih baik daripada melakukan satu putaran linier penuh untuk setiap elemen (yang akan menjadi n × n), tetapi tidak secepat pertumbuhan logaritmik murni. Algoritma pengurutan berbasis perbandingan yang efisien seperti merge sort dan quicksort (dalam kasus tipikal) mencapai O(n log n), dan dianggap sebagai tolok ukur praktis yang benar-benar kuat untuk masalah yang berkaitan dengan pengurutan — terbukti sebagai yang terbaik yang dapat dicapai oleh pengurutan berbasis perbandingan dalam kasus umum, itulah sebabnya begitu banyak upaya rekayasa selama beberapa dekade telah dilakukan pada algoritma yang mencapai batas ini.

O(n²): Waktu Kuadratik

Suatu algoritma adalah O(n²), atau waktu kuadratik, ketika pekerjaan yang dibutuhkan tumbuh dengan kuadrat ukuran input — biasanya merupakan ciri khas dari loop bersarang, di mana untuk setiap elemen dalam koleksi, kita melakukan satu putaran penuh lagi melalui koleksi tersebut. Pendekatan sederhana untuk memeriksa apakah dua angka dalam sebuah daftar berjumlah sama dengan nilai target, dengan membandingkan setiap pasangan yang mungkin, adalah contoh klasik O(n²): untuk daftar n item, kita melakukan sekitar n × n perbandingan. Pertumbuhan kuadratik adalah di mana masalah mulai menjadi benar-benar menyakitkan pada skala besar — ​​input seribu item berarti sekitar satu juta operasi, dan input satu juta item berarti sekitar satu triliun operasi, beban kerja yang dengan cepat menjadi tidak praktis bahkan pada perangkat keras modern yang cepat.

O(2ⁿ) dan O(n!): Waktu Eksponensial dan Faktorial

Di ujung spektrum terdapat kelas kompleksitas yang menjadi tidak praktis dengan sangat cepat. O(2ⁿ), waktu eksponensial, menggandakan jumlah total pekerjaan dengan setiap elemen tambahan yang ditambahkan ke input, yaitu solusi sederhana dan paksa untuk masalah kombinatorial tertentu, seperti menghasilkan setiap kemungkinan himpunan bagian dari suatu himpunan, menunjukkan perilaku ini, karena himpunan n item memiliki tepat 2ⁿ kemungkinan himpunan bagian. Algoritma O(n!), yang memiliki waktu faktorial, tumbuh lebih eksplosif lagi, dan muncul dalam pendekatan brute-force untuk masalah seperti menemukan rute terpendek melalui sekumpulan kota dengan memeriksa secara harfiah setiap kemungkinan urutan. Algoritma dalam kelas ini hanya benar-benar dapat digunakan untuk ukuran input yang sangat kecil; di luar sejumlah kecil elemen, jumlah operasi yang dibutuhkan melebihi apa pun yang bahkan komputer paling canggih pun dapat selesaikan dalam waktu yang wajar, itulah sebabnya mengapa sebagian besar desain algoritma secara khusus tentang menemukan pendekatan yang lebih cerdas yang sepenuhnya menghindari kelas-kelas ini untuk masalah yang pada awalnya tampaknya membutuhkannya.

Bagaimana Cara Menganalisis Kode untuk Menentukan Kompleksitas Big O-nya

Membangun keterampilan melihat sepotong kode dan menentukan kompleksitas Big O-nya bergantung pada serangkaian kebiasaan yang cukup konsisten, setelah kita memahami logika yang mendasarinya. Titik awalnya adalah mengidentifikasi apa yang sebenarnya diwakili oleh n dalam masalah spesifik tersebut — biasanya ukuran array input, string, atau struktur data — dan kemudian menghitung bagaimana jumlah operasi berhubungan dengan ukuran tersebut saat ukurannya bertambah.

Sebuah loop tunggal yang berulang sekali pada input berukuran n adalah O(n), yaitu jumlah iterasi tumbuh sebanding langsung dengan input. Sebuah loop bersarang di dalam loop lain, di mana loop dalam juga berulang pada seluruh input untuk setiap iterasi loop luar, adalah O(n²), yaitu untuk setiap n iterasi luar, kita melakukan n operasi lain, sehingga total operasi yang kita lakukan adalah n × n. Pola ini meluas secara alami — tiga loop bersarang, masing-masing berulang pada seluruh input, akan menjadi O(n³), dan seterusnya. Saat menganalisis kode dengan beberapa loop atau langkah terpisah (tidak bersarang) yang masing-masing bergantung pada n, kita umumnya menjumlahkan kompleksitas masing-masing daripada mengalikannya, dan kemudian hanya menyimpan suku terbesar, karena Big O memperhatikan pola pertumbuhan dominan saat n menjadi besar, dan suku yang lebih kecil menjadi semakin tidak relevan jika dibandingkan saat n bertambah besar.

Konstanta dihilangkan sepenuhnya dalam analisis ini. Algoritma yang melakukan perulangan melalui array input dua kali, dalam dua lintasan berurutan yang terpisah, secara teknis melakukan 2n operasi — tetapi ini masih digambarkan sebagai O(n), bukan O(2n), karena notasi Big O secara khusus memperhatikan bentuk kurva pertumbuhan, bukan pengali tepat di depannya. Demikian pula, algoritma yang melakukan sejumlah pekerjaan tambahan yang tetap dan terbatas di atas sebuah loop — misalnya, n operasi dari loop ditambah lima operasi konstan di tempat lain — masih O(n), karena biaya lima operasi tetap tersebut tidak bertambah sama sekali saat input bertambah, dan menjadi sangat tidak signifikan relatif terhadap n saat n menjadi besar.

Kasus Terbaik, Kasus Terburuk, dan Kasus Rata-Rata

Penting untuk menjelaskan nuansa penting: notasi Big O, dalam penggunaan yang paling umum, menggambarkan perilaku kasus terburuk suatu algoritma, yaitu jumlah maksimum pekerjaan yang mungkin dibutuhkan untuk ukuran input tertentu, di bawah susunan input yang paling tidak menguntungkan. Ini penting karena banyak algoritma berperilaku sangat berbeda tergantung pada data aktual yang diberikan, bukan hanya ukurannya.

Pencarian linier melalui daftar yang tidak terurut, misalnya, memiliki kasus terbaik O(1) — jika elemen pertama kebetulan adalah yang kita cari, kita langsung selesai — tetapi kasus terburuknya, di mana nilai target adalah elemen terakhir yang diperiksa atau tidak ada sama sekali, adalah O(n). Ketika orang menggambarkan pencarian linier sebagai "O(n)" tanpa kualifikasi lebih lanjut, mereka hampir selalu merujuk pada kasus terburuk ini, karena ini mewakili batas atas yang dijamin tentang berapa banyak pekerjaan yang mungkin dibutuhkan algoritma, terlepas dari bagaimana input tersebut diatur. Analisis kasus rata-rata, yang mempertimbangkan kinerja yang diharapkan di seluruh distribusi representatif dari kemungkinan input, juga merupakan ukuran yang benar-benar berguna dan umum dibahas, terutama untuk algoritma seperti quicksort, yang kinerja kasus rata-ratanya jauh lebih baik daripada kasus terburuknya yang relatif jarang terjadi — tetapi ketika seseorang menyatakan kompleksitas Big O suatu algoritma tanpa menentukan kasus mana yang mereka maksud, asumsi yang aman, dan konvensi standar industri, adalah bahwa mereka maksudkan kasus terburuk.

Big O Bukan Hanya Soal Waktu

Kesalahan umum yang sering terjadi dalam cara orang pertama kali mempelajari Big O notation adalah menganggapnya hanya menggambarkan waktu eksekusi. Padahal, notasi yang sama dan logika yang mendasarinya berlaku sama untuk kompleksitas ruang, yaitu seberapa banyak memori tambahan yang dibutuhkan algoritma, sebagai fungsi dari ukuran inputnya, di luar input itu sendiri. Algoritma yang perlu membuat struktur data baru yang berisi salinan yang telah diubah dari setiap elemen dalam inputnya memiliki kompleksitas ruang O(n), karena memori yang dibutuhkannya tumbuh secara langsung dengan ukuran input tersebut. Algoritma yang memproses inputnya di tempat, hanya menggunakan sejumlah kecil memori tambahan yang tetap terlepas dari seberapa besar inputnya, memiliki kompleksitas ruang O(1).

Perbedaan ini sangat penting dalam keputusan rekayasa nyata, karena kompleksitas waktu dan ruang seringkali saling bertentangan. Contoh klasiknya adalah caching, atau memoisasi: kita seringkali dapat membuat algoritma jauh lebih cepat dalam hal kompleksitas waktu dengan menyimpan, dan menggunakan kembali, hasil yang telah dihitung sebelumnya, tetapi melakukannya membutuhkan memori tambahan yang tumbuh seiring dengan jumlah hasil unik yang kita simpan. Baik versi algoritma yang lebih cepat dan lebih boros memori maupun versi yang lebih lambat dan lebih hemat memori bukanlah sesuatu yang secara abstrak "lebih baik" tanpa syarat, tetapi pilihan yang tepat sepenuhnya bergantung pada sumber daya mana — waktu pemrosesan atau memori yang tersedia — yang sebenarnya lebih terbatas dan berharga dalam sistem spesifik yang kita bangun.

Kesalahpahaman Umum yang Perlu Diluruskan

Salah satu kesalahpahaman yang paling sering terjadi adalah memperlakukan Big O sebagai ukuran langsung dan literal dari kecepatan dunia nyata, yaitu mengasumsikan bahwa algoritma O(n) akan selalu berjalan lebih cepat dalam praktiknya daripada algoritma O(n²). Ini tidak sepenuhnya benar, dan ini merupakan nuansa penting: Big O menggambarkan perilaku asimtotik, artinya prediksinya menjadi andal khususnya ketika n semakin besar, bukan pada setiap kemungkinan ukuran input. Karena Big O sengaja mengabaikan faktor konstanta, algoritma O(n²) dengan faktor konstanta yang sangat kecil benar-benar dapat mengungguli algoritma O(n) dengan faktor konstanta yang besar, untuk input berukuran kecil atau bahkan sedang — kerugian algoritma kuadratik hanya akan mendominasi secara andal setelah n tumbuh cukup besar sehingga perbedaan laju pertumbuhan mengalahkan perbedaan konstanta. Inilah mengapa, dalam rekayasa dunia nyata, algoritma tertentu dengan kompleksitas Big O yang secara teknis lebih buruk masih sengaja dipilih untuk situasi yang melibatkan input kecil secara konsisten, di mana kesederhanaan atau overhead konstanta yang lebih rendah benar-benar menang dalam praktiknya.

Kesalahpahaman umum kedua adalah menganggap bahwa kompleksitas Big O yang "lebih baik" selalu layak dikejar, terlepas dari biaya sebenarnya, dalam hal waktu rekayasa dan kompleksitas kode, untuk mencapainya. Dalam praktiknya, algoritma yang sederhana, mudah dibaca, dan O(n log n) seringkali merupakan pilihan rekayasa yang benar-benar tepat dibandingkan algoritma yang jauh lebih kompleks dan lebih sulit dipelihara yang mengurangi kompleksitasnya menjadi O(n), kecuali jika peningkatan kinerja spesifik tersebut benar-benar dibutuhkan pada skala di mana sistem akan beroperasi secara realistis. Big O adalah alat untuk berpikir jernih tentang skalabilitas, bukan papan skor di mana nilai yang lebih rendah secara otomatis lebih baik dalam setiap situasi tanpa memandang konteks.

Mengapa Big O Notation Benar-Benar Penting dalam Praktik

Big O Notation memiliki reputasi yang berlebihan sebagai topik wawancara teknis, dan memang benar bahwa pewawancara umumnya meminta kandidat untuk menganalisis atau mengoptimalkan kompleksitas suatu solusi. Tetapi memperlakukan Big O hanya sebagai ritual wawancara sangat meremehkan pentingnya yang sebenarnya dan praktis. Sistem nyata benar-benar menghadapi kesenjangan antara kelas kompleksitas dengan cara yang memiliki konsekuensi langsung dan nyata, yaitu fitur pencarian yang dibangun dengan kompleksitas O(n) mungkin terasa sangat responsif selama pengembangan dan pengujian terhadap kumpulan data sampel kecil, dan kemudian menjadi lambat secara nyata dan tidak dapat diterima setelah basis pengguna nyata dan volume data nyata suatu produk meningkat beberapa orde besarnya, pada titik tersebut kesenjangan antara perilaku linier dan logaritmik — atau antara linier dan kuadratik — berhenti menjadi masalah teoretis dan menjadi masalah kinerja nyata yang dihadapi pengguna.

Pemahaman yang baik tentang Big O juga membentuk cara para insinyur mengevaluasi pertimbangan selama perancangan sistem secara lebih luas, yaitu memilih struktur data yang tepat untuk pola akses tertentu, memutuskan apakah strategi caching tertentu sepadan dengan biaya memorinya, atau mengenali sejak awal bahwa pendekatan yang tampaknya masuk akal untuk suatu masalah akan menjadi benar-benar tidak dapat diterapkan setelah ukuran input yang sebenarnya perlu ditangani sistem dalam produksi diperhitungkan. Jenis penilaian ini, yaitu mengantisipasi bagaimana keputusan desain akan bertahan seiring peningkatan skala, daripada hanya mengevaluasi apakah keputusan tersebut berfungsi dengan benar pada kasus uji spesifik dan sederhana yang ada di hadapan kita saat ini — adalah keterampilan teknik yang benar-benar mendasar, dan Big O notation adalah kosakata bersama dan tepat yang memungkinkan untuk menalar dan mengkomunikasikan penilaian tersebut dengan jelas.

Jadi, Big O notation memberi ilmu komputer dan software engineering bahasa yang tepat dan independen dari perangkat keras untuk menggambarkan bagaimana penggunaan sumber daya suatu algoritma — waktu atau memori — tumbuh seiring dengan pertumbuhan inputnya, yang secara khusus berfokus pada bentuk pertumbuhan yang mendasarinya daripada pengukuran tertentu yang diambil pada mesin tertentu pada saat tertentu. Dari pencarian yang hampir instan O(1), melalui penskalaan yang sangat efisien O(log n), proporsionalitas langsung O(n), dan seterusnya hingga pertumbuhan yang semakin berat O(n²) dan seterusnya, setiap kelas kompleksitas menggambarkan hubungan yang benar-benar berbeda antara ukuran masalah dan pekerjaan yang dibutuhkan, dan memahami perbedaan praktis di antara mereka adalah salah satu keterampilan yang paling tahan lama dan dapat ditransfer di seluruh ilmu komputer.