تالار گفتمان مانشت

سلام دوستان
این سوال بازگشتی چطور باید حل کرد ؟؟؟

[attachment=14660]

جواب کوتاه اینه که با درخت بازگشت حل اش کنید.
اما اگر دنبال جواب مفصل هستید، الان فرصت اش رو ندارم اما بی جواب نمیذارم اش

(25 دى 1392 08:48 ب.ظ)هاتف نوشته شده توسط: [ -> ]جواب کوتاه اینه که با درخت بازگشت حل اش کنید.
اما اگر دنبال جواب مفصل هستید، الان فرصت اش رو ندارم اما بی جواب نمیذارم اش

ممنون میشم اگه توضیحش بدین منم نتونستم حلش کنم

(25 دى 1392 08:48 ب.ظ)هاتف نوشته شده توسط: [ -> ]جواب کوتاه اینه که با درخت بازگشت حل اش کنید.
اما اگر دنبال جواب مفصل هستید، الان فرصت اش رو ندارم اما بی جواب نمیذارم اش

حل از طریق درخت بازگشت که واضحه اما میخوام درختش تجزیه تحلیل شه
[attachment=14701]
فکر کنم حل این باشه
[tex]KN(1 \frac{3}{4} \frac{5}{32} ...)= c(KN)\Rightarrow O(KN)[/tex]

سلام
روی کاغذ حل کردم، ببخشید که کیفیت خوبی نداره ولی خب خواناست.

(06 بهمن 1392 09:03 ب.ظ)هاتف نوشته شده توسط: [ -> ]سلام
روی کاغذ حل کردم، ببخشید که کیفیت خوبی نداره ولی خب خواناست.

سپاسگذارم از جواب خوبتون ولی من اینجایی را که ارتفاع درخت را بدست میارید متوجه نمیشم یه سوال مشابهی هم دیدم که با مثال ارتفاع درخت را بدست آورده بود ولی با مثال زمان بیشتری از آدم گرفته میشه،اگه ممکنه یه کمی بیشتر توضیح بدین ممنون میشم

(08 بهمن 1392 11:02 ب.ظ)نارین نوشته شده توسط: [ -> ]سپاسگذارم از جواب خوبتون ولی من اینجایی را که ارتفاع درخت را بدست میارید متوجه نمیشم یه سوال مشابهی هم دیدم که با مثال ارتفاع درخت را بدست آورده بود ولی با مثال زمان بیشتری از آدم گرفته میشه،اگه ممکنه یه کمی بیشتر توضیح بدین ممنون میشم

خواهش می کنم.
درخت بالا رو ببینید، میدونیم که وقتی یک رابطه بازگشتی تموم میشه که به یک مقدار ثابت و اولیه برسه مثلا وقتی n بشه 1 بعدش دیگه تابع return میکنه، اون همون برگ های درخت هست.
اگر بخواهیم بدونیم درخت چند سطح داره باید ببینم طولانی ترین شاخه اش کجا ختم میشه، توی شاخه سمت چپ n داره هربار بر 2 تقسیم میشه و توی شاخه ی سمت راست k هربار داره بر 4 تقسیم میشه، پس میشه نتیجه گرفت شاخه سمت چپ دیـــرتر به برگ هاش میرسه (دقت کنید) پس اگر بخواهیم ارتفاع شاخه سمت چپ رو بدست بیاریم مطمئن هستیم که شاخه سمت راستی ازش کمتره.
توی خط سوم نوشتم که [tex](\frac{1}{2})^{i} n \geqslant 1[/tex] که i همون سطح درخت هست، مثلا در سطح دوم که i=2 هست میشه [tex]\frac{1}{4}n[/tex] این عبارت تا وقتی از 1 بزرگتر هست سطح جدید داریم، بعدش دیگه عملیات ریاضی هست تا i بدست بیاد، میبینید که i میتونه حداکثر logn بشه
هزینه ی هر سطح هم که قبلا حساب کردم، خط بعدش داره به ازای هر سطح اون هزینه رو حساب میکنه منتها چون حل اون سیگما سخته از یه قضیه استفاده میکنیم (اسم قضیه یادم نیست) و حد بالای سیگما رو بی نهایت میگیریم، nk که ربطی به سیگما ندارند بیرون میان و خود سیگما هم یه عبارت تصاعد هندسی هست که به راحتی قابل حله، در نهایت هم 4nk بدست اومده که از مرتبه [tex]O(nk)[/tex]
میشه اگر دقت کنید همه جا دست بالا گرفتیم و خیلی دقیق حساب نکردیم، برای همین درخت بازگشت مرتبه رو میتونه حساب کنه و نه زمان دقیق عملیات.

اوکی سپاسگذارم ، الان متوجه شدم

ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به 4 میشه.

(24 بهمن 1392 04:26 ب.ظ)hap777 نوشته شده توسط: [ -> ]ممنون از جواب . البته تو ارتفاع درخت اشتباه کردی. ارتفاعش میشه logn + logk علتشم اینه اول هی n تقسیم به دو میشه و k ثابت میمونه بعد n ثابت میمونه و k تقسیم به ۴ میشه.

چون هزینه هر سطح داره کم میشه، پس هزینه ای که توی ریشه هست غالب میشه و نیاز به ارتفاع درخت نداریم.

(24 بهمن 1392 04:36 ب.ظ)Riemann نوشته شده توسط: [ -> ]چون هزینه هر سطح داره کم میشه، پس هزینه ای که توی ریشه هست غالب میشه و نیاز به ارتفاع درخت نداریم.

درسته. منم فقط ارتفاع درختو گفتم اشتباهه نه جواب مسئله.