صفحهها: ۱ ۲
سلام دوستان
درخت بازگشتی این عبارت چی میشه؟
[tex]T(n)=T(n-1) T(\frac{n}{2}) n[/tex]
درخت جدا هر کدوم از n-1 و n/2 خیلی راحت میشه کشید اما وقتی باهم هستن جمع میشن چطور باید درختش رو کشید؟
پیشاپیش ممنون دوستان
بنظرم حد بالای رابطه همون قسمت اول بازگشته که از بازه [tex]O(n^2)[/tex] هستش.
(۰۴ مهر ۱۳۹۳ ۰۶:۰۷ ب.ظ)ADELZX نوشته شده توسط: بنظرم حد بالای رابطه همون قسمت اول بازگشته که از بازه [tex]O(n^2)[/tex] هستش.
منبع خوبی سراغ داری این قسمتو خوب توضیح داده باشه؟
سلام.باید n/2. رو حذف کنید و بعد درخت بازگشت رو رسم کنید
(۰۴ مهر ۱۳۹۳ ۰۶:۰۷ ب.ظ)ADELZX نوشته شده توسط: بنظرم حد بالای رابطه همون قسمت اول بازگشته که از بازه [tex]O(n^2)[/tex] هستش.
چطور حساب کردید؟
(۰۴ مهر ۱۳۹۳ ۰۷:۲۹ ب.ظ)miladcr7 نوشته شده توسط: سلام.باید n/2. رو حذف کنید و بعد درخت بازگشت رو رسم کنید
چرا باید n/2 حذف بشه؟ فکر کنم تو بازگشت ها تاثیر داشته باش
n را ریشه قرار بدید و درخت رسم کنید!هر بار مقدار n در یک سمت درخت یک واحد کم میشه و در سمت دیگه نصف میشه همین طور هر گره جدید رو ادامه میدیم....
حد بالای این تایع در سمتی بدست میاد که n-1 انجام میشه پس مرتبه این تابع از [tex]O(n^2)[/tex] است.
(۰۴ مهر ۱۳۹۳ ۰۹:۰۸ ب.ظ)m@hboobe نوشته شده توسط: n را ریشه قرار بدید و درخت رسم کنید!هر بار مقدار n در یک سمت درخت یک واحد کم میشه و در سمت دیگه نصف میشه همین طور هر گره جدید رو ادامه میدیم....
حد بالای این تایع در سمتی بدست میاد که n-1 انجام میشه پس مرتبه این تابع از [tex]O(n^2)[/tex] است.
قبول اما شما چطور جمع سطوح درخت رو انجام دادید؟ اخه روند خاصی براش به دست نمیاد!
فکر کنم استدلال شما اینطور که ارتفاع که N میشه تو هر سطح هم که یک ضریبی از N داریم پس میشه N^2 درسته؟ اگر اینطوره از کجا میدونید سیگما سطوح رو حساب کنید به N^3 نمیرسه؟
[attachment=16878]
سلام این مثال چون از دو تابع کاملا متفاوت تشکیل شده حل دقیقی نداره ولی روش حل تقریبیش اینه که اون تابعی که زودتر به یک میرسه رو بیخیال میشیم خب؟
حالا توی این مثال n/2 داره سریعتر به یک نزدیک میشه پس میتونیم حذفش کنیم یا یه روش دیگه برای حذف اینه که اون تابعی که زمان اجرای کمتری داره رو حذف میکنیم چون بازم زودتر به یک میرسه حالا دقت کن که مرتبه اجرای n/2 لگاریتمی هستش و اون یکی تابع مرتبش از n هست پس n/2 رو حذف کن حالا تابع باقیمونده مرتبه اجراش n به توان دو میشه
اکی؟؟؟
یعنی میشه اینطوری نتیجه گیری کلی کرد؟؟؟؟؟ ( اگه تابعی از مجموع چندین مرتبه مختلف تشکیل شده باشه ، بیشترین مرتبه مرتبه اجرایی اون تابعه؟)
سلام .توی تابع هایی که اینجوری ریتم مختلفی دارند بله
(۰۴ مهر ۱۳۹۳ ۱۰:۵۹ ب.ظ)miladcr7 نوشته شده توسط: سلام .توی تابع هایی که اینجوری ریتم مختلفی دارند بله
پس چرا تو سوالی که من پرسیدم تو اون یکی تاپیک مرتبه ی دو قسمت بهم ضرب شدند؟
(۰۴ مهر ۱۳۹۳ ۱۱:۰۶ ب.ظ)ziba.O نوشته شده توسط:(04 مهر ۱۳۹۳ ۱۰:۵۹ ب.ظ)miladcr7 نوشته شده توسط: سلام .توی تابع هایی که اینجوری ریتم مختلفی دارند بله
پس چرا تو سوالی که من پرسیدم تو اون یکی تاپیک مرتبه ی دو قسمت بهم ضرب شدند؟
میشه ادرسشو بدید؟؟؟؟
(۰۴ مهر ۱۳۹۳ ۱۱:۱۴ ب.ظ)miladcr7 نوشته شده توسط:(04 مهر ۱۳۹۳ ۱۱:۰۶ ب.ظ)ziba.O نوشته شده توسط:(04 مهر ۱۳۹۳ ۱۰:۵۹ ب.ظ)miladcr7 نوشته شده توسط: سلام .توی تابع هایی که اینجوری ریتم مختلفی دارند بله
پس چرا تو سوالی که من پرسیدم تو اون یکی تاپیک مرتبه ی دو قسمت بهم ضرب شدند؟
میشه ادرسشو بدید؟؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
دوست عزیز معذرت میخوام اینقدر گیج شدم قاطی کردم همه چیو اگه میشه یکم ساده تر اینارو واسم سوا کنین.خدا خیرت بده
(۰۴ مهر ۱۳۹۳ ۰۹:۴۱ ب.ظ)directline نوشته شده توسط:درسته حق با شماست اگر بخواهیم بطور دقیق درخت رسم کنید چنین چیزی به نتیجه جالبی نمیرسیم(04 مهر ۱۳۹۳ ۰۹:۰۸ ب.ظ)m@hboobe نوشته شده توسط: n را ریشه قرار بدید و درخت رسم کنید!هر بار مقدار n در یک سمت درخت یک واحد کم میشه و در سمت دیگه نصف میشه همین طور هر گره جدید رو ادامه میدیم....
حد بالای این تایع در سمتی بدست میاد که n-1 انجام میشه پس مرتبه این تابع از [tex]O(n^2)[/tex] است.
قبول اما شما چطور جمع سطوح درخت رو انجام دادید؟ اخه روند خاصی براش به دست نمیاد!
فکر کنم استدلال شما اینطور که ارتفاع که N میشه تو هر سطح هم که یک ضریبی از N داریم پس میشه N^2 درسته؟ اگر اینطوره از کجا میدونید سیگما سطوح رو حساب کنید به N^3 نمیرسه؟
ولی حداقل با همین روش که کاملا هم درست نیست (اگر دقت کنید جلوی جمله رسم درختم علامت تعجب گذاشتم
) متوجه میشیم که اگر بخواهیم محاسبه رو با اون قسمت از تایع که هر بار یک واحد کم میکنه انجام بدیم ارتفاع بیشتری داریم (با توجه به صحبتهای سایر بچه ها = دیر تر به یک نزدیک میشه!) پس اون بخش موثر در حل هستمن خودم اولین بار که به این مساله برخورد کردم اینجور درنظر گرفتم که ممکنه هر بار یه بخش از این تابع اتفاق بیفته با n-1 مرتبه که [tex]Theta(n^2)[/tex] شد و با n/2 از طریق مستر شد [tex]Theta(n)[/tex] که گفتم کران بالای حل میشه [tex]O(n^2)[/tex]
امیدوارم که با توضیحاتم گیج نشده باشید
موفق باشین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
دوست عزیز معذرت میخوام اینقدر گیج شدم قاطی کردم همه چیو اگه میشه یکم ساده تر اینارو واسم سوا کنین.خدا خیرت بده