سلام
پیچیدگی زمانی این رو کسی میتونه دقیق توضیح بده، یه جا دیدم اونم با انتگرال و قضیه آکرا حل شده.
[tex]n\sum^n_{i=1}\log i\: =\: ?\: [/tex]
سلام.
[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^n_{i=1}\log i[/tex] نیز [tex]\frac{n}{2}[/tex] از جملات بزرگتر یا مساوی [tex]\log\frac{n}{2}=\log n-1[/tex] هستند. در نتیجه : میتوان کل عبارت را از :
[tex]\theta(n^2\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] دونست.
به به. چه جوابی بودش
مرسی واقعا.
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!
i=n
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh
(۰۵ فروردین ۱۳۹۷ ۰۲:۵۱ ب.ظ)alirzafrzn نوشته شده توسط: لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!
i=n
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh
گمان کنم که مرتبه این الگوریتم میشه O(Log n) :lبا پایه۵ که پایه اهمیتی نداره همون Lg n میشه!