Efisiensi Algoritmik
Diperkenalkan| English | Makna |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | efisiensi algoritmik |
| slow/sləʊ/ | lambat |
| steps/steps/ | langkah-langkah |
| reasonable/ˈriːzənəbl/ | wajar |
| unreasonable/ʌnˈriːzənəbl/ | tidak wajar |
| heuristic/hjuːˈrɪstɪk/ | heuristik |
Benar belum tentu cukup baik
- Dua algoritma bisa keduanya benar, namun salah satunya mungkin jauh lebih baik untuk digunakan.
- Efisiensi algoritmik membandingkan algoritma berdasarkan sumber daya yang mereka gunakan — utamanya waktu dan memori.
- Algoritma yang benar tetapi lambat bisa menjadi tidak berguna pada input yang besar.
- Oleh karena itu kita memerlukan cara untuk membandingkan bagaimana cara mereka berskala.
Efisiensi algoritmik membandingkan algoritma melalui:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Efisiensi berkaitan dengan waktu dan memori saat input bertambah.
Menghitung langkah seiring bertambahnya n
- Perkirakan jumlah langkah yang diambil algoritma saat ukuran inputnya $n$ bertambah.
- Pencarian linear membutuhkan sekitar $n$ langkah; pencarian biner sekitar $\log_2 n$; membandingkan setiap pasangan sekitar $n^2$.
- Saat $n$ menjadi besar, perbedaan-perbedaan ini menjadi sangat signifikan.
- Bentuk pertumbuhan jauh lebih penting daripada penggunaan stopwatch.
Bagaimana waktu eksekusi bertambah seiring n
Geser slide n dan bandingkan kurva: log n tetap hampir datar, n naik secara konsisten, n² meledak. Inilah mengapa kita membandingkan algoritma berdasarkan cara mereka berskala, bukan dengan stopwatch.
Cocokkan setiap algoritma dengan perkiraan jumlah langkahnya untuk ukuran input n.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Tingkat pertumbuhan ini menentukan algoritma mana yang berskala baik.
Pertumbuhan mana yang dianggap tidak masuk akal saat n menjadi besar?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pertumbuhan eksponensial dengan cepat menjadi terlalu lambat.
Ketika jawaban pasti terlalu lambat, sebuah ______ menemukan solusi yang cukup baik dengan cepat.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Heuristik menukar jawaban sempurna demi kecepatan.
Wajar vs Tidak Wajar
- Kita memisahkan waktu berjalan yang wajar dari yang tidak wajar.
- Secara kasar, pertumbuhan seperti $n$ atau $n^2$ dianggap wajar; penggandaan langkah per item tambahan (seperti $2^n$) tidak.
- Ketika jawaban eksakta terlalu lambat, gunakan heuristik — solusi yang cukup baik yang ditemukan dengan cepat.
- Tidak sempurna, tetapi berguna ketika kesempurnaan mustahil dicapai dalam batas waktu.
Pencarian biner pada 1,000,000 item terurut membutuhkan paling banyak sekitar berapa langkah? (2^20 ≈ satu juta)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Karena 2^20 sedikit di atas satu juta, ~20 kali pembagian dua sudah memadai.
Algoritma yang benar bisa saja terlalu lambat untuk digunakan pada input besar.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Ia juga harus selesai dalam waktu yang wajar.
Terlalu lambat untuk digunakan
- Inilah mengapa beberapa algoritma benar terlalu lambat untuk dijalankan secara praktis pada input yang besar.
- Menjadi benar saja tidak cukup — sebuah algoritma juga harus selesai dalam waktu yang wajar.
Satu juta item. Pencarian linear terhadap 1,000,000 item yang telah diurutkan dapat memakan waktu hingga 1,000,000 langkah. Pencarian biner membutuhkan paling banyak sekitar 20, karena $2^{20}$ hanya sedikit lebih besar dari satu juta. Pada daftar kecil, perbedaannya sangat minim; namun pada satu juta item, pencarian biner adalah satu-satunya pilihan yang masuk akal.
Efisiensi algoritma membandingkan algoritma berdasarkan sumber daya saat ukuran input $n$ bertambah: linear $n$, biner $\log_2 n$, semua-pasang $n^2$. Pertumbuhan seperti $n$ atau $n^2$ adalah wajar; $2^n$ adalah tidak wajar (gunakan heuristik). Algoritma yang benar namun terlalu lambat pada input besar tidak cukup baik.