(۲۳ خرداد ۱۳۹۱ ۰۵:۳۲ ب.ظ)afagh1389 نوشته شده توسط:  خوب الگوریتم ها رو توی اینترنت پیدا کنید بعد پیچیدگیش رو حساب کنید . یا پیچیدگیش رو توی اینترنت پیدا کنید. بعد با هم مقایسه کنید.
مثلا توی این پی دی اف چندتا الگوریتم واسه کوله پشتی ۰و۱ نوشته و یکیش رو نوشته پیچیدگی O(nw داره.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


برای کوله پشتی کسری هم طبق متن زیر O(nlogn هست.

if the objects in the knapsack are already being sorted then it requires only O(n) times to arrange the objects...so total time require by the knapsack problem is
T(n)=(nlogn) because sorting the objects require O(nlogn) time...Remaining is to run for n objects O(n). Hence, bounded by O(nlogn)


با این اوصاف اگر W=n بشه . برای کوله پشتی صفر و یک مرتبه O(n^2 میشه.

خودتون هم میتونید توی گوگل سرچ کنید :
مرتبه زمانی : time complexity
کوله پشتی کسری : fractional knapsack
کوله پشتی صفرویک :knapsack 0/1