جواب n نمیشه؟!

(۳۰ دى ۱۳۹۱ ۰۸:۴۰ ب.ظ)۸Operation نوشته شده توسط:  جواب n نمیشه؟!

سلام.
چرا.
بر چه اساس حساب کردی؟

بر اساس مرج کردن دو آرایه مرتب از مرتبه o(n+ m گفتی/

(۳۰ دى ۱۳۹۱ ۱۱:۳۶ ب.ظ)mehdi.nine نوشته شده توسط:  بر اساس مرج کردن دو آرایه مرتب از مرتبه o(n+ m گفتی/

نه من این سوالو با ادغام حل نکردم! از رابطه زیر این جواب رو بدست آوردم:
در واقع این سوال تاحدودی مشابه سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
هستش اما بخاطر نیاز به جمع دو ایندکس ارایه الگوریتمش از مرتبه [tex]T(n)=T(n/2) 1 [/tex] به [tex]T(n)=2T(n/2) 1 [/tex] تغییر می کنه که مرتبه اش میشه همون[tex]O(n) [/tex]
اگه دوستان دیگه موافقند و نظر دیگری ندارن و اگه ابهامی بود بگو تا بیشتر توضیح بدم.

فکر کنم
دوتا ارایه مرتب با n ادغام میکنیم
که الان یه ارایه مرتب داریم
بعد هم یه جست و جوی خطی و جمع و مقایسه((مثلا یه شمارنده بذاریم،که وقتی دو تا عنصر باویژگی گفته شده رو پیدا کرد زیاد شه)
در طول ارایه انجام میدییم که همه این ها از مرتبه n
البته این تحلیل من شاید درست نباشه
دوستان نظر بدن

کاش پاسخ خود سنجش هم بذارید

به نظر من نمی تونیم ادغام کنیم چون اگه ادغام کنیم چطور میشه بفهمیم, a[i] , b[i] کدوما هستن. چون می خوایم اونا رو با هم جمع کنیم و مقایسه کنیم با x. به نظر من با log هم حل میشه. حالا بچه ها هم نظر بدن درسته یانه
ما از تکنیک شبیه جستجوی باینری استفاده می کنیم. اول دو عنصر وسط لیست ها رو با هم چک می کنیم. اگر جمعشون بزرگتر از x شد که دیگه به بخش دومی این لیستها کار نداریم چون حتما جمع اونها هم بزرگتر از x میشه. پس میریم به بخش اول و اونو به دو قسمت تقسیم می کنیم. اگر این بار هم جمع این دو عنصر وسطی بزرگتر از x شد که مثل قبل بخش دومش حذف میشه اما فرض کنین که کوچکتر بود پس مطمئنا اعداد بخش اول (سمت چپی) هر دو لیست هم با هم جمع بشن باز کوچکتر از xخواهند بود که تعدادشو به راحتی میشه حساب کرد. اگر این بخش دارای m عنصر باشه پس تعداد زوجهای جواب تاحالا میشه m^2. بنابراین میریم سراغ بخش راستی این بخش و کارا رو همین طور تکرار می کنیم. بنابراین چون در هر مرحله نصف مساله تکلیفش مشخص میشه ، پس مرتبه log هست

سلام
میشه
یه کم بیشتر توضیح بدید
جمع دو تا ایندکس ؟؟

(۰۱ بهمن ۱۳۹۱ ۱۲:۰۷ ق.ظ)nina69 نوشته شده توسط:  فکر کنم
دوتا ارایه مرتب با n ادغام میکنیم
که الان یه ارایه مرتب داریم
بعد هم یه جست و جوی خطی و جمع و مقایسه((مثلا یه شمارنده بذاریم،که وقتی دو تا عنصر باویژگی گفته شده رو پیدا کرد زیاد شه)
در طول ارایه انجام میدییم که همه این ها از مرتبه n
البته این تحلیل من شاید درست نباشه
دوستان نظر بدن

این الگوریتم شما از مرتبه n2 می شه. چون برای تک تک عناصر باید این کارارو تکرار کرد که می شه n * n + n که می شه On2

جواب سنجش هم چشم فردا می ذارم الان خدایی حسش نیس بیارمش

---

---

(۰۱ بهمن ۱۳۹۱ ۱۲:۱۷ ق.ظ)۸Operation نوشته شده توسط:  درسته

لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.

---

مرسی.
خوب منم دقیقا به همین فکر کردم . اما دقت کن مرتبه این کار می شه n* logn. ما هر بار لازم داریم عنصر وسط لیست اول رو انتخاب کنیم که از مرتبه O1 هستش حالا شبیه جست و جوی باینری در لیست دوم باید بگردیم که می شه O logn تا اینجا شده پس برای یک عنصر شده Olongn و ما باید باری تک تک عناصر انجام بدیم که می شه Onlogn که جواب اشتباس.

---

این پاسخ سنجش برای این سوال:

این دیگه چه جوابیه. این که میشه n^2 کجاش n هست. تازه گفته o ای کوچک??
شما فرض کن دو آرایه به صورت زیر باشه.
A 1 2 3 4 50
B 60 61 62 63 64
و x باشه ۶۸
خوب آخرین خانه A هست ۵۰ که با ۶۰ جمع شه میشه ۱۱۰ چون کمتر از x نیست پس باید بر روش یه حلقه دیگه بزنیم که میشه n و کانتر میشه ۴
حالا ۶۱ رو با ۵۰ جمع می کنیم بازم بیشتره باز مجبوریم روش حلقه بزنیم که بازم n هست و کانتر میشه ۴+۴=۸ و برای بقیه هم همین طور پس میشه n^2 فکر کنم
اما اگه این راهو بریم فکر کنم میشه همون اوی n که به ذهنم رسید.
یک شماره گر برای A درنظر بگیرید که به خونه آخر اشاره داره و یک اشاره گر دیگر که به خونه اول B اشاره داره. حالا شروع می کنیم. اگر جمع این دو عنصر کمتر از x بودند که بنابراین جمع تک تک عناصر A با خونه اول B کوچکتر از x میشه پس به همون اندازه به کانتر اضافه می کنیم و یه دونه اشاره گر B رو جلو می بریم. حال فرض کنین که خونه دوم B جمعش با خونه آخر A بزرگتر از x شد پس جمع تک تک عناصر B از خونه دوم تا آخر با خونه آخر A بزرگتر از x میشه در این صورت اشاره گر A یکی عقب میره و کانتر تغییری نمی کنه، همین کار را رو می کنیم تا یکی از اشاره گرها به آخر برسه. پس میشه اوی n.تو این مثال
۶۰ با ۵۰ جمع می شود جمعش از x بزرگتر است پس اگر ۵۰ با عناصر بعدی B جمع شود بازم بزرگتر است بنابراین اشاره گر A یکی عقب می رود. تا اینجا یک گام رفتیم. ۴ با ۶۰ مقایسه می شود جمعش کوچکتر است پس جمع ۶۰ با عناصر قبل اشاره گر A هم باز کوچکتر از x خواهد بود. کانتر می شود ۴ و اشاره گر B اضافه می شود این بار ۶۱ با ۴ و الی آخر. می بینید در هر گام یکی از اشاره گرها یک واحد حرکت می کند.
بدترین حالتشم زمانی هست که مثلا به این صورت آرایه ها باشند.
۱ ۳ ۵ ۷
۲ ۴ ۶ ۸
و x=9
که یکی در میان اشاره گرها جابجا میشن تا به آخر برسن که میشه ۲n

---

(۰۱ بهمن ۱۳۹۱ ۱۲:۳۱ ق.ظ)mahdiii نوشته شده توسط:  به نظر من نمی تونیم ادغام کنیم چون اگه ادغام کنیم چطور میشه بفهمیم, a[i] , b[i] کدوما هستن. چون می خوایم اونا رو با هم جمع کنیم و مقایسه کنیم با x. به نظر من با log هم حل میشه. حالا بچه ها هم نظر بدن درسته یانه
ما از تکنیک شبیه جستجوی باینری استفاده می کنیم. اول دو عنصر وسط لیست ها رو با هم چک می کنیم. اگر جمعشون بزرگتر از x شد که دیگه به بخش دومی این لیستها کار نداریم چون حتما جمع اونها هم بزرگتر از x میشه. پس میریم به بخش اول و اونو به دو قسمت تقسیم می کنیم. اگر این بار هم جمع این دو عنصر وسطی بزرگتر از x شد که مثل قبل بخش دومش حذف میشه اما فرض کنین که کوچکتر بود پس مطمئنا اعداد بخش اول (سمت چپی) هر دو لیست هم با هم جمع بشن باز کوچکتر از xخواهند بود که تعدادشو به راحتی میشه حساب کرد. اگر این بخش دارای m عنصر باشه پس تعداد زوجهای جواب تاحالا میشه m^2. بنابراین میریم سراغ بخش راستی این بخش و کارا رو همین طور تکرار می کنیم. بنابراین چون در هر مرحله نصف مساله تکلیفش مشخص میشه ، پس مرتبه log هست

این الگوریتمم یکم مشکل داشت بجایT=T(n/2)+1 میشه T=3*T(n/2)+1 که مرتبش میشه n^log3 در پایه ۲ که میشه n^1.58

(۰۱ بهمن ۱۳۹۱ ۰۳:۵۳ ق.ظ)mahdiii نوشته شده توسط:  لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.

دوست عزیز حقیقتش من وقتی سوال شما رو دیدم با روشهای استاد قلی زاده واسه حل این تستها اون رابطه رو ذهنی بدست آوردم،هنوزم فکر می کنم درسته !اما الان گه نشستم دقیقا اثباتش کنم برای خودم تا براتون بفرستم نتونستم در تئوری به رابطه بالا برسم!
خلاصه شرمنده شما شدم.
اما اگه تونستم گره مسئله رو بازکنم حتما جوابشو قرار میدم.
همگی موفق باشید.

آره مرتبش On می شه مرسی از اینکه وقت گذاشتی و عالی فکر کردی.

---

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

(01 بهمن ۱۳۹۱ ۰۳:۵۳ ق.ظ)mahdiii نوشته شده توسط:  لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.

دوست عزیز حقیقتش من وقتی سوال شما رو دیدم با روشهای استاد قلی زاده واسه حل این تستها اون رابطه رو ذهنی بدست آوردم،هنوزم فکر می کنم درسته !اما الان گه نشستم دقیقا اثباتش کنم برای خودم تا براتون بفرستم نتونستم در تئوری به رابطه بالا برسم!
خلاصه شرمنده شما شدم.
اما اگه تونستم گره مسئله رو بازکنم حتما جوابشو قرار میدم.
همگی موفق باشید.

دشمنت شرمنده.
فدا مدات.

سلام
به چه نتیجه ای رسیدین مطمئن شدین n می شه . چون جواب ارسال ۱۱ که انگار n رو رد کردن ؟

(۰۳ بهمن ۱۳۹۱ ۰۲:۱۰ ق.ظ)ana_12345 نوشته شده توسط:  سلام
به چه نتیجه ای رسیدین مطمئن شدین n می شه . چون جواب ارسال ۱۱ که انگار n رو رد کردن ؟

همون طوری که بچه ها گفتن من به راه حل سنجش ایراد گرفتم. چون اون طوری که اون حل کرده میشه n^2 اما بعدش یه راهی پیشنهاد کردم که میشه همون n

Emkanesh hast soalato upload konin?

سلام.
ارسال ۱۱ n رو رد نکرده پاسخنامه سنجش رو رد کرده چون طبق پاسخنامش که حل کنی می شه On2 اما در ادامش راهی توضیح دادن که با On حل شده.

---

(۰۳ بهمن ۱۳۹۱ ۰۲:۳۱ ق.ظ)milad1367 نوشته شده توسط:  Emkanesh hast soalato upload konin?

سلام سوال دقیقا همون چیزیه که توی ارسال اول توضیح دادم. فقط جای گزینه دو و سه رو باید عوض کنید.


دو لیست مرتب داریم هر کدوم n عضوی. می خوایم تعداد زوج های (i,j) را بشماریم که برای آن ها رابطه a[i] +b[j]<= x برقرار باشه.
الگوریتم کارا این کار را در چه زمانی انجام می دهد؟
logn
nlogn
n
n2

جالبه :
جدیدا کلا هرچی تست میدن بیشترشون میشه O_N

سلام
مرسی اقای mahdii . اره متوجه شدم . دفعه اول نفهمیدم . دفعه دوم دوباره خوندم فهمیدم چی به چی . دستتون درد نکنه