ببینید اون کاری که من کردم برای تمام مسائل جواب میده. شما گفتید
n!<n^n
log(n!)<logn^n
ولی اگه بخوایم با مرتبه زمانی بگین اونم O هردو مساوین.
n!=1*2*..n<n^n
n!=O(n^n)
n!=1*2*..n>=n/2*n/2*...*n/2>=(n/2)^(n/2)
پس !n مساوی با امگای n/2^n/2 هست.
پس !n میان این دو قرار می گیره که هر دو n^n هست.
برای log(n!) هم قضیه مشابه هست.
log(n!)<log(n^n)=nlogn
log(n!)=O(nlogn)
خوب این کجاش مشکل داره؟ n!=O(n^n) و log(n!)=O(nlogn)
(۰۱ بهمن ۱۳۹۱ ۰۱:۳۵ ق.ظ)ana_12345 نوشته شده توسط: (30 دى ۱۳۹۱ ۱۱:۴۹ ب.ظ)mahdiii نوشته شده توسط: به نظر من n^logn کوچکتر از !n هست. چرا؟ چون اگه از هر دو طرف log بگیری چی میشه؟
میشه
log(n!)=nlogn>=(logn)^2
و ما میدونیم که log به هر توانی بازم کوچکتر از چند جمله ایهاست مثل n و مشتقاتش مانند n^0.5 , ...
حتی شما اصلا اینو درنظر بگیر n!>=2^n که هست
میشه log(2^n)>=(logn)^2
چونlog(2^n)=n>=(logn)^2
پس حتی ۲ به توان n هم بزرگتر از n^logn است.[/align]
سلام
ممنونم از پاسختون .
حرفتون رو متوجه می شم اما اینجوری اگه قبول داشته باشین که n!<n^n ،دیگه هستش بعد اگه از راه شما بریم و از دو طرف log بگیریم در هر دو طرف به nlogn می رسیم و اینجوری بر طبق تحلیل شما باید بگیم n!, n^n با هم هم مرتبن در صورتی که اینطور نیست .درست می گم ؟
(۳۰ دى ۱۳۹۱ ۰۹:۴۴ ب.ظ)egm1176 نوشته شده توسط: میشه تست رو بذارید؟
راستش تستش ۳ تا گزینه طولانی دیگه داره که ۲ تاش درست و یکی غلط هست . اما چشم در اولین فرصت میام می نویسمش.
این گزینه جزو درستا بوده O(n^n = O(ni) حالا سوال اصلی این بود که وقتی ni کوچکتر از n^n هست این رابطه با o چرا درست هستش .
بعد چون من سوالم رو با مثال n^logn زدم ،به نظر دوستان مثال من غلط . حالا سوالم دو تا شد یکی همین قضیه n^logn ویکی هم همون سوال اصلی.
من فاکتوریل رو نمی تونم اینجا بنویسم مجبورم i رو بزارم بجاش . شرمنده .
"بعد اگه از راه شما بریم و از دو طرف log بگیریم
در هر دو طرف به nlogn می رسیم و اینجوری بر طبق تحلیل شما باید بگیم n!, n^n با هم هم مرتبن در صورتی که اینطور نیست .درست می گم ؟"
در هر دو طرف به nlogn می رسیم؟!! شما گفتید از هر دو طرف log می گیریم. بعد هر دو طرف میشن nlogn ؟ در صورتی log(n!) میشه nlogn که شما n!=n^n بگیرین. شما یه بار خودتون از این رابطه استفاده کردین و یه بار دیگه گفتین آیا این دو برابر هستن!!