ประสิทธิภาพของอัลกอริทึม
แนะนำใหม่| English | ความหมาย |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | ประสิทธิภาพของอัลกอริทึม |
| slow/sləʊ/ | ช้า |
| steps/steps/ | ขั้นตอน |
| reasonable/ˈriːzənəbl/ | สมเหตุสมผล |
| unreasonable/ʌnˈriːzənəbl/ | ไม่สมเหตุสมผล |
| heuristic/hjuːˈrɪstɪk/ | วิธีแบบฮิวริสติก |
ความถูกต้องไม่ใช่สิ่งที่ดีพอเสมอไป
- อัลกอริทึมสองตัวอาจถูกต้องทั้งคู่ แต่ตัวหนึ่งอาจดีกว่ามากในการใช้งาน
- ประสิทธิภาพของอัลกอริทึม เปรียบเทียบอัลกอริทึมโดยใช้ทรัพยากรที่พวกมันใช้ — ส่วนใหญ่คือเวลาและหน่วยความจำ
- อัลกอริทึมที่ถูกต้องแต่ช้าอาจไร้ประโยชน์กับอินพุตขนาดใหญ่
- ดังนั้นเราจึงต้องการวิธีในการเปรียบเทียบ วิธีการขยายขนาดของทั้งสอง
ประสิทธิภาพของอัลกอริทึมเปรียบเทียบอัลกอริทึมโดย:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ประสิทธิภาพเกี่ยวข้องกับเวลาและหน่วยความจำเมื่อข้อมูลเข้ามีขนาดใหญ่ขึ้น
นับขั้นตอนเมื่อ n ขยายตัว
- ประมาณจำนวน ขั้นตอน ที่อัลกอริทึมใช้เมื่อขนาดอินพุต $n$ ขยายตัว
- การค้นหาแบบเชิงเส้นใช้ประมาณ $n$ ขั้นตอน; การค้นหาแบบทวิภาคใช้ประมาณ $\log_2 n$; การเปรียบเทียบทุกคู่ใช้ประมาณ $n^2$
- เมื่อ $n$ มีขนาดใหญ่ ความแตกต่างเหล่านี้จะกลายเป็นมหาศาล
- รูปร่าง ของการเติบโตสำคัญกว่าการใช้จับเวลา
ความเร็วในการดำเนินการเพิ่มขึ้นตาม n อย่างไร
เลื่อนสไลด์ n และเปรียบเทียบกราฟ: log n ค่อนข้างราบเรียบ, n เพิ่มขึ้นอย่างต่อเนื่อง, n² พุ่งสูงขึ้นอย่างรวดเร็ว นี่คือเหตุผลที่เราเปรียบเทียบอัลกอริทึมด้วยการขยายขนาด ไม่ใช่ด้วยการจับเวลาด้วยนาฬิกาจับเวลา
จับคู่แต่ละอัลกอริทึมกับประมาณจำนวนขั้นตอนสำหรับขนาดข้อมูลเข้า n
Difficulty 2/5 · 140 coins + a small bonus on first completion today
อัตราการเติบโตเหล่านี้กำหนดว่าอัลกอริทึมใดจะขยายขนาดได้ดี
อัตราการเติบโตแบบใด被认为是不合理的当n变得很大时？
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การเติบโตแบบเอ็กซ์โพเนนเชียลกลายเป็นช้าเกินไปอย่างรวดเร็ว
เมื่อคำตอบที่แม่นยำช้าเกินไป ______ จะหาทางออกที่เพียงพอได้รวดเร็ว
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Heuristic สลับคำตอบที่สมบูรณ์แบบเพื่อความเร็ว
สมเหตุสมผลและไม่สมเหตุสมผล
- เราแยกเวลา运行的 สมเหตุสมผล ออกจาก ไม่สมเหตุสมผล
- โดยประมาณ การเติบโตเช่น $n$ หรือ $n^2$ ถือว่าสมเหตุสมผล; การเพิ่มจำนวนขั้นตอนเป็นสองเท่าสำหรับรายการเพิ่มเติม (เช่น $2^n$) ไม่ถือว่าสมเหตุสมผล
- เมื่อคำตอบที่แม่นยำช้าเกินไป ให้ใช้ heuristics — ทางออกที่เพียงพอ/fast
- ไม่สมบูรณ์แบบแต่มีประโยชน์เมื่อความสมบูรณ์แบบไม่สามารถทำได้ในเวลา
การค้นหาแบบ二分法ของรายการ 1,000,000 รายการที่เรียงลำดับแล้ว ต้องใช้ขั้นตอนสูงสุดประมาณกี่ขั้น? (2^20 ≈ ล้าน)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
เนื่องจาก 2^20 เกินล้านเพียงเล็กน้อย การแบ่งครึ่งประมาณ 20 ครั้งก็เพียงพอ
อัลกอริทึมที่ถูกต้องก็อาจช้าเกินไปสำหรับการใช้งานกับข้อมูลเข้าขนาดใหญ่
Difficulty 1/5 · 100 coins + a small bonus on first completion today
มันต้องเสร็จสิ้นภายในเวลาที่สมเหตุสมผล
ช้าเกินกว่าจะใช้งาน
- นี่คือเหตุผลที่บาง อัลกอริทึมที่ถูกต้อง ช้า มาก จนไม่สามารถรันได้ในทางปฏิบัติกับอินพุตขนาดใหญ่
- การถูกต้องอย่างเดียวไม่เพียงพอ — อัลกอริทึม还必须必须在合理的时间内完成。
หนึ่งล้านรายการ การค้นหาแบบเชิงเส้นของรายการ 1,000,000 รายการที่เรียงลำดับแล้วอาจใช้เวลาถึง 1,000,000 ขั้นตอน การค้นหาแบบทวิภาคใช้เวลาสูงสุดประมาณ 20 เพราะ $2^{20}$ เกินหนึ่งล้านเพียงเล็กน้อย对于小列表差距几乎不重要；在一百万项中，二分查找是唯一合理的选择。
ประสิทธิภาพเชิงอัลกอริทึม เปรียบเทียบอัลกอริทึมโดยพิจารณาจากทรัพยากรเมื่อขนาดอินพุต $n$ เพิ่มขึ้น: แบบเชิงเส้น $n$, แบบไบนารี $\log_2 n$, แบบคู่ทุกจุด $n^2$. การเติบโตแบบ $n$ หรือ $n^2$ ถือว่า สมเหตุสมผล; ส่วน $2^n$ นั้น ไม่สมเหตุสมผล (ควรใช้ วิธีเชิงประจักษ์/heuristics) อัลกอริทึมที่ถูกต้องแต่ช้าเกินไปสำหรับอินพุตขนาดใหญ่ถือว่าไม่เพียงพอ