سلام
رابطه بازگشتی به این شکل داریم که بینشون ضرب باشه نه جمع؟
[tex]t(n-2)*t(n-2)[/tex]
حس میکنم جایی این رابطه رو دیدم که ضرب بینشون رو همون جمع درنظر گرفتن و شده [tex]2^{\tfrac{n}{2}}[/tex]
ولی نمیشه به همین راحتی ضرب رو جمع درنظر گرفت!
این در کتاب مقسمی گفته شده
من اینجور فکر میکنم که:
این درسته که پیچیدگی میشه [tex]O(2^{\frac{n}{2}})[/tex]
اما با این فرض که تایع دوبار صدا زده شده و در هر بار n-2 داریم [tex]T(n)=2T(n-2)[/tex]
(۱۶ آبان ۱۳۹۲ ۰۶:۱۸ ب.ظ)m@hboobe نوشته شده توسط: این در کتاب مقسمی گفته شدهممنون محبوبه جان تصویر خیلی خوبی گذاشتی
من اینجور فکر میکنم که:
این درسته که پیچیدگی میشه [tex]O(2^{\frac{n}{2}})[/tex]
اما با این فرض که تایع دوبار صدا زده شده و در هر بار n-2 داریم [tex]T(n)=2T(n-2)[/tex]
من مشکلم همینه که چرا این دوتا رابطه از یه اوردر میشن در حالی که بین یکی جمع هست وبین یکی ضرب
[tex]t(n-1) t(n-1)// t(n-1)*t(n-1)[/tex]
اگه ضرب به معنی اینه که دو بار فراخوانی داریم پس جمع به چه معناست؟
من فکر میکنم که وقتی بینشون جمع باشه یعنی دوبار فراخوانی اما وقتی ضربه یعنی یه بار پس در حالت ضرب میشه:O(n)
(۱۶ آبان ۱۳۹۲ ۱۱:۱۶ ب.ظ)maryam.raz نوشته شده توسط:(16 آبان ۱۳۹۲ ۰۶:۱۸ ب.ظ)m@hboobe نوشته شده توسط: این در کتاب مقسمی گفته شدهممنون محبوبه جان تصویر خیلی خوبی گذاشتی
من اینجور فکر میکنم که:
این درسته که پیچیدگی میشه [tex]O(2^{\frac{n}{2}})[/tex]
اما با این فرض که تایع دوبار صدا زده شده و در هر بار n-2 داریم [tex]T(n)=2T(n-2)[/tex]
من مشکلم همینه که چرا این دوتا رابطه از یه اوردر میشن در حالی که بین یکی جمع هست وبین یکی ضرب
[tex]t(n-1) t(n-1)// t(n-1)*t(n-1)[/tex]
اگه ضرب به معنی اینه که دو بار فراخوانی داریم پس جمع به چه معناست؟
چرا نباید مرتبه اشون یکی باشه؟ ما برای هر n داریم دو تا دیگه رو حساب میکنیم حالا بینشون میخواد هر چی باشه. چه تاثیری توی تعداد مراحل کارمون داره؟ اون چیزی تعداد یعنی مرتبه رو رو محدود میکنه n هست و اینکه چند گام چند گام داریم حسابش میکنیم. تصور من اینه. نمیدونم چقدر درسته.
ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنه
(۱۴ آذر ۱۳۹۲ ۰۴:۰۸ ب.ظ)maryam.raz نوشته شده توسط: ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنهوقتی بینشون ضرب باشه میشه [tex]T(n)=T(n-2)*T(n-2)=T^2(n-2)[/tex]
و وقتی جمع باشه میشه [tex]T(n)=2T(n-2)[/tex]. به نظر شما این دو رابطه بازگشتی میتونن یکی باشن؟ مشخصه که نه.
با سلام
دقت کنید که این رابطه ها ، طبق جدول ، رابطه های بازگشتی تابع هستند و برای بدست آوردن مرتبه اجرایی آنها باید تعداد فراخوانی ها رو در نظر گرفت نه از قضیه اصلی یا قضایای مربوط به رابطه بازگشتی استفاده کرد!!!
کافیه با یه مثال این چندتا رابطه ها رو حل کنید و طبق تعداد فراخوانی ها مرتبه رو بدست بیارید.
من اینکار رو تو دو عکس زیر انجام دادم(با یه نقطه مرزی) . البته اگه نقاط مرزی عوض بشه مرتبه اجرایی عوض نمیشه فقط فرمول تعداد فراخوانی ها عوض میشه (با همان شکل کلی) . اگه توی بدست آوردن فرمول ها اشتباه کردم ببخشید چون با عجله نوشتم
[attachment=14110]
[attachment=14111]
(۱۴ آذر ۱۳۹۲ ۱۱:۵۲ ب.ظ)mfXpert نوشته شده توسط:من فرمول شمارو متوجه نشدم(14 آذر ۱۳۹۲ ۰۴:۰۸ ب.ظ)maryam.raz نوشته شده توسط: ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنهوقتی بینشون ضرب باشه میشه [tex]T(n)=T(n-2)*T(n-2)={(T(n-2))}^2[/tex] و وقتی جمع باشه میشه [tex]T(n)=2T(n-2)[/tex]. به نظر شما این دو رابطه بازگشتی میتونن یکی باشن؟ مشخصه که نه.
خب شما میگین اگه ضرب باشه از چه مرتبه ای میشه؟
(۱۵ آذر ۱۳۹۲ ۰۳:۵۰ ب.ظ)maryam.raz نوشته شده توسط: من فرمول شمارو متوجه نشدماون فرمولی که من نوشتم این نبود. نمیدونم چه اتفاقی افتاده که فرمول به این شکل عجیب در اومده بود. اصلاحش کردم.
(۱۴ آذر ۱۳۹۲ ۱۱:۵۲ ب.ظ)mfXpert نوشته شده توسط:ممنون نکته جدیدی بود(14 آذر ۱۳۹۲ ۰۴:۰۸ ب.ظ)maryam.raz نوشته شده توسط: ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنهوقتی بینشون ضرب باشه میشه [tex]T(n)=T(n-2)*T(n-2)=T^2(n-2)[/tex]
و وقتی جمع باشه میشه [tex]T(n)=2T(n-2)[/tex]. به نظر شما این دو رابطه بازگشتی میتونن یکی باشن؟ مشخصه که نه.
، الان اینو چه جوری باید حساب کرد؟ مقسمی که میگه جفتشون میشن [tex]2^{\frac{n}{2}}[/tex]
(۱۷ آذر ۱۳۹۲ ۰۱:۲۹ ق.ظ)maryam.raz نوشته شده توسط: الان اینو چه جوری باید حساب کرد؟ مقسمی که میگه جفتشون میشن [tex]2^{\frac{n}{2}}[/tex]ببینید اون چیزی که تو اون جدول کتاب مقسمی اومده روابط بازگشتی نیستن بلکه خود توابع هستن (به جای اینکه شبه کد برای توابع نوشته باشه بدنهی اونها رو به فرم ریاضی اونها نوشته). امیدوارم متوجه منظورم شده باشید.
ولی این دوتا با هم برابر نیییییستنن!!
(۱۸ آذر ۱۳۹۲ ۰۱:۰۵ ق.ظ)hoda ahmadi نوشته شده توسط: ولی این دوتا با هم برابر نیییییستنن!!لطفا با دلیل مطرح کنید!!