۰
subtitle
ارسال: #۱
چرا ( log n!=teta( n Log n است؟
با سلام .کسی میتونه بیزحمت رابطه بالا رو اثبات کنه. با تشکر...
۰
ارسال: #۲
چرا logn!=teta(nLogn)؟
وقتی n خیلی بزرگ باشه:
n!~n^n
پس به جای !n قرار میدیم n^n چون log گرفتیم توان میاد پشت log و تمام!
n!~n^n
پس به جای !n قرار میدیم n^n چون log گرفتیم توان میاد پشت log و تمام!
ارسال: #۳
RE: چرا logn!=teta(nLogn)؟
(۰۲ آذر ۱۳۸۹ ۰۸:۲۳ ق.ظ)afagh1389 نوشته شده توسط: وقتی n خیلی بزرگ باشه:
n!~n^n
پس به جای !n قرار میدیم n^n چون log گرفتیم توان میاد پشت log و تمام!
نـــــــــــــــــــــــــــــــــــه
n^n رشدش خیلی بیشتر از !n هست
یعنی در واقع:
کد:
n! = o(n^n)اون رابطه ای که ایشون پرسیدن، چند روش اثبات داره که توی جزوه‌ی تایپ شده‌ی سیدجوادی که توی نت هست، نوشته، مثلاً یکیش اینه که من گذاشتم
۰
ارسال: #۴
چرا logn!=teta(nLogn)؟
به هر حال به ما اینجوری گفتن.
این مشخصه که n^n خیلی بیشتر از n! هست ولی وقتی log میگیریم تفاوت چندانی ندارن!
این مشخصه که n^n خیلی بیشتر از n! هست ولی وقتی log میگیریم تفاوت چندانی ندارن!
۰
ارسال: #۵
RE: چرا logn!=teta(nLogn)؟
اگه توی اثبات کتاب مقسمی هم، صرفاً لگاریتم گرفته شدن از طرفین رو دلیل هم مرتبه شدنشون دونسته باشه، قطعاً غلطه!
مرتبه‌ی n^n از n بیشتره اما نمیشه گفت مرتبه‌ی log n^n و log n یکی هست! یعنی کلاً نمیشه گفت در حالت کلی لگاریتم یه چیزی با لگاریتم یه چیز دیگه لزوماً هم مرتبه هستند! و نیاز به اثبات داره ...
مرتبه‌ی n^n از n بیشتره اما نمیشه گفت مرتبه‌ی log n^n و log n یکی هست! یعنی کلاً نمیشه گفت در حالت کلی لگاریتم یه چیزی با لگاریتم یه چیز دیگه لزوماً هم مرتبه هستند! و نیاز به اثبات داره ...
۰
ارسال: #۶
چرا logn!=teta(nLogn)؟
ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
ارسال: #۷
RE: چرا logn!=teta(nLogn)؟
(۰۲ آذر ۱۳۸۹ ۱۰:۱۸ ب.ظ)afagh1389 نوشته شده توسط: ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!افاق نمیشه از تعریف تتا استفاده کرد حد اقل برای من قابل لمسه که درسته
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
ارسال: #۸
RE: چرا logn!=teta(nLogn)؟
(۰۲ آذر ۱۳۸۹ ۱۰:۱۸ ب.ظ)afagh1389 نوشته شده توسط: ببینید ۴^۴ =۲۵۶ , ۴!=۲۴ اما وقتی log میگیریم یکی میشه ۸ و دیگری میشه ۴/۵ یعنی اختلافشون خیلی کم میشه ۲۱۲ (۴-۲۵۶)کجا و ۳/۵ (۴/۵-۸) کجا!!!تو CLRS فصل سوم گفته که n!=o n^n (اوی کوچک)...
در ضمن در کتاب مقسمی n!=O(n^n نوشته big o نه Small o
من باز هم از استادمون میپرسم!
به هر حال برای یک قسمت از اثبات میشه از روش من استفاده کرد دیگه اینکه بگیم n!=O(n^n) و بعد از دو طرف log بگیریم که دیگه مشکلی نداره؟؟؟؟
بابت روشتون هم ممنون
۰
۰
ارسال: #۱۰
چرا logn!=teta(nLogn)؟
حالا یکی لا اقل بگه مقسمی چی نوشته تو کتابش. کسی اگه کتاب مقسمی رو داره این قسمت رو بذاره ببینیم اون چطوری اثبات کرده.
۰
۰
۰
