سوال میگه :
" اگر n عدد صحیح داشته باشیم که یکی از آنها x باشد، الگوریتمی که تشخیص دهد دو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا x می باشد، دارای کدام پیچیدگی است؟"
1) O(logn
2) O(n
3) O(nlogn
4) O(n^2
مقسمی میگه nlogn ولی مدرسان همین سوال و سرِ آزمون ششم داد که گفت n میشه. من تو همون آزمونم nlogn زده بودم. چجوری حل میشه؟
سلام
اگه بخوایم با جست و جوی دودویی حل کنیم جواب میشه nlogn (چون فقط زمان مرتب سازی مد نظره و پیدا کردن عنصر زمانش (1)O هستش)
ولی به نظرم بشه با جدول درهم سازی حل کرد به این صورت که 2n خونه در نظر بگیریم و بعد عناصر وارد کنیم و بعد مثلا اگه قراره x+Y =t عددمون بشه ما دو جدول درهم سازی دنبال خونه t-x هستیم گه زمانش (1)O .پس میشه جواب نهایی میشه O(n) که زمان ساخت جدول درهم سازیه
امیدوارم درست باشه
شاد باشین
(07 بهمن 1392 09:53 ب.ظ)*afsoon* نوشته شده توسط: [ -> ]سلام
اگه بخوایم با جست و جوی دودویی حل کنیم جواب میشه nlogn (چون فقط زمان مرتب سازی مد نظره و پیدا کردن عنصر زمانش (۱)O هستش)
ولی به نظرم بشه با جدول درهم سازی حل کرد به این صورت که ۲n خونه در نظر بگیریم و بعد عناصر وارد کنیم و بعد مثلا اگه قراره x+Y =t عددمون بشه ما دو جدول درهم سازی دنبال خونه t-x هستیم گه زمانش (۱)O .پس میشه جواب نهایی میشه O(n) که زمان ساخت جدول درهم سازیه
امیدوارم درست باشه
شاد باشین
پوران هم گفته nlogn
فکر کنم اصلا نیازی به مرتب سازی نباشه
با استفاده از تابع partition باید بشه حلش کرد ، در زمان n
این مثال رو میشه با تغییر در پیدا کردن بزرگترین زیر آرایه با استفاده از برنامه ریزی پویا حل کرد. البته مطمین نیستم. ولی احتمالا کار کنه
Sent from my SM-T210R using Tapatalk