اشتباه شما این است که هیچ وقت n^ log n بزرگتر از n فاتوریل نیست!!

(۳۰ دى ۱۳۹۱ ۰۲:۰۴ ب.ظ)majid_22 نوشته شده توسط:  اشتباه شما این است که هیچ وقت n^ log n بزرگتر از n فاتوریل نیست!!

سلام
ولی هست .
مرجع ارشد سپاهان .
و همینطور n رو log n بار در خودش ضرب کنید " توجه هم کنید که n عددی بزرگ هست " پس n^log n بزرگتر از !n هستش .

---

(۳۰ دى ۱۳۹۱ ۰۲:۵۴ ب.ظ)blackhalo1989 نوشته شده توسط:  اون i منظور فاکتوریله پس! خوب با علامت تعجب مینوشتید.

تقریبا
حالا که !n هست جواب چی می شه ؟؟؟

اومدم درستش کنم نشد .
ببخش دیگه

اون i منظور فاکتوریله پس! خوب با علامت تعجب مینوشتید.

نمیدونم!

میشه تست رو بذارید؟

به نظر من 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]

(۳۰ دى ۱۳۹۱ ۱۱:۴۹ ب.ظ)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 رو بزارم بجاش . شرمنده .

با mahdiii موافقم.

ببینید اون کاری که من کردم برای تمام مسائل جواب میده. شما گفتید
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 بگیرین. شما یه بار خودتون از این رابطه استفاده کردین و یه بار دیگه گفتین آیا این دو برابر هستن!!

سلام
نههههههههههههههههه قاطی دارم می کنم

من اینو گفتم


من می خواستم از راه شما "یعنی log گرفتن از طرفین " برای اثبات استفاده کنم
مگه هدف مقایسه ni و n^logn نبود؟
مگه نگفتین از دو طرف log می گیریم ؟ بعد از این به log ni و log(n^logn رسیدیم و بعد گفتین logni رو هم می دونیم تقریبا nlogn و log(n^logn) هم که می شه logn*logn یعنی logn^2
و بعد چون nlogn از" logn به توان ۲ "بزرکتر گفتین پس ni از n^logn بزرگتر هستش.

خوب من همینو برای مقایسه ni و n^n به کار می برم " فرض کنیم من و شما نمی دونیم ni<n^n اوکی؟؟
حالا از هر دو شون log می گیریم . log(ni) , و log(n^n) .بازم مثل بالا logni رو می دونیم تقریبا nlogn. در باره log(n^n) هم برابر می شه با nlog n
حالا به چی رسیدیم ؟؟؟ هر دو طرف شدن nlogn در صورتی که ما می دونیم ni کوچکتر از n^n

پس چرا این دفعه با log گرفتن از طرفین درست نشد ؟