سلام.
حل رابطه اولی رو انجام میدم. $T(n) = T(n-1) Logn$

این سوال رو راحت میشه با روش جایگذاری حل کرد. مراحلش بصورت زیر هست:
$T(n) = T(n-1) Logn$
$T(n) = T(n-2) Log(n-1) Logn$
$T(n) = T(n-3) Log(n-2) Log(n-1) Logn$
..
..
..
$T(n) = T(n-(n-1)) Log(1) Log(2) Log(3) ... Log(n-2) Log(n-1) Logn$
که با فرض T(1) = 0 میشه :
$T(n) = Log(1) Log(2) Log(3) ... Log(n-2) Log(n-1) Logn$

این تصاعد حسابی رو اگه حل کنید در نهایت جواب سوال میشه : $T(n)\, \varepsilon\, \Theta (nLogn)$

(۱۳ شهریور ۱۳۹۲ ۰۷:۱۷ ب.ظ)azad_ahmadi نوشته شده توسط:  $T(n) = Log(1) Log(2) Log(3) ... Log(n-2) Log(n-1) Logn$

این تصاعد حسابی رو اگه حل کنید در نهایت جواب سوال میشه : $T(n)\, \varepsilon\, \Theta (nLogn)$

به نظر من اینجور بهتره:
$T(n) = Log(1) Log(2) Log(3) ... Log(n-2) Log(n-1) Log(n) = Log(1*2*3 \dots * (n-1)*(n)) = Log(n!) = O(nLog n)$

ممنون از لطفتون
وافعا ممنون
من با روش جایگذاری حلش میکردم ولی آخرش گیر میکردم
مرسی

---

واسه رابطه دومی تا یه جاهایی رو با جایگذاری حل کردم.

$T(n)=2T(\frac{n}{2}) \frac{n}{\log n}$
$T(n)=2^{2}T(\frac{n}{2^{2}}) \frac{\frac{n}{2}}{\log \frac{n}{2}} \frac{n}{\log n}$
.
.
.
گسترشش که بدیم میشه :

$\frac{n}{\log n} \frac{n}{\log \frac{n}{2}} \frac{n}{\log \frac{n}{2^{2}}} ... = n\sum_{i=0}^{\log n} \frac{1}{\log\frac{n}{2^{i}} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-\log2^{i} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-i }$

از اینجا به بعدش رو دیگه نمیدونم چیکار کنم؟؟؟؟ نمیدونم چطوری میشه $O(n\log \log n)$ ؟؟؟

( فکر کنم باید یه نگاهی به سری ها تو ریاضی بندازم )

(۱۳ شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  $\frac{n}{\log n} \frac{n}{\log \frac{n}{2}} \frac{n}{\log \frac{n}{2^{2}}} ... = n\sum_{i=0}^{\log n} \frac{1}{\log\frac{n}{2^{i}} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-\log2^{i} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-i }$

از اینجا به بعدش رو دیگه نمیدونم چیکار کنم؟؟؟؟ نمیدونم چطوری میشه $O(n\log \log n)$ ؟؟؟

( فکر کنم باید یه نگاهی به سری ها تو ریاضی بندازم )

شما این سری رو از آخر به اول نگاه کن:

$\sum_{i=1}^{\log n} \frac{1}{\log n-i }$ میشه معادل با سری $\sum_{i=1}^{\log n} \frac{1}{ i }$ و از طرفی میدانیم که سری $\sum_{i=1}^{n} \frac{1}{i} = ln( n)$

(۱۳ شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  گسترشش که بدیم میشه :

$\frac{n}{\log n} \frac{n}{\log \frac{n}{2}} \frac{n}{\log \frac{n}{2^{2}}} ... = n\sum_{i=0}^{\log n} \frac{1}{\log\frac{n}{2^{i}} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-\log2^{i} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-i }$

از اینجا به بعدش رو دیگه نمیدونم چیکار کنم؟؟؟؟ نمیدونم چطوری میشه $O(n\log \log n)$ ؟؟؟

( فکر کنم باید یه نگاهی به سری ها تو ریاضی بندازم )

این بسطی که شما نوشتید برای تابع $T(n)=2T(\frac{n}{2}) n/\lg n$ هستش در حالی که تابعی که در پست اول خودتون قرار دادید $T(n)=3T(\frac{n}{3}) n/\lg n$ هستش.

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

(13 شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  گسترشش که بدیم میشه :

$\frac{n}{\log n} \frac{n}{\log \frac{n}{2}} \frac{n}{\log \frac{n}{2^{2}}} ... = n\sum_{i=0}^{\log n} \frac{1}{\log\frac{n}{2^{i}} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-\log2^{i} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-i }$

از اینجا به بعدش رو دیگه نمیدونم چیکار کنم؟؟؟؟ نمیدونم چطوری میشه $O(n\log \log n)$ ؟؟؟

( فکر کنم باید یه نگاهی به سری ها تو ریاضی بندازم )

این بسطی که شما نوشتید برای تابع $T(n)=2T(\frac{n}{2}) n/\lg n$ هستش در حالی که تابعی که در پست اول خودتون قرار دادید $T(n)=3T(\frac{n}{3}) n/\lg n$ هستش.

ببخشید اشتباه شده بود.
اصلاحش کردم

---

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

(13 شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  $\frac{n}{\log n} \frac{n}{\log \frac{n}{2}} \frac{n}{\log \frac{n}{2^{2}}} ... = n\sum_{i=0}^{\log n} \frac{1}{\log\frac{n}{2^{i}} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-\log2^{i} } = n\sum_{i=0}^{\log n} \frac{1}{\log n-i }$

از اینجا به بعدش رو دیگه نمیدونم چیکار کنم؟؟؟؟ نمیدونم چطوری میشه $O(n\log \log n)$ ؟؟؟

( فکر کنم باید یه نگاهی به سری ها تو ریاضی بندازم )

شما این سری رو از آخر به اول نگاه کن:

$\sum_{i=1}^{\log n} \frac{1}{\log n-i }$ میشه معادل با سری $\sum_{i=1}^{\log n} \frac{1}{ i }$ و از طرفی میدانیم که سری $\sum_{i=1}^{n} \frac{1}{i} = ln( n)$

ببخشید متوجه نشدم . خب حالا این چطوری میشه $O(n\log \log n)$ ؟؟

(۱۴ شهریور ۱۳۹۲ ۱۱:۲۹ ق.ظ)tarane.68 نوشته شده توسط:  ببخشید متوجه نشدم . خب حالا این چطوری میشه $O(n\log \log n)$ ؟؟

عبارت $\sum_{i=1}^{n}{\frac{1}{i}}$ از مرتبه بیگ اوی lgn هستش (به این موضوع توجه کنید که وقتی کران بالای سیگما n هستش اونوقت جلوی لگاریتم هم n اومده). حالا وقتی کران بالای این سیگما از n به lgn تغییر کنه داریم: $\sum_{i=1}^{\lg n}{\frac{1}{i}}=O(\lg \lg n)$
یه n هم که از قبل پشت سیگما بوده و این یعنی $n\sum_{i=1}^{\lg n}{\frac{1}{i}}=O(n\lg \lg n)$

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

(14 شهریور ۱۳۹۲ ۱۱:۲۹ ق.ظ)tarane.68 نوشته شده توسط:  ببخشید متوجه نشدم . خب حالا این چطوری میشه $O(n\log \log n)$ ؟؟

عبارت $\sum_{i=1}^{n}{\frac{1}{i}}$ از مرتبه بیگ اوی lgn هستش (به این موضوع توجه کنید که وقتی کران بالای سیگما n هستش اونوقت جلوی لگاریتم هم n اومده). حالا وقتی کران بالای این سیگما از n به lgn تغییر کنه داریم: $\sum_{i=1}^{\lg n}{\frac{1}{i}}=O(\lg \lg n)$
یه n هم که از قبل پشت سیگما بوده و این یعنی $n\sum_{i=1}^{\lg n}{\frac{1}{i}}=O(n\lg \lg n)$

متوجه شدم
ممنونم.لطف کردین