دوستان عزیز در حل این مساله کمکم میکنید
ممنون میشم
T (n )= 2T(n/4) + radikal n
مرتبه رو میخوام و از چه راهی حل میشه؟
از راه درخت بازگشتی حلش کردم شد radikal n.log n درسته؟؟؟
یه سوال دیگه هم داشتم
!T (n )= 2T(n/2) + log n
جوابش شده n.log^2 n ولی نمیدونم چرا؟؟؟
یه راهنمایی خواستم
سپاس فراووووووووووون
(۱۱ اردیبهشت ۱۳۹۳ ۱۱:۵۲ ق.ظ)Riemann نوشته شده توسط: سلامز
رابطه اولی $T(n) = 2T(n/4) + \sqrt{n}$ با استفاده از قضیه مستر میشه همون $\lg n \sqrt{n}$
رابطه دومی شما باید دقت داشته باشید که $\lg n! = O(n \lg n)$ که فکر کنم بتونید الان با مستر حلش کنید
ممنون مرسی از کمکتون
میشه بگید [tex]n^{\log^2_4}[/tex] میشه چی؟
بعد چه طور به این نتیجه رسیدید
سوال دوم هم [tex]n^{\log_2^2}\: =\: n[/tex] رو که بدست میاریم حالا باید با [tex]f(n)[/tex] مقایسه کنیم که اینجا [tex]n\: \log n[/tex]
حالا اینها هم درجه هستند؟؟؟
(۱۱ اردیبهشت ۱۳۹۳ ۱۲:۰۲ ب.ظ)tayebeh1991 نوشته شده توسط:(11 اردیبهشت ۱۳۹۳ ۱۱:۵۲ ق.ظ)Riemann نوشته شده توسط: سلامز
رابطه اولی $T(n) = 2T(n/4) + \sqrt{n}$ با استفاده از قضیه مستر میشه همون $\lg n \sqrt{n}$
رابطه دومی شما باید دقت داشته باشید که $\lg n! = O(n \lg n)$ که فکر کنم بتونید الان با مستر حلش کنید
ممنون مرسی از کمکتون
میشه بگید [tex]n^{\log^2_4}[/tex] میشه چی؟
بعد چه طور به این نتیجه رسیدید
سوال دوم هم [tex]n\: ^{\log_2^2}\: =\: n[/tex]n رو که بدست میاریم حالا باید با [tex]f(n)[/tex] مقایسه کنیم که اینجا [tex]n\: \log n[/tex]
حالا اینها هم درجه هستند؟؟؟
اولی میشه nبه توان ۱/۲ /////////log2 در مبنای ۴انگار همون log4^1/2در مبنای ۴ هست
دومی هم هم درجه اند
[/quote]
اولی میشه nبه توان ۱/۲ /////////log2 در مبنای ۴انگار همون log4^1/2در مبنای ۴ هست
دومی هم هم درجه اند
[/quote]
ممنون دوست خوبم
لایک دارید هوارتااااااااااااااا
سوال اول رو فهمیدم
ولی سوال دوم
مگه نمیگیم nlogn درجه اش از n بیشتره؟؟؟
یعنی logn بی تاثیره این وسط...؟!!!!
اولی میشه nبه توان ۱/۲ /////////log2 در مبنای ۴انگار همون log4^1/2در مبنای ۴ هست
دومی هم هم درجه اند
[/quote]
ممنون دوست خوبم
لایک دارید هوارتااااااااااااااا
سوال اول رو فهمیدم
ولی سوال دوم
مگه نمیگیم nlogn درجه اش از n بیشتره؟؟؟
یعنی logn بی تاثیره این وسط...؟!!!!
[/quote]
بله
طبق قضیه اصلی که میگه
صرف نظر از یک ضریب logn به توان kاگه برابر بودند
بله
طبق قضیه اصلی که میگه
صرف نظر از یک ضریب logn به توان kاگه برابر بودند
[/quote]
من این قضیه رو ندیدم
میشه قضیه رو کامل واسم بزاری؟
لطف میکنی عزیزم
(۱۱ اردیبهشت ۱۳۹۳ ۰۳:۲۰ ب.ظ)tayebeh1991 نوشته شده توسط: بله
طبق قضیه اصلی که میگه
صرف نظر از یک ضریب logn به توان kاگه برابر بودند
من این قضیه رو ندیدم
میشه قضیه رو کامل واسم بزاری؟
لطف میکنی عزیزم
[/quote]
جواب اولی درسته ولی دومی رو شما نمی تونید از قضیه اصلی حل کنید چون در هیچ حالتی از این قضیه نمیگنجه ولی درclrs یه تبصره برای این جور مسائل وجود داره فکر کنم اثبات کرده که اگر [tex]t(n)=aT(\frac{n}{b}) n^{\log a\: be\: paye\: b}\cdot(\log n)^k[/tex]
اونوقت [tex]t(n)=\theta(n^{\log a\: be\: paye\: b}\cdot(\log n)^{k 1})[/tex]
که در مسئله شما k=1 وجواب میشه [tex]t(n)=\theta(n\cdot(\log n)^2)[/tex]
اگه ابهامی بود بگید
اگرT(n)=aT(n/b)+f(n)باشد که در آن a>=1 وb>=2
طبق قضیه اصلی:
۱)اگر) f(n)=O(n^( log_b^(a-ἑ) ) وἑ>0 آنگاه T(n)=ϴ((n^( log_b^a ))
{اگرn^( log_b^a ) بزرگتر باشد}
۲)اگر f(n)= ϴ (n^( log_b^a ) ( log〖n)〗^k) وK>=0آنگاه T(n)= ϴ (n^( log_b^a ) ( log〖n)〗^(k+1))
{اگر f(n) وn^( log_b^a ) صرف نظر از یک ضریب ( log〖n)〗^k مساوی باشند}
۳)اگر f(n)=ᾨ(n^( log_b^(a+ἑ) )) و وἑ>0 آنگاه T(n)=ϴ (f(n))
{اگر f(n)بزرگتر باشد}
و طبق این اصل این مسئله قابل حل است(هم مسئله ۱ وهم۲)
تنها مسائلی را نمیتوان حل کرد که درون پرانتز T، nدر زیر رادیکال باشد
که البته آن ها را نیز با تغییر متغیر میتوان این قضیه را دخیل کرد و توسط آن حل نمود
مسائلی هم چون T(n)=4T(√n/3)+〖log〗^۲ n
این قضیه اصلی رو سعی کن به کار ببری اگه نتونستی بگو کمکت کنم
تو ورد نوشتم اینجا که پیست کردم یه کم به هم ریخته شد
عکس گرفتم تا واضح تر باشه
امیدوارم متوجه بشید کامل که خیلی مهم هست و توی کنکور زیاد تکرارشده
(۱۱ اردیبهشت ۱۳۹۳ ۰۶:۱۵ ب.ظ)matin_delphi نوشته شده توسط:(11 اردیبهشت ۱۳۹۳ ۰۳:۲۰ ب.ظ)tayebeh1991 نوشته شده توسط: بله
طبق قضیه اصلی که میگه
صرف نظر از یک ضریب logn به توان kاگه برابر بودند
من این قضیه رو ندیدم
میشه قضیه رو کامل واسم بزاری؟
لطف میکنی عزیزم
جواب اولی درسته ولی دومی رو شما نمی تونید از قضیه اصلی حل کنید چون در هیچ حالتی از این قضیه نمیگنجه ولی درclrs یه تبصره برای این جور مسائل وجود داره فکر کنم اثبات کرده که اگر [tex]t(n)=aT(\frac{n}{b}) n^{\log a\: be\: paye\: b}\cdot(\log n)^k[/tex]
اونوقت [tex]t(n)=\theta(n^{\log a\: be\: paye\: b}\cdot(\log n)^{k 1})[/tex]
که در مسئله شما k=1 وجواب میشه [tex]t(n)=\theta(n\cdot(\log n)^2)[/tex]
اگه ابهامی بود بگید
[/quote]
ممنون خیلی لطف کردید فهمیدم
سپاس فراوووووووووون
(۱۲ اردیبهشت ۱۳۹۳ ۱۲:۰۹ ق.ظ)مهنیا نوشته شده توسط: اگرT(n)=aT(n/b)+f(n)باشد که در آن a>=1 وb>=2
طبق قضیه اصلی:
۱)اگر) f(n)=O(n^( log_b^(a-ἑ) ) وἑ>0 آنگاه T(n)=ϴ((n^( log_b^a ))
{اگرn^( log_b^a ) بزرگتر باشد}
۲)اگر f(n)= ϴ (n^( log_b^a ) ( log〖n)〗^k) وK>=0آنگاه T(n)= ϴ (n^( log_b^a ) ( log〖n)〗^(k+1))
{اگر f(n) وn^( log_b^a ) صرف نظر از یک ضریب ( log〖n)〗^k مساوی باشند}
۳)اگر f(n)=ᾨ(n^( log_b^(a+ἑ) )) و وἑ>0 آنگاه T(n)=ϴ (f(n))
{اگر f(n)بزرگتر باشد}
و طبق این اصل این مسئله قابل حل است(هم مسئله ۱ وهم۲)
تنها مسائلی را نمیتوان حل کرد که درون پرانتز T، nدر زیر رادیکال باشد
که البته آن ها را نیز با تغییر متغیر میتوان این قضیه را دخیل کرد و توسط آن حل نمود
مسائلی هم چون T(n)=4T(√n/3)+〖log〗^۲ n
این قضیه اصلی رو سعی کن به کار ببری اگه نتونستی بگو کمکت کنم
تو ورد نوشتم اینجا که پیست کردم یه کم به هم ریخته شد
عکس گرفتم تا واضح تر باشه
امیدوارم متوجه بشید کامل که خیلی مهم هست و توی کنکور زیاد تکرارشده
خیلی عالی بود ممنون مرسی
دیگه ابهاماتم کامل رفع شد
خیلی خیلی خیلی...... لطف کردید تشکر فراوووووووووووون