سلام، سوال از این قرار است:
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
(۱۹ بهمن ۱۳۹۲ ۰۱:۲۳ ب.ظ)fulgent نوشته شده توسط: سلام، سوال از این قرار است:از مرتبه nlogn میشه.
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
آرایه A را مرتب میکنیم
یه مجموعه 'A تشکیل میدیم ، که اعضاش x-y باشند و y عضو A
عناصر 'A رو مرتب میکنیم
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم
A و 'A رو با هم ادغام میکنیم
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
(۱۹ بهمن ۱۳۹۲ ۰۱:۳۷ ب.ظ)e.shrm نوشته شده توسط:(19 بهمن ۱۳۹۲ ۰۱:۲۳ ب.ظ)fulgent نوشته شده توسط: سلام، سوال از این قرار است:از مرتبه nlogn میشه.
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
آرایه A را مرتب میکنیم
یه مجموعه 'A تشکیل میدیم ، که اعضاش x-y باشند و y عضو A
عناصر 'A رو مرتب میکنیم
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم
A و 'A رو با هم ادغام میکنیم
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
خب این الگوریتم پیچیدگی اش چیه؟ میشه همین طور پیچیدگی هر مرحله رو جدا بگی؟
ادغام A و 'Aمگه میشه؟! یکی مرتب و دیگری نامرتب؟
بالاخره کی اون دوتا عنصر پیدا شد؟ در کدام مرحله؟
با الگوریتم حاصل جمع زیر مجموعه ها می شه اینکارو کرد اونوقت (۲ به توان n) می شه ولی اونوقت همه زیر مجموعه ها پیدا می شن ولی این چون گفته یکیشو نمی دانم شاید الگوریتم دیگه ای که زمانش کمتر از این بشه وجود داشته باشه!مثلا اول آرایه رو مرتب کنیم بعد با جستجوی دودویی ببینیم پیدا می شه یا نه؟!
(۱۹ بهمن ۱۳۹۲ ۰۱:۳۶ ب.ظ)tayebe68 نوشته شده توسط:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خودتون هم که تو این پست شرکت داشتید
سوال این با اون فرق میکنه....اونجا x جز ارایه بود ولی اینجا نیست.
(۱۹ بهمن ۱۳۹۲ ۰۱:۳۷ ب.ظ)e.shrm نوشته شده توسط: از مرتبه nlogn میشه.مرتبه زمانی ها رو اضافه کردم بالا. گفتم که هر دو رو مرتب میکنیم.
آرایه A را مرتب میکنیم ----> nlogn
یه مجموعه 'A تشکیل میدیم ، که اعضاnش x-y باشند و y عضو A هستند. ----> n
عناصر 'A رو مرتب میکنیم -----> nlogn
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم ---->n
A و 'A رو با هم ادغام میکنیم-------> n
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
یه مثال برا خودت بزن ، منم اینو یه جا خوندم که برات نوشتم.
(۱۹ بهمن ۱۳۹۲ ۰۱:۵۵ ب.ظ)e.shrm نوشته شده توسط:میشه روی این مثال حلش کنی؟ من به جواب نمیرسم!(19 بهمن ۱۳۹۲ ۰۱:۳۷ ب.ظ)e.shrm نوشته شده توسط: از مرتبه nlogn میشه.مرتبه زمانی ها رو اضافه کردم بالا. گفتم که هر دو رو مرتب میکنیم.
آرایه A را مرتب میکنیم ----> nlogn
یه مجموعه 'A تشکیل میدیم ، که اعضاnش x-y باشند و y عضو A هستند. ----> n
عناصر 'A رو مرتب میکنیم -----> nlogn
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم ---->n
A و 'A رو با هم ادغام میکنیم-------> n
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
یه مثال برا خودت بزن ، منم اینو یه جا خوندم که برات نوشتم.
این ارایه منه:
[۱,۴,۷,۵,۱۳,۲,۱۹,۰,۱۵,۸]
و عدد x= 10 هست.
حال شما برای پیدا کردن دو عنصر در ارایه که جمعشون بشه ۱۰ (یعنی ۸ و۲ ) روند الگوریتم رو میگید؟
مرحله اول آرایمون رو با مرتبه nlogn مرتب می کنیم
از اینجا دو تا راه داریم که اولی راه عادی و دومی یه مقدار بهینه تر هست
راه اول: مقدار i رو برابر اندیس اولین عنصر و j رو برابر اندیس آخرین عنصر قرار بدیم
اگر حاصل جمع از x بزرگتر بود مقدار j یک واحد کم میشه و اگر حاصل جمع از x کوچکتر بود مقدار i یک واحد اضاف میشه
این عمل اونقدر ادامه پیدا میکنه که یا اون دو عدد پیدا شه و یا i بزرگتر از j بشه که به معنی عدم وجود این دو عدد هست
هزینه هم برابر n میشه
هزینه میشه: nlogn+n
راه دوم: اول به دنبال عدد x بگردیم به صورت دودویی اگر x داخل آرایه بود اندیسش منهای ۱ رو داخل j میریزیم و اگر داخل آرایه نبود این الگوریتم کوچکترین عدده بزرگتر از x رو به ما میده و در اینصورت اندیس این عنصر منهای ۱ داخل j میریزیم و بقیه اعمال میشه همون مراحل بالا
هزینه میشه nlogn+logn+n که البته اینجا دقیقا n نیست و کمتر از n میشه
(۱۹ بهمن ۱۳۹۲ ۰۳:۱۶ ب.ظ)hosshah نوشته شده توسط: مرحله اول آرایمون رو با مرتبه nlogn مرتب می کنیمبله جواب داد....متشکرم
از اینجا دو تا راه داریم که اولی راه عادی و دومی یه مقدار بهینه تر هست
راه اول: مقدار i رو برابر اندیس اولین عنصر و j رو برابر اندیس آخرین عنصر قرار بدیم
اگر حاصل جمع از x بزرگتر بود مقدار j یک واحد کم میشه و اگر حاصل جمع از x کوچکتر بود مقدار i یک واحد اضاف میشه
این عمل اونقدر ادامه پیدا میکنه که یا اون دو عدد پیدا شه و یا i بزرگتر از j بشه که به معنی عدم وجود این دو عدد هست
هزینه هم برابر n میشه
هزینه میشه: nlogn+n
راه دوم: اول به دنبال عدد x بگردیم به صورت دودویی اگر x داخل آرایه بود اندیسش منهای ۱ رو داخل j میریزیم و اگر داخل آرایه نبود این الگوریتم کوچکترین عدده بزرگتر از x رو به ما میده و در اینصورت اندیس این عنصر منهای ۱ داخل j میریزیم و بقیه اعمال میشه همون مراحل بالا
هزینه میشه nlogn+logn+n که البته اینجا دقیقا n نیست و کمتر از n میشه
(۱۹ بهمن ۱۳۹۲ ۰۳:۳۹ ب.ظ)fulgent نوشته شده توسط: بله جواب داد....متشکرم
خدا رو شکر
خواهش می کنم
اول در زمان [tex]nlogn[/tex] آرایه را مرتب میکنیم
حالا در n مرحله اعمال زیر را انجام میدیم
مرحله ۱ :
x - A[1] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم و اگر بود که مسئله حل شده و اگر نبود مرحله بعدی
مرحله ۲ :
x - A[2] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم
... و تا اینکه برای تمام n عنصر آرایه این رویه را انجام میدیم که هر مرحله هزینه جستجوی logn داره و n مرحله داشتیم که میشه nlogn
و در کل زمان میشه ۲nlogn
(۱۹ بهمن ۱۳۹۲ ۱۰:۲۲ ب.ظ)masoud67 نوشته شده توسط: اول در زمان [tex]nlogn[/tex] آرایه را مرتب میکنیم
حالا در n مرحله اعمال زیر را انجام میدیم
مرحله ۱ :
x - A[1] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم و اگر بود که مسئله حل شده و اگر نبود مرحله بعدی
مرحله ۲ :
x - A[2] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم
... و تا اینکه برای تمام n عنصر آرایه این رویه را انجام میدیم که هر مرحله هزینه جستجوی logn داره و n مرحله داشتیم که میشه nlogn
و در کل زمان میشه ۲nlogn
از اینکه وقت گذاشتین متشکرم
این سوال دو جواب دارد. یکی nlogn که دوستان اشاره کردند.
یکی دیگه هم با استفاده از جدول درهم ساز که می شه او ان. البته قبل از اینکه بدونم چنین راه حلی هست منم مثل بقیه فکر می کردم حداقلش nlogn هست که اشتباه می کردم.
پاسخ درهم ساز به این مساله در یکی از آزمون های مدرسان اومده بود.