سلام
به نظر من اینطور حل میشه:

$T(n)=\frac{1}{n}[T(1) T(2) ... T(n-3) T(n-2) T(n-1) (3n)]$

حالا $T(n-1)$ رو هم بست میدم:

$T(n-1)=\frac{1}{n-1}[T(1) T(2) ... T(n-3) T(n-2) (3(n-1))]$

حالا باز شده ی $T(n-1)$ رو در$T(n)$ جایگزین میکنم:

$T(n)=\: \frac{1}{n}[T(1) T(2) ... T(n-2) \frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] 3n]$
و یک +۳ و -۳ به داخل [ ] اضافه می کنم:

$T(n)=\: \frac{1}{n}[T(1) T(2) ... T(n-2) \frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] 3n 3-3]$

حالاداریم
$3n 3-3 = (3n-3) 3\: =\: 3(n-1) 3$
یه ذره جابجایی برای فهم بهتر...

$T(n)=\: \frac{1}{n}[\frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] [T(1) T(2) ... T(n-2) 3(n-1)] 3]$

حالا میبینیم که همه چیز دوبار تکرار شده ودر واقع دوبار $T(n-1)$ بسط داده شده و فقط مشکل ما نبودن کسر $\frac{1}{n-1}$ در ابتدای عبارت دوم هست که با یک ضریب n-1 درست میشه البته اون +۳ رو هم فراموش نمی کنم!

یعنی اینجوری!

$T(n)\: =\: \frac{1}{n}[T(n-1) (n-1)T(n-1) 3] =\: \frac{1}{n}[nT(n-1) 3] =\: T(n-1) \frac{3}{n} \: \: \: \:$

که اگه اشتباه نکنم میشه:
$\: T(n)=T(n-1) \frac{3}{n}\: =\ln(n)\: \: \: \:$

امیدوارم که مفید باشه

(۰۱ شهریور ۱۳۹۳ ۱۲:۴۶ ق.ظ)reza777gh نوشته شده توسط:  سلام
به نظر من اینطور حل میشه:

$T(n)=\frac{1}{n}[T(1) T(2) ... T(n-3) T(n-2) T(n-1) (3n)]$

حالا $T(n-1)$ رو هم بست میدم:

$T(n-1)=\frac{1}{n-1}[T(1) T(2) ... T(n-3) T(n-2) (3(n-1))]$

حالا باز شده ی $T(n-1)$ رو در$T(n)$ جایگزین میکنم:

$T(n)=\: \frac{1}{n}[T(1) T(2) ... T(n-2) \frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] 3n]$
و یک +۳ و -۳ به داخل [ ] اضافه می کنم:

$T(n)=\: \frac{1}{n}[T(1) T(2) ... T(n-2) \frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] 3n 3-3]$

حالاداریم
$3n 3-3 = (3n-3) 3\: =\: 3(n-1) 3$
یه ذره جابجایی برای فهم بهتر...

$T(n)=\: \frac{1}{n}[\frac{1}{n-1}[T(1) ... T(n-2) 3(n-1)] [T(1) T(2) ... T(n-2) 3(n-1)] 3]$

حالا میبینیم که همه چیز دوبار تکرار شده ودر واقع دوبار $T(n-1)$ بسط داده شده و فقط مشکل ما نبودن کسر $\frac{1}{n-1}$ در ابتدای عبارت دوم هست که با یک ضریب n-1 درست میشه البته اون +۳ رو هم فراموش نمی کنم!

یعنی اینجوری!

$T(n)\: =\: \frac{1}{n}[T(n-1) (n-1)T(n-1) 3] =\: \frac{1}{n}[nT(n-1) 3] =\: T(n-1) \frac{3}{n} \: \: \: \:$

که اگه اشتباه نکنم میشه:
$\: T(n)=T(n-1) \frac{3}{n}\: =\ln(n)\: \: \: \:$

امیدوارم که مفید باشه

روش درست همینه!!
البته من به این رسیدم
$T(n)\: =\: \frac{n 1}{n}T(n-1)\: \: 3n$

(۰۱ شهریور ۱۳۹۳ ۰۲:۲۵ ب.ظ)Riemann نوشته شده توسط:  

(01 شهریور ۱۳۹۳ ۱۲:۴۶ ق.ظ)reza777gh نوشته شده توسط:  یعنی اینجوری!

$T(n)\: =\: \frac{1}{n}[T(n-1) (n-1)T(n-1) 3] =\: \frac{1}{n}[nT(n-1) 3] =\: T(n-1) \frac{3}{n} \: \: \: \:$

که اگه اشتباه نکنم میشه:
$\: T(n)=T(n-1) \frac{3}{n}\: =\ln(n)\: \: \: \:$

امیدوارم که مفید باشه

روش درست همینه!!
البته من به این رسیدم
$T(n)\: =\: \frac{n 1}{n}T(n-1)\: \: 3n$

سلام.
دوست عزیز اگه اصلا سوای حل کردن دقیق این رابطه همون به صورت سوالم نگاه کنی "حداقل حداقل" یه هزینه ۳n رو تو فراخوانی اول تابع داری که باعث میشه کلااااااا توابع هزینه های زیر $\theta(n)$ مثل $\ln(n)$ تو همون فراخوانی اول رد بشه !!!

سلام درسته، من یادمه این شبیه تحلیل مرتبه زمانی مرتب سازی سریع هست، کتاب Introduction to algoirthms a creative approach رو اگه دم دست داری، قسمت مرتبه زمانی ها یه اینجور مثالی زده.

(۰۱ شهریور ۱۳۹۳ ۰۳:۳۹ ب.ظ)Riemann نوشته شده توسط:  سلام درسته، من یادمه این شبیه تحلیل مرتبه زمانی مرتب سازی سریع هست، کتاب Introduction to algoirthms a creative approach رو اگه دم دست داری، قسمت مرتبه زمانی ها یه اینجور مثالی زده.

سلام دوباره
حرف شما کاملا درسته و آقای منبر توی کتابش تابع بازگشتی زیر رو برای حل زمان مسئله مرتب سازی سریع معرفی کرده :


ولی در واقع اگه یخورده دقت کنیم همین $\frac{2}{n}$ هست که وقتی بعنوان ضریب $\alpha$ و $\beta$ در تابع T ضرب میشه مجموع کسری بیشتر از مقدار ۱ رو به ما میده که خب براحتی طبق قضیه می تونیم اثبات کنیم که وقتی مجموع ضرایب بیشتر یک باشه هزینه ارتفاع این درخت $\theta(f(n))\cdot\log n$ هست(ضمنا تاثیر دقیق این $\frac{2}{n}$ رو توی سری هارمونیکی که آقای منبر معرفی کرده میشه دید). ولی توی مسئله ما ضریب $\frac{1}{n}$ رو داریم که با جمع زدن ضریب به کسری کمتر از ۱ می رسیم و باعث میشه "سری ثابت" رو برای ارتفاع درخت درنظر بگیریم.

ضمنا یه نکته داخل پرانتزی اینکه اگه تابع که برای مرتب سازی سریع معرفی شده رو حتی به صورت همون عبارت اولش یعنی
$T(n)=n-1 \frac{1}{n}\sum_{i=1}^nT(i)$
نیز نگاه کنیم در اینجا سیگمای ما مجموع n تا عبارت و نه n-1 عبارت رو معرفی کرده که این باعث میشه دقیقا مجموع کسرهای ما ۱ بشه و طبق رابطه هزینه $\theta(f(n))\cdot\log n$ رو داشته باشیم.


نکته ریز اختلاف این دو مسئله در همین " مجموع کسرهای ضرایب که آیا ۱ میشه یا کمتر از ۱" هستش که خب باید بهش دقت بشه و آقای قدسی به همین دلیل هزینه $\theta(n)$ رو برای این مسئله معرفی کرده.

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

(۰۱ شهریور ۱۳۹۳ ۰۲:۰۴ ق.ظ)miladcr7 نوشته شده توسط:  سلام خسته نباشید خیلی خوب توصیح دادید واقعا مرسی.ولی انصافا ادم اولین بار این جور سوالا رو میبینه خیلی خیلی سخته بخواد اینقدر ابتکاری حلشون کنه

خواهش میکنم. برای خودمم چیزی حدود نیم ساعت طول کشید تا حل شد! البته اگه درست باشه!
معمولا این سوال ها اگه نکته خاصی نداشته باشن با بسط دادن به یه جاهایی میرسن.

سلام . این سوال از نوع بازگشتی های معمولیه فقط صورتش یخورده آدم رو میترسونه، سخت نیست و براحتی قابل اثبات

اگر توجه کنیم فرم رابطه به صورت آشنای زیر هستش:

می دونیم که اگر $\alpha \beta<1$ جواب رابطه ما همون $\theta(n)$ میشه.

برای مثال فرض کنید ما $n=3$ قرار بدیم قسمت بازگشت تابع به صورت زیر باز میشه:


که خب ساختاری شبیه نوع صورت مسئله ما که در ابتدا گفته شد داره با این تفاوت ریز که دیگه خبری از ضریب n برای بازگشت وجود نداره و فقط ضرایب $\alpha$ و $\beta$ و امثالهم رو داریم. بزرگترین ضریب ثابت نیز همون فراخوانی آخر یعنی n-1 هستش (که البته کار ما رو برای اثبات نیز خیلی راحتر میکنه چرا که در سطوح بعدی درخت بازگشت دیگه خبری از هزینه به بزرگی ۳n وجود نداره و هزینه ها همگی ناچیز و مجموع ضرایبی کمتر از ۱ رو دارن).

در نهایت باعث میشه حد بالای رابطه رو در ابتدا $T(n)=\sum_{i=1}^{\log n}c^in=\theta(n)$ به ازای هر ورودی n برای جمع هزینه هر سطح درخت و کل ارتفاع درخت معرفی کنیم.
خب نکته آخر اینکه ضریب هزینه ثابت بازگشت ما (یعنی جمع کل سری در اینجا) خیلی کمتر از سری $\sum^{\log n}_{i=1}c^in$ است که معرفی شد چرا که ما توی بازگشتمون ضرایبی بسیار کمتر از n رو فراخوانی میکنیم (در حد یک عدد ثابت مثل $\frac{1}{3}$ یا $\frac{2}{3}$). یعنی اگه بخوایم بهتر بگیم توی این مسئله ما فقط هزینه به بزرگی n رو در فراخوانی اول و در سطح اول درخت داریم (۳n) و برای بقیه سطوح درخت هزینه ثابت میشه که رابطه $T(n)=3n \sum^{(\log n)-1}_{i=1}c^i$ دقیقا هزینه کل رو نشون میده که از $\theta(n)$ هست. در اینجا هزینه c رو هم میتونیم $c=\frac{n-1}{n}$ تعریف کنیم(مخرج مشترک کسرها).
در هر صورت ما هزینه n رو "حداقل حداقل" در سطح اول درختمون داریم که باعث میشه رابطه رو حداقل از $Omega(n)$ معرفی کنیم.

حلشم که نگاه کردم از کتاب $\theta(n)$ رو با استقراء اثبات کرده.

سلام دوستان

واقعا ممنون از اینکه اینقدر خوب توضیح دادین