(۲۸ آبان ۱۳۹۴ ۱۲:۴۳ ق.ظ)IranianWizard نوشته شده توسط:  سلام.کسی میدونه که باید چجور پیچیدگی زمانی این مسئله ی بازگشتی رو بدست بیارم؟
$T(n)\: =\: T(\frac{n}{2}\: \: \sqrt{n})\: \: \sqrt{6046}$

T(n) < T(n/2 + n) + 80
پس
T(n) < T(3n/2) + 80
در نتیجه
T(n)=O(log n)

حالا جواب چی بوده؟

(۲۸ آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط:  حالا جواب چی بوده؟

متاسفانه جوابشو نمیدونم.یه تمرینه.هرچقد بهش فکر کردم،به ذهنم نرسید که چجور حلش کنم.
خب اینجور شما یه حد بالا واسش تعریف کردین.ولی دقیقش که معلوم نیست

---

(۲۸ آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط:  T(n) < T(n/2 + n) + 80
پس
T(n) < T(3n/2) + 80
در نتیجه
T(n)=O(log n)

یه سوال داشتم.شما گفتین رشد ( T( n کوچکتر از رشد T(3n/2) + 80 هستش...ولی این T(3n/2) + 80 که اصلا قابل حل نیست.چون اینجور که ما n رو نمیشکنیم.هر بار بزرگترش میکنیم که.

با قضیه مستر هم که قابل حل نیست.چون در aT(n/b) + c باید b بزرگتر از ۱ باشه،ولی اینجا b=2/3 هستش.

(۲۸ آبان ۱۳۹۴ ۰۴:۱۱ ق.ظ)IranianWizard نوشته شده توسط:  

(28 آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط:  حالا جواب چی بوده؟

متاسفانه جوابشو نمیدونم.یه تمرینه.هرچقد بهش فکر کردم،به ذهنم نرسید که چجور حلش کنم.
خب اینجور شما یه حد بالا واسش تعریف کردین.ولی دقیقش که معلوم نیست

---

(۲۸ آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط:  T(n) < T(n/2 + n) + 80
پس
T(n) < T(3n/2) + 80
در نتیجه
T(n)=O(log n)

یه سوال داشتم.شما گفتین رشد ( T( n کوچکتر از رشد T(3n/2) + 80 هستش...ولی این T(3n/2) + 80 که اصلا قابل حل نیست.چون اینجور که ما n رو نمیشکنیم.هر بار بزرگترش میکنیم که.

با قضیه مستر هم که قابل حل نیست.چون در aT(n/b) + c باید b بزرگتر از ۱ باشه،ولی اینجا b=2/3 هستش.

آره شما درست میگید ولی درحالت کلی برای nهای بزرگ sqrt(n) < n/a هست که a عددی ثابت هست.
یعنی شما میتونید یه a دلخواه در نظر بگیرید که مقدار T(bn/c) جوری بدست بیاد که b/c <1 بشه و باز هم جواب logn هست. حالا مبناش خیلی فرق نمیکنه
امیدوارم منظورم رو متوجه شده باشید

من فکر میکنم جواب این سوال اینطوری بشه:
$n=2^m$
$T(2^m)=T(2^{m-1} 2^{\frac{m}{2}}) O(1)$
$S(m)=S(m-1 \frac{m}{2}) O(1)$
$S(m)=S(\frac{3m}{2}-1) O(1)$

$O(\log m)$
با تغییر متغیر

$O(\log\log n)$
امیدوارم درست باشه

(۳۰ آذر ۱۳۹۴ ۱۲:۱۳ ب.ظ)LEA3C نوشته شده توسط:  من فکر میکنم جواب این سوال اینطوری بشه:
$n=2^m$
$T(2^m)=T(2^{m-1} 2^{\frac{m}{2}}) O(1)$
$S(m)=S(m-1 \frac{m}{2}) O(1)$
$S(m)=S(\frac{3m}{2}-1) O(1)$

$O(\log m)$
با تغییر متغیر

$O(\log\log n)$
امیدوارم درست باشه

دوستان کسی راجع به این راه حلی که من نوشتم نظری نداره؟
به نظر خودم که درسته نظر شما چیه؟

برای این سوال نکته داریم :
$T(n)=T(\frac{n}{a}) b\: ,\: a>1\: \Rightarrow\: O(\log_an)$

علاوه بر حل با نکته شما با توجه به رابطه ای که با هم ارزی ساخته شده می توانید از تغییر متغیر استفاده کنید و یک رابطه ی ناهمگن بسازید.

به این شکل که جمله ی $\frac{3n}{2^k}=1\:$ را در نظر گرفته که ۱ شرط توقف می باشد. سپس مقدار k را از این رابطه بدست آورید که می شود :
$k=\log_{\frac{2}{3}}n\:$

سپس در معادله ی اصلی به جای مقداری ۳n قرار دهید $2^k$ .
معادله به صورت مقابل میشود :
$T(2^k)=T\: (\frac{2^k}{2}) 80\: =T\: (2^{k-1}) 80$
سپس با تغییر متغیر :
$t_k=T(2^k)\:$ در معادله ی فوق آن را به صورت :

$t_k=t_{k-1} 80$ بنویسید.

حال با توجه به روابط بازگشتی و حل آنها،این رابطه را که یک رابطه ی ناهمگن است حل کنید که به مرتبه ی زمانی ذکر شده در نکته خواهید رسید.

فکر کنم با درخت بازگشت هم قابل حل باشد

(۲۸ آبان ۱۳۹۴ ۰۳:۳۴ ب.ظ)amniat0101 نوشته شده توسط:  برای این سوال نکته داریم :
$T(n)=T(\frac{n}{a}) b\: ,\: a>1\: \Rightarrow\: O(\log_an)$

علاوه بر حل با نکته شما با توجه به رابطه ای که با هم ارزی ساخته شده می توانید از تغییر متغیر استفاده کنید و یک رابطه ی ناهمگن بسازید.

به این شکل که جمله ی $\frac{3n}{2^k}=1\:$ را در نظر گرفته که ۱ شرط توقف می باشد. سپس مقدار k را از این رابطه بدست آورید که می شود :
$k=\log_{\frac{2}{3}}n\:$

سپس در معادله ی اصلی به جای مقداری ۳n قرار دهید $2^k$ .
معادله به صورت مقابل میشود :
$T(2^k)=T\: (\frac{2^k}{2}) 80\: =T\: (2^{k-1}) 80$
سپس با تغییر متغیر :
$t_k=T(2^k)\:$ در معادله ی فوق آن را به صورت :

$t_k=t_{k-1} 80$ بنویسید.

حال با توجه به روابط بازگشتی و حل آنها،این رابطه را که یک رابطه ی ناهمگن است حل کنید که به مرتبه ی زمانی ذکر شده در نکته خواهید رسید.

فکر کنم با درخت بازگشت هم قابل حل باشد

ممنون از پاسختون.
ولی شما اومدین $\frac{3n}{2^k}=1$ قرار دادین.در حالیکه بایستی بنویسیم $(\frac{3}{2})^kn=1$ .و هر بار n با اینکه تقسیم بر ۲ میشه،ضربدر ۳ هم میشه.که اینجور به هیچوقت به ۱ نمیرسه.
پس اینجور اینکه گفتین $3n\: =\: 2^k$ اشتباه میشه.

---

(۲۸ آبان ۱۳۹۴ ۰۳:۵۲ ب.ظ)sixsixsix نوشته شده توسط:  آره شما درست میگید ولی درحالت کلی برای nهای بزرگ sqrt(n) < n/a هست که a عددی ثابت هست.
یعنی شما میتونید یه a دلخواه در نظر بگیرید که مقدار T(bn/c) جوری بدست بیاد که b/c <1 بشه و باز هم جواب logn هست. حالا مبناش خیلی فرق نمیکنه
امیدوارم منظورم رو متوجه شده باشید

بله متوجه شدم.ممنونم از پاسختون.

نکته ای رو که گفتید فکر نکنم جایی گقته شده باشه و هرچند تو بعضی منال ها جواب درست میده اما نمیشه بصور کلی درست درنظر گرفت
ما یک نکته داریم که :

$T(n)=aT(n-b) c$

که مرتبه این رابطه بصورت $T(n)\in\theta(a^{\frac{n}{b}})$
و نکته دوم هم که مربوط به قضیه مستره

که $T(n)=aT(\frac{n}{b}) c$ که a=1 , b>1
انگاه $T(n)=T(\frac{n}{b}) c$

$T(n)\in\theta(\log n)$
-----------
حالا تو این مثال

$T(n)<T(\frac{n}{2} n) c$

$T(n)<T(\frac{3n}{2}) c$

$T(n)<T(\frac{n}{\frac{2}{3}}) c$

با تغییر متغییر $n=(\frac{2}{3})^k$

$T((\frac{2}{3})^k)=T((\frac{2}{3})^{k-1}) c$

با تغییر متغیر $T((\frac{2}{3})^k)$ به $t_k$ داریم

$t(k)=t(k-1) c$ که مرتبه ان میشود $\theta(k)$

که با توجه به $n=(\frac{2}{3})^k$
K میشود $k=\log_{\frac{2}{3}}\: n$

که با جایگذاری $T(n)\in\theta(\log n)$

---

نکته ای رو که گفتید فکر نکنم جایی گقته شده باشه و هرچند تو بعضی منال ها جواب درست میده اما نمیشه بصور کلی درست درنظر گرفت
ما یک نکته داریم که :

$T(n)=aT(n-b) c$

که مرتبه این رابطه بصورت $T(n)\in\theta(a^{\frac{n}{b}})$
و نکته دوم هم که مربوط به قضیه مستره

که $T(n)=aT(\frac{n}{b}) c$ که a=1 , b>1
انگاه $T(n)=T(\frac{n}{b}) c$

$T(n)\in\theta(\log n)$
-----------
حالا تو این مثال

$T(n)<T(\frac{n}{2} n) c$

$T(n)<T(\frac{3n}{2}) c$

$T(n)<T(\frac{n}{\frac{2}{3}}) c$

با تغییر متغییر $n=(\frac{2}{3})^k$

$T((\frac{2}{3})^k)=T((\frac{2}{3})^{k-1}) c$

با تغییر متغیر $T((\frac{2}{3})^k)$ به $t_k$ داریم

$t(k)=t(k-1) c$ که مرتبه ان میشود $\theta(k)$

که با توجه به $n=(\frac{2}{3})^k$
K میشود $k=\log_{\frac{2}{3}}\: n$

که با جایگذاری $T(n)\in\theta(\log n)$

که مبنای لگاریتم تو مرتبه زمانی مهم نیست

بله حق با شماست بنده اشتباه کردم :
ولی فکر کنم این راه حل درست باشد :

$T(n)=3\: T\: (\frac{n}{2}) 80$
در رابطه ی بالا اگر به روش جایگذاری و تکرار عمل کنیم میرسیم به چنین رابطه ای :
$3^k\: T(\frac{n}{2^k})$
حال داریم :
$\frac{n}{2^k}=1\: \Rightarrow\: n=2^k\: ,\: \: k=\log_2n\: \: \: 3^kT(1)=3^{\log_2n}$

حال به جای n ها قرار میدهیم : $\: n=2^k\:$
که به این رابطه میرسیم :
$T(2^k)=3^{\log_22^k}\: T(\frac{2^k}{2}) 80\: \: \Rightarrow\: T(2^k)=2^{klog_23}\: T\: (2^{k-1}) 80\:$
حال اگر $\log_23\approx1$ و فکر کنم با توجه به اینکه تمرکز ما بیشتر بر روی مقدار k است این درست باشد.داریم :
$T(2^k)=2^kT(2^{k-1}) 80$
حال با تغییر متغیر : $t_k=2^k$
داریم :
$t_k=t_k\: (t_{k-1}) 80\: \Rightarrow\: \: t_k-t_k\times t_{k-1}=80\: \Rightarrow\: t_k(1-t_{k-1})=80\: \Rightarrow\: k(1-k)=80$

حال برای حل رابطه ی ناهمگن بالا داریم : مقدار چند جمله ای ما عدد ثابت ۸۰ هست که از درجه ی صفر می باشد.(البته در بالا دقت نمایید که برای حل روابط بازگشتی ناهمگن ما میتوانیم قسمت همگن را با برابر قرار دادن صفر محاسبه کنیم که از همانجا یک ریشه ی k=0 بدست می آید و نادیده گرفته میشود)
نهایتا به این میرسیم که : $(k-1)^2=0$
که ریشه ی تعدد ۲ دارد:
حال در آخر سر داریم :
$t_k=c_1(1)^n c_2k(1)^n$
با جایگذاری $k=\log_2n$
و به دست آوردن مقادیر C ها میتوان به پیچیدگی $\log_2n$ رسید

امیدوارم درست باشد

(۲۸ آبان ۱۳۹۴ ۰۸:۲۹ ب.ظ)amniat0101 نوشته شده توسط:  بله حق با شماست بنده اشتباه کردم :
ولی فکر کنم این راه حل درست باشد :

$T(n)=3\: T\: (\frac{n}{2}) 80$
در رابطه ی بالا اگر به روش جایگذاری و تکرار عمل کنیم میرسیم به چنین رابطه ای :
$3^k\: T(\frac{n}{2^k})$
حال داریم :
$\frac{n}{2^k}=1\: \Rightarrow\: n=2^k\: ,\: \: k=\log_2n\: \: \: 3^kT(1)=3^{\log_2n}$

حال به جای n ها قرار میدهیم : $\: n=2^k\:$
که به این رابطه میرسیم :
$T(2^k)=3^{\log_22^k}\: T(\frac{2^k}{2}) 80\: \: \Rightarrow\: T(2^k)=2^{klog_23}\: T\: (2^{k-1}) 80\:$
حال اگر $\log_23\approx1$ و فکر کنم با توجه به اینکه تمرکز ما بیشتر بر روی مقدار k است این درست باشد.داریم :
$T(2^k)=2^kT(2^{k-1}) 80$
حال با تغییر متغیر : $t_k=2^k$
داریم :
$t_k=t_k\: (t_{k-1}) 80\: \Rightarrow\: \: t_k-t_k\times t_{k-1}=80\: \Rightarrow\: t_k(1-t_{k-1})=80\: \Rightarrow\: k(1-k)=80$

حال برای حل رابطه ی ناهمگن بالا داریم : مقدار چند جمله ای ما عدد ثابت ۸۰ هست که از درجه ی صفر می باشد.(البته در بالا دقت نمایید که برای حل روابط بازگشتی ناهمگن ما میتوانیم قسمت همگن را با برابر قرار دادن صفر محاسبه کنیم که از همانجا یک ریشه ی k=0 بدست می آید و نادیده گرفته میشود)
نهایتا به این میرسیم که : $(k-1)^2=0$
که ریشه ی تعدد ۲ دارد:
حال در آخر سر داریم :
$t_k=c_1(1)^n c_2k(1)^n$
با جایگذاری $k=\log_2n$
و به دست آوردن مقادیر C ها میتوان به پیچیدگی $\log_2n$ رسید

امیدوارم درست باشد

خیلی ممنونم از وقتی که میذارید.
ولی $T(n)=T(\frac{3n}{2}) 80$ خیلی با $T(n)=3T(\frac{n}{2}) 80$ متفاوته

بله حق با شماست.ولی توی همین سعی و خطا نکته هایی به ذهنم میاد که حرف نداره.سوال قبلی با فرض خودم درسته.

و اما برای این سوال یک نظری دارم، ولی خودتان جستجو کنید و صحیح یا غلط بودنش را به ما هم بگید.

به نظرم اگر در همان ابتدای کار تغیر متغیر دهیم بهتر باشد : به این شکل که :
$T(n)=T(\frac{3n}{2}) 80\: \Rightarrow\:$
با تغییر متغیر : $n=2^k\:$
داریم :
$T(2^k)=T(3\times2^{k-1}) 80$
حال مجددا تغییر متغیر داده و داریم :
$t_k=2^k\: \Rightarrow\: t_k=3t_{k-1} 80\: \Rightarrow\: t_k-3t_{k-1}=80$

این را تا آخر امتحان کنید، اگر هم به نتیجه نرسیدید، نکته ای که در ابتدای حل مثال عرض کردم رو برای همیشه در خاطرتون خواهید داشت
و هر زمان این شکل از سوالات روابط بازگشتی رو ببینید با اون نکته حلش میکنید.اگر این شکل روابط ساده بودن قطعا توی سه کتاب چنین نکته ای رو براشون بیان نمیکردن.