۰
subtitle
ارسال: #۱
  
الگوریتم مناسب برای یافتن دو عنصر از ارایه که مجموع مقادیرشان برابر x است
سلام، سوال از این قرار است:
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
۱
ارسال: #۲
  
RE: یافتن الگوریتم بهینه در مساله داده شده
اول در زمان [tex]nlogn[/tex] آرایه را مرتب میکنیم
حالا در n مرحله اعمال زیر را انجام میدیم
مرحله ۱ :
x - A[1] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم و اگر بود که مسئله حل شده و اگر نبود مرحله بعدی
مرحله ۲ :
x - A[2] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم
... و تا اینکه برای تمام n عنصر آرایه این رویه را انجام میدیم که هر مرحله هزینه جستجوی logn داره و n مرحله داشتیم که میشه nlogn
و در کل زمان میشه ۲nlogn
حالا در n مرحله اعمال زیر را انجام میدیم
مرحله ۱ :
x - A[1] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم و اگر بود که مسئله حل شده و اگر نبود مرحله بعدی
مرحله ۲ :
x - A[2] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم
... و تا اینکه برای تمام n عنصر آرایه این رویه را انجام میدیم که هر مرحله هزینه جستجوی logn داره و n مرحله داشتیم که میشه nlogn
و در کل زمان میشه ۲nlogn
ارسال: #۳
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۱۰:۲۲ ب.ظ)masoud67 نوشته شده توسط: اول در زمان [tex]nlogn[/tex] آرایه را مرتب میکنیم
حالا در n مرحله اعمال زیر را انجام میدیم
مرحله ۱ :
x - A[1] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم و اگر بود که مسئله حل شده و اگر نبود مرحله بعدی
مرحله ۲ :
x - A[2] = y
و مقدار y را در آرایه مرتب با جستجوی دودویی جستجو میکنیم
... و تا اینکه برای تمام n عنصر آرایه این رویه را انجام میدیم که هر مرحله هزینه جستجوی logn داره و n مرحله داشتیم که میشه nlogn
و در کل زمان میشه ۲nlogn
از اینکه وقت گذاشتین متشکرم
۰
ارسال: #۴
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۰۱:۲۳ ب.ظ)fulgent نوشته شده توسط: سلام، سوال از این قرار است:از مرتبه nlogn میشه.
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
آرایه A را مرتب میکنیم
یه مجموعه 'A تشکیل میدیم ، که اعضاش x-y باشند و y عضو A
عناصر 'A رو مرتب میکنیم
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم
A و 'A رو با هم ادغام میکنیم
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
ارسال: #۵
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۰۱:۳۷ ب.ظ)e.shrm نوشته شده توسط:(19 بهمن ۱۳۹۲ ۰۱:۲۳ ب.ظ)fulgent نوشته شده توسط: سلام، سوال از این قرار است:از مرتبه nlogn میشه.
فرض کنید ارایه نامرتب A با n عنصر ، و عدد معینی مانند x داده شده است.
حال می خواهیم در صورت وجود دو عنصر از ارایه که مجموع مقادیرشان برابر x است را پیدا کنیم.
در بدترین حالت، بهترین الگوریتم چیست و از چه پیچیدگی زمانی برخوردار است؟
آرایه A را مرتب میکنیم
یه مجموعه 'A تشکیل میدیم ، که اعضاش x-y باشند و y عضو A
عناصر 'A رو مرتب میکنیم
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم
A و 'A رو با هم ادغام میکنیم
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
خب این الگوریتم پیچیدگی اش چیه؟ میشه همین طور پیچیدگی هر مرحله رو جدا بگی؟
ادغام A و 'Aمگه میشه؟! یکی مرتب و دیگری نامرتب؟
بالاخره کی اون دوتا عنصر پیدا شد؟ در کدام مرحله؟
ارسال: #۶
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۰۱:۳۷ ب.ظ)e.shrm نوشته شده توسط: از مرتبه nlogn میشه.مرتبه زمانی ها رو اضافه کردم بالا. گفتم که هر دو رو مرتب میکنیم.
آرایه A را مرتب میکنیم ----> nlogn
یه مجموعه 'A تشکیل میدیم ، که اعضاnش x-y باشند و y عضو A هستند. ----> n
عناصر 'A رو مرتب میکنیم -----> nlogn
اگر عنصر تکراری داشت ، تکراری ها رو حذف میکنیم ---->n
A و 'A رو با هم ادغام میکنیم-------> n
شرط لازم و کافی برای ایکه در مجموعه A فقط دو عنصر وجود داشته باشد که مجموعشان دقیقا برابر X شود این است که مقادیر مشابه یکدیگر در مجموعه ادغام شده خروجی در موقعیت های پست سر هم ظاهر شوند.
یه مثال برا خودت بزن ، منم اینو یه جا خوندم که برات نوشتم.
ارسال: #۷
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۰۱:۵۵ ب.ظ)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 هست.
حال شما برای پیدا کردن دو عنصر در ارایه که جمعشون بشه ۱۰ (یعنی ۸ و۲ ) روند الگوریتم رو میگید؟
۰
ارسال: #۸
  
RE: یافتن الگوریتم بهینه در مساله داده شده
با الگوریتم حاصل جمع زیر مجموعه ها می شه اینکارو کرد اونوقت (۲ به توان n) می شه ولی اونوقت همه زیر مجموعه ها پیدا می شن ولی این چون گفته یکیشو نمی دانم شاید الگوریتم دیگه ای که زمانش کمتر از این بشه وجود داشته باشه!مثلا اول آرایه رو مرتب کنیم بعد با جستجوی دودویی ببینیم پیدا می شه یا نه؟!
۰
ارسال: #۹
  
RE: یافتن الگوریتم بهینه در مساله داده شده
مرحله اول آرایمون رو با مرتبه nlogn مرتب می کنیم
از اینجا دو تا راه داریم که اولی راه عادی و دومی یه مقدار بهینه تر هست
راه اول: مقدار i رو برابر اندیس اولین عنصر و j رو برابر اندیس آخرین عنصر قرار بدیم
اگر حاصل جمع از x بزرگتر بود مقدار j یک واحد کم میشه و اگر حاصل جمع از x کوچکتر بود مقدار i یک واحد اضاف میشه
این عمل اونقدر ادامه پیدا میکنه که یا اون دو عدد پیدا شه و یا i بزرگتر از j بشه که به معنی عدم وجود این دو عدد هست
هزینه هم برابر n میشه
هزینه میشه: nlogn+n
راه دوم: اول به دنبال عدد x بگردیم به صورت دودویی اگر x داخل آرایه بود اندیسش منهای ۱ رو داخل j میریزیم و اگر داخل آرایه نبود این الگوریتم کوچکترین عدده بزرگتر از x رو به ما میده و در اینصورت اندیس این عنصر منهای ۱ داخل j میریزیم و بقیه اعمال میشه همون مراحل بالا
هزینه میشه nlogn+logn+n که البته اینجا دقیقا n نیست و کمتر از n میشه
از اینجا دو تا راه داریم که اولی راه عادی و دومی یه مقدار بهینه تر هست
راه اول: مقدار i رو برابر اندیس اولین عنصر و j رو برابر اندیس آخرین عنصر قرار بدیم
اگر حاصل جمع از x بزرگتر بود مقدار j یک واحد کم میشه و اگر حاصل جمع از x کوچکتر بود مقدار i یک واحد اضاف میشه
این عمل اونقدر ادامه پیدا میکنه که یا اون دو عدد پیدا شه و یا i بزرگتر از j بشه که به معنی عدم وجود این دو عدد هست
هزینه هم برابر n میشه
هزینه میشه: nlogn+n
راه دوم: اول به دنبال عدد x بگردیم به صورت دودویی اگر x داخل آرایه بود اندیسش منهای ۱ رو داخل j میریزیم و اگر داخل آرایه نبود این الگوریتم کوچکترین عدده بزرگتر از x رو به ما میده و در اینصورت اندیس این عنصر منهای ۱ داخل j میریزیم و بقیه اعمال میشه همون مراحل بالا
هزینه میشه nlogn+logn+n که البته اینجا دقیقا n نیست و کمتر از n میشه
ارسال: #۱۰
  
RE: یافتن الگوریتم بهینه در مساله داده شده
(۱۹ بهمن ۱۳۹۲ ۰۳:۱۶ ب.ظ)hosshah نوشته شده توسط: مرحله اول آرایمون رو با مرتبه nlogn مرتب می کنیمبله جواب داد....متشکرم
از اینجا دو تا راه داریم که اولی راه عادی و دومی یه مقدار بهینه تر هست
راه اول: مقدار i رو برابر اندیس اولین عنصر و j رو برابر اندیس آخرین عنصر قرار بدیم
اگر حاصل جمع از x بزرگتر بود مقدار j یک واحد کم میشه و اگر حاصل جمع از x کوچکتر بود مقدار i یک واحد اضاف میشه
این عمل اونقدر ادامه پیدا میکنه که یا اون دو عدد پیدا شه و یا i بزرگتر از j بشه که به معنی عدم وجود این دو عدد هست
هزینه هم برابر n میشه
هزینه میشه: nlogn+n
راه دوم: اول به دنبال عدد x بگردیم به صورت دودویی اگر x داخل آرایه بود اندیسش منهای ۱ رو داخل j میریزیم و اگر داخل آرایه نبود این الگوریتم کوچکترین عدده بزرگتر از x رو به ما میده و در اینصورت اندیس این عنصر منهای ۱ داخل j میریزیم و بقیه اعمال میشه همون مراحل بالا
هزینه میشه nlogn+logn+n که البته اینجا دقیقا n نیست و کمتر از n میشه
ارسال: #۱۱
  
RE: یافتن الگوریتم بهینه در مساله داده شده
۰
ارسال: #۱۲
  
RE: یافتن الگوریتم بهینه در مساله داده شده
این سوال دو جواب دارد. یکی nlogn که دوستان اشاره کردند.
یکی دیگه هم با استفاده از جدول درهم ساز که می شه او ان. البته قبل از اینکه بدونم چنین راه حلی هست منم مثل بقیه فکر می کردم حداقلش nlogn هست که اشتباه می کردم.
پاسخ درهم ساز به این مساله در یکی از آزمون های مدرسان اومده بود.
یکی دیگه هم با استفاده از جدول درهم ساز که می شه او ان. البته قبل از اینکه بدونم چنین راه حلی هست منم مثل بقیه فکر می کردم حداقلش nlogn هست که اشتباه می کردم.
پاسخ درهم ساز به این مساله در یکی از آزمون های مدرسان اومده بود.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close