۰
subtitle
ارسال: #۱
علوم کامپیوتر ۸۸ - مرتب سازی
سوال میگه :
" اگر n عدد صحیح داشته باشیم که یکی از آنها x باشد، الگوریتمی که تشخیص دهد دو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا x می باشد، دارای کدام پیچیدگی است؟"
۱) O(logn
۲) O(n
۳) O(nlogn
۴) O(n^2
مقسمی میگه nlogn ولی مدرسان همین سوال و سرِ آزمون ششم داد که گفت n میشه. من تو همون آزمونم nlogn زده بودم. چجوری حل میشه؟
" اگر n عدد صحیح داشته باشیم که یکی از آنها x باشد، الگوریتمی که تشخیص دهد دو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا x می باشد، دارای کدام پیچیدگی است؟"
۱) O(logn
۲) O(n
۳) O(nlogn
۴) O(n^2
مقسمی میگه nlogn ولی مدرسان همین سوال و سرِ آزمون ششم داد که گفت n میشه. من تو همون آزمونم nlogn زده بودم. چجوری حل میشه؟
۲
ارسال: #۲
RE: علوم کامپیوتر ۸۸ - مرتب سازی
سلام
اگه بخوایم با جست و جوی دودویی حل کنیم جواب میشه nlogn (چون فقط زمان مرتب سازی مد نظره و پیدا کردن عنصر زمانش (۱)O هستش)
ولی به نظرم بشه با جدول درهم سازی حل کرد به این صورت که ۲n خونه در نظر بگیریم و بعد عناصر وارد کنیم و بعد مثلا اگه قراره x+Y =t عددمون بشه ما دو جدول درهم سازی دنبال خونه t-x هستیم گه زمانش (۱)O .پس میشه جواب نهایی میشه O(n) که زمان ساخت جدول درهم سازیه
امیدوارم درست باشه
شاد باشین
اگه بخوایم با جست و جوی دودویی حل کنیم جواب میشه nlogn (چون فقط زمان مرتب سازی مد نظره و پیدا کردن عنصر زمانش (۱)O هستش)
ولی به نظرم بشه با جدول درهم سازی حل کرد به این صورت که ۲n خونه در نظر بگیریم و بعد عناصر وارد کنیم و بعد مثلا اگه قراره x+Y =t عددمون بشه ما دو جدول درهم سازی دنبال خونه t-x هستیم گه زمانش (۱)O .پس میشه جواب نهایی میشه O(n) که زمان ساخت جدول درهم سازیه
امیدوارم درست باشه
شاد باشین
ارسال: #۳
RE: علوم کامپیوتر ۸۸ - مرتب سازی
(۰۷ بهمن ۱۳۹۲ ۰۹:۵۳ ب.ظ)*afsoon* نوشته شده توسط: سلام
اگه بخوایم با جست و جوی دودویی حل کنیم جواب میشه nlogn (چون فقط زمان مرتب سازی مد نظره و پیدا کردن عنصر زمانش (۱)O هستش)
ولی به نظرم بشه با جدول درهم سازی حل کرد به این صورت که ۲n خونه در نظر بگیریم و بعد عناصر وارد کنیم و بعد مثلا اگه قراره x+Y =t عددمون بشه ما دو جدول درهم سازی دنبال خونه t-x هستیم گه زمانش (۱)O .پس میشه جواب نهایی میشه O(n) که زمان ساخت جدول درهم سازیه
امیدوارم درست باشه
شاد باشین
پوران هم گفته nlogn
۰
ارسال: #۴
RE: علوم کامپیوتر ۸۸ - مرتب سازی
فکر کنم اصلا نیازی به مرتب سازی نباشه
با استفاده از تابع partition باید بشه حلش کرد ، در زمان n
با استفاده از تابع partition باید بشه حلش کرد ، در زمان n
۰
ارسال: #۵
RE: علوم کامپیوتر ۸۸ - مرتب سازی
این مثال رو میشه با تغییر در پیدا کردن بزرگترین زیر آرایه با استفاده از برنامه ریزی پویا حل کرد. البته مطمین نیستم. ولی احتمالا کار کنه
Sent from my SM-T210R using Tapatalk
Sent from my SM-T210R using Tapatalk
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close