Comparing algorithms and ADTs in algorithms
Diperkenalkan
15:32
Pencarian & Pengurutan
Buku telepon dengan satu juta nama. Jika Anda memeriksanya satu per satu, Anda mungkin melakukan satu juta perbandingan. Namun Anda sudah tahu triknya: buka di tengah…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| Big-O/bɪɡ əʊ/ | Notasi 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/ | pencarian kedalaman |
| breadth-first/bredθ fɜːst/ | pencarian lebar |
| 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
How running time grows with n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs.
Which Big-O describes binary search?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Linear search is 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.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 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.
An "in place" sort:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
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.
Which statements about Big-O are correct? Select semua that apply.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
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.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
Nilai yang mudah 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