کسی نظری راجب این سوال نداره؟؟؟؟؟

(۲۱ تیر ۱۳۹۴ ۰۱:۳۴ ب.ظ)LEA3C نوشته شده توسط:  سلام
به نظرم این سوال رو تو پاسخ نامه اشتباه حل کردن چون هزینه هر عمل در هر صورت logn هست ولی تو حلش (۱)O رو تحلیل کرده که به نظرم اشتباه هست
کسی میتونه توضیحی بده
ممنون

سلام
در مورد سوالتون یکی از منابع خوب همون کتاب داده ساختارها و مبانی الگوریتم های دکتر قدسی هستش بخش تحلیل سرشکنی.
این سوال از مثال دوم ایشون یعنی افزایش شمارنده دودویی گرفته شده. در شمارنده دودویی با هر بار اضافه کردن ۱ بطور میانگین lgn تا از اعداد تغییر می کنند که در این سوال همون for از صفر تا lgn رو نشون میده .
اما اگه بخایم با تابع پتانسیل عمل تشابه رو بررسی کنیم می بینید که برای شمارنده دودویی تابع پتانسیل تعداد یک های آرایه در نظر گرفته شده و در این سوال تعداد اعداد غیر صفر.
در هنگام تحلیل به روش تابع پتانسبل دقت کنید که در هر بار فراخوانی در این سوال L (یا همان lgn) درایه غیر صفر صفر می شوند و حداکثر یک درایه صفر غیرصفر می شود. و البته در شمارنده هم بهمین ترتیب است.
در صورتی که مشکلی باقی موند بفرمائید در صورتی که اطلاعاتی داشتم راهنمایی خواهم کرد.
آرزوی موفقیت.

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