سلام. دوستان مرتبه زمانی این سوال چیست؟
[tex]T(n)=\sqrt n T(\sqrt n) O(n)[/tex]
آیا [tex]\small nloglogn[/tex] میشه؟
(۳۰ دى ۱۳۹۲ ۰۱:۲۵ ق.ظ)mahmood1 نوشته شده توسط: سلام. دوستان مرتبه زمانی این سوال چیست؟
[tex]T(n)=\sqrt n T(\sqrt n) O(n)[/tex]
آیا [tex]\small nloglogn[/tex] میشه؟
بله جواب درسته.
(T(n))/n=(T(√(n)))/√n+1
حالا می توان با این تغییر متغیر داشت:
n=2^m
یعنی داریم:
(T(2^m))/2^m =(T(√(۲^m )))/√(۲^m )+1
F(m)=(T(2^m))/2^m
و اکنون داریم:اگه ۲m رو با رادیکال بنویسیم داریم F(m/2)
پس :
F(m)=F(m/2)+1
برای این عبارت چون m=lgn هست ، خواهیم داشت:
F(m)=lglgn و چون در ابتدا تقسیم بر N کرده بودیم در کل داریم:
T(n)=n lglg n
ممنون روش حل این سوالات با جایگذاری چطور میشه؟
صرفا میخوام بدونم از اون روش جواب هم همین بدست میاد؟
ببخشیدا. تشکر
(۳۰ دى ۱۳۹۲ ۰۱:۵۱ ق.ظ)mahmood1 نوشته شده توسط: ممنون روش حل این سوالات با جایگذاری چطور میشه؟
صرفا میخوام بدونم از اون روش جواب هم همین بدست میاد؟
ببخشیدا. تشکر
روش جایگذاری تو اینجور سوالات خیلی وقت گیر میشه و حتی تو بعضی از مسائل با باز کردن کردن سوالات به جواب نمیشه رسید.راحت ترین حل اینجور مسائل روش تغییر متغیره.بخصوص وقتی رادیکالی باشه.