amir_pro
یک شنبه 24 خرداد 1388, 13:21 عصر
الگوریتمی که 2n عدد را از ورودی دریافت کند و اعداد را به 2 مجموعه n تایی طوری تقسیم کند که حاصل جمع دو مجموعه برابر شود.
مرتبه این الگوریتم برابر با ترکیب n از 2n که برابر با 2n!/(n!)^2 است. حالا باید از چه الگوریتی استفاده کرد که مرتبه کمتری داشته باشه؟
یک روش اینه که از گرافی استفاده کنیم که از n+1 راس تشکیل شده که از هر راسی به راس دیگر دو یال وجود دارد که وزن یکی همان وزن عنصر اول مجموعه و وزن یال دیگر قرینه همان وزن. حالا گراف را طوری پیمایش می کنیم که طول مسیر صفر شود.
مرتبه این الگوریتم هم 2n!/(n!)^2 است.
مثلا از مجموعه 1،2،3،4 دو مجموعه 1،4 و مجموعه 2،3 حاصل شود.
مرتبه این الگوریتم برابر با ترکیب n از 2n که برابر با 2n!/(n!)^2 است. حالا باید از چه الگوریتی استفاده کرد که مرتبه کمتری داشته باشه؟
یک روش اینه که از گرافی استفاده کنیم که از n+1 راس تشکیل شده که از هر راسی به راس دیگر دو یال وجود دارد که وزن یکی همان وزن عنصر اول مجموعه و وزن یال دیگر قرینه همان وزن. حالا گراف را طوری پیمایش می کنیم که طول مسیر صفر شود.
مرتبه این الگوریتم هم 2n!/(n!)^2 است.
مثلا از مجموعه 1،2،3،4 دو مجموعه 1،4 و مجموعه 2،3 حاصل شود.