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

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

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

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

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

به نظر من اینجور بهتره:
[tex]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)[/tex]

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

---

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

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

[tex]\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 }[/tex]

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

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

(۱۳ شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  [tex]\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 }[/tex]

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

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

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

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

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

[tex]\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 }[/tex]

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

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

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

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

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

[tex]\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 }[/tex]

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

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

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

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

---

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

(13 شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)tarane.68 نوشته شده توسط:  [tex]\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 }[/tex]

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

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

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

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

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

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

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

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

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

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

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