418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ 6

จาก Theory Wiki

รุ่นแก้ไขเมื่อ 09:11, 1 สิงหาคม 2552 โดย Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'เขียน Recurrence ของเวลาการทำงานของอัลกอริทึมนี้ได้ดัง…')

(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)

ไปยังการนำทาง ไปยังการค้นหา

เขียน Recurrence ของเวลาการทำงานของอัลกอริทึมนี้ได้ดังนี้

$T(n)=({\sqrt {k}})T({\sqrt {k}})+O(n)$

ใช้ Tree ในการหา $\Theta$ ของ T(n) ได้ดังนี้

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=418531_ภาคต้น_2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ/เฉลยข้อ_6&oldid=6610"