۰
subtitle
ارسال: #۱
  
درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
سلام
پیچیدگی زمانی این رو کسی میتونه دقیق توضیح بده، یه جا دیدم اونم با انتگرال و قضیه آکرا حل شده.
[tex]n\sum^n_{i=1}\log i\: =\: ?\: [/tex]
پیچیدگی زمانی این رو کسی میتونه دقیق توضیح بده، یه جا دیدم اونم با انتگرال و قضیه آکرا حل شده.
[tex]n\sum^n_{i=1}\log i\: =\: ?\: [/tex]
۰
ارسال: #۲
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
سلام.
[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=\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]
۰
ارسال: #۳
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
سلام. وقت بخیر.
[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] دونست.
[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] دونست.
۰
ارسال: #۴
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
ممنون. نمیدونم چرا درکم از سیگما و ریاضی و لگاریتم پایینه
.
میدونم قضیه چیه توی مسائل یادم میره ازشون استفاده کنم.واقعا ممنون![Smile Smile](images/smilies/smile.gif)
پاسخ پژوهش اینجوریه :
میشه اینو بگید منظورش چیه ؟
در عبارت [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] دانست.
اون قسمت اول دقیقا چه بلایی سرش آورده که استدلالش اینه؟!!!
![Confused Confused](images/smilies/confused.gif)
میدونم قضیه چیه توی مسائل یادم میره ازشون استفاده کنم.واقعا ممنون
![Smile Smile](images/smilies/smile.gif)
پاسخ پژوهش اینجوریه :
میشه اینو بگید منظورش چیه ؟
در عبارت [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] دانست.
اون قسمت اول دقیقا چه بلایی سرش آورده که استدلالش اینه؟!!!
۰
ارسال: #۵
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
به به. چه جوابی بودش![Smile Smile](images/smilies/smile.gif)
مرسی واقعا.
![Smile Smile](images/smilies/smile.gif)
مرسی واقعا.
۰
ارسال: #۶
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!![Huh Huh](images/smilies/huh.gif)
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh
![Huh Huh](images/smilies/huh.gif)
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
ارسال: #۷
  
RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)
(۰۵ فروردین ۱۳۹۷ ۰۲:۵۱ ب.ظ)alirzafrzn نوشته شده توسط: لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!
i=n
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5
لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh
گمان کنم که مرتبه این الگوریتم میشه O(Log n) :lبا پایه۵ که پایه اهمیتی نداره همون Lg n میشه!
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close