Algorithmic efficiency · Efisiensi algoritma
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
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.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
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.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
Waktu berjalan yang wajar vs tidak wajar
- Beberapa algoritma tumbuh lambat: gandakan input, kerjakan sekitar ganda pekerjaan.
- Beberapa algoritma tumbuh cepat: sedikit tambahan input berarti lonjakan besar dalam pekerjaan.
- Waktu berjalan "wajar" tumbuh cukup lambat untuk selesai; "tidak wajar" meledak.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
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))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
Ketika cepat tidak cukup
- Beberapa masalah tidak ada algoritma cepat yang diketahui.
- Metode yang ada hanya mencoba sejumlah besar kemungkinan — terlalu lambat untuk input besar.
- Untuk kasus ini, kita sering menerima jawaban yang cukup baik alih-alih yang sempurna.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
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.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
Ide kunci untuk diingat
- Efisiensi berkaitan dengan bagaimana pekerjaan tumbuh seiring ukuran input.
- Algoritma yang tumbuh lambat dapat skala ke input besar; yang tumbuh cepat tidak.
- Beberapa masalah tidak wajar untuk diselesaikan secara tepat, dan beberapa masalah tak terputuskan.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
Kesalahan umum
- Big-O menggambarkan bagaimana waktu berjalan TUMBUH seiring ukuran input.
- Algoritma waktu wajar dapat skala; yang tidak wajar tidak.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
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". Tekan Periksa jawaban.
How algorithms scale · Bagaimana algoritma berskala
As input grows, O(n²) explodes while O(log n) barely moves. · Saat input bertambah, O(n²) meledak sementara O(log n) hampir tidak bergerak.
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. · Tulis scan_compares(data, target) yang mengembalikan berapa banyak perbandingan yang dilakukan pencarian linear. Bandingkan setiap item ke target, hitung satu setiap kali, dan berhenti segera setelah menemukannya. Jika tidak ada dalam daftar, Anda membandingkan setiap item. Contoh: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
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. · Tulis pair_count(n) yang menggunakan perulangan di dalam perulangan (keduanya atas range(n)) dan mengembalikan berapa kali langkah dalam berjalan. Ini adalah n × n. Contoh: pair_count(3) → 9. Ini tumbuh jauh lebih cepat daripada satu perulangan.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
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) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Tulis count_orderings(n) yang mengembalikan berapa banyak urutan berbeda yang bisa ditempati oleh n item — yaitu 1 × 2 × ... × n (n faktorial). count_orderings(0) adalah 1. Contoh: count_orderings(3) → 6. Perhatikan betapa cepatnya meledak: count_orderings(10) melebihi 3 juta.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.