پیچیدگی زمانی این تابع چقدر است؟ T(n)=T(sqrt n)+1 - نسخه‌ی قابل چاپ

پیچیدگی زمانی این تابع چقدر است؟ T(n)=T(sqrt n)+1 - sipser - 26 خرداد ۱۳۹۳ ۰۷:۴۸ ب.ظ پیچیدگی زمانی این تابع چقدره؟ یک توضیح مختصر هم بدید ممنون [tex]T(n)\: =\: T(\sqrt{n}) 1[/tex]

RE: پیچیدگی زمانی این تابع چقدر است؟ T(n)=T(sqrt n)+1 - Morris - 26 خرداد ۱۳۹۳ ۰۹:۰۱ ب.ظ تابع مورد نظر : [tex]T(n)=T(\sqrt{n}) 1[/tex] از تغییر متغیر زیر استفاده می کنیم : [tex]n=2^{2^k}[/tex] بنابراین خواهیم داشت : [tex]T(2^{2^k})=T(2^{2^{k-1}}) 1[/tex] برای سهولت و زیبایی به صورت زیر می نویسیم : [tex]M(k)=M(k-1) 1[/tex] مرتبه [tex]M(k)[/tex] برابر است با [tex]\theta(k)[/tex] حال باید k به n تبدیل شود : [tex]n=2^{2^k}[/tex] [tex]\lg n\: =2^k[/tex] [tex]\lg\lg n\: =\: k[/tex] بنابراین مرتبه تابع آغازین برابر است : [tex]\theta(\lg\lg n)[/tex].

RE: پیچیدگی زمانی این تابع چقدر است؟ T(n)=T(sqrt n)+1 - so@ - 27 آذر ۱۳۹۳ ۱۲:۳۵ ب.ظ سلام جناب موریس میشه بیزحمت برام توضیح بدید چرا بعضی جاها در روش تغییر متغیر [tex]n=2^k[/tex] و در بعضی جاها [tex]n=2^{2^k}[/tex] بعد اینک چرا به جای K ب توان ۱/۲ نوشتید K-1 من تو این مبحث مشکل دارم ممنون میشم راهنمایی کنید