من توابع رادیکالی رو هرجا که دیدم با تغییر متغییر حل کرده
من n/log n رو نمیفهمم چی شد،یعنی کلاً باهاش مشکل دارم،تو لینکی هم که خانوم Aurora گذاشتن هم نفهمیدم چی شده!! میشه راهنماییم کنید یا منبعی رو بگید که از روی اون این مطلب رو بفهمم
این شکل رو از حل تمرین clrs گذاشتم.
[attachment=6279]
تو این شکل مجموع هر سطر رو حساب می کنیم. که اگر دقت کنی مجموع هر سطر یک رابطه با خود اون سطر داره: n/logn-i
ارتفاع رو بدست بیاریم:برای ارتفاع باید چند تا جمله از بازگشتی رو حل کنیم. برای این سوال
T(n)=2T(n/2)+n/log n
(۴t(n/4) + n/log(n/2) + n/log(n=
همین طور که ادامه بدیم متوجه خواهیم شد که اون قسمتی که رنگی کردم رابطه اش این هست: n/2^i
n/2^i=1
از هر دو طرف لگاریتم می گیریم: (log 1= log n/(2^i
i=log n
خوب حالا هم ارتفاع داریم و هم رابطه سطر.
[attachment=6277]
برای محاسبه این مجموع می تونیم یکم حلش کنیم.
[attachment=6278]
این یک سری هارمونیک از یک تا لگاریتم n هست. مجموع سری هارمونیک از یک تا n میشه log n.
پس مجموع این هارمونیک از یک تا log n میشه log log n. پس مرتبه میشه n log log n.
تو حل تمرین مجموع رو از ۰ تا log n-1 گرفته. من از یک تا log n گرفتم. نمی دونم چطوری این کارو کرده.
این سوال رو می تونید با جایگذاری با تکرار هم حل کنید.
سلام به همه دوستان!
مرتبه زمانی این تابع چند هستش؟!با توجه به اینکه اگر -۱ نبود طبق قالب مستر بود!اما این طبق مستر نیست!
پیشاپیش مرسی
سلام
ضریب ثابت در معادله اثر نداره. پس -۱ رو حذف کن و مستر بزن.
اگه استدلالیش هم بخوای یه عددی مثه ۱۰۲۴ در نظر بگیر خوب با (m/2-1) میشه ۵۱۱ بعد ۲۵۵ و ....۱ که تاثیری به اونصورت در معادله جوابمون نداره یعنی اگه -۱ هم برداریم میشه ۵۱۲ بعد ۲۵۶ و...۱ که بازم ۱۰ مرحله اجراش طول میکشه یا به صورت دیگه می تونیم بگین اینجا تقسیم به تفریق غلبه میکنه.
آره حق با شماست!ممنون!اما این ضریب ثابت هر عددی باشه مشکل نداره یا فقط اعداد کوچیک این مدلیه؟!
نه مشکلی نداره اگه مثلاً (n/2-1000) هم باشه ما اگه n=1000000 بگیریم باز هم این ۱۰۰۰ تاثیری در معادله نداره چون همواره ما می تونیم یه عدد بزرگی براش پیدا کنیم که این ۱۰۰۰ رو بپیچونیم پس مقدارشم مهم نیس.
سلام
من که میگم مرتبه زمانی این تابع m^2 هستش
سلام. بنظر من از مرتبه m^{2}lgm میشه. از روی درختش راحت بدست میاد.
(۱۹ مهر ۱۳۹۱ ۰۹:۱۴ ب.ظ)Jooybari نوشته شده توسط: سلام. بنظر من از مرتبه m^{2}lgm میشه. از روی درختش راحت بدست میاد.
درسته!
دوستان من هم یه ایده دارم برای حل سوال میشه بگید درسته نظرم یا نه؟
اگر [tex]m-2 = n[/tex] بگیریم:
میتونیم بنویسیم :
[tex]4T(\frac{n}{2}) (n-2)^{2}[/tex]
که با قضیه اصلی حل میشه و جواب میشه :
[tex]\theta (m^{2}.\lg m)[/tex]
(۱۹ مهر ۱۳۹۱ ۱۰:۴۸ ب.ظ)nomad:D نوشته شده توسط: دوستان من هم یه ایده دارم برای حل سوال میشه بگید درسته نظرم یا نه؟
اگر [tex]m-2 = n[/tex] بگیریم:
میتونیم بنویسیم :
[tex]4T(\frac{n}{2}) (n-2)^{2}[/tex]
که با قضیه اصلی حل میشه و جواب میشه :
[tex]\theta (m^{2}.\lg m)[/tex]
آره تغییر متغیرش به نظرم درسته و البته جالب![/code][/quote]
سلام دوستان ممنون میشم به این سوالات جواب بدین لطفا توضیح بدین ( سوالاتم خیلی میتدی هستن اما خوب سوالن دیگه
جواب سوال ۵
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اومده.
(۲۰ مهر ۱۳۹۱ ۰۱:۲۵ ب.ظ)مهربان نوشته شده توسط: سلام دوستان ممنون میشم به این سوالات جواب بدین لطفا توضیح بدین ( سوالاتم خیلی میتدی هستن اما خوب سوالن دیگه
سلام دوست من
جواب یکی از سوالای شما رو مینویسم :
مرتبه رابطه بازگشتی محاسبه ب.م.م دو عدد a و b است : O(log a)