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

ข้อย่อย 1

ใช้ master method กรณีที่ 3

จากโจทย์ $a=2,b=2,f(n)=n^{3}$

จะได้ $n^{\log _{b}a}=n^{\log _{2}2}=n$

จะได้ $a(f((n/b))=2f(n/2)=(1/4)n^{3}\leq n^{3}$ เมื่อ $c=1/4$

ดังนั้นจะได้ว่า $T(n)=\Theta (f(n))=\Theta (n^{3})$

ข้อย่อย 2

ใช้ master method กรณีที่ 3

จะได้ $a=1,b=10/9,f(n)=n$

หา $n^{\log _{b}a}=n^{\log _{10/9}1=n^{0}=1}$

หา $a(f(n/b))=f(9n/10)=9n/10\leq n$ เมื่อ $c=9/10$

ดังนั้น $T(n)=\Theta (f(n))=\Theta (n)$

ข้อย่อย 3

ใช้ master method กรณีที่ 2

จะได้ $a=16,b=4,f(n)=n^{2}$

หา $n^{\log _{b}a}=n^{\log _{4}16}=n^{2}$

ดังนั้น $T(n)=\Theta (n^{\log _{b}a}\lg n)=\Theta (n^{2}\lg n)$

ข้อย่อย 4

ใช้ master method กรณีที่ 3

จะได้ $a=7,b=3,f(n)=n^{2}$

หา $n^{\log _{b}a}=n^{\log _{3}7}$

หา $a(f(n/b))=7(f(n/3))=(7/9)n^{2}\leq n^{2}$ เมื่อ $c=7/9$

ดังนั้น $T(n)=\Theta (f(n))=\Theta (n^{2})$

ข้อย่อย 5

ใช้ master method กรณีที่ 1

จะได้ $a=7,b=2,f(n)=n^{2}$

หา $n^{\log _{b}a}=n^{\log _{2}7}$

ดังนั้น $T(n)=\Theta (n^{\log _{b}a})=\Theta (n^{\log _{2}7})$

ข้อย่อย 6

ใช้ master method กรณีที่ 2

จากโจทย์ $a=2,b=4,f(n)=n^{1/2}$

จะได้ $n^{\log _{b}a}=n^{\log _{4}2}=n^{1/2}$

ดังนั้นจะได้ว่า $T(n)=\Theta (n^{\log _{b}a}\lg n)=\Theta ({\sqrt {n}}\lg n)$

ข้อย่อย 7

ข้อย่อย 8

ข้อย่อย 9

ใช้ master method กรณีที่ 1

จากโจทย์ $a=3,b=2,f(n)=n\log n$

จะได้ $n^{\log _{b}a}=n^{\log _{2}3}$

ดังนั้นจะได้ว่า $T(n)=\Theta (n^{\log _{b}a})=\Theta (n^{\log _{2}3})$