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

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

ارسال:
  

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

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

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

[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 هستش.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال از بازگشتی Aurora ۷ ۳,۲۰۳ ۱۷ شهریور ۱۳۹۱ ۱۱:۴۰ ب.ظ
آخرین ارسال: azad_ahmadi
  (کمک در حل تست) تابع بازگشتی مربوط به برج هانوی samaneh_aftab ۴ ۵,۴۱۴ ۰۵ تیر ۱۳۹۱ ۰۱:۰۴ ب.ظ
آخرین ارسال: Parva
Lightbulb درخواست راهنمایی در حل رابطه بازگشتی - rasool - ۵۱ ۵,۴۸۸ ۲۴ بهمن ۱۳۹۰ ۰۷:۱۷ ق.ظ
آخرین ارسال: sasanlive
Lightbulb روابط بازگشتی دو متغیره - rasool - ۳ ۱,۹۷۸ ۰۶ دى ۱۳۹۰ ۰۵:۲۷ ب.ظ
آخرین ارسال: homa
Smile حل رابطه بازگشتی Mojtaba ۹ ۲,۲۱۴ ۰۶ آبان ۱۳۹۰ ۱۱:۰۵ ب.ظ
آخرین ارسال: - rasool -
  تبدیلات در قضیه اصلی پشتکار ۶ ۱,۷۲۷ ۰۴ آبان ۱۳۹۰ ۰۳:۲۸ ب.ظ
آخرین ارسال: - rasool -
  جواب رابطه بازگشتی زیر چیست؟ پشتکار ۷ ۲,۲۴۵ ۲۸ مهر ۱۳۹۰ ۱۱:۲۸ ق.ظ
آخرین ارسال: si.mozhgan
  حل یه رابطه بازگشتی و نکته مهم آن پشتکار ۴ ۲,۲۵۷ ۲۵ مهر ۱۳۹۰ ۱۱:۵۲ ب.ظ
آخرین ارسال: ahmadi_development
Question سوال از روابط بازگشتی livane_abi ۱۲ ۵,۵۲۱ ۱۹ مهر ۱۳۹۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: Masoud05
  مرتبه اجرایی تابع بازگشتی khavar_1365 ۶ ۶,۹۷۶ ۱۴ مهر ۱۳۹۰ ۱۱:۰۱ ب.ظ
آخرین ارسال: summer_66

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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