۰
subtitle
ارسال: #۱
  
رابطه بازگشتی
T(n)=2T(n/2) + n/logn
۱)بچه ها کسی میتونه حل اینو برام توضیح بده!!
پارسه درخت بازگشتیو برای فقطn/lognکشیده ک من سر درنیاوردم ازش!
۲)تو رابطه بازگشتی زیر مرتبه رو n^2بگیریم؟؟پارسه حل کرده شدهn^2 logn
T(n)= 16T(n/4) + n^2
۱)بچه ها کسی میتونه حل اینو برام توضیح بده!!
پارسه درخت بازگشتیو برای فقطn/lognکشیده ک من سر درنیاوردم ازش!
۲)تو رابطه بازگشتی زیر مرتبه رو n^2بگیریم؟؟پارسه حل کرده شدهn^2 logn
T(n)= 16T(n/4) + n^2
۱
ارسال: #۲
  
RE: رابطه بازگشتی
سلام برای پاسخ به سوال اولتون ببینید.
درختشو رسم میکنیم.من به صورت سطح سطح براتون مینویسم:
سطح اول(فقط ریشه)[tex]\leftarrow[/tex][tex]\frac{n}{Logn}[/tex]
سطح دوم[tex]\leftarrow[/tex][tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})},\frac{\frac{n}{2}}{\log(\frac{n}{2})}[/tex]
سطح سوم[tex]\leftarrow[/tex] 4 تا عبارت [tex]\frac{\frac{n}{4}}{Log(\frac{n}{4})}[/tex] داریم
سطوح بعدی هم همین ریتم رو داره.حالا باید مقادیر تمام سطوح رو با هم جمع بزنیم:
[tex]\frac{n}{\log(n)} \frac{n}{\log(\frac{n}{2})} \frac{n}{\log(\frac{n}{4})} \frac{n}{\log(\frac{n}{8})} ......[/tex]
که حالا اینجری ساده میکنیم:
[tex]\: n(\frac{1}{\log(n)} \frac{1}{\log(n)-1} \frac{1}{\log(n)-2} \frac{1}{\log(n)-3} ......)[/tex]
که این عبارت همین عبارته زیره و ما اونو برعکس نوشتیم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})[/tex]
و این رابطه رو هم میدونیم:
[tex](\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{EveryThing})=Ln(EveryThing)[/tex]
پس برای رابطه بالا داریم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})=n\ast Ln(Log(n))=(n)LogLog(n)[/tex]
پاسخ سوال دومتون هم ببینید رابطه ما اینه:
[tex]T(n)=16T(\frac{n}{4}) n^2[/tex]
از قضیه اصلی استفاده میکنیم:[tex]Log^{16}_4=2\rightarrow n^2=n^2\rightarrow T(n)=n^2Log(n)[/tex]
[tex]n^2[/tex] سمت راست همون [tex]n^2[/tex] تو معادله هستش
درختشو رسم میکنیم.من به صورت سطح سطح براتون مینویسم:
سطح اول(فقط ریشه)[tex]\leftarrow[/tex][tex]\frac{n}{Logn}[/tex]
سطح دوم[tex]\leftarrow[/tex][tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})},\frac{\frac{n}{2}}{\log(\frac{n}{2})}[/tex]
سطح سوم[tex]\leftarrow[/tex] 4 تا عبارت [tex]\frac{\frac{n}{4}}{Log(\frac{n}{4})}[/tex] داریم
سطوح بعدی هم همین ریتم رو داره.حالا باید مقادیر تمام سطوح رو با هم جمع بزنیم:
[tex]\frac{n}{\log(n)} \frac{n}{\log(\frac{n}{2})} \frac{n}{\log(\frac{n}{4})} \frac{n}{\log(\frac{n}{8})} ......[/tex]
که حالا اینجری ساده میکنیم:
[tex]\: n(\frac{1}{\log(n)} \frac{1}{\log(n)-1} \frac{1}{\log(n)-2} \frac{1}{\log(n)-3} ......)[/tex]
که این عبارت همین عبارته زیره و ما اونو برعکس نوشتیم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})[/tex]
و این رابطه رو هم میدونیم:
[tex](\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{EveryThing})=Ln(EveryThing)[/tex]
پس برای رابطه بالا داریم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})=n\ast Ln(Log(n))=(n)LogLog(n)[/tex]
پاسخ سوال دومتون هم ببینید رابطه ما اینه:
[tex]T(n)=16T(\frac{n}{4}) n^2[/tex]
از قضیه اصلی استفاده میکنیم:[tex]Log^{16}_4=2\rightarrow n^2=n^2\rightarrow T(n)=n^2Log(n)[/tex]
[tex]n^2[/tex] سمت راست همون [tex]n^2[/tex] تو معادله هستش
۱
ارسال: #۳
  
RE: رابطه بازگشتی
ببخشید این توضیحات رو میدم جسارت نباشه!!!
ببینید درخت بازگشت رو چجوری رسم میکنیم؟؟
قسمت ثابت ریشه و شاخه هامون هم قسمت های بازگشتی میشن قبول؟؟؟؟
حالا قسمت ثابت چیه؟[tex]\frac{n}{Log(n)}[/tex]
و در ضمن ما رابطه اصلی رو به این رابطه تبدیل میکنیم:[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) \frac{n}{Log(n)}[/tex]
خب ریشه که شد [tex]\frac{n}{Log(n)}[/tex] و شاخه سمت چپ و راست که یکین.حالا شاخه چجوریه.دقت کنید قسمت بازگشتی ما به صورت [tex]\frac{n}{2}[/tex] هستش به زبون ساده میگم تو سطح بعد هر جا [tex]n[/tex] دیدی جاش [tex]n/2[/tex] بذار خب؟؟؟
حالا ما [tex]\frac{n}{Log(n)}[/tex] رو داریم جای [tex]n[/tex] هاش [tex]n/2[/tex] میذاریم که میشه:[tex]\frac{\frac{n}{2}}{Log(\frac{n}{2})}[/tex]
ببینید ما در واقع اصل کار اینه [tex]\frac{n}{Log(n)}[/tex] رو داریم و هر بار داریم نصفش میکنیم
ببینید درخت بازگشت رو چجوری رسم میکنیم؟؟
قسمت ثابت ریشه و شاخه هامون هم قسمت های بازگشتی میشن قبول؟؟؟؟
حالا قسمت ثابت چیه؟[tex]\frac{n}{Log(n)}[/tex]
و در ضمن ما رابطه اصلی رو به این رابطه تبدیل میکنیم:[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) \frac{n}{Log(n)}[/tex]
خب ریشه که شد [tex]\frac{n}{Log(n)}[/tex] و شاخه سمت چپ و راست که یکین.حالا شاخه چجوریه.دقت کنید قسمت بازگشتی ما به صورت [tex]\frac{n}{2}[/tex] هستش به زبون ساده میگم تو سطح بعد هر جا [tex]n[/tex] دیدی جاش [tex]n/2[/tex] بذار خب؟؟؟
حالا ما [tex]\frac{n}{Log(n)}[/tex] رو داریم جای [tex]n[/tex] هاش [tex]n/2[/tex] میذاریم که میشه:[tex]\frac{\frac{n}{2}}{Log(\frac{n}{2})}[/tex]
ببینید ما در واقع اصل کار اینه [tex]\frac{n}{Log(n)}[/tex] رو داریم و هر بار داریم نصفش میکنیم
۰
ارسال: #۴
  
RE: رابطه بازگشتی
موضوع اینه چرا فقط برای n/lognدرخت اومده کشیده؟؟؟؟؟؟؟؟
بعدم رو چ حساب nlognتو سطح بعد میشه ۲تا[tex]\frac{n}{\frac{2}{\log(\frac{n}{2})}}[/tex] میشه؟؟؟؟؟
بعدم رو چ حساب nlognتو سطح بعد میشه ۲تا[tex]\frac{n}{\frac{2}{\log(\frac{n}{2})}}[/tex] میشه؟؟؟؟؟
۰
ارسال: #۵
  
RE: رابطه بازگشتی
مشکل من همین رسم درخت بازگشتی بود!!!!!
پس همیشه مقدار ثابت رو ریشه میگیرم!!مث روند تقسیم و حل فرزندانش رو میسازیم درسته؟
مثلا تو مسئله زیر داریم:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10}) n[/tex]
ریشه رو n می گیریم بعد فرزند چپ میشه [tex]\frac{n}{5}[/tex]فرزند راست هم میشه[tex]\frac{7n}{10}[/tex]
بعد زیر درخت چپ هر دفعه بجای n میزاریم [tex]\frac{n}{5}[/tex] برای زیر درخت راست هم بجای n میزاریم [tex]\frac{7n}{10}[/tex]؟؟؟؟؟؟؟
درست میگم یا نه؟
پس همیشه مقدار ثابت رو ریشه میگیرم!!مث روند تقسیم و حل فرزندانش رو میسازیم درسته؟
مثلا تو مسئله زیر داریم:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10}) n[/tex]
ریشه رو n می گیریم بعد فرزند چپ میشه [tex]\frac{n}{5}[/tex]فرزند راست هم میشه[tex]\frac{7n}{10}[/tex]
بعد زیر درخت چپ هر دفعه بجای n میزاریم [tex]\frac{n}{5}[/tex] برای زیر درخت راست هم بجای n میزاریم [tex]\frac{7n}{10}[/tex]؟؟؟؟؟؟؟
درست میگم یا نه؟
ارسال: #۶
  
RE: رابطه بازگشتی
(۱۳ دى ۱۳۹۳ ۰۱:۴۷ ب.ظ)shamim_70 نوشته شده توسط: مشکل من همین رسم درخت بازگشتی بود!!!!!
پس همیشه مقدار ثابت رو ریشه میگیرم!!مث روند تقسیم و حل فرزندانش رو میسازیم درسته؟
مثلا تو مسئله زیر داریم:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10}) n[/tex]
ریشه رو n می گیریم بعد فرزند چپ میشه [tex]\frac{n}{5}[/tex]فرزند راست هم میشه[tex]\frac{7n}{10}[/tex]
بعد زیر درخت چپ هر دفعه بجای n میزاریم [tex]\frac{n}{5}[/tex] برای زیر درخت راست هم بجای n میزاریم [tex]\frac{7n}{10}[/tex]؟؟؟؟؟؟؟
درست میگم یا نه؟
بله کاملا درسته!!!!ببین هر بار که داشتی میشکستی یه نودی رو باید دو شاخه براش بذاری یکی از شاخه ها n/10 و یکی ۷n/10
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۷۹۱ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) | Saman | ۶ | ۷,۵۸۹ |
۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ آخرین ارسال: saeed_vahidi |
|
رابطه n~1 | Mr.R3ZA | ۰ | ۲,۰۱۴ |
۲۰ خرداد ۱۳۹۷ ۰۱:۳۵ ق.ظ آخرین ارسال: Mr.R3ZA |
|
توصیه های مهم در رابطه با انتخاب رشته (مهم) | Happiness.72 | ۰ | ۲,۱۸۲ |
۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ آخرین ارسال: Happiness.72 |
|
رابطه چند به یک | somayeh afsh | ۰ | ۱,۷۶۳ |
۰۷ خرداد ۱۳۹۷ ۱۲:۲۸ ب.ظ آخرین ارسال: somayeh afsh |
|
رسم درخت بازگشتی برای t(n)=9t(n/3)+n | jumper | ۶ | ۶,۷۸۸ |
۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ آخرین ارسال: jumper |
|
حل رابطه جایگذاری با تکرار | rahkaransg | ۱ | ۲,۳۶۴ |
۱۷ دى ۱۳۹۶ ۱۱:۲۹ ق.ظ آخرین ارسال: rahkaransg |
|
حل روابط بازگشتی درجه ۳ | rahkaransg | ۲ | ۳,۱۳۶ |
۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ آخرین ارسال: rahkaransg |
|
جواب رابطه های بازگشتی | rahkaransg | ۰ | ۱,۸۷۱ |
۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ آخرین ارسال: rahkaransg |
|
تقسیم در جبر رابطه ای | Ella | ۱ | ۲,۳۱۹ |
۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ آخرین ارسال: Ella |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close