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

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

ارسال:
۲۷ مهر ۱۳۹۰, ۰۸:۰۶ ب.ظ (آخرین ویرایش در این ارسال: ۲۷ مهر ۱۳۹۰ ۰۸:۱۷ ب.ظ، توسط پشتکار.)
یه سوال بازگشتی از قضیه اصلی
این رابطه بازگشتی رو کسی میتونه حل کنه؟

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


مسئله من زانی هست که درختشو رسم می کنم.
مسئله های دیگه راحت میشه تعیین کردن مقدار i یا بعبارتی ارتفاع درخت چنده.
اینو نمی دونم چطوری باید تعیین کنم
هر راه حلی هم که نگاه کردم همشون کپی هم بودن و من چیزی دستگیرم نشد...Huh
یافتن تمامی ارسال‌های این کاربر
ارسال:
۲۷ مهر ۱۳۹۰, ۰۹:۳۳ ب.ظ (آخرین ویرایش در این ارسال: ۲۷ مهر ۱۳۹۰ ۰۹:۳۴ ب.ظ، توسط si.mozhgan.)
RE: یه سوال بازگشتی از قضیه اصلی
بعد از کشیدن درخت برای بدست آوردن i




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

من می تونم Smile
فرمول موفقیت در کنکور =یک درصد هوش + نود و نه درصد پشتکارIdea
یافتن تمامی ارسال‌های این کاربر
ارسال:
۲۹ مهر ۱۳۹۰, ۱۱:۵۱ ب.ظ
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 داده اند در واقع همان جمع هزینه های سطوح درخت می باشد که هدف ما هم همینه.
و من هم تایید می کنم.


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
ارسال:
۰۲ آبان ۱۳۹۰, ۰۹:۵۲ ب.ظ (آخرین ویرایش در این ارسال: ۰۳ آبان ۱۳۹۰ ۱۱:۴۲ ب.ظ، توسط پشتکار.)
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 هستش.


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
ارسال:
۰۲ آبان ۱۳۹۰, ۱۱:۱۴ ب.ظ (آخرین ویرایش در این ارسال: ۰۲ آبان ۱۳۹۰ ۱۱:۲۰ ب.ظ، توسط - rasool -.)
RE: یه سوال بازگشتی از قضیه اصلی
(۰۲ آبان ۱۳۹۰ ۱۱:۰۰ ب.ظ)sasanlive نوشته شده توسط:  
(02 آبان ۱۳۹۰ ۱۰:۳۰ ب.ظ)yaali نوشته شده توسط:  
(02 آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:  




دلیل [tex]logn-1[/tex] در بالای سیگما اینه که ارتفاع درخت [tex]log\frac{n}{2}[/tex] هستش که [tex]log\frac{n}{2}=logn log\frac{1}{2}=logn-1[/tex].

اینو سوال تو یه topic دیگه هم مطرح شده بود که البته قبلا واسه پیشگیری اونو تو topic زیر توضیح داده بودم . زیاد سوالو گندش نکنین.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
.


دوست عزیزم بحث بزرگ کردن سوال نیست . بحث فهمیدنه .

دلیل شما برای اون "منهای یک" قانع کننده نیست چون:
ارتفاع درخت i= Logn هستش.


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
ارسال: #۱۰
۰۳ آبان ۱۳۹۰, ۰۱:۳۶ ق.ظ (آخرین ویرایش در این ارسال: ۰۳ آبان ۱۳۹۰ ۰۱:۵۲ ق.ظ، توسط sasanlive.)
RE: یه سوال بازگشتی از قضیه اصلی
(۰۲ آبان ۱۳۹۰ ۱۱:۱۴ ب.ظ)yaali نوشته شده توسط:  
(02 آبان ۱۳۹۰ ۱۱:۰۰ ب.ظ)sasanlive نوشته شده توسط:  
(02 آبان ۱۳۹۰ ۱۰:۳۰ ب.ظ)yaali نوشته شده توسط:  
(02 آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:  




دلیل [tex]logn-1[/tex] در بالای سیگما اینه که ارتفاع درخت [tex]log\frac{n}{2}[/tex] هستش که [tex]log\frac{n}{2}=logn log\frac{1}{2}=logn-1[/tex].

اینو سوال تو یه topic دیگه هم مطرح شده بود که البته قبلا واسه پیشگیری اونو تو topic زیر توضیح داده بودم . زیاد سوالو گندش نکنین.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
.


دوست عزیزم بحث بزرگ کردن سوال نیست . بحث فهمیدنه .

دلیل شما برای اون "منهای یک" قانع کننده نیست چون:
ارتفاع درخت i= Logn هستش.
بله ارتفاع logn هست . به دلیل اینکه سریع جواب میدم بعضی اوقات احتمال اشتباه هست.

دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.

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

برای همین مقدار بالای سیگما را تا logn-1 گرفت.

پــرواز را به خاطـر بسپـار پـرنده مردنـی اسـت.
یافتن تمامی ارسال‌های این کاربر
ارسال: #۱۱
۰۴ آبان ۱۳۹۰, ۰۹:۴۹ ق.ظ (آخرین ویرایش در این ارسال: ۰۴ آبان ۱۳۹۰ ۰۹:۵۹ ق.ظ، توسط پشتکار.)
RE: یه سوال بازگشتی از قضیه اصلی
(۰۳ آبان ۱۳۹۰ ۰۱:۳۶ ق.ظ)sasanlive نوشته شده توسط:  دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.

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

برای همین مقدار بالای سیگما را تا logn-1 گرفت.

این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
یافتن تمامی ارسال‌های این کاربر
ارسال: #۱۲
۰۹ آبان ۱۳۹۰, ۱۲:۱۲ ق.ظ
RE: یه سوال بازگشتی از قضیه اصلی
(۰۴ آبان ۱۳۹۰ ۰۹:۴۹ ق.ظ)پشتکار نوشته شده توسط:  [quote='sasanlive' pid='50982' dateline='1319490371']

این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
چون این رابطه بازگشتی یه درخت کامل رو تشکیل میده و چون سطح ریشه رو از صفر در نظر گرفتیم. پس در سطح آخر[tex]2^{i}[/tex] گره داره که هزینه هرکدومشون ۱ هست. و ارتفاع درخت هم [tex]i=logn[/tex] هست. پس مجموع هزینه سطح آخر میشه:

[tex]2^{i}*1=2^{logn}*1=n[/tex]

پــرواز را به خاطـر بسپـار پـرنده مردنـی اسـت.
یافتن تمامی ارسال‌های این کاربر


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  خرید کتاب زبان اصلی آموزش برنامه نویسی جاوا 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