زمان کنونی: ۳۱ خرداد ۱۴۰۳, ۰۲:۲۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

ارسال:
  

Saman پرسیده:

درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

سلام

پیچیدگی زمانی این رو کسی میتونه دقیق توضیح بده، یه جا دیدم اونم با انتگرال و قضیه آکرا حل شده.

[tex]n\sum^n_{i=1}\log i\: =\: ?\: [/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Pure Liveliness پاسخ داده:

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]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Jooybari پاسخ داده:

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] دونست.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

ممنون. نمیدونم چرا درکم از سیگما و ریاضی و لگاریتم پایینهConfused.
میدونم قضیه چیه توی مسائل یادم میره ازشون استفاده کنم.واقعا ممنونSmile
پاسخ پژوهش اینجوریه :
میشه اینو بگید منظورش چیه ؟
در عبارت [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] دانست.

اون قسمت اول دقیقا چه بلایی سرش آورده که استدلالش اینه؟!!!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

به به. چه جوابی بودشSmile
مرسی واقعا.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

alirzafrzn پاسخ داده:

RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh

i=n
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5

لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

ارسال:
  

saeed_vahidi پاسخ داده:

RE: درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی)

(۰۵ فروردین ۱۳۹۷ ۰۲:۵۱ ب.ظ)alirzafrzn نوشته شده توسط:  لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh

i=n
While ( i>1 )
For ( j=1 ; j<=i ; j++ )
i = i/5

لطفا زمان اجرای اینو بهم بنویسید یا توضیح بدین لگاریتم و سیگما نیاز داره توهم ؟؟!!!Huh

گمان کنم که مرتبه این الگوریتم میشه O(Log n) :lبا پایه۵ که پایه اهمیتی نداره همون Lg n میشه!
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  روابط احساسی خارج از ازدواج مردان متأهل morweb ۶۲ ۳۱,۹۰۳ ۱۰ بهمن ۱۴۰۲ ۰۲:۴۱ ب.ظ
آخرین ارسال: fatemehbiglar
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۲۸۶ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۸۷۳ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۷۱۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۲۰,۰۶۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  مصاحبه دکتری- بخش تدریس wskf ۱ ۲,۵۰۰ ۲۸ فروردین ۱۳۹۹ ۰۴:۳۰ ب.ظ
آخرین ارسال: Masoud05
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۶۵۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۵۷۷ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۸۱,۰۰۸ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۲,۳۸۶ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close