Algorithmic efficiency
Apa yang akan kita lakukan
- Dua program bisa benar keduanya tetapi membutuhkan waktu yang sangat berbeda.
- Pelajaran ini tentang efisiensi: bagaimana pekerjaan bertambah seiring bertambahnya input.
- Bacalah dan pikirkan idenya; kemudian beberapa tugas singkat memungkinkan Anda menghitung langkah-langkah sendiri.
Menghitung beban kerja
- Kita mengukur algoritma berdasarkan berapa banyak langkah yang dilakukannya, bukan detik.
- Langkah dalam detik bergantung pada komputer; menghitung langkah tidak.
- Input lebih banyak biasanya berarti lebih banyak langkah. Pertanyaannya adalah seberapa banyak lebih banyak.
Waktu berjalan yang wajar vs tidak wajar
- Waktu yang wajar berarti jumlah langkah bertambah sebagai polinomial, atau lebih lambat: konstan, linear, kuadratik, atau kubik.
- Satu loop bersifat linear. Loop di dalam loop bersifat kuadratik (n × n). Kuadratik tumbuh lebih cepat daripada linear, namun tetap merupakan waktu yang wajar.
- Waktu yang tidak wajar berarti pertumbuhan eksponensial atau faktorial. Sedikit tambahan input dapat membuat beban kerja melonjak drastis.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
Demo kecil: menghitung langkah
- Di bawah ini kita menghitung perbandingan yang dilakukan pencarian linear.
- Perhitungannya tumbuh seiring dengan ukuran daftar — pertumbuhan lambat dan stabil.
- Cobalah mengubah ukurannya untuk melihat perhitungannya mengikuti perubahan tersebut.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
Ketika cepat tidak cukup
- Beberapa masalah tidak memiliki algoritma dengan waktu yang wajar.
- Metode eksak mungkin mencoba semua urutan. Itu adalah pertumbuhan faktorial, sehingga tidak wajar untuk input besar.
- Heuristik adalah jalan pintas yang dapat memberikan jawaban yang cukup baik. Tidak dijamin menjadi yang terbaik. Anda tidak perlu menghafal satu heuristik tertentu.
Masalah tak terputuskan
- Lebih buruk dari lambat: beberapa masalah tidak dapat diselesaikan oleh algoritma apa pun.
- Ini disebut masalah tak terputuskan.
- Secepat apa pun komputer menjadi, tidak ada program yang selalu dapat memberikan jawaban yang benar.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
Ide kunci untuk diingat
- Efisiensi berkaitan dengan bagaimana jumlah langkah bertambah seiring ukuran input, bukan berapa banyak detik yang dibutuhkan satu komputer.
- Pertumbuhan polinomial atau lebih rendah adalah waktu yang wajar. Loop bersarang (n × n) masih dianggap wajar.
- Pertumbuhan eksponensial atau faktorial adalah waktu yang tidak wajar. Beberapa masalah juga tidak dapat diputuskan.
Kesalahan umum
- Menilai loop bersarang sebagai tidak wajar. Pertumbuhan kuadratik dan kubik masih termasuk waktu yang wajar.
- Menggunakan notasi Big-O formal sebagai aturan ujian. Big-O tidak diuji. Garis ini menunjukkan polinomial atau lebih rendah, dibandingkan dengan eksponensial atau faktorial.
Sekarang Anda coba
- Tulis fungsi-fungsi kecil yang menghitung langkah untuk merasakan bagaimana beban kerja tumbuh.
- Bandingkan satu loop, loop bersarang, dan "coba semua urutan". Loop bersarang masih merupakan waktu yang wajar. Tekan Periksa jawaban.
How algorithms scale
Square growth rises faster than a straight line, and it is still reasonable time. Factorial growth is unreasonable.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) adalah 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million.
Klik Jalankan untuk melihat output di sini.