(۳۰ دى ۱۳۹۲ ۰۱:۲۵ ق.ظ)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