سلام.
[tex]\sum^n_{i=1}\log i=\log1+\log2+\log3+...+\log n=\log\: 1\times2\times3\times...\times n=log(n!) = n\log n[/tex]

با انتگرال: [tex]\sum^n_{i=1}\log i\: \approx\: \int^n_{i=1}\log i=ilogi-i\: \mid_{i=1}^{i=n}=nlogn-n-(1\log1-1)=\theta(n\log n)[/tex]

سلام. وقت بخیر.

[tex]\sum_{i=1}^n\log i=\log1+\log 2+...+\log n[/tex]

یه قاعده از لگاریتم به شکل زیره:

[tex]\log ab=\log a+\log b[/tex]

طبق این رابطه با فرض اینکه [tex]a=\frac{n}{2}[/tex] و [tex]b=2[/tex] میتونیم بنویسیم [tex]\log\frac{n}{2}=\log n-\log 2[/tex] که لگاریتم عدد ۲ به ازای مبنای ۲ برابر ۱ و به ازای مبنای عدد نپر کوچکتر از ۱ میشه. تو اون سیگمای بالایی هم میدونیم n/2 از جملات بزرگتر از [tex]\log\frac{n}{2}[/tex] هستن. پس این جملات بزرگتر مساوی [tex]\log n -1[/tex] هستن. همه جملات هم کوچکتر مساوی [tex]\log n[/tex] هستن. پس مرتبه زمانی این مجموع رو میشه [tex]\theta(n\log n)[/tex] دونست.