تالار گفتمان مانشت
سوال ۳۹-آی تی ۹۲-مرتبه زمانی - نسخه‌ی قابل چاپ

سوال ۳۹-آی تی ۹۲-مرتبه زمانی - Good! - 14 بهمن ۱۳۹۲ ۰۷:۳۸ ب.ظ

سلام دوستان
میشه لطف کنید بگید این سوال تو قسمت ۵ و ۶ چی میگه؟گزینه ها چی میگن کلا؟گزینه هایی که ماهان داده بجای - علامت + گذاشته!حتی اگه اینا = هم باشه من جوابو متوجه نمیشم.صورت سوال و گزینه های ماهان هم با اینی که پارسه گذاشته متفاوته!تنها جوابیم که پارسه داده اینه که گزینه ۱ درسته

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - نارین - ۱۵ بهمن ۱۳۹۲ ۱۱:۲۰ ق.ظ

لطفا اگه کسی بلده جواب بده منم با این سوالا مشکل داشتم ، پیشاپیش سپاسگذارم

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - *afsoon* - 15 بهمن ۱۳۹۲ ۰۱:۴۴ ب.ظ

سلام
اگه برا هر مجموعه یه مثال بزنین راحت میتونین متوجه منظور سوال بشین
در واقع اگه برا {a{2,5,7 برا {b{1,3,8 در نظر بگیرین حالا k میشه ۱ و x برابر ۵ i برابر ۲ میشه و شرط اول در این مجموعه صدق نمیکنه باید با دومی حل بشه
توضیحش یکم سخته اما جواب به نظرم این طوری به دست میاد که میانه مجموعه اول میتونه از همه مجموعه دوم بزرگتر باشه که میشه (T(n,m و یا نه میانه اولی از نصف مجموعه دوم بزگتر باشه که میشه (T(n/2,m و در مورد رابطهی بازگشتی مجموعه با جواب log m به دست میاد
ولی (O(1 نمیدونم چرا در نظر گرفته شاید اگه دو تا مجموعه یکسان باشن همون اول جواب به دست میاد به همین دلیل در نظر گرفته دلیل غیر این به ذهنم نرسید
حالا این نظر خودمه دوستان اگه نظری دارن خوشحال میشم متوجه اشتباهم بشم Smile

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - Good! - 15 بهمن ۱۳۹۲ ۰۵:۳۱ ب.ظ

(۱۵ بهمن ۱۳۹۲ ۰۱:۴۴ ب.ظ)*afsoon* نوشته شده توسط:  سلام
اگه برا هر مجموعه یه مثال بزنین راحت میتونین متوجه منظور سوال بشین
در واقع اگه برا {a{2,5,7 برا {b{1,3,8 در نظر بگیرین حالا k میشه ۱ و x برابر ۵ i برابر ۲ میشه و شرط اول در این مجموعه صدق نمیکنه باید با دومی حل بشه
توضیحش یکم سخته اما جواب به نظرم این طوری به دست میاد که میانه مجموعه اول میتونه از همه مجموعه دوم بزرگتر باشه که میشه (T(n,m و یا نه میانه اولی از نصف مجموعه دوم بزگتر باشه که میشه (T(n/2,m و در مورد رابطهی بازگشتی مجموعه با جواب log m به دست میاد
ولی (O(1 نمیدونم چرا در نظر گرفته شاید اگه دو تا مجموعه یکسان باشن همون اول جواب به دست میاد به همین دلیل در نظر گرفته دلیل غیر این به ذهنم نرسید
حالا این نظر خودمه دوستان اگه نظری دارن خوشحال میشم متوجه اشتباهم بشم Smile

من متاسفانه متوجه توضیحتون برای قسمت ۵و۶ نشدم Undecided
O(1) برای کارای به دست اوردن r و k هست.Log m هم برای جستجو در ارایه B

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - *afsoon* - 15 بهمن ۱۳۹۲ ۰۶:۰۳ ب.ظ

با مثال میتونین متوجه بشین
در واقع r داره کمک میکنه که بدونیم میانه اشتراک دو مجموعه از مجموعه aانتخاب میشه یا b
اگه r کمتر باشه مقدارش از n/2+i یعنی میانه اشتراک مجموعه ها از بین مجموعه {a{1...n/2 , و {b{1...iبه دست میاد ر غیر این صورتم که از مرحله ۶

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - Good! - 16 بهمن ۱۳۹۲ ۰۸:۳۸ ق.ظ

(۱۵ بهمن ۱۳۹۲ ۰۶:۰۳ ب.ظ)*afsoon* نوشته شده توسط:  با مثال میتونین متوجه بشین
در واقع r داره کمک میکنه که بدونیم میانه اشتراک دو مجموعه از مجموعه aانتخاب میشه یا b
اگه r کمتر باشه مقدارش از n/2+i یعنی میانه اشتراک مجموعه ها از بین مجموعه {a{1...n/2 , و {b{1...iبه دست میاد ر غیر این صورتم که از مرحله ۶

اون صفرها نقطه س؟؟HuhAngryهی من میگم این ۱۰۰m ینی چی چیه آخه!
دستتون درد نکنه
ببخشید من همش مشکلم اینه که متوجه نمیشم اون اندیسهای A, B چی هستن؟میشه محدوده A,B رو تو مرحله ۶ بگید؟
شما منظورتون اینه که با مثال متوجه اون محدوده بشم چون تایپش اشتباس؟؟
جوابی که تو گزینه ۱ هست T(n/20m) منظورش T(n/2,m) هست؟؟T(n,m) رو برای مرحله ۶ نوشته و T(n/2,m) برای مرحله ۵/و چون فقط یکیشون قابل انجام هست منها کرده؟
خیلی ممنون میشم به این سوالا هم پاسخ بدین.Smile

Re: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - nafas_70 - 16 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ

صورت درست سوال:


Sent from my C5303 using Tapatalk

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - Good! - 17 بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ

(۱۶ بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط:  صورت درست سوال:


Sent from my C5303 using Tapatalk

دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو Undecided

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - tayebe68 - 17 بهمن ۱۳۹۲ ۰۹:۴۰ ب.ظ

۱ در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m

در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶

که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)

RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - nafas_70 - 17 بهمن ۱۳۹۲ ۱۰:۴۲ ب.ظ

(۱۷ بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)Good! نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط:  صورت درست سوال:


Sent from my C5303 using Tapatalk

دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو Undecided

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


RE: سوال ۳۹-آی تی ۹۲-مرتبه زمانی - Good! - 17 بهمن ۱۳۹۲ ۱۱:۳۱ ب.ظ

(۱۷ بهمن ۱۳۹۲ ۱۰:۴۲ ب.ظ)nafas_70 نوشته شده توسط:  
(17 بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)Good! نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط:  صورت درست سوال:


Sent from my C5303 using Tapatalk

دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو Undecided

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

دستت درد نکنه خیلی لطف بزرگی کردیBlush

(۱۷ بهمن ۱۳۹۲ ۰۹:۴۰ ب.ظ)tayebe68 نوشته شده توسط:  1 در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m

در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶

که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)

دستت درد نکنه خیلی لطف بزرگی کردی.ممنونم از همه تونBlushShy

(۱۷ بهمن ۱۳۹۲ ۰۹:۴۰ ب.ظ)tayebe68 نوشته شده توسط:  1 در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m

در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶

که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)

دستت درد نکنه خیلی لطف بزرگی کردی.ممنونم از همه تونBlushShy