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

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

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

[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]

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Star دوره موضوعی --> حل روابط بازگشتی --> روابط دهم - rasool - ۲ ۲,۱۴۲ ۰۳ بهمن ۱۳۹۳ ۱۲:۴۵ ق.ظ
آخرین ارسال: mostafa2012
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه ششم - rasool - ۸ ۳,۶۲۶ ۰۱ آبان ۱۳۹۲ ۱۰:۰۷ ق.ظ
آخرین ارسال: Mänu
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - rasool - ۵ ۲,۶۲۹ ۱۳ مهر ۱۳۹۲ ۰۳:۲۵ ب.ظ
آخرین ارسال: vojoudi
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هفتم - rasool - ۱ ۱,۹۸۲ ۱۱ بهمن ۱۳۹۰ ۰۴:۰۶ ب.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم - rasool - ۴ ۲,۶۱۷ ۱۱ بهمن ۱۳۹۰ ۱۲:۱۹ ب.ظ
آخرین ارسال: Masoud05
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه پنجم - rasool - ۱ ۲,۰۸۲ ۱۱ بهمن ۱۳۹۰ ۱۲:۱۸ ب.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هشتم - rasool - ۱ ۲,۲۸۸ ۱۰ بهمن ۱۳۹۰ ۰۹:۰۷ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه چهارم - rasool - ۱ ۱,۸۱۹ ۱۰ بهمن ۱۳۹۰ ۰۹:۰۰ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه دوم - rasool - ۱ ۲,۲۱۷ ۱۰ بهمن ۱۳۹۰ ۰۲:۳۴ ب.ظ
آخرین ارسال: Mohammad-A
  مرتبه این تابع بازگشتی از چه راهی بدست میاید ahmadi_development ۵ ۳,۳۲۸ ۱۸ مهر ۱۳۹۰ ۰۶:۳۷ ب.ظ
آخرین ارسال: sasanlive

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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