صفحه‌ها: ۱ ۲
آقا یه سوال رشد کدوم تابع سریع تره با دلیل. !logn یا !(logn)?
(۰۱ بهمن ۱۳۹۱ ۰۷:۲۹ ب.ظ)mahdiii نوشته شده توسط: آقا یه سوال رشد کدوم تابع سریع تره با دلیل. !logn یا !(logn)?!(logn) بیشتره!نجومی هم بیشتره!
lgn! = nlgn
مثال:n=1024
logn!=10240
۳۶۲۸۸۰۰=!(logn)
(۱۸ دى ۱۳۹۱ ۱۱:۵۱ ب.ظ)Amir V نوشته شده توسط: قضیه مستر میگه اگه [tex]f(n)=nLog^k n[/tex] ، اون وقت کل مسئله میشه از nLog^(K+1) n
وقتی که f برابر تتا باشه این قضیه درست. اما اینجا f=log(ni)=O(nlogn) هستش .
قضیه ی master اینه :
![[تصویر: 156722_1_1379086327.gif]](https://img.manesht.ir/156722_1_1379086327.gif)
سوال شما اینه :
[tex]T(n)= 2T(n/2) lgn![/tex]
ببین سمت چپ میشه n به توان لگاریتم ۲ در مبنای ۲ که جواب میشه teta_n
سمت راست هم میشه : teta_nLgn
----
در اینجا حالت خاص رو داریم :
اینجا چون f(n در [tex]lg^k(n)[/tex] ضرب شده ابتدا [tex]lg^k(n)[/tex] رو حذف کن میشه:
سمت چپ میشه o_n
سمت راست هم میشه o_n
چون مساوی شدن پس سمت راست یعنی f(n) رو lgn ضرب می کنی میشه nlgn
---
حالا اون چیزی که حذف کرده بودیم یعنی [tex]lg^k(n)[/tex] رو دوباره درش ضرب کن میشه :
[tex]nlg^{k 1}(n)[/tex]
[tex]nlg^{2}(n)[/tex]
---------
در حالت کلی یک حالت داریم به اسم حالت تعمیم:
[tex]t(n)=aT(\frac{n}{b}) f(n)[/tex]
اگر در روش قضیه ی اصلی داشته باشیم :
[tex]f(n)\varepsilon \theta(n^{log_{b}^{a}})lg^k{n}[/tex]
و k>=0 باشد داریم:
[tex]T(n)\varepsilon \theta(n^{log_{b}^{a}})lg^{k 1}{n}[/tex]
----------------------
مثال :
[tex]T(n)=2t(n/2) nlgn=\theta(nlg^2n)[/tex]
مثال بعدی:
[tex]T(n)=4t(n/2) n^2lgn=\theta(n^2lg^2n)[/tex]
نکته ای که جا گذاشتم هم اینه :
ثابت میشه که lg(n!)=nlgn
---
من جزوه ی طورانی رو که واسه پارسالش هست دارم همین سوال رو حل کرده و جوابش هم همون nlog^2n (به توان ۲) و نمیدونم چرا تو کتابش نوشته nlogn
منم طورانی رو دارم ولی نه واسه پارسال
عکس بگیرید آپلود کنید بدید ببینیم کجا اشکال داره
احتمالا اشتباه تایپی بوده