سلام خسته نباشید.دوستانی که از روی جزوه ساختمان اقای یوسفی( که بچه ها لطف کردن توی سایت قرار دادن) پیش میرن ،من توی قسمت درخت های بازگشتی با چند تا سوال مواجه شدم ممنون میشم کمکم کنید
۱-توی صفحه ۱۸ مثال [tex]T(n)=T(\frac{n}{3}) T(\frac{2n}{3}) n[/tex] چرا وقتی به این نتیجه رسیدیم که [tex]n.Log^n_3\: <\: T(n)\: <n.Log^n_{\frac{3}{2}}[/tex] بعدش گفتیم که:
[tex]T(n)=Ω(n.Log^n_{\frac{3}{2}})[/tex]
[tex]T(n)=O(n.Log^n_{\frac{3}{2}})[/tex]
و بعدش نتیجه گرفتیم :
[tex]T(n)=\theta(n.Log^n_{\frac{3}{2}})[/tex]
اینو متوجه نشدم
۲-تو مثال [tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10})[/tex] چرا برای محاسبه زمان اجرا از ارتفاع درخت استفاده نکردیم بر خلاف مثالهای قبل؟
۳-توی رسم درخت بازگشتی وقتی میگیم درختمون پر نیست،دقیقا به چه معنیه؟
۴-مبحث توان میخواد چی رو بگه؟
ببخشید سوالام خیلی زیاد شد
در۲////
چون مجموع اعداد کسرها یعنی یک بنجم بعللاوه دو دهم میشه نه دهم و نه دهم کوچکتر از ۱ است نکته داشتیم که طبق قضیه دیگه ای میشه n
برای سوال اولم...
داشتیم وقتی تابع بین دوتا حدود باشه که حالاهم بین دوتا حدود لگاریتمی است میشه تتا...حالام چون لگاریتم در هربایه ای رشدش فرقی نمیکنه میشه تتای لگاریتم.االبته برای چب شما اشتباه نوشتین زیرا هست امگای n لگاریتم ۳ .اما شما اشتباها نوشتین بیگ اوهه nلگ سه دوم
در ۳ هم...
یعنی شاخه ی سمت چبی در درخت زودتر por..... میشه تا شاخه ی سمت راستی درخت.یعنی شاخه ی سمت چبی زودتر به عدد ۱ میرسه....توضیحا در کتاب بوران یوسفی هستها....
اشتباه تصحیح شد
(۱۱ مرداد ۱۳۹۳ ۱۱:۴۲ ب.ظ)ریحان نوشته شده توسط: در۲////
چون مجموع اعداد کسرها یعنی یک بنجم بعللاوه دو دهم میشه نه دهم و نه دهم کوچکتر از ۱ است نکته داشتیم که طبق قضیه دیگه ای میشه n
برای سوال اولم...
داشتیم وقتی تابع بین دوتا حدود باشه که حالاهم بین دوتا حدود لگاریتمی است میشه تتا...حالام چون لگاریتم در هربایه ای رشدش فرقی نمیکنه میشه تتای لگاریتم.االبته برای چب شما اشتباه نوشتین زیرا هست امگای n لگاریتم ۳ .اما شما اشتباها نوشتین بیگ اوهه nلگ سه دوم
در ۳ هم...
یعنی شاخه ی سمت چبی در درخت زودتر por..... میشه تا شاخه ی سمت راستی درخت.یعنی شاخه ی سمت چبی زودتر به عدد ۱ میرسه....توضیحا در کتاب بوران یوسفی هستها....
توی پوران پژوهش که بخش بازگشتی هاش (فصل ۲) که خیلی گنگ و مبهم در مورد درخت بازگشتی توضیح داده!
این توضیحی که شما می فرمایید در کدوم بخششه؟
من واقعا در مورد رسم درخت بازگشتی گیج شدم!
(۱۴ مهر ۱۳۹۳ ۱۲:۰۵ ق.ظ)atropak نوشته شده توسط:کدوم مثال رو مشکل داری؟(11 مرداد ۱۳۹۳ ۱۱:۴۲ ب.ظ)ریحان نوشته شده توسط: در۲////
چون مجموع اعداد کسرها یعنی یک بنجم بعللاوه دو دهم میشه نه دهم و نه دهم کوچکتر از ۱ است نکته داشتیم که طبق قضیه دیگه ای میشه n
برای سوال اولم...
داشتیم وقتی تابع بین دوتا حدود باشه که حالاهم بین دوتا حدود لگاریتمی است میشه تتا...حالام چون لگاریتم در هربایه ای رشدش فرقی نمیکنه میشه تتای لگاریتم.االبته برای چب شما اشتباه نوشتین زیرا هست امگای n لگاریتم ۳ .اما شما اشتباها نوشتین بیگ اوهه nلگ سه دوم
در ۳ هم...
یعنی شاخه ی سمت چبی در درخت زودتر por..... میشه تا شاخه ی سمت راستی درخت.یعنی شاخه ی سمت چبی زودتر به عدد ۱ میرسه....توضیحا در کتاب بوران یوسفی هستها....
توی پوران پژوهش که بخش بازگشتی هاش (فصل ۲) که خیلی گنگ و مبهم در مورد درخت بازگشتی توضیح داده!
این توضیحی که شما می فرمایید در کدوم بخششه؟
من واقعا در مورد رسم درخت بازگشتی گیج شدم!
اون دو تا مثالی که در قسمت درخت بازگشتی کشیده یکیش برای تابع [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] که در توضیح نوشته که باید ارتفاع درخت هم در اون ضرب بشه!
چرا در اولی ارتفاع درخت ضرب نشده ولی در دومی ضرب شده؟
اصن نحوه ی کشیدن درخت بازگشت به چه صورته؟ نه توی کتاب مقسمی و نه توی کتاب پوران توضیح ندادن ، فقط یکی دوتا مثال گفتن و رد شدن!
(۱۵ مهر ۱۳۹۳ ۱۲:۱۹ ق.ظ)atropak نوشته شده توسط: اون دو تا مثالی که در قسمت درخت بازگشتی کشیده یکیش برای تابع [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] که در توضیح نوشته که باید ارتفاع درخت هم در اون ضرب بشه!
چرا در اولی ارتفاع درخت ضرب نشده ولی در دومی ضرب شده؟
اصن نحوه ی کشیدن درخت بازگشت به چه صورته؟ نه توی کتاب مقسمی و نه توی کتاب پوران توضیح ندادن ، فقط یکی دوتا مثال گفتن و رد شدن!
سلام.یه لطف کن همین متن رو توی یه تاپیک جدید بنویس تا کامل برات توضیح بدم
چون چند بار تذکر دادن توی تاپیک های قبلی دوباره سوال نذاریم.همین متنو تا تاپیک جدید بذتر فقط
تاپیک رو ایجاد کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.