صفحه‌ها: ۱ ۲
![[تصویر: 62236_1_1379096101.png]](https://img.manesht.ir/62236_1_1379096101.png)
گزینه درست ۲nشده حداکثر مقایسه برای پیدا کردن xچون در صورت وجود گفته nهست ضریب ۲ برای چی؟؟؟؟
(۲۰ دى ۱۳۹۰ ۰۲:۳۱ ب.ظ)vijay نوشته شده توسط:ماتریس زیرو فرض کن. که تقریبا به اون ترتیبی که گفته مرتب شده.
گزینه درست ۲nشده حداکثر مقایسه برای پیدا کردن xچون در صورت وجود گفته nهست ضریب ۲ برای چی؟؟؟؟
![[تصویر: 62242_1_1379096101.png]](https://img.manesht.ir/62242_1_1379096101.png)
۴۰ ۳۰ ۲۰ ۱۰
۴۱ ۳۱ ۲۱ ۱۱
۴۲ ۳۲ ۲۲ ۱۲
۴۳ ۳۳ ۲۳ ۱۳
میخوایم عدد ۴۳ پیدا کنیم که حداکثر مقایسه هست.
با n=4 مقایسه در سطر میفهمیم در سطر آخره و با n=4 مقایسه در ستون میفهمیم در ستون آخره.
پس کلا شد n+n=2n
یعنی الگورریتم ما عدد xرا بااعداد اول و آخر هرسطر مقایسه میکنه بین آنها نبود میره سطر بعد همینطور تا آخر.بعد اگه در سطری با این روش پیدا شد میره سراغ ستونش که همون nتا ستون میشه حداکثر و میشه ۲n.
استدلال من اینه از جواب شما دوست عزیز درسته؟؟؟
(۲۰ دى ۱۳۹۰ ۰۷:۱۳ ب.ظ)vijay نوشته شده توسط: یعنی الگورریتم ما عدد xرا بااعداد اول و آخر هرسطر مقایسه میکنه بین آنها نبود میره سطر بعد همینطور تا آخر.بعد اگه در سطری با این روش پیدا شد میره سراغ ستونش که همون nتا ستون میشه حداکثر و میشه ۲n.
استدلال من اینه از جواب شما دوست عزیز درسته؟؟؟
در این مثال ابتدا میاد سطر اولو میبینه و با تک تکشون مقایسه میکنه. میبینه که ۴۳ از ۴۰ هم بزرگتره پس میفهمه جواب تو ستون آخره. اینکارو حداکثر با n=4 مقایسه انجام داد.
حالا میاد تو ستون آخر مقایسه رو انجام میده و میبینه جواب تو سطر آخره که میتونه حداکثر با n=4 مقایسه پیدا کنه.
پس در کل با n=2n مقایسه جواب پیدا میشه.
مثلا برای پیدا کردن ۳۲ بعد از مقایسه در سطر اول میفهمه که ۳۲ کوچکتر از ۴۰ هست و جواب در ستون سوم قرار داره و فقط این ستونو میگرده و ...
البته بدترین حالت به صورت زیر هست:
۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳
حالا فرض کنید که میخوایم ۱۵ رو پیدا کنیم.
الگوریتم درست توی این مساله به صورت اریب حرکت میکنه. اگه گفتین چه شکلی؟
با الگوریتم قبلی ۳n زمان می‌بره!
همون روش قبلی که گفتیم ولی این بار فکر کنم یه برگشت به عقب داریم یعنی از۱۶ به ۱۳
(۲۰ دى ۱۳۹۰ ۰۸:۵۵ ب.ظ)admin نوشته شده توسط: البته بدترین حالت به صورت زیر هست:اگه تو ماتریس شما اول ستونو بگرده بعد سطرو باز جواب کمتر از ۲n میشه.
۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳
حالا فرض کنید که میخوایم ۱۵ رو پیدا کنیم.
الگوریتم درست توی این مساله به صورت اریب حرکت میکنه. اگه گفتین چه شکلی؟
با الگوریتم قبلی ۳n زمان می‌بره!
روش مرتب سازی ماتریس شما فرق میکنه با روش مرتب سازی شده در ماتریس من.
در ماتریس که من نوشتم ستونها رو برحسب دهگانی که دارن متمایز کرده و سطرها رو بر حسب یکانی که دارن متمایز کرده. ولی در ماتریس شما چون این ترتیب وجود نداره این حالت پیش اومده.
میتونیم الگوریتمی جوری بنویسیم که طبق روش مرتب سازی ما ماترسیو جستجو کنه. و مثلا اگر مثله ماتریس شما نشه ستونها رو بر حسب دهگان متمایز کرد و اعداد شبیه هم در دهگان بوجود بیاد اونوقت اول ستونها رو جستجو کنه.
(۲۰ دى ۱۳۹۰ ۰۹:۲۹ ب.ظ)sasanlive نوشته شده توسط: روش مرتب سازی ماتریس شما فرق میکنه با روش مرتب سازی شده در ماتریس من.خوب چطوری می‌نویسی آخر سر؟ اول ستون یا اول سطر؟ الگوریتم شما در بدترین شرایط پیچیدگیش ۳n-1 است.
در ماتریس که من نوشتم ستونها رو برحسب دهگانی که دارن متمایز کرده و سطرها رو بر حسب یکانی که دارن متمایز کرده. ولی در ماتریس شما چون این ترتیب وجود نداره این حالت پیش اومده.
میتونیم الگوریتمی جوری بنویسیم که طبق روش مرتب سازی ما ماترسیو جستجو کنه. و مثلا اگر مثله ماتریس شما نشه ستونها رو بر حسب دهگان متمایز کرد و اعداد شبیه هم در دهگان بوجود بیاد اونوقت اول ستونها رو جستجو کنه.
چطوری می‌خوای بفهمی که شکل ماتریس چجوریه؟
الگوریتم دقیق اینطوریه:
به صورت اریب از بالا شروع میکنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو میکنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی میکنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که میشه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n میشه
(۲۰ دى ۱۳۹۰ ۰۹:۴۹ ب.ظ)admin نوشته شده توسط: خوب چطوری می‌نویسی آخر سر؟ اول ستون یا اول سطر؟ الگوریتم شما در بدترین شرایط پیچیدگیش ۳n-1 است.
چطوری می‌خوای بفهمی که شکل ماتریس چجوریه؟
الگوریتم دقیق اینطوریه:
به صورت اریب از بالا شروع میکنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو میکنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی میکنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که میشه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n میشه
الگوریتم مرتب سازی به شکل بهینه نوشته میشه.
ما زمان جستجو رو تو این مسئله میخوایم.
شما ماتریسو فقط پشت سره هم نوشتین و الگوریتم مرتب سازی خاصی روش پیاده سازی نشده. باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه. چون مسئله گفته هم در ستون و هم در سطر مرتب سازی صورت گرفته.
اگه میشه با اعداد در ماتریسه خودتون یا من روند جستجوتونو شرح بدین تا ما متوجه بشیم به چه شکلی الگوریتم شما جستجو میکنه.
(۲۰ دى ۱۳۹۰ ۱۰:۱۵ ب.ظ)sasanlive نوشته شده توسط: باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه.
الان که دوباره جواب خودم رو دیدم فهمیدم یه مشکلی هست توش. مثلا برای پیدا کردن ۴ جواب نمی‌ده.
مساله خیلی جالب شد ماتریس زیر رو در نظر بگیرید:
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴
حالا فرض کنید که می‌خواید ۱۴ رو پیدا کنید. چطوری پیدا می‌کنید؟
الگوریتم برای ۱۱ چطوری جواب میده؟
برای یافتن ۱۲ چه کار می‌کنید؟
فکر کنم از جستجوی باینری باید یه بهره‌ای ببریم
نمیشه با مقایسه آخرین عنصر هر سطر، ابتدا هر سطر را پیدا کنیم (همان مرتبه n) و بعد که سر پیدا شد با مرتبه Logn عنصر مورد نظر را پیدا کنیم. اسم این جستجویی که Logn بود یادم رفت.
(۲۰ دى ۱۳۹۰ ۱۰:۲۸ ب.ظ)admin نوشته شده توسط: ماتریس من هم تو سطر و هم تو ستون مرتبه.
نمیگم مرتب نیست.
میگم از ابتدا روش الگوریتم مرتب سازی خاصی بکار برده نشده و چون پشت سره هم نوشتین مرتبه.
در سوال گفته سطر و ستون مرتب شدن یعنی بر اساس یه الگوریتمی. شما بر چه اساسی سطرو جدا و ستونو جدا مرتب کردین؟
(۲۰ دى ۱۳۹۰ ۱۰:۲۸ ب.ظ)admin نوشته شده توسط: الگوریتم دقیق اینطوریه:
به صورت اریب(قطری) از بالا شروع میکنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو میکنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی میکنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که میشه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n میشه
اگه میشه با عدد شرح بدین من فکر میکنم الگوریتم جستجوتون ایراد داره.
لطف کنین با عدد در ماتریس خودتون یا من روش جستجو رو توضیح بدین.
البته برای جستجو سطر بالا و ستون چپ باید از روش‌های باینری استفاده کنید.
(۲۰ دى ۱۳۹۰ ۱۰:۱۵ ب.ظ)sasanlive نوشته شده توسط: شما ماتریسو فقط پشت سره هم نوشتین و الگوریتم مرتب سازی خاصی روش پیاده سازی نشده. باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه. چون مسئله گفته هم در ستون و هم در سطر مرتب سازی صورت گرفته.ماتریس‌های مثال من هر دو تا هم در سطر و هم در ستون مرتب هستند
(۲۰ دى ۱۳۹۰ ۱۰:۳۵ ب.ظ)pos نوشته شده توسط: نمیشه با مقایسه آخرین عنصر هر سطر، ابتدا هر سطر را پیدا کنیم (همان مرتبه n) و بعد که سر پیدا شد با مرتبه Logn عنصر مورد نظر را پیدا کنیم. اسم این جستجویی که Logn بود یادم رفت.نه
مثال:
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴
حالا فرض کنید که می‌خواید ۱۴ رو پیدا کنید. چطوری پیدا می‌کنید؟
الگوریتم برای ۱۱ چطوری جواب میده؟
برای یافتن ۱۲ چه کار می‌کنید؟
فکر کنم از جستجوی باینری باید یه بهره‌ای ببریم
(۲۰ دى ۱۳۹۰ ۱۰:۵۵ ب.ظ)admin نوشته شده توسط: ماتریس‌های مثال من هر دو تا هم در سطر و هم در ستون مرتب هستند
میدونم مرتب هستن ولی وقتی یه تعداد عدد میدن بدون ترتیب خاص الگوریتم مرتب سازی اول سطرو جدا و ستونو جدا بر اساس الگوریتم خاصی مرتب میکنه.و فرض میکنیم اعدادو به شکلی در ماتریس مرتب میکنه که جستجوی ما بهینه بشه و بعد حداکثر زمان جستجو رو توش پیدا میکنیم.ولی شما فقط اعدادو معمولی مرتب کردین و بصورت ترتیبی در ماتریس قرار دادین. مرتب میشه ولی جستجو رو بهینه نمیکنه.
هنوز مثال عددی نزدین. من هر چی از روش شما میرم به حالتهای نقض برمیخورم.