การวิเคราะห์เวลาในการรันแบบไม่เป็นทางการ
แนะนำใหม่| English | ความหมาย |
|---|---|
| run time/rʌn taɪm/ | เวลาในการรัน |
| linear/ˈlɪnɪə/ | เชิงเส้น |
| quadratic/kwɒˈdrætɪk/ | กำลังสอง |
การนับปริมาณงาน
- เราวัด เวลาในการทำงาน ของโปรแกรมโดย จำนวนครั้ง ที่คำสั่งหลักของมันทำงาน
- ไม่ใช่จำนวนวินาที (ซึ่งแปรผันตามเครื่อง) — แต่เป็น จำนวนการดำเนินการ เมื่ออินพุตเพิ่มขึ้น
- มีการดำเนินการมากขึ้นสำหรับขนาดอินพุตเดียวกัน → อัลกอริทึมช้าลง
- สิ่งนี้ช่วยให้เราเปรียบเทียบอัลกอริทึมได้อย่างยุติธรรม โดยไม่ขึ้นอยู่กับฮาร์ดแวร์
ลูปเดียว: ประมาณ n
- ลูปที่วนผ่าน
nรายการ จะรันโค้ดภายในประมาณnครั้ง - เพิ่มอินพุตเป็นสองเท่า → การทำงานประมาณสองเท่า นี่คือ การเติบโตแบบเชิงเส้น
- การรวมค่าในอาเรย์, การค้นหาในลิสต์ทีละรายการ: ทั้งหมดประมาณ
nขั้นตอน - เขียนแบบไม่เป็นทางการว่า "อันดับ
n"
ลูปซ้อน: ประมาณ n²
- ลูปซ้อน ที่วนผ่าน
nรายการ จะรันโค้ดภายในประมาณn × n = n²ครั้ง - เพิ่มอินพุตเป็นสองเท่า → การทำงานประมาณ สี่เท่า นี่คือ การเติบโตแบบกำลังสอง
- การจับคู่เปรียบเทียบทุกคู่, การเติมตาราง
n × n: ประมาณn²ขั้นตอน n²เติบโตเร็วกว่าnมากเมื่อnมีขนาดใหญ่ขึ้น
การเปรียบเทียบอัตราการเติบโต
- เพื่อเปรียบเทียบอัลกอริทึม ให้ถามว่า การทำงานเติบโตอย่างไร เมื่ออินพุตเพิ่มขึ้น
- สำหรับ
nที่มีขนาดใหญ่ อัลกอริทึมnจะชนะอัลกอริทึมn²— มักจะชนะด้วยระยะห่างมาก - เน้นไปที่ส่วนของโค้ดที่รันมากที่สุด (มักจะเป็นลูปชั้นในสุด)
- พจน์ที่เติบโตเร็วที่สุดจะกำหนดเวลาในการรันทั้งหมด
ตัดสินเวลาในการรันจาก 'การเติบโต' ไม่ใช่จำนวนคงที่ อัลกอริทึมที่ทำ n ขั้นตอนและทำ 2n + 5 ขั้นตอน ทั้งสองมีการเติบโตแบบ เชิงเส้น — สำหรับการเปรียบเทียบ ค่าคงที่และ +5 ไม่สำคัญ; แต่ 'รูปร่าง' (n เทียบกับ n²) สำคัญ ลูปเดียวประมาณ n; ลูปซ้อน ประมาณ n² ซึ่งเติบโตเร็วกว่ามากสำหรับอินพุตที่มีขนาดใหญ่
สองวิธีในการหาซ้ำใน n รายการ:
- ลูปซ้อน เปรียบเทียบทุกคู่: ประมาณ
n²ขั้นตอน - เรียงลำดับก่อน แล้ววนหนึ่งรอบ: มีขั้นตอนน้อยลงมากสำหรับ
nขนาดใหญ่ - สำหรับ
n = 1000,n²คือล้านขั้นตอน — วิธีn²ช้ากว่ามาก
การวิเคราะห์เวลาในการรันแบบไม่เป็นทางการ นับจำนวนครั้งที่คำสั่งรัน เมื่ออินพุตเพิ่มขึ้น ลูปเดียว บน n รายการ ประมาณ n (เชิงเส้น); ลูปซ้อน ประมาณ n² (กำลังสอง) ซึ่งเติบโตเร็วกว่ามาก เปรียบเทียบอัลกอริทึมโดยดูที่ การเติบโต เน้นไปที่โค้ดที่ถูกเรียกใช้มากที่สุด (ลูปชั้นในสุด)
การทำงานเพิ่มขึ้นตาม n อย่างไร
ลูปซ้อน (n²) เพิ่มขึ้นเร็วกว่ามากเมื่อเทียบกับลูปเดี่ยว (n)
ลูปเดี่ยวบน n รายการ จะทำงานร่างงานประมาณกี่ครั้ง?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
One loop over n items → ประมาณ n ขั้นตอน (linear)
ลูปซ้อนบน n รายการ จะทำงานร่างงานภายในประมาณกี่ครั้ง?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n × n = n² (quadratic)
สำหรับ n = 1000 อัลกอริทึม n² จะใช้เวลาประมาณกี่ล้านขั้นตอน?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
1000² = 1,000,000 = 1 ล้าน
สำหรับ n ขนาดใหญ่ อัลกอริทึม n ขั้นตอน โดยทั่วไปจะเร็วกว่าอัลกอริทึม n² ขั้นตอน
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n² เพิ่มขึ้นเร็วกว่ามาก จึงทำงานมากกว่ามากที่ n ขนาดใหญ่
เราวัดเวลาในการรันเป็นวินาที ซึ่งเหมือนกันในทุกคอมพิวเตอร์
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เรานับจำนวนคำสั่งเทียบกับขนาดข้อมูล — วินาทีแตกต่างกันไปตามเครื่อง