با سلام .کسی میتونه بیزحمت رابطه بالا رو اثبات کنه. با تشکر...
وقتی n خیلی بزرگ باشه:
n!~n^n
پس به جای !n قرار میدیم n^n چون log گرفتیم توان میاد پشت log و تمام!
(۰۲ آذر ۱۳۸۹ ۰۸:۲۳ ق.ظ)afagh1389 نوشته شده توسط: وقتی n خیلی بزرگ باشه:
n!~n^n
پس به جای !n قرار میدیم n^n چون log گرفتیم توان میاد پشت log و تمام!
نـــــــــــــــــــــــــــــــــــه
n^n رشدش خیلی بیشتر از !n هست
یعنی در واقع:
کد:
n! = o(n^n)اون رابطه ای که ایشون پرسیدن، چند روش اثبات داره که توی جزوه‌ی تایپ شده‌ی سیدجوادی که توی نت هست، نوشته، مثلاً یکیش اینه که من گذاشتم
[attachment=107]
به هر حال به ما اینجوری گفتن.
این مشخصه که n^n خیلی بیشتر از n! هست ولی وقتی log میگیریم تفاوت چندانی ندارن!
(۰۲ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)Soheil نوشته شده توسط: بچه‌ها این مسئله تو کتاب مقسمی هم حل شده و فکر کنم به جواب آفاق خانم رسیده بود، اگه کسی داره ببینه درستش چیه، بحث رو مبهم نذارید.من ۲تا جواب واسه اثباتش دیدم یکی که قابل لمسه همینی که ۵۴m4n3h گذاشت
یکی هم با تقریب استرلینگ و کمک گرفتن از اینکه n!=o n^n
و n!=w 2^n
که جواب بالایی راحتتره
اگه توی اثبات کتاب مقسمی هم، صرفاً لگاریتم گرفته شدن از طرفین رو دلیل هم مرتبه شدنشون دونسته باشه، قطعاً غلطه!
مرتبه‌ی n^n از n بیشتره اما نمیشه گفت مرتبه‌ی log n^n و log n یکی هست! یعنی کلاً نمیشه گفت در حالت کلی لگاریتم یه چیزی با لگاریتم یه چیز دیگه لزوماً هم مرتبه هستند! و نیاز به اثبات داره ...
ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
(۰۲ آذر ۱۳۸۹ ۱۰:۱۸ ب.ظ)afagh1389 نوشته شده توسط: ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!افاق نمیشه از تعریف تتا استفاده کرد حد اقل برای من قابل لمسه که درسته
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
شما عبارت زیر رو قبول دارید؟
[attachment=113]
حالا یکی لا اقل بگه مقسمی چی نوشته تو کتابش. کسی اگه کتاب مقسمی رو داره این قسمت رو بذاره ببینیم اون چطوری اثبات کرده.
(۰۲ آذر ۱۳۸۹ ۱۰:۱۸ ب.ظ)afagh1389 نوشته شده توسط: ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!تو CLRS فصل سوم گفته که n!=o n^n (اوی کوچک)...
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
خوب کتاب مقسمی اشتباه زیاد داره!
اگه با دیدن این اثبات هم قانع نشدین بگید یه جور دیگه اثباتشو بذارم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
آفاق جان باید هوپیتال استفاده کنید.