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





اول تو زمان(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

(۰۸ بهمن ۱۳۹۷ ۰۴:۴۸ ب.ظ)ph0en1x نوشته شده توسط:  

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





اول تو زمان(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 هست و استفاده نویسنده کتاب از پارتیشن بیشتر باعث پیچیده شدن الگوریتم شده و هیچ فایده‌ای برای خواننده نداره!