Algorithmic efficiency
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.
สิ่งที่เราจะทำ
- โปรแกรมสองตัวอาจถูกต้องทั้งคู่แต่ใช้เวลา ต่างกันมาก
- บทเรียนนี้เกี่ยวกับ ประสิทธิภาพ: การทำงานเพิ่มขึ้นอย่างไรเมื่ออินพุตเพิ่มขึ้น
- อ่านและคิดเกี่ยวกับแนวคิด; จากนั้นโจทย์สั้นๆ幾個会让你自己 นับขั้นตอน ได้
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.
นับการทำงาน
- เราวัดอัลกอริทึมโดย จำนวนขั้นตอน ที่ทำได้ ไม่ใช่วินาที
- ขั้นตอนเป็นวินาทีขึ้นอยู่กับคอมพิวเตอร์; การนับขั้นตอนไม่
- อินพุตมากขึ้นมักหมายถึงขั้นตอนมากขึ้น คำถามคือ เพิ่มเท่าไหร่
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.
เวลาทำงานที่ยอมรับได้ vs ไม่ยอมรับได้
- บางอัลกอริทึมเติบโต ช้า: เพิ่มอินพุตเป็นสองเท่า ทำงานประมาณสองเท่า
- บางอัลกอริทึมเติบโต เร็ว: อินพุตเพิ่มเล็กน้อย การทำงานพุ่งสูงขึ้นมหาศาล
- "เวลาที่ยอมรับได้" เติบโตช้าพอที่จะเสร็จสิ้น; "ไม่ยอมรับได้" จะพุ่งสูงเกินควบคุม
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.
ตัวอย่างจำลอง: นับขั้นตอน
- ด้านล่างเรานับจำนวนการเปรียบเทียบที่การค้นหาเชิงเส้นทำ
- จำนวนเพิ่มขึ้นตาม ขนาดรายการ - เติบโตช้าและสม่ำเสมอ
- ลองเปลี่ยนขนาดเพื่อดูจำนวนที่ติดตามมัน
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.
เมื่อความเร็วไม่เพียงพอ
- บางปัญหาไม่มี อัลกอริทึม ที่รวดเร็วKnown
- วิธีเดียวคือการลองความเป็นไปได้จำนวนมาก - ช้าเกินไปสำหรับอินพุตขนาดใหญ่
- สำหรับกรณีเหล่านี้ เรามักยอมรับคำตอบที่ พอใช้ได้ แทนคำตอบที่สมบูรณ์แบบ
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.
ปัญหาที่พิสูจน์ไม่ได้
- بد worse กว่าช้า: บางปัญหา ไม่สามารถ แก้ไขได้ด้วยอัลกอริทึมใดๆ เลย
- เหล่านี้เรียกว่า ปัญหาที่พิสูจน์ไม่ได้
- ไม่ว่าคอมพิวเตอร์จะเร็วแค่ไหน ก็ไม่มีโปรแกรมใดให้คำตอบที่ถูกต้องเสมอไป
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.
แนวคิดสำคัญที่ต้องจำ
- ประสิทธิภาพ是关于 how work grows with input size
- อัลกอริทึมที่เติบโตช้าขยายไปยังอินพุตขนาดใหญ่ได้; ที่เติบโตเร็วทำไม่ได้
- บางปัญหาคือการแก้ไขอย่างแม่นยำเป็นเรื่องไม่สมเหตุสมผล และบางปัญหาเป็นปัญหาที่พิสูจน์ไม่ได้
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
ข้อผิดพลาดที่พบบ่อย
- Big-O อธิบาย how the running time GROWS with the input size
- อัลกอริทึมที่ทำงานภายในเวลาที่สมเหตุสมผลจะขยายได้; อย่างอื่นทำไม่ได้
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.
ลองดูเลย
- เขียนฟังก์ชันเล็กๆ ที่ นับขั้นตอน เพื่อรู้สึก how the work grows
- เปรียบเทียบลูปเดี่ยว, ลูปซ้อน, และ "ลองทุกวิธี" กด Check answer
How algorithms scale · Algorithm Scaling
As input grows, O(n²) explodes while O(log n) barely moves. · เมื่ออินพุตเพิ่มขึ้น O(n²) พุ่งสูงขึ้น ในขณะที่ O(log n) เคลื่อนไหวน้อยมาก
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. · เขียน scan_compares(data, target) ที่คืนค่าจำนวนการเปรียบเทียบของ linear search เปรียบเทียบแต่ละรายการกับ target นับหนึ่งทุกครั้งที่ compares และ หยุดทันทีที่พบ หากไม่อยู่ในรายการ คุณ compared ทุกรายการ ตัวอย่าง: scan_compares([5, 8, 2], 8) → 2
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · เขียน pair_count(n) ที่ใช้ลูป ภายใน ลูป (ทั้งสองวนรอบ range(n)) และคืนค่าจำนวนครั้งที่ inner step ทำงาน นี่คือ n × n ตัวอย่าง: pair_count(3) → 9 grows เร็วกว่าลูปเดี่ยว
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · เขียน count_orderings(n) ที่คืนค่าจำนวนวิธีจัดเรียงที่แตกต่างกันของ n รายการ นั่นคือ 1 × 2 × ... × n (n factorial) count_orderings(0) คือ 1 ตัวอย่าง: count_orderings(3) → 6 Notice how fast it explodes: count_orderings(10) เกิน 3 ล้าน
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่