ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 5"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'แต่ละรอบการทำงานของ i พิจารณา while ลูป จะได้ว่า while ลู…') |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
แต่ละรอบการทำงานของ i | แต่ละรอบการทำงานของ i | ||
| − | พิจารณา while ลูป จะได้ว่า while ลูปทำงาน lg i ครั้ง | + | พิจารณา while ลูป จะได้ว่า เมื่อ i มีค่า 1 ลูป while จะไม่ทำงาน เมื่อ i มีค่าเป็น 2 ลูป while จะทำงาน 1 ครั้ง เมื่อ i มีค่าเป็น 3,4 ลูป while จะทำงาน 2 ครั้ง เมื่อ i มีค่าเป็น 5,6,7 ลูป while จะทำงาน 3 ครั้ง ดังนั้นสรุปได้ว่า while ลูปทำงาน lg i ครั้ง |
| + | และในอัลกอริทึมนี้ i มีค่าตั้งแต่ 1 ถึง n ดังนั้นทั้งอัลกอริทึม ลูป while จะทำงาน lg n ครั้งนั่นเอง | ||
เนื่องจาก ลูป for ทำงานทั้งหมด n ครั้ง (เมื่อ i = 1 ถึง i = n) | เนื่องจาก ลูป for ทำงานทั้งหมด n ครั้ง (เมื่อ i = 1 ถึง i = n) | ||
ดังนั้น จะได้ว่าเวลาการของอัลกอริทึมนี้โดยเฉลี่ยคือ <math> \Theta (n(log n))</math> | ดังนั้น จะได้ว่าเวลาการของอัลกอริทึมนี้โดยเฉลี่ยคือ <math> \Theta (n(log n))</math> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 07:13, 3 สิงหาคม 2552
แต่ละรอบการทำงานของ i
พิจารณา while ลูป จะได้ว่า เมื่อ i มีค่า 1 ลูป while จะไม่ทำงาน เมื่อ i มีค่าเป็น 2 ลูป while จะทำงาน 1 ครั้ง เมื่อ i มีค่าเป็น 3,4 ลูป while จะทำงาน 2 ครั้ง เมื่อ i มีค่าเป็น 5,6,7 ลูป while จะทำงาน 3 ครั้ง ดังนั้นสรุปได้ว่า while ลูปทำงาน lg i ครั้ง และในอัลกอริทึมนี้ i มีค่าตั้งแต่ 1 ถึง n ดังนั้นทั้งอัลกอริทึม ลูป while จะทำงาน lg n ครั้งนั่นเอง
เนื่องจาก ลูป for ทำงานทั้งหมด n ครั้ง (เมื่อ i = 1 ถึง i = n)
ดังนั้น จะได้ว่าเวลาการของอัลกอริทึมนี้โดยเฉลี่ยคือ
