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

یه سوال بازگشتی از قضیه اصلی

ارسال:
  

پشتکار پرسیده:

یه سوال بازگشتی از قضیه اصلی

این رابطه بازگشتی رو کسی میتونه حل کنه؟

[tex]T(n)=2T(\frac{n}{2}) \frac{n}{logn}[/tex]


مسئله من زانی هست که درختشو رسم می کنم.
مسئله های دیگه راحت میشه تعیین کردن مقدار i یا بعبارتی ارتفاع درخت چنده.
اینو نمی دونم چطوری باید تعیین کنم
هر راه حلی هم که نگاه کردم همشون کپی هم بودن و من چیزی دستگیرم نشد...Huh

۰
ارسال:
  

si.mozhgan پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

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




کجا مشکل دارین؟

ارسال:
  

پشتکار پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

(۲۷ مهر ۱۳۹۰ ۰۹:۳۳ ب.ظ)si.mozhgan نوشته شده توسط:  بعد از کشیدن درخت برای بدست آوردن i



کجا مشکل دارین؟

مگه نباید کل رابطه رو برابر یک قرار بدیم؟
n رو در صورت هیچی در نظر نگیریم؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

من نمی دونم مشکلتون کجاست درخت رو کشیدم وضمیمه می کنم ارتفاع درخت هم lgn است
که از روی درخت روابط زیر رو داریم
[tex]\frac{n}{lgn} \frac{n}{lgn-1} \frac{n}{lgn-2} ...=n(\frac{1}{lgn} \frac{1}{lgn-1} \frac{1}{lgn-2} ...)=nlglgn[/tex]


فایل‌(های) پیوست شده

۰
ارسال:
  

پشتکار پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

ببینید مسئله من اینجاس که اگر قرار باشه [tex]\frac{n}{logn-i}[/tex] رو برابر یک قرار بدهیم.
پس i چطوری حساب میشه؟

۰
ارسال:
  

- rasool - پاسخ داده:

یه سوال بازگشتی از قضیه اصلی

برای یافتن ارتفاع درخت شما باید عبارت داخل پرانتز جلوی T رو پس از i مرحله مساوی یک بگذارید.

یعنی [tex]\LARG \frac{n}{2^{i}}=1\rightarrow i=Log n[/tex]

(البته من سطح ریشه رو صفر فرض کردم)

--------------------------------------------------------------------------------------------
اون جوابی هم که دوستمون ahmadnouri داده اند در واقع همان جمع هزینه های سطوح درخت می باشد که هدف ما هم همینه.
و من هم تایید می کنم.

۰
ارسال:
  

پشتکار پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

متوجه شدم: Smile
ببینید داریم:

[tex]\frac{n}{2^{i}}=1[/tex]

[tex]i = logn[/tex]

[tex]\sum_{i=0}^{logn-1}\frac{n}{logn-i}[/tex]

حالا علت اینکه سیگما تا logn-1 هستش اینه که اگه تا logn باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بودBig Grin

ارسال:
  

- rasool - پاسخ داده:

RE: یه سوال بازگشتی از قضیه اصلی

(۰۲ آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:  متوجه شدم: Smile
ببینید داریم:

[tex]\frac{n}{2^{i}}=1[/tex]

[tex]i = logn[/tex]

[tex]\sum_{i=1}^{logn-1}\frac{n}{logn-i}[/tex]

حالا علت اینکه سیگما تا logn-1 هستش اینه که اگه تا logn باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بودBig Grin

روی سیکما i از صفر شروع می شه نه از یک.( سطح ریشه صفره)

در مورد اون "منهای یک" که در Lgn -1 بالای سیکما هستش هم فکر می کنم باید دلیل بهتری (یک دلیل ساختمان داده ای) برای اومدنش داشته باشه.


چون بازه‌ی سیکما باید از i=0 (سطح صفرم) تا سطح آخر( یعنی i )باشه و i هم مساوی Log n هستش.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  خرید کتاب زبان اصلی آموزش برنامه نویسی جاوا moslem73421 ۶ ۹۰۴ ۱۴ فروردین ۱۳۹۹ ۰۹:۰۶ ب.ظ
آخرین ارسال: marvelous
  مطالعه کتاب زبان اصلی saharitst ۲ ۳۱۷ ۱۱ اسفند ۱۳۹۸ ۱۱:۳۸ ب.ظ
آخرین ارسال: saharitst
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۲,۶۵۵ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
Sad سوال از قضیه ی بیز Nazari76 ۱ ۹۹۸ ۲۶ خرداد ۱۳۹۷ ۰۷:۵۴ ب.ظ
آخرین ارسال: saeed_vahidi
  تشخیص دو قضیه از هم Mr.R3ZA ۵ ۱,۵۱۳ ۳۱ اردیبهشت ۱۳۹۷ ۱۲:۱۴ ق.ظ
آخرین ارسال: pioneer01
  فروش کتاب های منبع اصلی و کنکوری ارشد htninety ۰ ۷۹۰ ۱۱ فروردین ۱۳۹۷ ۰۴:۵۹ ب.ظ
آخرین ارسال: htninety
  رسم درخت بازگشتی برای t(n)=9t(n/3)+n jumper ۶ ۱,۹۹۶ ۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ
آخرین ارسال: jumper
  حل روابط بازگشتی درجه ۳ rahkaransg ۲ ۹۰۹ ۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ
آخرین ارسال: rahkaransg
  جواب رابطه های بازگشتی rahkaransg ۰ ۵۵۷ ۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ
آخرین ارسال: rahkaransg
  روابط بازگشتی amir_ghanati ۴ ۱,۳۰۶ ۰۴ شهریور ۱۳۹۶ ۰۳:۲۳ ق.ظ
آخرین ارسال: amir_ghanati

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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