تالار گفتمان مانشت

سلام دوستان .

این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :



و این هم پاسخ آن است که در زیر آمده :





سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.



ممنونم.

(02 آذر 1392 05:47 ق.ظ)Morris نوشته شده توسط: [ -> ]سلام دوستان .

این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :



و این هم پاسخ آن است که در زیر آمده :





سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.



ممنونم.

به نظر من هم پاسخ شما درسته.

(02 آذر 1392 08:07 ق.ظ)e.sharmi نوشته شده توسط: [ -> ]به نظر من هم پاسخ شما درسته.

بسیار ممنونم.

(02 آذر 1392 11:59 ب.ظ)Morris نوشته شده توسط: [ -> ]

(02 آذر 1392 08:07 ق.ظ)e.sharmi نوشته شده توسط: [ -> ]به نظر من هم پاسخ شما درسته.

بسیار ممنونم.

البته یه جاهایی استفاده از مستر صحیح نیست و باید از درخت استفاده کرد. جاهایی که وقتی لگاریتم میگیریم از f رابطه به صورت چند جمله ای بزرگتر یا کوچکتر نباشه. البته اینجا چند جمله ای کوچکتره و نباید موردی باشه ولی بازم شک دارم که نکنه از اون حالات خاص هست

(03 آذر 1392 12:03 ق.ظ)zimenswall نوشته شده توسط: [ -> ]

(02 آذر 1392 11:59 ب.ظ)Morris نوشته شده توسط: [ -> ]

(02 آذر 1392 08:07 ق.ظ)e.sharmi نوشته شده توسط: [ -> ]به نظر من هم پاسخ شما درسته.

بسیار ممنونم.

البته یه جاهایی استفاده از مستر صحیح نیست و باید از درخت استفاده کرد. جاهایی که وقتی لگاریتم میگیریم از f رابطه به صورت چند جمله ای بزرگتر یا کوچکتر نباشه. البته اینجا چند جمله ای کوچکتره و نباید موردی باشه ولی بازم شک دارم که نکنه از اون حالات خاص هست

کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!




مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(03 آذر 1392 12:57 ق.ظ)Morris نوشته شده توسط: [ -> ]کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

البته ایشون درخت را اشتباه کشیده بودن. درختشون دو شاخه ای شده بود و این اشتباهه.
من درختشو کشیدم و جوابی که بدست آوردم 2k-2 بود. البته اگر درست گفته باشم.

(03 آذر 1392 01:01 ق.ظ)zimenswall نوشته شده توسط: [ -> ]

(03 آذر 1392 12:57 ق.ظ)Morris نوشته شده توسط: [ -> ]کاملا حق با شماست !
البته دوستمون آقای ریمان در ارسال زیر این قسمت از مساله را با استفاده از درخت بازگشتی حل کردند که به همان جواب پارسه رسیده ! من که کاملا گیج شدم !!!


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

البته ایشون درخت را اشتباه کشیده بودن. درختشون دو شاخه ای شده بود و این اشتباهه.
من درختشو کشیدم و جوابی که بدست آوردم ۲k-2 بود. البته اگر درست گفته باشم.

گویا حواس من هم مثل ایشان پرت بوده !

درختی که من بدست آوردم اینجوری بود
اگر بدخطه یا اشتباهی هست ببخشید.

(02 آذر 1392 05:47 ق.ظ)Morris نوشته شده توسط: [ -> ]سلام دوستان .

این سوال ۱۰۰ از طراحی الگوریتم نرم افزار از آزمون ۵۰ درصد اول پارسه بود :



و این هم پاسخ آن است که در زیر آمده :





سوال من اینه که در اون قسمتی که [tex]g(k)[/tex] محاسبه می شود، چطور با استفاده از قضیه اصلی، به چنین پاسخی رسیده است ؟
من فکر می کنم پاسخ درست [tex]g(k) = \theta (k)[/tex] است.



ممنونم.

سلام دوست گرامی

این یک تبصره در قضیه اساسی هست که اگر رابطه بازگشتی به این صورت بود:

T(n)=aT(n/b) + (n ^ log a) * (log n) ^ d

جواب این خواهد بود: n ^ log a * log n ^ (d+1) = javab

در ضمن در روابط بالا منطور لوگ a بر مبنای b هست.

(13 آذر 1392 12:05 ق.ظ)misagh01 نوشته شده توسط: [ -> ]این یک تبصره در قضیه اساسی هست که اگر رابطه بازگشتی به این صورت بود:

T(n)=aT(n/b) + (n ^ log a) * (log n) ^ d

جواب این خواهد بود: n ^ log a * log n ^ (d+1) = javab

در معادله بالا چیزی که شما گفتید صدق نمیکنه.

بله ! همونطور که دوستمون zimenswall گفتند، این شرط در این مثال صدق نمی کند.
ممنون از شما.