با سلام

دقت کنید که این رابطه ها ، طبق جدول ، رابطه های بازگشتی تابع هستند و برای بدست آوردن مرتبه اجرایی آنها باید تعداد فراخوانی ها رو در نظر گرفت نه از قضیه اصلی یا قضایای مربوط به رابطه بازگشتی استفاده کرد!!!
کافیه با یه مثال این چندتا رابطه ها رو حل کنید و طبق تعداد فراخوانی ها مرتبه رو بدست بیارید.
من اینکار رو تو دو عکس زیر انجام دادم(با یه نقطه مرزی) . البته اگه نقاط مرزی عوض بشه مرتبه اجرایی عوض نمیشه فقط فرمول تعداد فراخوانی ها عوض میشه (با همان شکل کلی) . اگه توی بدست آوردن فرمول ها اشتباه کردم ببخشید چون با عجله نوشتم

این در کتاب مقسمی گفته شده
من اینجور فکر میکنم که:
این درسته که پیچیدگی میشه [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]
اگه ضرب به معنی اینه که دو بار فراخوانی داریم پس جمع به چه معناست؟

(۱۶ آبان ۱۳۹۲ ۱۱:۱۶ ب.ظ)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 هست و اینکه چند گام چند گام داریم حسابش میکنیم. تصور من اینه. نمیدونم چقدر درسته.

من فکر میکنم که وقتی بینشون جمع باشه یعنی دوبار فراخوانی اما وقتی ضربه یعنی یه بار پس در حالت ضرب میشه:O(n)

ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنه

(۱۴ آذر ۱۳۹۲ ۰۴:۰۸ ب.ظ)maryam.raz نوشته شده توسط:  ممنون از همه دوستانی که مشارکت کردن فک کنم حق باشماست و جمع یا ضرب بودن فرقی نمیکنه

وقتی بینشون ضرب باشه میشه [tex]T(n)=T(n-2)*T(n-2)=T^2(n-2)[/tex]
و وقتی جمع باشه میشه [tex]T(n)=2T(n-2)[/tex]. به نظر شما این دو رابطه بازگشتی میتونن یکی باشن؟ مشخصه که نه.

(۱۴ آذر ۱۳۹۲ ۱۱:۵۲ ب.ظ)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 نوشته شده توسط:  ولی این دوتا با هم برابر نیییییستنن!!

لطفا با دلیل مطرح کنید!!