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

پیدا کردن 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ای که حاصل جمع دو عدد

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اصول ماشین های کنترل عددی و مطلبی ملینا ارشد ۱ ۲,۰۰۲ ۲۸ بهمن ۱۴۰۰ ۰۸:۰۹ ب.ظ
آخرین ارسال: vista2000
  پیدا کردن دستگیره manager_66 ۵ ۴,۳۵۵ ۲۸ آذر ۱۴۰۰ ۱۲:۴۴ ب.ظ
آخرین ارسال: blackhalo1989
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۴,۴۹۹ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  جایی برای پیدا کردن توابع آماده جاوااسکریپت f.b ۷ ۴,۰۰۹ ۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ
آخرین ارسال: calm
  انالیز عددی Mahjub24 ۱۰ ۱۲,۷۰۳ ۰۱ آذر ۱۳۹۹ ۱۲:۲۴ ب.ظ
آخرین ارسال: mohammadasadi1
  پیدا کردن موضوع پایان نامه k1.technology ۲ ۷,۷۴۲ ۲۱ خرداد ۱۳۹۹ ۱۲:۵۴ ب.ظ
آخرین ارسال: bankabzar
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۸۸۸ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  مسدود کردن سایت و نرم افزار تلگرام wiisconsin ۶ ۶,۴۶۷ ۲۴ بهمن ۱۳۹۸ ۰۵:۳۸ ق.ظ
آخرین ارسال: one hacker alone
  تعداد روش های نوشتن عدد n ss311 ۲ ۲,۹۵۳ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تست جمع کننده با پیش گویی رقم نقلی Sanazzz ۰ ۱,۶۸۱ ۲۹ اردیبهشت ۱۳۹۸ ۰۲:۲۴ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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