زمان کنونی: ۲۷ بهمن ۱۳۹۷, ۰۹:۴۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

پیدا کردن xای که حاصل جمع دو عدد

ارسال:
  

Sanazzz پرسیده:

Sad پیدا کردن xای که حاصل جمع دو عدد

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

[تصویر:  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
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

ph0en1x پاسخ داده:

RE: پیدا کردن xای که حاصل جمع دو عدد

(۰۸ بهمن ۱۳۹۷ ۰۲:۵۰ ب.ظ)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 هست و استفاده نویسنده کتاب از پارتیشن بیشتر باعث پیچیده شدن الگوریتم شده و هیچ فایده‌ای برای خواننده نداره!
نقل قول این ارسال در یک پاسخ

ارسال:
  

Saman پاسخ داده:

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 هست و استفاده نویسنده کتاب از پارتیشن بیشتر باعث پیچیده شدن الگوریتم شده و هیچ فایده‌ای برای خواننده نداره!
روی x پارتیشن زده چون خواسته تکلیف عناصر کمتر از xمشخص بشه چون جمع دوتا عنصر که ازxکوچیکتر هست میشه x نه دوتا عنصری که ازش بزرگتره.پس xرو پارتیشن قرار میدیم و عناصر کوچیکتر ازxمیفتن یه سمت و بزرگتر ها یه سمت.حالا بزرگا دیگه به درد نمیخورن و کنار میگذاریم. دقت کنید که پس از عمل پارتیشن رویxعناصری که سمت راست و چپ پارتیشن میفتن لزروما مرتب نیستن(پس نمیشه پس از عمل پارتیشن جستجوی دودویی بزنیم روی قسمت کوچیکتر یا بزرگتر)
عناصر قبل از عنصر محوری رو با مرتب سازی پایه که مرتبه ی nlognهست مرتب میکنیم که بتونیم اختلاف عناصر رو برای برابری با مقدار xبسنجیم
پس در نهایت داریم n+nlogn که زمان میشه همونnlogn
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Sanazzz پاسخ داده:

RE: پیدا کردن xای که حاصل جمع دو عدد

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال طراحی الگوریتم آی تی ۹۲(عدد گلوگاه) tarane1992 ۱۸ ۵,۳۶۹ ۲۲ فروردین ۱۳۹۶ ۰۹:۳۲ ق.ظ
آخرین ارسال: *ahoo
  عدد nام کاتالان ali.majed.ha ۲ ۳۳۸ ۱۹ اسفند ۱۳۹۵ ۰۵:۲۸ ب.ظ
آخرین ارسال: ali.majed.ha
  تریس کردن دو Parallel for H-Arshad ۰ ۲۹۳ ۰۹ آذر ۱۳۹۵ ۰۸:۵۱ ب.ظ
آخرین ارسال: H-Arshad
  پیدا کردن با ارزش ترین مسیر در یک ماتریس kamal3401 ۵ ۱,۱۷۷ ۱۶ خرداد ۱۳۹۵ ۰۹:۳۳ ب.ظ
آخرین ارسال: Behnam‌
  مرتبه زمانی پیدا کردن تعداد عدد ememem ۱ ۵۷۴ ۲۴ فروردین ۱۳۹۵ ۱۱:۵۷ ق.ظ
آخرین ارسال: LEA3C
  حفظ کردن فاطمه ارشد ای تی ۱ ۵۷۲ ۱۶ اردیبهشت ۱۳۹۴ ۰۲:۴۲ ب.ظ
آخرین ارسال: gunnersregister
  پیدا کردن چرخه فرصت در گراف ashy ۱ ۸۰۷ ۰۴ اردیبهشت ۱۳۹۴ ۱۲:۱۷ ق.ظ
آخرین ارسال: MShariati
  تعداد مقایسه برای min-heap کردن یک max-heap rezajam ۴ ۱,۳۲۰ ۱۲ اسفند ۱۳۹۳ ۰۱:۴۷ ق.ظ
آخرین ارسال: sali_h
  سوال ۴۸ - کنکور آیتی ۹۲ (عدد گلوگاهی) ƊƦЄƛM ۲ ۶۴۲ ۰۹ بهمن ۱۳۹۳ ۱۲:۱۱ ب.ظ
آخرین ارسال: ƊƦЄƛM
  پیدا کردن قطر درخت ازاد MiladCr7 ۴ ۱,۳۴۸ ۰۹ بهمن ۱۳۹۳ ۱۱:۱۷ ق.ظ
آخرین ارسال: a-t-e-f-e-h

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close