زمان کنونی: ۰۶ دى ۱۴۰۳, ۰۹:۵۵ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

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

ارسال:
  

m@hboobe پرسیده:

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

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

[tex]T(n)=T(n/4) T(3n/4) n^{2}[/tex]

در صورتی که [tex]T(1)=1[/tex]

الف) [tex]\theta (nlogn)[/tex]
ب) [tex]\theta (n^{2}logn)[/tex]
ج) [tex]\theta (n^{3})[/tex]
د) [tex]\theta (n^{2})[/tex]
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

SnowBlind پاسخ داده:

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

اگه شما درخت این رابطه رو بکشید یه درخت نا متوازن داره که به یکی با ارتفاع [tex]log_{4}(n)[/tex] و دیگری [tex]log_{\frac{4}{3}}(n)[/tex]

که اگه شما یه مجموع بزنی حد بالا و پایین بدست میاد و در نهایت میشه [tex]\Theta( n^{2})[/tex]

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

[tex]T(n) < n^{2}\sum _{i = 0}^{log_{\frac {4}{3}}n}(\frac{10}{16})^{i}< cn^{2} = O(n^{2})[/tex]
واسه حد پایین هم سری تا [tex]log_{4}n[/tex] بگیرید و در نهایت میشه
[tex]\Theta( n^{2})[/tex]
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

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

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

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




طبق نکته کتاب آقای مقسمی :
[tex]\frac{3}{4} \frac{1}{4}=1 \Rightarrow n^{2}\log n[/tex]
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Masoud05 پاسخ داده:

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

یه روش سریع تر هم هست که در آن :
[tex]T(3n/4) T(n/4)= O(n)[/tex]

و طبق قضیه اصلی جواب گزینه ۴ میشه.
نقل قول این ارسال در یک پاسخ

ارسال:
  

SnowBlind پاسخ داده:

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

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

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

قضیه اصلی مگه واسه رابطه های به فرم [tex]aT(n/b) f(n)[/tex] نیست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Masoud05 پاسخ داده:

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

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

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

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

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

۱
ارسال:
  

Mehrdad7soft پاسخ داده:

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

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

اگر مجموع برابر با ۱ بشه جواب می‌شه
log n * f
اینجا میشه n^{2}logn
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tabassomesayna پاسخ داده:

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

سلام
در کتاب ۶۰۰ مسئله ی دکتر قدسی دقیقا" مشابه همین سوال هستش که جواب داده شده :
[tex]n^{2}logn[/tex]
یعنی گزینه ۲ , ولی در پاسخنامه گزینه ۴ رو علامت زدنHuh
از روش تستی هم بخوایم بریم گزینه ۲ میشه
آخرش کدوم جوابه ؟؟
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

hoda ahmadi پاسخ داده:

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

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

۰
ارسال: #۱۰
  

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

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

با سلام
در کتاب آقای قدسی عین این مسئله اومده. در گزینه ها جواب زده شده [tex]n^{2}[/tex] ولی در راه حل ها که مسئله حل شده در نهایت پاسخ درست [tex]n^{2}logn[/tex] اعلام شده .
جواب کتاب آقای قدسی :


نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۱
  

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

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به 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

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

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

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close