Kompleksitas Waktu dan Kompleksitas Ruang Suatu Algoritma Dijelaskan
Bayangkan dua program yang melakukan pekerjaan yang persis sama. Beri masing-masing program seribu data dan Anda tidak dapat membedakannya. Namun, beri mereka satu miliar data, dan salah satunya selesai sebelum Anda melepaskan tombol Enter sementara yang lain masih terus berjalan hingga Selasa depan.
Laptop yang sama. Data yang sama. Yang membedakannya adalah kompleksitas waktu, yang hanyalah istilah untuk seberapa cepat beban kerja algoritma meningkat seiring bertambahnya input yang diberikan.
Kita akan membahas apa arti istilah tersebut sebenarnya, bagaimana notasi Big O menuliskannya, bagaimana cara menghitungnya dari kode nyata, dan di mana kompleksitas ruang berperan. Kemudian, di bagian akhir, kita akan sampai pada titik di mana semua ini berhenti menjadi pekerjaan rumah dan mulai membutuhkan biaya nyata: kontrak pintar.
Apa itu kompleksitas waktu suatu algoritma?
Lupakan detik sejenak. Kompleksitas waktu menghitung langkah-langkah. Perbandingan, penugasan, sedikit aritmatika di sana-sini, dan Anda menulis totalnya sebagai fungsi dari n, yang merupakan ukuran input.
Inilah fungsi paling membosankan yang bisa dibayangkan:
Python def print_all(items): for item in items: print(item)
Sepuluh barang? Sepuluh kali perjalanan melalui jalur yang sama. Sepuluh ribu? Sepuluh ribu perjalanan.
Pekerjaan tersebut menanjak dalam garis lurus di samping input, jadi kita menyebutnya O(n).
Nah, mungkin setiap perjalanan sebenarnya membutuhkan tiga operasi kecil, bukan satu. Baiklah, itu 3n. Sejujurnya, tidak ada yang peduli, karena menggandakan daftar tetap menggandakan pekerjaan, dan kurva pertumbuhan itulah yang kita inginkan. Angka pastinya sengaja diabaikan.
Itulah mengapa setiap kursus DSA dan separuh wawancara pemrograman di luar sana selalu menekankan kompleksitas waktu. Jika Anda dapat membaca kompleksitas suatu algoritma hanya dengan melihatnya, Anda dapat menebak bagaimana algoritma tersebut akan berperilaku pada data input yang belum pernah Anda uji. Dan, dalam lingkungan produksi, sebagian besar data memang demikian.
Mengapa Waktu Eksekusi Merupakan Ukuran yang Buruk untuk Suatu Algoritma
Jadi mengapa tidak menjalankan program tersebut dengan menggunakan timer saja? Banyak orang melakukannya, dan saya mengerti. Masalahnya adalah waktu eksekusi akan menyeret sejumlah hal yang tidak ada hubungannya dengan algoritma Anda:
- Perangkat keras. Laptop saya yang berusia lima tahun dan sebuah kotak cloud baru akan memberikan angka yang sangat berbeda untuk skrip yang sama.
- Bahasa pemrograman. Tulis loop yang sama dalam C dan Python, dan Anda mungkin akan melihat perbedaan 10 kali lipat, atau lebih.
- Beban sistem. Beberapa pembaruan latar belakang berjalan, pengumpul sampah (garbage collector) aktif, cache menjadi dingin. Hasil Anda dipindahkan.
- Apa pun input yang Anda ambil. Pengurutan yang berjalan cepat pada data yang hampir terurut dapat berjalan lambat pada data yang diacak.
Stopwatch hanya memberikan satu hasil pengukuran pada satu kotak dengan satu input. Namun, jika Anda meminta data 100 kali lipat, stopwatch tidak memberikan hasil apa pun.
Jumlah langkah tidak akan berubah. Algoritma yang sama, input yang sama, dan Anda akan mendapatkan jumlah langkah yang sama, baik itu Rust di server rak atau JavaScript di ponsel seseorang. Itulah mengapa kompleksitas waktu adalah pertarungan yang adil antara dua solusi sebelum Anda melakukan benchmark apa pun. Saya tetap akan melakukan benchmark setelahnya, untuk sekadar informasi. Itu hanya pertanyaan yang berbeda.
Penjelasan tentang Notasi Big O dan Notasi Asimtotik Lainnya
Buku teks menyebut ini notasi asimtotik, yang terdengar lebih buruk daripada kenyataannya. Anda membiarkan n menjadi sangat besar dan berhenti memperhatikan hal-hal kecil, sehingga pengali konstan dan input kecil hilang dan hanya kurva pertumbuhan yang tersisa. Ada tiga di antaranya yang perlu diketahui:
| Notasi | Apa yang dijelaskannya | Arti sederhana | Contoh |
|---|---|---|---|
| Big O, O(f(n)) | Batas atas | Algoritma tersebut tidak tumbuh lebih cepat dari f(n) | Pencarian linear adalah O(n) |
| Big-Omega, Ω(f(n)) | Batas bawah | Algoritma tersebut membutuhkan setidaknya f(n) pekerjaan. | Setiap pengurutan perbandingan adalah Ω(n log n) |
| Big-Theta, Θ(f(n)) | Terikat erat | Batas atas dan bawah cocok | Merge sort adalah Θ(n log n) |
Dalam praktiknya, Anda akan mendengar notasi Big O sekitar 95% dari waktu. Notasi ini menetapkan batas atas, yang berarti waktu eksekusi tidak akan bertambah lebih cepat daripada laju di dalam tanda kurung. Ulasan kode pertama saya di pekerjaan nyata melibatkan seorang pengembang senior yang menulis "O(n²), pls fix" di samping loop bersarang, dan yang mereka maksud adalah kompleksitas waktu kasus terburuk adalah kuadratik dan daftar tersebut akan menjadi jauh lebih panjang.
Omega dan Theta sebagian besar digunakan dalam mata kuliah universitas tentang analisis algoritma, dan saya rasa saya sudah bertahun-tahun tidak mengetik keduanya di tempat kerja. Big O menang karena menjawab apa yang sebenarnya ditanyakan orang dalam rapat, yaitu "seberapa buruk dampaknya jika lalu lintas meningkat tiga kali lipat?"
Ada satu hal teknis yang membingungkan saya untuk sementara waktu. Karena Big O hanyalah batas atas, fungsi O(n) juga O(n²), secara harfiah, sama seperti orang yang tingginya 5 kaki adalah "di bawah 7 kaki." Benar dan tidak berguna. Setiap orang mengutip batasan terketat yang dapat mereka benarkan dan saya akan melakukan hal yang sama.
Kelas Kompleksitas Waktu Umum Beserta Contohnya
Tidak banyak kelas yang akan Anda temui dalam kode sebenarnya, mungkin hanya tujuh jika Anda menghitung yang rumit. Kira-kira beginilah biaya masing-masing kelas pada n = 1.000:
| Kelas | Nama | Contoh umum | Operasi pada n = 1.000 |
|---|---|---|---|
| O(1) | Konstan | Indeks array, pencarian tabel hash | 1 |
| O(log n) | Logaritmik | Pencarian biner | ~10 |
| Pada) | Linier | Memindai daftar | 1.000 |
| O(n log n) | Linearithmik | Merge sort, quicksort (rata-rata) | ~10.000 |
| O(n²) | Kuadrat | Perulangan bersarang, pengurutan gelembung | 1.000.000 |
| O(2ⁿ) | Eksponensial | Fibonacci rekursif naif | Lebih dari sekadar atom di alam semesta |
| Pada!) | Faktorial | tenaga penjualan keliling yang menggunakan kekuatan kasar | Bahkan lebih besar |
O(1): Waktu Konstan
Baik kamus Python Anda memiliki sepuluh kunci atau sepuluh juta, mengambil satu kunci berdasarkan kunci biayanya hampir sama, begitu pula membaca item[5] dari sebuah daftar. Kesederhanaan itulah inti dari waktu konstan.
O(log n): Waktu Logaritmik
Saya menganggap ini sebagai algoritma "menebak angka antara 1 dan 100", di mana setiap tebakan menyingkirkan setengah dari yang tersisa. Pencarian biner melakukan hal yang sama pada daftar yang sudah diurutkan:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Dengan satu miliar item yang sudah diurutkan, dibutuhkan sekitar 30 perbandingan, sementara jika diproses satu per satu bisa memakan waktu hingga satu miliar, dan saya tidak pernah berhenti menganggap itu lucu.
O(n) dan O(n log n)
Algoritma linear mengunjungi setiap elemen sejumlah kali yang tetap, seperti halnya Anda mencari angka terbesar dalam kolom spreadsheet secara manual. O(n log n) adalah batas untuk pengurutan yang baik. Merge sort membagi daftar menjadi item tunggal (log n level pembagian) dan kemudian melakukan satu proses linear per level sambil menggabungkan, sehingga waktu eksekusinya tetap sama terlepas dari apakah data datang dalam keadaan terurut atau acak.
O(n²) dan Lebih Buruk
Kode kuadratik hampir selalu memiliki loop yang terselip di dalam loop lain, seperti pengecekan duplikat ini yang membandingkan setiap pasangan:
Python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Pertumbuhan eksponensial dan faktorial jauh lebih buruk. Deret Fibonacci rekursif dalam buku teks terus menyelesaikan submasalah yang sama berulang kali, sehingga setiap penambahan 1 pada n kira-kira menggandakan pekerjaan. Pada n = 20 Anda tidak akan menyadarinya; pada n = 60 Anda bisa memasak makan malam, memakannya, mencuci piring, dan pekerjaan itu masih belum selesai.
Cara Menghitung Kompleksitas Waktu Langkah demi Langkah
Anda hampir tidak pernah membutuhkan bukti formal untuk menghitung kompleksitas waktu. Saya memikirkan daftar ini dan itu mencakup sebagian besar kode yang saya lihat:
- Definisikan n. Tentukan ukuran input: panjang sebuah daftar, jumlah node dalam sebuah graf, jumlah digit dalam sebuah angka.
- Hitung pekerjaan di setiap baris. Pernyataan sederhana (penugasan, perbandingan, aritmatika) membutuhkan biaya O(1).
- Tambahkan blok berurutan. Dua loop yang berurutan, masing-masing melewati n, menghasilkan n + n = 2n.
- Kalikan blok bersarang. Sebuah loop dengan n di dalam loop lain dengan n menghasilkan n × n = n².
- Hilangkan konstanta. 2n menjadi n, dan 500 menjadi 1.
- Pertahankan hanya suku yang dominan. Dalam n² + n, bagian n² menjadi jauh lebih besar daripada bagian lainnya seiring bertambahnya nilai n.
Selesai dengan cepat. Perhitungan Anda menjadi T(n) = 3n² + 5n + 2. Masukkan satu juta: 3n² adalah tiga triliun, 5n adalah lima juta. Kesalahan pembulatan. Sebut saja O(n²), selesai.
Perulangan yang melompati satu per satu alih-alih melangkah satu per satu lebih licik:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Setiap putaran mengurangi n menjadi setengahnya, sehingga loop while ini berhenti setelah kira-kira log₂(n) putaran. Yang pada dasarnya merupakan jawaban lengkap untuk pertanyaan "kapan kompleksitas waktu menjadi O(log n)?" Jika sisa yang ada menyusut dengan faktor konstan setiap langkahnya, maka kompleksitas waktunya adalah O(log n).
Rekursi membutuhkan satu alat lagi, yaitu rekurensi. Pengurutan gabungan (merge sort) melakukan dua pekerjaan setengah ukuran dan kemudian penggabungan, sehingga T(n) = 2T(n/2) + n. Teorema master adalah contekan untuk rekurensi dengan bentuk seperti itu, dan untuk yang satu ini menghasilkan O(n log n).
Dan aturan praktis dari pemrograman kompetitif yang sering saya gunakan: mesin normal dapat menyelesaikan sekitar 10⁸ operasi sederhana per detik. Ini sangat kasar, tetapi cukup untuk memeriksa kompleksitas waktu suatu solusi sebelum Anda menekan tombol kirim. Dengan n sebesar 10⁵, O(n²) adalah sekitar 10¹⁰ operasi, jadi Anda akan kehabisan waktu. O(n log n) kurang dari 2 juta. Berjalan lancar.
Analisis Kasus Terburuk, Kasus Terbaik, dan Kasus Rata-Rata
Jika algoritma yang sama diberi input yang berbeda, jumlah pekerjaan yang harus dilakukan dapat berubah secara drastis. Pencarian linear menunjukkannya dengan baik:
- Skenario terbaik: apa yang Anda inginkan berada tepat di depan. Satu perbandingan saja dan Anda tersingkir.
- Skenario terburuk: letaknya di paling akhir, atau sama sekali tidak ada. Itu bukan perbandingan.
- Kasus rata-rata: jika bisa terjadi di mana saja dengan peluang yang sama, Anda akan memeriksa sekitar n/2 secara rata-rata. Tetap saja O(n), perlu diingat.
Tanyakan kepada seorang pengembang tentang "kompleksitas" sesuatu dan mereka hampir selalu akan memberi Anda kompleksitas waktu terburuk, karena angka itu adalah janji yang dapat Anda jadikan acuan perencanaan.
Misalkan API Anda menangani permintaan dalam waktu O(n) paling buruk. Bagus, sekarang Anda tahu bagaimana perilaku permintaan paling lambat, dan Anda juga terlindungi ketika seseorang sengaja mengirimkan data sampah kepada Anda. Orang-orang memang melakukan ini: jika penyerang mengetahui kunci mana yang menyebabkan tabel hash Anda bertabrakan, maka hanya kunci itulah yang akan Anda lihat untuk sementara waktu.
Kasus rata-rata layak diperhatikan karena skenario buruk jarang terjadi. Quicksort adalah contoh terbaik di sini, dengan rata-rata O(n log n) tetapi bisa merosot menjadi O(n²) jika Anda memilih pivot secara naif pada data yang sudah diurutkan. Pustaka standar mengatasi hal itu dengan pivot acak, atau dengan beralih ke algoritma pengurutan yang berbeda setelah rekursi menjadi terlalu dalam.
Apa Itu Kompleksitas Ruang dan Ruang Tambahan?
Memori adalah biaya lain yang dikeluarkan oleh sebuah algoritma. Kompleksitas ruang melacak seberapa banyak memori yang Anda butuhkan seiring bertambahnya ukuran input, dan Anda menuliskannya dengan notasi Big O yang sama seperti waktu.
Sebagian dari memori itu adalah input itu sendiri, yang tetap Anda bayar apa pun yang Anda lakukan dengannya. Bagian yang sebenarnya Anda kendalikan disebut ruang tambahan, artinya hal-hal ekstra yang dialokasikan kode Anda saat bekerja, seperti variabel sementara dan array baru, ditambah tumpukan panggilan yang tidak diingat siapa pun sampai mereka mengalami masalah.
Beberapa contoh singkat:
- Menukar dua variabel membutuhkan beberapa slot terlepas dari hal lainnya, jadi ini adalah ruang tambahan O(1).
- Menyalin daftar berisi n item ke dalam daftar baru akan membutuhkan memori tambahan sebesar O(n).
- Melakukan rekursi sedalam n level akan menyisakan n frame yang berada di tumpukan, yang membutuhkan ruang O(n) meskipun Anda tidak pernah membuat array.
Saya menyaksikan seorang pengembang junior menghabiskan satu sore untuk masalah terakhir itu. Fungsi rekursif mereka tampaknya tidak menggunakan memori sama sekali, tetapi setiap panggilan yang belum selesai tertahan di tumpukan menunggu panggilan yang lebih dalam untuk selesai, dan pada input yang besar, semuanya gagal karena stack overflow.
Banyak optimasi hanyalah menukar memori dengan waktu atau sebaliknya. Memoization menyimpan hasil yang telah Anda hitung, yang mengurangi waktu Fibonacci sederhana dari O(2ⁿ) menjadi O(n) dengan imbalan memori O(n). Tabel hash memberi Anda pencarian rata-rata O(1) dengan menghabiskan ruang pada bucket. Pada server dengan RAM 64 GB, pertukaran itu biasanya mudah, tetapi pada mikrokontroler atau di dalam kontrak pintar, Anda akan berpikir dua kali.
Kompleksitas Waktu dan Ruang dari Struktur Data Umum
Memilih struktur data yang tepat biasanya lebih baik daripada melakukan penyesuaian mikro pada apa pun yang ada di dalam loop Anda. Biaya rata-rata untuk struktur data yang paling sering Anda gunakan adalah:
| Struktur data | Mengakses | Mencari | Menyisipkan | Menghapus | Ruang angkasa |
|---|---|---|---|---|---|
| Susunan | O(1) | Pada) | Pada) | Pada) | Pada) |
| Daftar tertaut | Pada) | Pada) | O(1) | O(1) | Pada) |
| Tabel hash | tidak tersedia | O(1) | O(1) | O(1) | Pada) |
| Pohon pencarian biner seimbang | O(log n) | O(log n) | O(log n) | O(log n) | Pada) |
| Tumpukan biner | O(1) untuk min/max | Pada) | O(log n) | O(log n) | Pada) |
Dua catatan kaki. Penyisipan dan penghapusan pada linked list hanya O(1) jika Anda sudah memegang node tersebut. Dan hash table dapat merosot ke O(n) ketika banyak kunci bertabrakan.
Algoritma pengurutan juga sangat beragam:
| Algoritma pengurutan | Terbaik | Rata-rata | Terburuk | Ruang tambahan |
|---|---|---|---|---|
| Pengurutan gelembung | Pada) | O(n²) | O(n²) | O(1) |
| Pengurutan gabungan | O(n log n) | O(n log n) | O(n log n) | Pada) |
| Pengurutan cepat | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Susun tumpukan | O(n log n) | O(n log n) | O(n log n) | O(1) |
Merge sort hasilnya dapat diprediksi tetapi membutuhkan memori tambahan. Heap sort melakukan pengurutan di tempat dan mempertahankan hasil terburuk yang sama. Quick sort, meskipun memiliki batasan yang kurang ideal, cenderung lebih unggul dalam praktiknya.
Kompleksitas Waktu dalam Blockchain dan Kontrak Pintar
Di sinilah letak keseruannya. Di server Anda sendiri, algoritma yang ceroboh akan membuang CPU dan mungkin mengganggu pengguna. Di Ethereum atau rantai EVM lainnya, hal itu akan membuang uang. Setiap opcode yang dieksekusi oleh smart contract membutuhkan gas, yang dibayar dengan koin asli rantai tersebut, sehingga jumlah operasi Anda akan muncul sebagai tagihan seseorang. Dengan kata lain, kompleksitas waktu yang buruk memiliki harga tersendiri.
Misalnya, Anda memiliki kontrak yang berulang melalui setiap pemegang token untuk membayar hadiah. O(n), dan biaya gas meningkat seiring bertambahnya jumlah pemegang token. Pada hari peluncuran, tidak ada yang menyadarinya.
Kemudian daftar pemegang terus bertambah. Suatu hari pembayaran membutuhkan lebih banyak gas daripada batas gas blok, yaitu batas maksimal jumlah gas yang dapat ditampung oleh satu blok. Setelah itu, transaksi tidak dapat diproses. Bukan karena "lambat." Transaksi tersebut memang tidak pernah berhasil, dan dana apa pun yang menunggu di balik fungsi tersebut pada dasarnya akan macet. Auditor mencatat loop tak terbatas seperti ini sebagai pelanggaran penolakan layanan, dan itu wajar.
Solusinya adalah pemikiran kompleksitas, sesederhana itu:
- Bagilah pekerjaan menjadi beberapa bagian dengan ukuran tetap yang dibagi menjadi beberapa transaksi.
- Balikkan sehingga setiap pengguna mengklaim hadiahnya sendiri. Setiap panggilan adalah O(1).
- Gantikan perulangan dengan pembuktian Merkle.
Saya menyukai bukti Merkle sebagai contoh mengapa log n sangat penting di dalam blockchain. Pohon Merkle menghash sejumlah besar data menjadi satu hash akar.
Untuk membuktikan bahwa satu entri termasuk dalam himpunan n, Anda membutuhkan sekitar log₂(n) hash. Untuk satu juta entri, itu kira-kira 20. Bukan satu juta. Airdrop mengandalkan ini, dan dompet Bitcoin ringan menggunakan trik yang sama untuk mengkonfirmasi transaksi tanpa mengunduh seluruh blok.
Di luar blockchain, situasinya sama. Bayangkan sebuah sistem pembayaran yang mencocokkan setiap transaksi blockchain yang masuk dengan faktur dengan memindai setiap faktur yang terbuka. O(n) per pembayaran, dan akan semakin lambat seiring pertumbuhan toko. Masukkan faktur-faktur tersebut ke dalam hash map yang dikunci berdasarkan alamat atau ID, dan setiap pencocokan hanya membutuhkan waktu O(1). Dan jika Anda tidak ingin membangun dan mengelola sistem tersebut sendiri, gateway pembayaran kripto seperti Plisio dapat melakukannya untuk Anda.
