انجمنصفحه اولجستجوی انجمن

[فرزین]

ضمن تشکر از آقای تنهایی که سبب شدند دانشجویان مشتاق و علاقمند در این فروم گرد بیایند
سوال ۳۴ تخصصی نرم افزار یکی از سوالات مورد بحث است در کارشناسی ارشد علوم کامپیوتر ۸۷ سوال ۸۶ مشابه به این سوال بود ولی ابعاد ماتریس n*n نبود در کتابی که شامل حل سوالات کنکور علوم کامپیوتر تالیف آقای مقسمی بود جواب این مساله n log n ذکر شده بود ولی در کنکور امسال ۲n آمده است دوستان نظری در این رابطه دارند یا نه ؟
تصویر سوال[/url]

[mdgh]

این الگوریتم به این صورت هست که ابتدا ستون اول را با توجه با اینکه اعداد مرتب هستند با جستجوی دودویی جستجو کنیم و بعد ستون دوم و ... درنهایت هم ستون nام (البته سطر به سطر هم میشه پیش رفت). از آنجایی که n تا ستون داریم و n بار جستجوی دودویی را اجرا میکنیم پس مرتبه‌ی این الگوریتم nlogn خواهد بود.
حال باید به این فکر کنیم که جستجوهای دودویی در این الگوریتم(که n بار اجرا می شود) هر بار دنبال چه عددی هستند؟ آیا این الگوریتم جواب درست می دهد؟ پاسخ آن خیر است، با این الگوریتم به جواب نمی رسیم.

[mahdieh-Z]

تو گزینه های اعلام شده از طرف سنجش برای این سوال علوم کامپیوتر سال ۸۷ هم همون ۲n اومده و اینکه اگه از این الگوریتم (پایین توضیحش دادم) استفاده بشه به جواب میرسیم(۲n) و اگه از جستجوی دودویی استفاده بشه مرتبه الگوریتم بدتر میشه!

متن الگوریتم هم تو همون علوم کامپیوتر سال ۸۷ اومده بود اینکه در بدترین حالت باید مثلا تا آخر سطر اول بره جلو و بعد بیاد پایین تا آخر سطر آخر... (همون ۲n)
چیزی که از توصیف کلی الگوریتمش یادم مونده استفاده از مرتب بودن هم تو سطر هست هم تو ستون!
شما از اولین خونه از آخرین سطر شروع میکنید(به سمت بالا) و تو این ستون با مقایسه با بعدی اگه x کوچکتر از محتویات اون خونه بود جلو میرید (اگه مساوی بود که پیدا شده) ولی اگه بزگتر بود میریم سراغ ستون بعدی سطر پایین...
 امیدوارم شکل زیر کمک کنه منظورم رو برسونم(عددهایی که دورشون دایرست ترتیب مقایسه‌ها رو نشون میده)

اگه کسی مثال نقض بده برای الگوریتم عالی میشه!

[mdgh]

الگوریتمی که مرتبه آن ۲n است از جستجوی دودویی استفاده نمی کند.

[msmiran]

سلام دوستان
این سوال به نظر من جای هیچ بحثی نداره
با این الگوریتم گزینه ۱ صحیح خواهد بود:
عدد مورد جستجو رو x در نظر میگریم،
جستجو رو از عدد موجود در آخرین سطر ستون اول شروع میکنیم، مقدار x رو با این عدد مقایسه میکنیم، اگه این عدد از x بزرگتر بود، در همون ستون، یک سطر به عقب برمیگردیم، و اگه از x کوچکتر بود، در همون سطر، یک ستون به جلو حرکت میکنیم، در این حالت بدترین حالت ۲n خواهد شد.
زمانی nlogn صحیح خواهد بود که ماتریس یا فقط سطرها مرتبط شده باشن، یا فقط ستون ها، ولی در اینجا هم سطر و هم ستون مرتب شده،
برا فهمش هم میتونید از عکس mahdieh-Z استفاده کنید،