Membandingkan algoritma dan ADT dalam algoritma
| English | Bahasa Indonesia |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | kompleksitas waktu |
| space complexity/speɪs kəmˈpleksɪti/ | kompleksitas ruang |
| depth-first/depθ fɜːst/ | depth-first |
| breadth-first/bredθ fɜːst/ | breadth-first |
| binary tree/ˈbaɪnəri triː/ | pohon biner |
Algoritma yang akan bertahan melampaui alam semesta
- Seorang salesman harus mengunjungi 25 kota dan kembali ke rumah melalui rute terpendek. Cobalah setiap urutan dan ada sekitar $10^{23}$ di antaranya. Mesin yang memeriksa satu miliar per detik akan membutuhkan tiga juta tahun.
- Tambahkan satu kota lagi dan kerjanya berlipat ganda 25 kali. Itu bukan komputer yang perlu lebih cepat; itu adalah pendekatan yang tidak pernah bisa berhasil, pada kecepatan apa pun, pada perangkat keras apa pun.
- Mengetahui hal ini sebelum Anda menulis program adalah tujuan dari analisis kompleksitas. Ini adalah perbedaan antara memilih algoritma dan menemukan, beberapa bulan kemudian, bahwa kode Anda tidak dapat diskalakan.
- Pelajaran ini adalah Big-O untuk waktu dan ruang, serta bagaimana ADT membentuk algoritma yang dibangun di atasnya.
Kompleksitas waktu
- Kompleksitas waktu menjelaskan bagaimana waktu eksekusi bertambah seiring ukuran input $n$. Ditulis dalam notasi Big-O, yang hanya mempertahankan suku dominan dan mengabaikan konstanta.
- $O(1)$ konstan, waktu tidak bergantung pada $n$ sama sekali. $O(\log n)$ logaritmik, seperti dalam pencarian biner. $O(n)$ linear, seperti dalam pencarian linear. $O(n \log n)$, pengurutan yang baik. $O(n^2)$ kuadratik, seperti dalam bubble sort dan insertion sort.
- Alasan konstanta diabaikan: mereka tertutupi. Algoritma $O(n^2)$ mungkin mengalahkan algoritma $O(n \log n)$ untuk $n = 10$, tetapi pada $n = 10{,}000$ tidak ada yang bisa diselamatkan oleh konstanta.
Kurva bersilangan sekali, dan setelah itu urutan menentukan segalanya
Bagaimana waktu eksekusi bertambah seiring n
Geser n ke atas dan bandingkan kurvanya: O(1) dan O(log n) tetap hampir datar, O(n) naik secara stabil, O(n²) meledak. Inilah mengapa Big-O — bukan stopwatch — digunakan untuk membandingkan algoritma pada input besar.
Big-O manakah yang mendeskripsikan binary search?
Pengurangan rentang separuh setiap langkah adalah logaritmik — O(log n).
Big-O manakah yang mendeskripsikan bubble sort dalam kasus terburuk?
Dua loop bersarang atas n elemen menghasilkan O(n²).
Pasangkan setiap algoritma dengan kompleksitas waktunya.
Linear search adalah O(n), binary search O(log n), bubble sort O(n²).
Contoh terpecahkan: apa yang dilakukan penggandaan input
- Algoritma membutuhkan 4 detik untuk 1,000 item. Perkirakan waktunya untuk 2,000 item jika algoritma tersebut $O(n)$, lalu jika $O(n^2)$.
- $O(n)$: menggandakan $n$ menggandakan waktu, jadi sekitar 8 detik.
- $O(n^2)$: menggandakan $n$ menguadratkan waktu, sehingga sekitar 16 detik. Pada 10,000 item akan menjadi 100 kali lipat dari yang asli, sekitar 400 detik.
- $O(\log n)$ hanya akan menambah satu langkah, dan $O(1)$ tidak akan berubah sama sekali. Reasonkan berdasarkan urutan, bukan berdasarkan rumus.
Algoritma O(n kuadrat) membutuhkan waktu 4 detik untuk 1,000 item. Sekitar berapa detik yang dibutuhkan untuk 2,000?
Menggandakan n mengkuadratkan waktu O(n kuadrat). Penggandaan yang sama pada algoritma O(n) akan mengubah waktu dari 4 detik menjadi 8.
Kompleksitas ruang
- Kompleksitas ruang adalah tambahan memori yang dibutuhkan algoritma, melebihi input itu sendiri.
- Bubble sort dan insertion sort menggunakan $O(1)$ memori tambahan: mereka bekerja in place, hanya memerlukan beberapa variabel. Merge sort menggunakan $O(n)$, karena membangun array kedua.
- Rekursi menggunakan memori stack sebanding dengan kedalaman-nya, karena setiap panggilan yang belum selesai menyimpan frame-nya sendiri.
- Seringkali ada trade-off waktu dan memori: menyimpan hasil untuk menghindari menghitung ulang, seperti yang dilakukan memoisasi, membeli kecepatan dengan ruang.
Apa lagi yang memutuskan pilihan
- Big-O berkaitan dengan pertumbuhan, bukan kecepatan absolut. Untuk $n$ yang kecil, algoritma sederhana $O(n^2)$ bisa mengalahkan algoritma rumit $O(n \log n)$, dan lebih mudah ditulis dengan benar.
- Stabilitas penting ketika daftar sudah diurutkan berdasarkan bidang lain. Kesederhanaan penting karena algoritma sederhana memiliki lebih sedikit tempat untuk menyembunyikan bug.
- Jawaban jujur untuk "algoritma mana" sering menyebutkan urutan dan kondisinya: ini, karena $n$ besar dan datanya tiba tanpa urutan.
Sortir "in place":
Algoritma in-place (seperti bubble dan insertion sort) mengurutkan di dalam array asli, menggunakan ruang ekstra konstan.
Mengapa kompleksitas ruang bubble sort adalah O(1) meskipun mengurutkan array berisi n item?
Ini mengurutkan in-place. Merge sort adalah O(n) karena membangun array kedua, dan biaya rekursi sebanding dengan kedalamannya.
ADT di dalam algoritma
- Tipe data abstrak dari topik 10 adalah mesin yang algoritma dibangun darinya, dan memilih salah satu membentuk algoritmanya.
- Stack memberikan pencarian depth-first: dorong tetangganya, ambil yang paling baru, dan pencarian menyelam ke bawah satu jalur sebelum mundur. Rekursi menggunakan call stack untuk hal yang sama persis.
- Queue memberikan pencarian breadth-first:Speechkan tetangganya, ambil yang tertua, dan pencarian menyebar keluar dalam cincin, yang merupakan cara menemukan jalur terpendek dalam graf tak berbobot.
- Pohon biner menjaga nilai dalam urutan sehingga pencarian membuang setengah simpul yang tersisa di setiap langkah, memberikan pencarian biner's $O(\log n)$ atas struktur yang juga dapat tumbuh.
Pernyataan manakah tentang Big-O yang benar? Pilih semua yang berlaku.
Big-O tidak menyebut apa-apa tentang detik; ini tentang pertumbuhan. Itulah mengapa titik potong dengan algoritma sederhana ada pada ukuran kecil.
Contoh terpecahkan: graf yang sama, dua pencarian
- Labirin dieksplorasi dari satu pintu masuk. Bandingkan penggunaan stack dengan penggunaan queue.
- Dengan stack, jalur yang ditemukan terakhir dieksplorasi berikutnya, jadi pencarian turun dalam ke satu rute hingga buntu, lalu mundur. Menggunakan memori sebanding dengan kedalaman jalur.
- Dengan queue, jalur yang ditemukan paling lama dieksplorasi berikutnya, jadi pencarian memeriksa segala sesuatu yang berjarak satu langkah, lalu segala sesuatu yang berjarak dua langkah. Menemukan rute terpendek pertama, tetapi menahan setiap posisi pada jarak saat ini di memori.
- Sebutkan ADT, sebutkan urutan eksplorasi yang dihasilkan, dan sebutkan akibatnya.
Stack (LIFO) secara alami mendorong traversal depth-first, sedangkan queue (FIFO) mendorong traversal breadth-first.
ADT yang Anda pilih menentukan urutan pencarian — stack masuk dalam terlebih dahulu, queue menjelajah tingkat demi tingkat.
Pasangkan setiap ADT dengan pencarian yang dihasilkan dan konsekuensinya.
Terbaru pertama atau tertua pertama. Pilihan tunggal ini yang menentukan apakah pencarian masuk dalam atau melebar.
⟦⟧ Nilai yang sering terlewat
- Big-O menggambarkan pertumbuhan dengan ukuran input, bukan detik. "Cepat" bukanlah jawaban kompleksitas.
- Menggandakan input menggandakan waktu $O(n)$ dan menggandakan empat kali (kuadruplik) waktu $O(n^2)$. Reasonkan berdasarkan urutan.
- Kompleksitas ruang adalah memori tambahan, sehingga pengurutan in-place memiliki $O(1)$ meskipun ukurannya array $n$.
- Stack memberikan pencarian kedalaman, queue memberikan pencarian lebar. Mendapatkan pasangan ini dengan benar adalah inti dari beberapa soal.
Anda telah memahaminya
- kompleksitas waktu dalam Big-O menggambarkan pertumbuhan dengan $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; konstanta diabaikan karena pada skala besar urutan yang menentukan
- menggandakan $n$ menggandakan $O(n)$ dan mengkuadratkan $O(n^2)$; titik potong dengan algoritma "lebih buruk" hanya ada untuk $n$ kecil
- kompleksitas ruang adalah memori tambahan: pengurutan in place adalah $O(1)$, merge sort adalah $O(n)$, dan rekursi membebani kedalaman stack
- stack memberikan pencarian kedalaman, queue memberikan pencarian lebar, dan pohon biner mengurangi setengah simpul tersisa pada setiap langkah