با سلام و آرزوی موفقیت برای تمام دوستان
میخواستم بدونم برای بدست آوردن مرتبه زمانی این تابع بازگشتی
چجوری باید عمل کرد.
[tex]T(n)=T(n-2) 1/lg(n)[/tex]
(۰۷ مرداد ۱۳۹۲ ۰۳:۴۱ ب.ظ)عزیز دادخواه نوشته شده توسط: به نظرم طبق این قضیه باید خطی باشه چون رشد جمله اول سریع ار از جمله دوم تابعه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با تشکر از پاسختون ولی فکر میکنم قضیه اصلی (master) واسه توابعی به فرم زیر باشه
[tex]T(n)=aT(n/b) f(n)[/tex]
بشرط اینکه ۱<=a و ۱<b
تابع من فرم پارامترش خطی است درست ولی اینکه بشه از master استفاده کرد فکر نکنم
(۰۷ مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)عزیز دادخواه نوشته شده توسط: T(n)=aT(n-b )+f© =O(n/b)=O(n
البت به شرطی که رشد جمله اول سریع تر باشه باز به نظرم خطیه کاش کس دیگه ای هم نظر میداد[/align]
من با حلش رسیدم به این :
[tex]T(n)=T(0) \sum_{i=1}^{n/2}\frac{1}{log(2i)}[/tex]
(۰۷ مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)عزیز دادخواه نوشته شده توسط: T(n)=aT(n-b )+f© =O(n/b)=O(n
البت به شرطی که رشد جمله اول سریع تر باشه باز به نظرم خطیه کاش کس دیگه ای هم نظر میداد[/align]
من کتاب مقسمی رو دارم از این هم نمیشه استفاده کرد چون این واسه توابعی که بقول شما fc ثابت باشه مثال نقضش هم این تابعه
[tex]T(n)=T(n-1) 1/n[/tex]
طبق قضیه شما این باید بشه On ولی ساختار درختیش رو که تشکیل بدیم میشه Olgn برای حل این نباید دنبال قضیه خاصی بگردی که بهش بخوره باید ساختار درختیش رو بکشی که واسه این فکر کنم اگر n زوج باشه یا فرد باشه انتهای درخت فرق بکنه من مشکلم در اصل
پیدا کردن یه رابطه ریاضی برای مجموع زیر تو ساختار درختیشه
[tex]1/lg(n) 1/lg(n-2) 1/lg(n-4) ... 1[/tex]
که البته این واسه وقتی که n زوج باشه اگر چه زوج و فرد بودنش نباید تو جواب نهایی موثر باشه
(۰۷ مرداد ۱۳۹۲ ۰۴:۴۱ ب.ظ)amin222 نوشته شده توسط:(07 مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)عزیز دادخواه نوشته شده توسط: T(n)=aT(n-b )+f© =O(n/b)=O(n
البت به شرطی که رشد جمله اول سریع تر باشه باز به نظرم خطیه کاش کس دیگه ای هم نظر میداد[/align]
من کتاب مقسمی رو دارم از این هم نمیشه استفاده کرد چون این واسه توابعی که بقول شما fc ثابت باشه مثال نقضش هم این تابعه
[tex]T(n)=T(n-1) 1/n[/tex]
طبق قضیه شما این باید بشه On ولی ساختار درختیش رو که تشکیل بدیم میشه Olgn برای حل این نباید دنبال قضیه خاصی بگردی که بهش بخوره باید ساختار درختیش رو بکشی که واسه این فکر کنم اگر n زوج باشه یا فرد باشه انتهای درخت فرق بکنه من مشکلم در اصل
پیدا کردن یه رابطه ریاضی برای مجموع زیر تو ساختار درختیشه
[tex]1/lg(n) 1/lg(n-2) 1/lg(n-4) ... 1[/tex]
که البته این واسه وقتی که n زوج باشه اگر چه زوج و فرد بودنش نباید تو جواب نهایی موثر باشه
من با جایگزینی به اون سیگما رسیدم که با درختی که شما ساختی منطبق است و میشه با دستکاری حدود تابع رو بدست آورد
من به این نتیجه رسیدم که پیچیدگی میشه : [tex]O(n)>O(f(n)) >O(\frac{n}{logn})[/tex]
(۰۷ مرداد ۱۳۹۲ ۰۴:۲۳ ب.ظ)vojoudi نوشته شده توسط:(07 مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)عزیز دادخواه نوشته شده توسط: T(n)=aT(n-b )+f© =O(n/b)=O(n
البت به شرطی که رشد جمله اول سریع تر باشه باز به نظرم خطیه کاش کس دیگه ای هم نظر میداد[/align]
من با حلش رسیدم به این :
[tex]T(n)=T(0) \sum_{i=1}^{n/2}\frac{1}{log(2i)}[/tex]
آفرین تقربا درسته ولی این واسه n زوج اگر فرد باشه دیگه این نیست ولی در کل نباید تو جواب نهایی تاثیر بذاره حالا بعد این تازه مشکل اصلی من رو اشاره کردی جواب اون سیگمای لعنتی چی میشه که پاسخ نهایی رو بدیم؟؟؟؟؟؟؟؟
(۰۷ مرداد ۱۳۹۲ ۰۴:۵۰ ب.ظ)amin222 نوشته شده توسط:(07 مرداد ۱۳۹۲ ۰۴:۲۳ ب.ظ)vojoudi نوشته شده توسط:(07 مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)عزیز دادخواه نوشته شده توسط: T(n)=aT(n-b )+f© =O(n/b)=O(n
البت به شرطی که رشد جمله اول سریع تر باشه باز به نظرم خطیه کاش کس دیگه ای هم نظر میداد[/align]
من با حلش رسیدم به این :
[tex]T(n)=T(0) \sum_{i=1}^{n/2}\frac{1}{log(2i)}[/tex]
آفرین تقربا درسته ولی این واسه n زوج اگر فرد باشه دیگه این نیست ولی در کل نباید تو جواب نهایی تاثیر بذاره حالا بعد این تازه مشکل اصلی من رو اشاره کردی جواب اون سیگمای لعنتی چی میشه که پاسخ نهایی رو بدیم؟؟؟؟؟؟؟؟
یعنی به صورت قطعی نمیشه گفت؟؟؟جوابتون بصورت حدی بین ۲ مقدار درست بنظر میاد اگه ازدوستان کسی نظر دیگه داره لطف کنه بگه هنوز یکم دو به شکم راستی این یکی از تمرینهای کتاب کورمن هستش هر چی تو اینترنت گشتم جوابی واسش پیدا کنم بیفایده بود اگه کسی از دوستان منبعی برای حل مسائل کورمن داره بگه ممنون میشم البته اون pdf که بعضی از تمرینا رو پاسخ داده دارم
آره نمیتونم دقیق بگم فقط حدود میتونم بگم.
با توجه به سری های زیر
[tex]1/1 1/2 1/3 ... 1/n=logn[/tex]
[tex]1/1 1/2 1/3 ... 1/logn=loglogn[/tex]
میشه اینجوری گفت:
[tex]\sum_{i=2}^{i=n/2} 1/log(2i)<\sum_{i=1}^{i=n} 1/log(i)=O(loglogn)[/tex]
(۰۷ مرداد ۱۳۹۲ ۰۹:۴۰ ب.ظ)Farid_Feyzi نوشته شده توسط: با توجه به سری های زیر
[tex]1/1 1/2 1/3 ... 1/n=logn[/tex]
[tex]1/1 1/2 1/3 ... 1/logn=loglogn[/tex]
میشه اینجوری گفت:
[tex]\sum_{i=2}^{i=n/2} 1/log(2i)<\sum_{i=1}^{i=n} 1/log(i)=O(loglogn)[/tex]
من دیگه حرفی نمیزنم جواب آقا فرید حجته!! ممنون بابت وقتی که می ذارین
(۰۷ مرداد ۱۳۹۲ ۰۹:۴۰ ب.ظ)Farid_Feyzi نوشته شده توسط: با توجه به سری های زیر
[tex]1/1 1/2 1/3 ... 1/n=logn[/tex]
[tex]1/1 1/2 1/3 ... 1/logn=loglogn[/tex]
تا اینجا درسته ولی ! من بدست آوردم
[tex]\sum_{i=1}^{\frac{n}{2}}(\frac{1}{log(2i)})=\frac{1}{1 log(1)} \frac{1}{1 log(2)} \frac{1}{1 log(3)} ... \frac{1}{1 log(\frac{n}{2})}[/tex]
تا اینجا هم که درسته ؟ اوکی ؟ خوب من چه کار کردم ؟ اومدم به جای همه حملات این سری گذاشتم : [tex](\frac{1}{1 log(\frac{n}{2})})[/tex]
[tex]\sum_{i=1}^{\frac{n}{2}}(\frac{1}{log(2i)})= \underbrace{\frac{1}{1 log(1)} \frac{1}{1 log(2)} \frac{1}{1 log(3)} ... \frac{1}{1 log(\frac{n}{2})}}_\frac{n}{2}[/tex]
سری ما [tex]\frac{n}{2}[/tex] جمله داره پس اگر بخواهیم کمترین مقدار رو حساب کنیم (حد پایین) میشود :
[tex]\frac{n}{2}(\frac{1}{1 log(\frac{n}{2})})=\frac{n}{2 2log(\frac{n}{2})}\in \Omega (\frac{n}{log(n)})[/tex]
من ثابت کردم که کمتر از [tex] \Omega (\frac{n}{log(n)})[/tex] نمیتونه بشه. تا اینجا هم اوکی ؟
شما ثابت کردی که پیچیدگی میشود : [tex]O(loglog(n))[/tex] در صورتی که [tex]loglog(n) < \frac{n}{log(n)}[/tex]
و این نشون میده که جواب شما صحیح نیست.
(۰۷ مرداد ۱۳۹۲ ۱۱:۳۲ ب.ظ)vojoudi نوشته شده توسط: و این نشون میده که جواب شما صحیح نیست.معذرت میخوام، من بعد نوشتن اون دو تا سری، فک کردم مخرج [tex]1/i[/tex] هست و به لگاریتمه توجه نکردم!(قاطی کردم درواقع!) حق با شماس، جواب من کاملاً اشتباهه
مرسی آقای وجودی
اطلاعات بیشتر در مورد این رابطه بازگشتی رو اینجا ببینید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این سری هم یادتون باشه:
[tex]\sum_{i=2}^{n}\frac{1}{log(i)}\approx \frac{n}{logn}[/tex]
![[تصویر: 200030_Capture3.png]](https://img.manesht.ir/200030_Capture3.png)
(۰۷ مرداد ۱۳۹۲ ۱۱:۳۲ ب.ظ)vojoudi نوشته شده توسط:(07 مرداد ۱۳۹۲ ۰۹:۴۰ ب.ظ)Farid_Feyzi نوشته شده توسط: با توجه به سری های زیر
[tex]1/1 1/2 1/3 ... 1/n=logn[/tex]
[tex]1/1 1/2 1/3 ... 1/logn=loglogn[/tex]
تا اینجا درسته ولی ! من بدست آوردم
[tex]\sum_{i=1}^{\frac{n}{2}}(\frac{1}{log(2i)})=\frac{1}{1 log(1)} \frac{1}{1 log(2)} \frac{1}{1 log(3)} ... \frac{1}{1 log(\frac{n}{2})}[/tex]
تا اینجا هم که درسته ؟ اوکی ؟ خوب من چه کار کردم ؟ اومدم به جای همه حملات این سری گذاشتم : [tex](\frac{1}{1 log(\frac{n}{2})})[/tex]
[tex]\sum_{i=1}^{\frac{n}{2}}(\frac{1}{log(2i)})= \underbrace{\frac{1}{1 log(1)} \frac{1}{1 log(2)} \frac{1}{1 log(3)} ... \frac{1}{1 log(\frac{n}{2})}}_\frac{n}{2}[/tex]
سری ما [tex]\frac{n}{2}[/tex] جمله داره پس اگر بخواهیم کمترین مقدار رو حساب کنیم (حد پایین) میشود :
[tex]\frac{n}{2}(\frac{1}{1 log(\frac{n}{2})})=\frac{n}{2 2log(\frac{n}{2})}\in \Omega (\frac{n}{log(n)})[/tex]
من ثابت کردم که کمتر از [tex] \Omega (\frac{n}{log(n)})[/tex] نمیتونه بشه. تا اینجا هم اوکی ؟
شما ثابت کردی که پیچیدگی میشود : [tex]O(loglog(n))[/tex] در صورتی که [tex]loglog(n) < \frac{n}{log(n)}[/tex]
و این نشون میده که جواب شما صحیح نیست.
با رسم درخت جواب همانlog log n
چرا من این بخش رو هر چجقدر میخونم متوجه نمیشم ؟
شما چقدر راحت حل میکنید.
واقعا حسرت تو دلم موند این بخش رو یاد بگیرم.
استاد ما هم زیاد بلد نیست این بخشو. از رو کتاب هم ادم یاد نمیگیره.
واقعا باید چیکار کنه ادم
وای بچه ها لطفا به فارسی هم کمی در مورو مراحل کار توضیح بدین.منم متوجه نشدم چی به چیه