نمیدونم
سلام . کسی میتونه در رابطه با حل این سوال راهنماییم کنه؟
از کتاب clrs ویرایش سوم فصل ۳ صفحه ۵۷ سوال ۴-۳/۲

is the function [tex]\lceil\log n\rceil![/tex] polynomially bounded?
is the function [tex]\lceil\log\log n\rceil![/tex] polynomially bounded?

ببخشید انگلیسی تایپ کردم میخواستم خودتون صورت سوال رو ببینید.
[/quote]

(۰۹ مهر ۱۳۹۴ ۱۰:۱۶ ب.ظ)safura1371 نوشته شده توسط:  نمیدونم
سلام . کسی میتونه در رابطه با حل این سوال راهنماییم کنه؟
از کتاب clrs ویرایش سوم فصل ۳ صفحه ۵۷ سوال ۴-۳/۲

is the function [tex]\lceil\log n\rceil![/tex] polynomially bounded?
is the function [tex]\lceil\log\log n\rceil![/tex] polynomially bounded?

ببخشید انگلیسی تایپ کردم میخواستم خودتون صورت سوال رو ببینید.

[/quote]
====
از تقریب استرلینگ استفاده کن.
به این صورت که برای !n تقریب رو حساب کن.از طرفین لگاریتم بگیر بعدش میفهمی که مرتبه ش" چند جمله ای" از مرتبه nlogn هست.
برای دومی هم همین کارو بکن.

(۰۹ مهر ۱۳۹۴ ۱۱:۰۰ ب.ظ)neghab01 نوشته شده توسط:  

(09 مهر ۱۳۹۴ ۱۰:۱۶ ب.ظ)safura1371 نوشته شده توسط:  نمیدونم
سلام . کسی میتونه در رابطه با حل این سوال راهنماییم کنه؟
از کتاب clrs ویرایش سوم فصل ۳ صفحه ۵۷ سوال ۴-۳/۲

is the function [tex]\lceil\log n\rceil![/tex] polynomially bounded?
is the function [tex]\lceil\log\log n\rceil![/tex] polynomially bounded?

ببخشید انگلیسی تایپ کردم میخواستم خودتون صورت سوال رو ببینید.

====
از تقریب استرلینگ استفاده کن.
به این صورت که برای !n تقریب رو حساب کن.از طرفین لگاریتم بگیر بعدش میفهمی که مرتبه ش" چند جمله ای" از مرتبه nlogn هست.
برای دومی هم همین کارو بکن.
[/quote]

راه حل ساده تری ندارید ؟
انجامش دادم اما واسم گیج کننده بود و چیزی نفهمیدم

(۱۱ مهر ۱۳۹۴ ۱۲:۲۶ ب.ظ)معمری نوشته شده توسط:  

(09 مهر ۱۳۹۴ ۱۱:۰۰ ب.ظ)neghab01 نوشته شده توسط:  

(09 مهر ۱۳۹۴ ۱۰:۱۶ ب.ظ)safura1371 نوشته شده توسط:  نمیدونم
سلام . کسی میتونه در رابطه با حل این سوال راهنماییم کنه؟
از کتاب clrs ویرایش سوم فصل ۳ صفحه ۵۷ سوال ۴-۳/۲

is the function [tex]\lceil\log n\rceil![/tex] polynomially bounded?
is the function [tex]\lceil\log\log n\rceil![/tex] polynomially bounded?

ببخشید انگلیسی تایپ کردم میخواستم خودتون صورت سوال رو ببینید.

====
از تقریب استرلینگ استفاده کن.
به این صورت که برای !n تقریب رو حساب کن.از طرفین لگاریتم بگیر بعدش میفهمی که مرتبه ش" چند جمله ای" از مرتبه nlogn هست.
برای دومی هم همین کارو بکن.

راه حل ساده تری ندارید ؟
انجامش دادم اما واسم گیج کننده بود و چیزی نفهمیدم
[/quote]
======
!n رو بین تقریب استرلینگ بزار با دو تا مقدار برای C0 , C1 حد پایین که میشه خودِ همون تقریب.حد بالا هم میشه مثلا یه مقدار تابعی از عدد e به صورت نمایی.حالا شما دوس داشتی یه جور دیگه حد بالاش رو بزن.
حالا خیلی خودمونی که بگم انگار شما تابع !n رو گیر انداختید.(این میشه تقریب استرلینگ).بعد چون فاکتوریل شما log هم داره.از کل طرفین log بگیرید.
چون تقریب استرلینگ تابعش نمایی هست وقتی log بگیرید یه مقدار log با توان n دارید.حالا n رو ببر پشت لگاریتم..حل میشه و در واقع شما تابع !log n رو انگار گیر انداختی.

طراحی الگوریتم مدرسان هم نکته ی تقریب استرلینگ رو هم گفته اما نگفته کلا این تابع چیه.این تابع رو راحت میشه توی نت سرچ کرد و به دست آورد.

فصل اول کتاب الگوریتم پوران پژوهش کامل توضیح داده

(۱۳ مهر ۱۳۹۴ ۰۶:۲۷ ب.ظ)sahabi2015 نوشته شده توسط:  فصل اول کتاب الگوریتم پوران پژوهش کامل توضیح داده

====
راستش زیادم کامل نیست!
آخه نگفته توابع فاکتوریل چطور کنترل میشن.همینطوری یهویی گفته این با اون هم ارز هست!
اون تقریب استرلینگ توی گسسته هم هست.نمیخواد حتما ریاضیش رو بلد باشیم.فقط !n رو بهش محدود میکنیم.
مثه حالت های اولیه تعیین حد بالا و پایین