در کتاب پوران دوتا درخت بازگشتی کشیده که یکیش برای تابع [tex]T(n)=2T(\frac{n}{2}) n^2[/tex] که رسمش کرده و فقط هر سطر را با هم جمع کرده و در نهایت همه را با هم جمع کرده که شده [tex]O(n^2)[/tex] !
یکی دیگه که تابعش [tex]T(n)=T(\frac{n}{2}) T(\frac{2n}{3}) n[/tex] هست را هر سطر را جمع کرده و در نهایت همه را جمع کرده و شده [tex]O(nlogn)[/tex] که در توضیح نوشته که باید ارتفاع درخت هم در اون ضرب بشه!
چرا در اولی ارتفاع درخت ضرب نشده ولی در دومی ضرب شده؟
اصن نحوه ی کشیدن درخت بازگشت به چه صورته؟ نه توی کتاب مقسمی و نه توی کتاب پوران توضیح ندادن ، فقط یکی دوتا مثال گفتن و رد شدن!
سلام
تو بعضی از درخت ها جمع هر سطر با سطر دیگه برابر نیست در این حالت باید همه ی سطر ها رو با هم جمع زد ( در این حالت هااکثرا ارتفاع درخت برای ما مهم نیست)
مثلا همون رابطه ی اولی که نوشته اید سطر اول درخت n سطر دوم n/2 سطر بعد n/4 سطر بعد n/8 و... است
پس مرتبه می شه
[tex]n^2 n^2/2 n^2/4 n^2/8 ...=n^2(1 1/2 1/4 1/8 ...)=n^2(\frac{1}{1-\frac{1}{2}})=O(n^2)[/tex]
دقت کنید که چون عبارت داخل پرانتز یک تصاعد هندسی نزولی است پس اصلا انتعاش مهم نیست پس مهم نیست که ماارتفاع درخت رو بدونیم .
اما بعضی از حالت های درخت بازگشتی ها وقتی نودهای هر سطر را جمع بزنیم تقریبا مساوی هستند در این شرایط به جای جمع زدن مقدار کل سطرها با هم می آییم یک سطر را در تعداد سطرها ضرب می کنیم واضه دیگه یعنی مثلا به جای این که بنویسیم ۵+۵+۵+۵ می نویسیم ۵*۴ در یان شرایط ارتفاع درخت مهم می شود
(۱۶ مهر ۱۳۹۳ ۱۲:۴۳ ب.ظ)fatemeh69 نوشته شده توسط: سلام
تو بعضی از درخت ها جمع هر سطر با سطر دیگه برابر نیست در این حالت باید همه ی سطر ها رو با هم جمع زد ( در این حالت هااکثرا ارتفاع درخت برای ما مهم نیست)
مثلا همون رابطه ی اولی که نوشته اید سطر اول درخت n سطر دوم n/2 سطر بعد n/4 سطر بعد n/8 و... است
پس مرتبه می شه
[tex]n^2 n^2/2 n^2/4 n^2/8 ...=n^2(1 1/2 1/4 1/8 ...)=n^2(\frac{1}{1-\frac{1}{2}})=O(n^2)[/tex]
دقت کنید که چون عبارت داخل پرانتز یک تصاعد هندسی نزولی است پس اصلا انتعاش مهم نیست پس مهم نیست که ماارتفاع درخت رو بدونیم .
اما بعضی از حالت های درخت بازگشتی ها وقتی نودهای هر سطر را جمع بزنیم تقریبا مساوی هستند در این شرایط به جای جمع زدن مقدار کل سطرها با هم می آییم یک سطر را در تعداد سطرها ضرب می کنیم واضه دیگه یعنی مثلا به جای این که بنویسیم ۵+۵+۵+۵ می نویسیم ۵*۴ در یان شرایط ارتفاع درخت مهم می شود
در تکمیل حرفای دوستمون، در اولی اگر دقت کنی داخل پارانتز نهایتا از ۱ کوچکتر هست. پس چه بهتر مجموع اون اعداد رو یک حساب کنیم (البته چون صحبت از مرتبه اجرایی است اینقدر ساده میگما
)اما در دومی اگر سطرها رو جمع بزنی میشه [tex]n_1 n_2 n_3 \: ....\: n_h[/tex]
خب اگه بیاییم از n فاکتور بگیریم میشه [tex]n(1 1 1 ... 1)[/tex] که تعداد ۱ های داخل پارانتز h تا است، اما h چنده؟ خب اینم ارتفاع درخت میشه که همون logn هست که تو ریاضی گسسته خوب توضیح داده شده.
البته یه نکته دیگه اینکه در درخت بازگشت، ارتفاع رو بدترین حالت یعنی همون گرهی که ارتفاعش از همه بزرگتر است رو در نظر میگیریم. واسه همین در این مثال دومی میاد ارتفاع رو [tex]\log_{\frac{3}{2}}n[/tex] که همان [tex]\log_ba[/tex] هست که a و b هم تو مرتبه اجرایی T(n) هستند.
اما نهایتا تو جواب نهایی همون logn لحاظ میشه (باز طبق تعریف مرتبه اجرایی)
ممنون از شما دو دوست عزیز
کاملا محاسبه اش رو از روی درخت متوجه شدم
فقط اینکه چه جوری می تونم درخت رو بکشم؟
می شه یه توضیحی در مورد رسم درخت بفرمایید.
(۱۶ مهر ۱۳۹۳ ۰۱:۳۵ ب.ظ)poldasht نوشته شده توسط: اگر دقت کنی داخل پارانتز نهایتا از ۱ کوچکتر هست.
یه چیزی، ظاهرا داخل پارانتز آنچنان که گفتم هم از یک کوچکتر نیست
، اما به هر حال یه عدد ثابته که دوستمون زحمتشو کشیدن نوشتن که میشه ۲، یکم از ۱ بزرگتر عدد ثابتم فرقی نداره تو مرتبه اجرایی چند باشه، چون کلا حساب نمیشه.
دوستان مثلا چنین تابعی رو چه جوری می شه براش درخت کشید؟
[tex]T(n)=3T(n-2) 2^nlgn[/tex]
(۱۸ مهر ۱۳۹۳ ۰۹:۲۲ ب.ظ)atropak نوشته شده توسط: دوستان مثلا چنین تابعی رو چه جوری می شه براش درخت کشید؟درخت کشیدنش کاری نداره حل کردنش و بدست آوردن حاصل جمع نودهاش سخته
[tex]T(n)=3T(n-2) 2^nlgn[/tex]
برای درخت کشیدن شما رابطه بازگشتی رو می نویسی و طرف سمت راست مساوی هر چی که به فرم T بود رو توی برگ و هر چیز دیگه رو تو ریشه قرار می دهیم
یعنی تو مرحله اول T(n-2) ها توی برگ و [tex]2^n\log n[/tex] توی ریشه قرار می گیره
حالا همون T(n-3) رو هم معادله شو از روی معادله اصلی به دست میاریم وهر چی به فرم T یود تو برگ ها و غیر آن را ریشه ی زیر درخت قرار می دهیم و این کار را تا رسیدن به پایه ی رابطه ی بازگشتی ادامه می دهیم اگر رابطه ی بازگشتی پایه (یا شرط اولیه ) نداشت تا وقتی که عبارات معنادار هستند ادامه می دهیم
البته این چیزی رو که نوشته اید فعلا نمی دونم از چه مرتبه زمانیه
بچا ها فصل اول کتاب پوران فرمول های خیلی جالبی در مورد این مرتبه ها گذاشته بخونید خیلی خوبه و راحت البته حفظی
(۱۶ مهر ۱۳۹۳ ۱۲:۴۳ ب.ظ)fatemeh69 نوشته شده توسط: .... به جای این که بنویسیم ۵+۵+۵+۵ می نویسیم ۵*۴ در یان شرایط ارتفاع درخت مهم می شودلطفاً توضیح بدید ارتفاع درخت چطوری بدست میاد؟
(۲۱ مهر ۱۳۹۳ ۱۱:۵۹ ب.ظ)Ametrine نوشته شده توسط: لطفاً توضیح بدید ارتفاع درخت چطوری بدست میاد؟تو این مثالی که نوشتید در هر سطح از درخت ۲ تا از مقدار n کم می شود درخت تا سطحی ا دامه دارد که n به ۲ برسد (چرادو؟ چون مبنای لگاریتممان دو است و لگاریتم عدد کمتر از دو در مبنای دو منفی می شود)
حالا وقتی از n شروع می کنیم و می خواهیم به دو برسیم و هر سطح که میایم پایین دو واحد کم می شه چند سطح باید بیاییم پایین تا بشه دو؟
n-2/2
چرا؟
چون اگه از n قرار بود دو واحد دو واحد کم بشه تا به صفر برسیم باید n/2 بار کم می کردیم
اما اگه بخواهیم به دو برسیم باید (n-2)/2بار کم کنیم
(۲۲ مهر ۱۳۹۳ ۱۲:۵۷ ق.ظ)fatemeh69 نوشته شده توسط:تشکر، متوجه شدم.(21 مهر ۱۳۹۳ ۱۱:۵۹ ب.ظ)Ametrine نوشته شده توسط: لطفاً توضیح بدید ارتفاع درخت چطوری بدست میاد؟تو این مثالی که نوشتید در هر سطح از درخت ۲ تا از مقدار n کم می شود درخت تا سطحی ا دامه دارد که n به ۲ برسد (چرادو؟ چون مبنای لگاریتممان دو است و لگاریتم عدد کمتر از دو در مبنای دو منفی می شود)
حالا وقتی از n شروع می کنیم و می خواهیم به دو برسیم و هر سطح که میایم پایین دو واحد کم می شه چند سطح باید بیاییم پایین تا بشه دو؟
n-2/2
چرا؟
چون اگه از n قرار بود دو واحد دو واحد کم بشه تا به صفر برسیم باید n/2 بار کم می کردیم
اما اگه بخواهیم به دو برسیم باید (n-2)/2بار کم کنیم