(۱۳ شهریور ۱۳۹۲ ۰۷:۱۷ ب.ظ)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]

(۱۳ شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)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] ؟؟؟

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

(۱۳ شهریور ۱۳۹۲ ۰۸:۲۹ ب.ظ)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] ؟؟؟

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

(۱۳ شهریور ۱۳۹۲ ۱۱:۵۸ ب.ظ)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]

(۱۴ شهریور ۱۳۹۲ ۱۱:۲۹ ق.ظ)tarane.68 نوشته شده توسط:  ببخشید متوجه نشدم . خب حالا این چطوری میشه [tex]O(n\log \log 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]