ارسال: #۱

۰۷ شهریور ۱۳۹۲, ۱۱:۰۵ ب.ظ

m@hboobe پرسیده:

مرتبه رابطه بازگشتی

کدام گزینه بهترین پاسخ برای رابطه زیر است؟

$T(n)=T(n/4) T(3n/4) n^{2}$

در صورتی که

$T(1)=1$

الف)

$\theta (nlogn)$
ب)

$\theta (n^{2}logn)$
ج)

$\theta (n^{3})$
د)

$\theta (n^{2})$

ارسال: #۲

۰۷ شهریور ۱۳۹۲, ۱۱:۵۳ ب.ظ

SnowBlind پاسخ داده:

RE: مرتبه رابطه بازگشتی

اگه شما درخت این رابطه رو بکشید یه درخت نا متوازن داره که به یکی با ارتفاع

$log_{4}(n)$ و دیگری

$log_{\frac{4}{3}}(n)$

که اگه شما یه مجموع بزنی حد بالا و پایین بدست میاد و در نهایت میشه

$\Theta( n^{2})$

این یکی از سری ها میشه:

$T(n) < n^{2}\sum _{i = 0}^{log_{\frac {4}{3}}n}(\frac{10}{16})^{i}< cn^{2} = O(n^{2})$
واسه حد پایین هم سری تا

$log_{4}n$ بگیرید و در نهایت میشه

$\Theta( n^{2})$

ارسال: #۳

۲۹ آبان ۱۳۹۲, ۰۴:۴۹ ب.ظ

tarane.68 پاسخ داده:

RE: مرتبه رابطه بازگشتی

با سلام
جواب این رابطه بازگشتی

$n^{2}\log n$ میشه
توی کتاب طراحی الگوریتم آقای مقسمی هم تفریبا چنین مثالی هست.

طبق نکته کتاب آقای مقسمی :

$\frac{3}{4} \frac{1}{4}=1 \Rightarrow n^{2}\log n$

ارسال: #۴

۱۰ شهریور ۱۳۹۲, ۱۲:۳۵ ب.ظ

Masoud05 پاسخ داده:

RE: مرتبه رابطه بازگشتی

یه روش سریع تر هم هست که در آن :

$T(3n/4) T(n/4)= O(n)$

و طبق قضیه اصلی جواب گزینه ۴ میشه.

ارسال: #۵

۱۱ شهریور ۱۳۹۲, ۰۱:۲۷ ق.ظ

SnowBlind پاسخ داده:

RE: مرتبه رابطه بازگشتی

(۱۰ شهریور ۱۳۹۲ ۱۲:۳۵ ب.ظ)Masoud05 نوشته شده توسط: یه روش سریع تر هم هست که در آن :
$T(3n/4) T(n/4)= O(n)$

و طبق قضیه اصلی جواب گزینه ۴ میشه.

قضیه اصلی مگه واسه رابطه های به فرم

$aT(n/b) f(n)$ نیست

ارسال: #۶

۱۱ شهریور ۱۳۹۲, ۱۱:۵۲ ق.ظ

Masoud05 پاسخ داده:

RE: مرتبه رابطه بازگشتی

(۱۱ شهریور ۱۳۹۲ ۰۱:۲۷ ق.ظ)SnowBlind نوشته شده توسط:
(10 شهریور ۱۳۹۲ ۱۲:۳۵ ب.ظ)Masoud05 نوشته شده توسط: یه روش سریع تر هم هست که در آن :
$T(3n/4) T(n/4)= O(n)$

و طبق قضیه اصلی جواب گزینه ۴ میشه.

قضیه اصلی مگه واسه رابطه های به فرم $aT(n/b) f(n)$ نیست

ممنون از توجه تون . دقیقا به همین علت که گفتید ، من در ۲ مرحله جواب گرفتم . مرحله اولش از یه نکته تستی که در کتاب های کنکور اومده استفاده کردم ( که البته روش علمی نیست بنظرم اما برا تست جواب میده ) و مرحله دوم قضیه مستر زدم . این روشی که من گفتم یه خورده خیلی سریع هست و امکان اشتباه هم هست اگه باهاش کار نکرده باشید. بنظرم ساده ترین کار درخت کشیدن باشه .

ارسال: #۷

۲۹ آبان ۱۳۹۲, ۰۵:۵۶ ب.ظ

Mehrdad7soft پاسخ داده:

RE: مرتبه رابطه بازگشتی

جواب این دوست عزیز که آخر جواب داده درست هستش

اگر مجموع برابر با ۱ بشه جواب می‌شه
log n * f
اینجا میشه n^{2}logn

ارسال: #۸

۲۵ مهر ۱۳۹۲, ۰۲:۲۵ ب.ظ

tabassomesayna پاسخ داده:

RE: مرتبه رابطه بازگشتی

سلام
در کتاب ۶۰۰ مسئله ی دکتر قدسی دقیقا" مشابه همین سوال هستش که جواب داده شده :

$n^{2}logn$
یعنی گزینه ۲ , ولی در پاسخنامه گزینه ۴ رو علامت زدن Huh

از روش تستی هم بخوایم بریم گزینه ۲ میشه
آخرش کدوم جوابه ؟؟

ارسال: #۹

۱۴ آذر ۱۳۹۲, ۰۱:۴۰ ب.ظ

hoda ahmadi پاسخ داده:

RE: مرتبه رابطه بازگشتی

سلام دوستان
به نظر من اگه طبق مستر بریم میشه گزینه ۴/
حالا کسی میدونه جواب درستش واقعا چیه؟؟؟

ارسال: #۱۰

۱۴ آذر ۱۳۹۲, ۰۲:۱۲ ب.ظ

tarane.68 پاسخ داده:

RE: مرتبه رابطه بازگشتی

با سلام
در کتاب آقای قدسی عین این مسئله اومده. در گزینه ها جواب زده شده

$n^{2}$ ولی در راه حل ها که مسئله حل شده در نهایت پاسخ درست

$n^{2}logn$ اعلام شده .
جواب کتاب آقای قدسی :

ارسال: #۱۱

۲۷ آذر ۱۳۹۲, ۰۱:۳۲ ب.ظ

۲۰۱۳محمد پاسخ داده:

RE: مرتبه رابطه بازگشتی

دوستان عزیز طبق قرمول : در صورتی که در رابطه ( T(n) = T(a/b) + T(c/d) + F(n

a/b +c/d برابر با یک باشد جواب میشود ( O(log n ) * F(n
پس اینجا هم چون برابر یک میشه پس جواب میشه n^2 log n

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟	Azadam	۶	۵,۴۵۲	۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life
	نظر در رابطه با استاد داور	علیصا	۰	۱,۹۰۴	۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا
	مرتبه ایجاد درخت	rad.bahar	۱	۳,۵۵۲	۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar
	مرتبه شبه کد	rad.bahar	۱	۲,۴۹۰	۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir
	حل مساله مرتبه زمانی حلقه های تو در تو	sarashahi	۱۶	۲۳,۹۸۵	۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda
	مرتبه زمانی	Sanazzz	۱۷	۲۲,۶۲۳	۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh
	مرتبه زمانی یافتن قطر	Sepideh96	۲	۳,۹۹۷	۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30
	مرتبه مانی	Sanazzz	۳	۳,۹۶۷	۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz
	مرتبه زمانی	Sanazzz	۰	۲,۱۳۵	۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz
	درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)	Saman	۶	۷,۸۴۴	۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ آخرین ارسال: saeed_vahidi

مرتبه رابطه بازگشتی

مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

RE: مرتبه رابطه بازگشتی

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?