پيچيدگي زماني

[yasercomeng]

يه سري سوال در مورد پيچيدگي زماني هم داشتم كه خودم نتونستم حل كنم يا اگرم حل كردم نمي دونم جوابش درسته يا نه ممنون مي شم كمكم كنيد:
١- T(n)=sqrt(n)T(sqrt(n))+n جواب خودم واسه اين مسئله O(n) هست كه با روش جايگذاري بدست آوردم.
٢- T(n)=2T(n/2)+(n/lgn) جواب خودم واسه اين يكي O(nloglogn) هست البته يادم نمياد چه جوري حلش كردم.

[Salar Ashgi]

سلام ، روش حل هر دو مساله رو توضیح میدم :

1) این مورد که ساده است و روش حل آنرا در عکس گذاشته ام :

http://salarcpp.persiangig.com/Solve%201.JPG

***) در ضمن روش جاگذاری همیشه بهترین نیست و در بعضی مسائل ممکن است خیلی

دیر به جواب برسد (مثل مورد دوم )

2- اما حل مساله دوم :

http://salarcpp.persiangig.com/Solve%202.JPG

***)ولی خودمونیم فکر نمی کنم حل این مسائل رو با این روش ها ، به این شکل و به این

زودی ، جایی پیدا میکردی ، در هر حال در این سایت جمع شده ایم برای حل مشکلات هم !!!

موفق و پیروز باشید !!!

[yasercomeng]

آقا واقعا دمت گرم. بابا تو ديگه كي هستي:تشویق::تشویق::تشویق::تش� �یق::تشویق:
يه سوال در مورد سوال دوم و شيوه ي حل اون داشتم. نمي خوام شيوه ي حل رو بدونم فقط مي خوام بدونم اين متد adra-bazzi چيه و بر چه اصولي استواره و يه توضيحه مختصر در موردش. فقط همين:گیج:
بازم ازت تشكر مي كنم

[yasercomeng]

دو تا سواله جديد هم داشتم
1- اين پيچيدگي زماني رو چه طور بايد حساب كرد:
W(n)=W(7n/10)+w(n/5)+11n/5 كه جوابش هست O(n)
من سعي كردم با اين روش Akra-bazzi حلش كنم اما نتونستم مقدار مناسبي براي p پيدا كنم.
اما خودمونيما اين متد Akra-bazzi هم عجب روش ايه ها!!!

[Salar Ashgi]

دو تا سواله جديد هم داشتم
1- اين پيچيدگي زماني رو چه طور بايد حساب كرد:
W(n)=W(7n/10)+w(n/5)+11n/5 كه جوابش هست O(n)
من سعي كردم با اين روش Akra-bazzi حلش كنم اما نتونستم مقدار مناسبي براي p پيدا كنم.
اما خودمونيما اين متد Akra-bazzi هم عجب روش ايه ها!!!

اینجور مسائل که معمولا طرف دوم دو یا سه و ... تابع بازگشتی هست ، بهتره بروش

Akra-bazzi حل بشه ، چون با جایگذاری خیلی دیر به جواب میرسه ! در این طور مسائل

معمولا p بصورت دقیق بدست نمیاد و باید یه تقریبی از اون رو که به p خیلی نزدیکه رو در نظر

بگیرید !

در مورد توضیح روش Akra-bazzi هم ، اگه یه کم سرچ کنید ، مطالب جالبی بدست میارید ،

بحثش کمی مفصله و بطور مختصر میشه گفت مسائل زیادی از حل روابط بازگشتی ، با این

روش و یک انتگرال حل میشه (بعضی جاها واقعا معرکه است ، خصوصا وقتی که روشهای

دیگه نمیتونه مساله رو حل کنه )

موفق و پیروز باشید !!!

[yasercomeng]

دوستان عزيز اخه اين چه جاي دعواست. من باز هم از دوست خوبم آقا سالار تشكر ميكنم و ميگم اصلا ايشون از خود راضي و مغرور نيستند چون كمه كمه كمش به مسئله من فكر كردند. آقا دمت گرم واقعا هم فكرشو نميكردم به اين زودي جوابمو بدي.:تشویق::تشویق::تشویق::تشو یق:
اما اگه اشكال نداره يكي دو تا سوال ديگه هم داشتم كه اگه فقط لطف كنيد و طريقه راه حل رو بهم بگين ( مثلا استفاده از قضيه master يا Akra-bazzi) من واقعا ممنون ميشم و شما هم حق رفاقت و زكات علمتون رو پرداختين:لبخندساده::لبخندس� �ده:
اگه ممكنه فقط راه حل رو بگين:

2- B(n)=nB(n-1)^2 , n>=1, B(0)=1

3- A(n)+nA(n-1)=n! , n>=1, A(0)=1

4- A(n)^2 -2A(n-1)=0, n>=1, A(0)=2
بازم پيشاپيش از دوستان تشكر ميكنم و خواهشم هم اينه كه يه بحث علمي رو به يه بحث سليقه اي مربوط نكنين (mr golbafan):لبخند: