تالار گفتمان مانشت
پیچیدگی این تابع چی میشه - نسخه‌ی قابل چاپ

پیچیدگی این تابع چی میشه - Only_God - 05 آذر ۱۳۹۰ ۰۶:۱۰ ب.ظ

سلام
پیچیدگی تابع زیر چی میشه ؟
t(n)=t(2n/3)+logn ^2

RE: پیچیدگی این تابع چی میشه - homa - 05 آذر ۱۳۹۰ ۰۷:۲۶ ب.ظ

(۰۵ آذر ۱۳۹۰ ۰۶:۱۰ ب.ظ)Only_God نوشته شده توسط:  سلام
پیچیدگی تابع زیر چی میشه ؟
t(n)=t(2n/3)+logn ^2

پیچیدگی تابع برابر [tex] {log_{}}^{n^{2}}[/tex]

RE: پیچیدگی این تابع چی میشه - sasanlive - 05 آذر ۱۳۹۰ ۰۸:۵۰ ب.ظ

(۰۵ آذر ۱۳۹۰ ۰۷:۳۶ ب.ظ)Only_God نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۷:۲۶ ب.ظ)homa نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۶:۱۰ ب.ظ)Only_God نوشته شده توسط:  سلام
پیچیدگی تابع زیر چی میشه ؟
t(n)=t(2n/3)+logn ^2

پیچیدگی تابع برابر [tex] {log_{}}^{n^{2}}[/tex]
Yaeni f(n)>n ^log a bar paie 2/3 ast
?

b تو این رابطه بازگشتی ۳/۲ هست .


[tex]T(\frac{2n}{3})=T(\frac{n}{\frac{3}{2}})[/tex]

منظورت کدومه.

[tex]logn^{2}=2logn[/tex]

[tex](logn)^{2}=log^{2}n[/tex]

RE: پیچیدگی این تابع چی میشه - sniazvand - 16 آذر ۱۳۹۰ ۰۲:۵۳ ب.ظ

(۰۵ آذر ۱۳۹۰ ۰۸:۵۰ ب.ظ)sasanlive نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۷:۳۶ ب.ظ)Only_God نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۷:۲۶ ب.ظ)homa نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۶:۱۰ ب.ظ)Only_God نوشته شده توسط:  سلام
پیچیدگی تابع زیر چی میشه ؟
t(n)=t(2n/3)+logn ^2

پیچیدگی تابع برابر [tex] {log_{}}^{n^{2}}[/tex]
Yaeni f(n)>n ^log a bar paie 2/3 ast
?

b تو این رابطه بازگشتی ۳/۲ هست .


[tex]T(\frac{2n}{3})=T(\frac{n}{\frac{3}{2}})[/tex]

منظورت کدومه.

[tex]logn^{2}=2logn[/tex]

[tex](logn)^{2}=log^{2}n[/tex]

به نظر من:
طبق قضیه اساسی تعمیم در حل مسائل بازگشتی در این جا:
a=1
b=3/2
log a در مبنای b میشه ۰ بناراین f که همان logn به توان دو است متعلق به تتای این log ضرب در log n به توان دو است در نتیجه کل تابع متعلق به تتای log n به توان ۳ است.[/align]

RE: پیچیدگی این تابع چی میشه - sasanlive - 16 آذر ۱۳۹۰ ۰۳:۰۴ ب.ظ

(۱۶ آذر ۱۳۹۰ ۰۲:۵۳ ب.ظ)sniazvand نوشته شده توسط:  به نظر من:
طبق قضیه اساسی تعمیم در حل مسائل بازگشتی در این جا:
a=1
b=3/2
log a در مبنای b میشه ۰ بناراین f که همان logn به توان دو است متعلق به تتای این log ضرب در log n به توان دو است در نتیجه کل تابع متعلق به تتای log n به توان ۳ است.[/align]

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

RE: پیچیدگی این تابع چی میشه - پشتکار - ۱۶ آذر ۱۳۹۰ ۰۳:۳۳ ب.ظ

(۰۵ آذر ۱۳۹۰ ۰۷:۳۶ ب.ظ)Only_God نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۷:۲۶ ب.ظ)homa نوشته شده توسط:  
(05 آذر ۱۳۹۰ ۰۶:۱۰ ب.ظ)Only_God نوشته شده توسط:  سلام
پیچیدگی تابع زیر چی میشه ؟
t(n)=t(2n/3)+logn ^2

پیچیدگی تابع برابر [tex] {log_{}}^{n^{2}}[/tex]
Yaeni f(n)>n ^log a bar paie 2/3 ast
?

بر پایه ۳/۲

پیچیدگی این تابع چی میشه - atefeh.gh - 04 دى ۱۳۹۰ ۰۳:۳۱ ب.ظ

سلام این سوال طبق یه قضیه به نام master حل میشه .logn^2