(۲۵ شهریور ۱۳۹۲ ۱۲:۱۱ ب.ظ)nsabery نوشته شده توسط:  می شه بیتر توضیح بدین که چرا مرتبه این برنامه Log*n است؟

الگوریتم شما انقدر از n لگاریتم می‌گیره تا بالاخره به عددی کوچک‌تر یا مساوی ۲ برسه. بنابراین تعداد دفعات اجرای حلقه‌ی while شما (و در نتیجه زمان اجرای برنامه) می‌شه تعداد دفعاتی که پشت سر هم باید از یک عدد لگاریتم گرفت تا نتیجه بشه عددی کوچک‌تر یا مساوی ۲/

طبق تعریف به این تعداد اصطلاحاً میگن لگاریتم مکرر یا همون لُگ استار ($log^{*}(n)$). بنابراین زمان اجرای شما همون لُگ استار n میشه :-)

سلام به نظر می رسه باید [ log n)/2) ] بشه .

این که از log n باید مرتبه زمانی مون کمتر بشه ، که واضحه .
اما با دو تا مثال n=8, n= 16 که برای هر کدوم حلقه ۲و ۱ بار تکرار می شه من حدس زدم .

سلام.

تعداد اجرای حلقه‌ی برنامه شما دقیقاً از روی تعریف $log^{*}(n)$ گرفته شده ("لُگ استار" یا "لگاریتم مکرر")، یعنی تعداد دفعاتی که نیازه پشت سر هم از یک عدد لگاریتم بگیریم تا به عدد ۱ برسیم. بنابراین زمان اجرای برنامه‌تون از مرتبه‌ی $\Theta(log^{*}(n))$ هستش :-)


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

می شه بیتر توضیح بدین که چرا مرتبه این برنامه Log*n است؟