سلام.
دو لیست مرتب داریم هر کدوم n عضوی. می خوایم تعداد زوج های (i,j) را بشماریم که برای آن ها رابطه a[i] +b[j]<= x برقرار باشه.
الگوریتم کارا این کار را در چه زمانی انجام می دهد؟
logn
n
nlogn
n2
همه از مرتبه O هستند.
بر اساس مرج کردن دو آرایه مرتب از مرتبه o(n+ m گفتی/
فکر کنم
دوتا ارایه مرتب با n ادغام میکنیم
که الان یه ارایه مرتب داریم
بعد هم یه جست و جوی خطی و جمع و مقایسه((مثلا یه شمارنده بذاریم،که وقتی دو تا عنصر باویژگی گفته شده رو پیدا کرد زیاد شه)
در طول ارایه انجام میدییم که همه این ها از مرتبه n
البته این تحلیل من شاید درست نباشه
دوستان نظر بدن
(30 دى 1391 11:36 ب.ظ)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]
اگه دوستان دیگه موافقند و نظر دیگری ندارن و اگه ابهامی بود بگو تا بیشتر توضیح بدم.
کاش پاسخ خود سنجش هم بذارید
به نظر من نمی تونیم ادغام کنیم چون اگه ادغام کنیم چطور میشه بفهمیم, a[i] , b[i] کدوما هستن. چون می خوایم اونا رو با هم جمع کنیم و مقایسه کنیم با x. به نظر من با log هم حل میشه. حالا بچه ها هم نظر بدن درسته یانه
ما از تکنیک شبیه جستجوی باینری استفاده می کنیم. اول دو عنصر وسط لیست ها رو با هم چک می کنیم. اگر جمعشون بزرگتر از x شد که دیگه به بخش دومی این لیستها کار نداریم چون حتما جمع اونها هم بزرگتر از x میشه. پس میریم به بخش اول و اونو به دو قسمت تقسیم می کنیم. اگر این بار هم جمع این دو عنصر وسطی بزرگتر از x شد که مثل قبل بخش دومش حذف میشه اما فرض کنین که کوچکتر بود پس مطمئنا اعداد بخش اول (سمت چپی) هر دو لیست هم با هم جمع بشن باز کوچکتر از xخواهند بود که تعدادشو به راحتی میشه حساب کرد. اگر این بخش دارای m عنصر باشه پس تعداد زوجهای جواب تاحالا میشه m^2. بنابراین میریم سراغ بخش راستی این بخش و کارا رو همین طور تکرار می کنیم. بنابراین چون در هر مرحله نصف مساله تکلیفش مشخص میشه ، پس مرتبه log هست
سلام
میشه
یه کم بیشتر توضیح بدید
جمع دو تا ایندکس ؟؟
(01 بهمن 1391 12:07 ق.ظ)nina69 نوشته شده توسط: [ -> ]فکر کنم
دوتا ارایه مرتب با n ادغام میکنیم
که الان یه ارایه مرتب داریم
بعد هم یه جست و جوی خطی و جمع و مقایسه((مثلا یه شمارنده بذاریم،که وقتی دو تا عنصر باویژگی گفته شده رو پیدا کرد زیاد شه)
در طول ارایه انجام میدییم که همه این ها از مرتبه n
البته این تحلیل من شاید درست نباشه
دوستان نظر بدن
این الگوریتم شما از مرتبه n2 می شه. چون برای تک تک عناصر باید این کارارو تکرار کرد که می شه n * n + n که می شه On2
جواب سنجش هم چشم فردا می ذارم الان خدایی حسش نیس بیارمش
(01 بهمن 1391 12:17 ق.ظ)8Operation نوشته شده توسط: [ -> ]درسته
لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.
مرسی.
خوب منم دقیقا به همین فکر کردم . اما دقت کن مرتبه این کار می شه n* logn. ما هر بار لازم داریم عنصر وسط لیست اول رو انتخاب کنیم که از مرتبه O1 هستش حالا شبیه جست و جوی باینری در لیست دوم باید بگردیم که می شه O logn تا اینجا شده پس برای یک عنصر شده Olongn و ما باید باری تک تک عناصر انجام بدیم که می شه Onlogn که جواب اشتباس.
این پاسخ سنجش برای این سوال:
![[تصویر: 0f73eyjpok2brg0flbti.jpg]](http://www.axofile.com/images/0f73eyjpok2brg0flbti.jpg)
این دیگه چه جوابیه. این که میشه n^2 کجاش n هست. تازه گفته o ای کوچک??
شما فرض کن دو آرایه به صورت زیر باشه.
A 1 2 3 4 50
B 60 61 62 63 64
و x باشه 68
خوب آخرین خانه A هست 50 که با 60 جمع شه میشه 110 چون کمتر از x نیست پس باید بر روش یه حلقه دیگه بزنیم که میشه n و کانتر میشه 4
حالا 61 رو با 50 جمع می کنیم بازم بیشتره باز مجبوریم روش حلقه بزنیم که بازم n هست و کانتر میشه 4+4=8 و برای بقیه هم همین طور پس میشه n^2 فکر کنم
اما اگه این راهو بریم فکر کنم میشه همون اوی n که به ذهنم رسید.
یک شماره گر برای A درنظر بگیرید که به خونه آخر اشاره داره و یک اشاره گر دیگر که به خونه اول B اشاره داره. حالا شروع می کنیم. اگر جمع این دو عنصر کمتر از x بودند که بنابراین جمع تک تک عناصر A با خونه اول B کوچکتر از x میشه پس به همون اندازه به کانتر اضافه می کنیم و یه دونه اشاره گر B رو جلو می بریم. حال فرض کنین که خونه دوم B جمعش با خونه آخر A بزرگتر از x شد پس جمع تک تک عناصر B از خونه دوم تا آخر با خونه آخر A بزرگتر از x میشه در این صورت اشاره گر A یکی عقب میره و کانتر تغییری نمی کنه، همین کار را رو می کنیم تا یکی از اشاره گرها به آخر برسه. پس میشه اوی n.تو این مثال
60 با 50 جمع می شود جمعش از x بزرگتر است پس اگر 50 با عناصر بعدی B جمع شود بازم بزرگتر است بنابراین اشاره گر A یکی عقب می رود. تا اینجا یک گام رفتیم. 4 با 60 مقایسه می شود جمعش کوچکتر است پس جمع 60 با عناصر قبل اشاره گر A هم باز کوچکتر از x خواهد بود. کانتر می شود 4 و اشاره گر B اضافه می شود این بار 61 با 4 و الی آخر. می بینید در هر گام یکی از اشاره گرها یک واحد حرکت می کند.
بدترین حالتشم زمانی هست که مثلا به این صورت آرایه ها باشند.
1 3 5 7
2 4 6 8
و x=9
که یکی در میان اشاره گرها جابجا میشن تا به آخر برسن که میشه 2n
(01 بهمن 1391 12:31 ق.ظ)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 در پایه 2 که میشه n^1.58
(01 بهمن 1391 03:53 ق.ظ)mahdiii نوشته شده توسط: [ -> ]لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.
دوست عزیز حقیقتش من وقتی سوال شما رو دیدم با روشهای استاد قلی زاده واسه حل این تستها اون رابطه رو ذهنی بدست آوردم،هنوزم فکر می کنم درسته !اما الان گه نشستم دقیقا اثباتش کنم برای خودم تا براتون بفرستم نتونستم در تئوری به رابطه بالا برسم!
خلاصه شرمنده شما شدم.
اما اگه تونستم گره مسئله رو بازکنم حتما جوابشو قرار میدم.
همگی موفق باشید.
آره مرتبش On می شه مرسی از اینکه وقت گذاشتی و عالی فکر کردی.
(01 بهمن 1391 09:40 ق.ظ)8Operation نوشته شده توسط: [ -> ] (01 بهمن 1391 03:53 ق.ظ)mahdiii نوشته شده توسط: [ -> ]لطفا بیش تر توضیح بده و همین طور درباره روابط بازگشتیت که به دست آوردی. کاری به محاسبش ندارمو خودشو از کجا اومد و چه طور تبدیل شد.
دوست عزیز حقیقتش من وقتی سوال شما رو دیدم با روشهای استاد قلی زاده واسه حل این تستها اون رابطه رو ذهنی بدست آوردم،هنوزم فکر می کنم درسته !اما الان گه نشستم دقیقا اثباتش کنم برای خودم تا براتون بفرستم نتونستم در تئوری به رابطه بالا برسم!
خلاصه شرمنده شما شدم.
اما اگه تونستم گره مسئله رو بازکنم حتما جوابشو قرار میدم.
همگی موفق باشید.
دشمنت شرمنده.
فدا مدات.
سلام
به چه نتیجه ای رسیدین مطمئن شدین n می شه . چون جواب ارسال 11 که انگار n رو رد کردن ؟
Emkanesh hast soalato upload konin?