تالار گفتمان مانشت
پیدا کردن xای که حاصل جمع دو عدد - نسخه‌ی قابل چاپ

پیدا کردن xای که حاصل جمع دو عدد - Sanazzz - 08 بهمن ۱۳۹۷ ۰۲:۵۰ ب.ظ

سلام
میخواستم بدونم این سواله اینجوری که من دارم میگم درسته

[تصویر:  465811_04xl_p_20190128_130207_vhdr_on_1.jpg]


[تصویر:  465811_wibm_p_20190128_130132_vhdr_on_1.jpg]
اول تو زمان(o(n عنصر xرو پیدا میکنیم
بعد عمل partition رو انجام میدیم با محور قرار دادن عنصر xکه باعث میشه عناصر کوچکتر از xقبلش بیان و عناصر بزرگتر از x بعدش بیان که اینکارو در زمان (o(n انجام میشه
حالا دو عنصری که جمعشون قرار بشه x باید قبل از x باشن پس در زما nlogn مرتبشون میکنیم
حالا اگه x+y=z باش برای هر عنصری مثل yمیایم حاصل x-yرو حساب میکنیم تو قسمت کوچیکا میگردیم حالا بدترین حالت وقتیه که ما اصلا عنصر بزرگتر از xنداشته باشیم پس باید برای n_1عنصر این مقایسه انجام بشه که آیا مقدارش با x_yبربر است یا نه
و چون باید برای nعنصر مانند yکه تو قسمت کوچیکا هستن اینکارو انجام بدیم میشه nبه توان دو
و حالا هم بین تمام زمان هایی که گفتم nبه توان دو از هه بیشتر پس میشه همین nبه توان دو
ولی اینجا که حل کرده مثل شکلش فرض کرده که عنصر xتقریبا وسط قرار میگیره و ما هر بار باید نصف آرایه رو برای پیدا کردن x_y جستجو کنیم و میشه
T n/2= T + تتای۱
که میشه logn و چون n بار حساب میشه در نهایت میشه nlog n

RE: پیدا کردن xای که حاصل جمع دو عدد - ph0en1x - 08 بهمن ۱۳۹۷ ۰۴:۴۸ ب.ظ

(۰۸ بهمن ۱۳۹۷ ۰۲:۵۰ ب.ظ)Sanazzz نوشته شده توسط:  سلام
میخواستم بدونم این سواله اینجوری که من دارم میگم درسته

[تصویر:  465811_04xl_p_20190128_130207_vhdr_on_1.jpg]


[تصویر:  465811_wibm_p_20190128_130132_vhdr_on_1.jpg]
اول تو زمان(o(n عنصر xرو پیدا میکنیم
بعد عمل partition رو انجام میدیم با محور قرار دادن عنصر xکه باعث میشه عناصر کوچکتر از xقبلش بیان و عناصر بزرگتر از x بعدش بیان که اینکارو در زمان (o(n انجام میشه
حالا دو عنصری که جمعشون قرار بشه x باید قبل از x باشن پس در زما nlogn مرتبشون میکنیم
حالا اگه x+y=z باش برای هر عنصری مثل yمیایم حاصل x-yرو حساب میکنیم تو قسمت کوچیکا میگردیم حالا بدترین حالت وقتیه که ما اصلا عنصر بزرگتر از xنداشته باشیم پس باید برای n_1عنصر این مقایسه انجام بشه که آیا مقدارش با x_yبربر است یا نه
و چون باید برای nعنصر مانند yکه تو قسمت کوچیکا هستن اینکارو انجام بدیم میشه nبه توان دو
و حالا هم بین تمام زمان هایی که گفتم nبه توان دو از هه بیشتر پس میشه همین nبه توان دو
ولی اینجا که حل کرده مثل شکلش فرض کرده که عنصر xتقریبا وسط قرار میگیره و ما هر بار باید نصف آرایه رو برای پیدا کردن x_y جستجو کنیم و میشه
T n/2= T + تتای۱
که میشه logn و چون n بار حساب میشه در نهایت میشه nlog n

نه خب وقتی میاد عناصر کوچکتر از x رو مرتب میکنه (با مرتبه nlogn) از این به بعد جستجو رو با جستجوی دودویی انجام میده که از مرتبه logn هست و اگه n بار جستجو انجام بشه میشه nlogn.

یه الگوریتم ساده (بدون استفاده از پارتیشن) اینه که آرایه رو در زمان nlogn مرتب کنیم و به ازای هر عنصر y دنبال عنصر zای باشیم که جمعشون باهم میشه x! چون آرایه رو مرتب کردیم، میتونیم برای هر عنصر یه بار جستجو رو انجام بدیم که هربار از مرتبه‌ی logn خواهد بود. و در کل این عمل هم میشه nlogn
پس در نهایت چه از پارتیشن استفاده کنیم و چه نکنیم مرتبه nlogn هست و استفاده نویسنده کتاب از پارتیشن بیشتر باعث پیچیده شدن الگوریتم شده و هیچ فایده‌ای برای خواننده نداره!

RE: پیدا کردن xای که حاصل جمع دو عدد - Saman - 08 بهمن ۱۳۹۷ ۰۵:۱۵ ب.ظ

(۰۸ بهمن ۱۳۹۷ ۰۴:۴۸ ب.ظ)ph0en1x نوشته شده توسط:  
(08 بهمن ۱۳۹۷ ۰۲:۵۰ ب.ظ)Sanazzz نوشته شده توسط:  سلام
میخواستم بدونم این سواله اینجوری که من دارم میگم درسته

[تصویر:  465811_04xl_p_20190128_130207_vhdr_on_1.jpg]


[تصویر:  465811_wibm_p_20190128_130132_vhdr_on_1.jpg]
اول تو زمان(o(n عنصر xرو پیدا میکنیم
بعد عمل partition رو انجام میدیم با محور قرار دادن عنصر xکه باعث میشه عناصر کوچکتر از xقبلش بیان و عناصر بزرگتر از x بعدش بیان که اینکارو در زمان (o(n انجام میشه
حالا دو عنصری که جمعشون قرار بشه x باید قبل از x باشن پس در زما nlogn مرتبشون میکنیم
حالا اگه x+y=z باش برای هر عنصری مثل yمیایم حاصل x-yرو حساب میکنیم تو قسمت کوچیکا میگردیم حالا بدترین حالت وقتیه که ما اصلا عنصر بزرگتر از xنداشته باشیم پس باید برای n_1عنصر این مقایسه انجام بشه که آیا مقدارش با x_yبربر است یا نه
و چون باید برای nعنصر مانند yکه تو قسمت کوچیکا هستن اینکارو انجام بدیم میشه nبه توان دو
و حالا هم بین تمام زمان هایی که گفتم nبه توان دو از هه بیشتر پس میشه همین nبه توان دو
ولی اینجا که حل کرده مثل شکلش فرض کرده که عنصر xتقریبا وسط قرار میگیره و ما هر بار باید نصف آرایه رو برای پیدا کردن x_y جستجو کنیم و میشه
T n/2= T + تتای۱
که میشه logn و چون n بار حساب میشه در نهایت میشه nlog n

نه خب وقتی میاد عناصر کوچکتر از x رو مرتب میکنه (با مرتبه nlogn) از این به بعد جستجو رو با جستجوی دودویی انجام میده که از مرتبه logn هست و اگه n بار جستجو انجام بشه میشه nlogn.

یه الگوریتم ساده (بدون استفاده از پارتیشن) اینه که آرایه رو در زمان nlogn مرتب کنیم و به ازای هر عنصر y دنبال عنصر zای باشیم که جمعشون باهم میشه x! چون آرایه رو مرتب کردیم، میتونیم برای هر عنصر یه بار جستجو رو انجام بدیم که هربار از مرتبه‌ی logn خواهد بود. و در کل این عمل هم میشه nlogn
پس در نهایت چه از پارتیشن استفاده کنیم و چه نکنیم مرتبه nlogn هست و استفاده نویسنده کتاب از پارتیشن بیشتر باعث پیچیده شدن الگوریتم شده و هیچ فایده‌ای برای خواننده نداره!
روی x پارتیشن زده چون خواسته تکلیف عناصر کمتر از xمشخص بشه چون جمع دوتا عنصر که ازxکوچیکتر هست میشه x نه دوتا عنصری که ازش بزرگتره.پس xرو پارتیشن قرار میدیم و عناصر کوچیکتر ازxمیفتن یه سمت و بزرگتر ها یه سمت.حالا بزرگا دیگه به درد نمیخورن و کنار میگذاریم. دقت کنید که پس از عمل پارتیشن رویxعناصری که سمت راست و چپ پارتیشن میفتن لزروما مرتب نیستن(پس نمیشه پس از عمل پارتیشن جستجوی دودویی بزنیم روی قسمت کوچیکتر یا بزرگتر)
عناصر قبل از عنصر محوری رو با مرتب سازی پایه که مرتبه ی nlognهست مرتب میکنیم که بتونیم اختلاف عناصر رو برای برابری با مقدار xبسنجیم
پس در نهایت داریم n+nlogn که زمان میشه همونnlogn

RE: پیدا کردن xای که حاصل جمع دو عدد - Sanazzz - 09 بهمن ۱۳۹۷ ۰۳:۰۴ ق.ظ

خیلی خیلی خیلی خیلی خیلی خیل خیلیییییییییییی ممنونم که جواب دادین
از هر دوتون ممنونمممممم
تشکااااات ویژههههه