۱
subtitle
ارسال: #۱
  
مرتبه زمانی یک رابطه بازگشتی
سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
۲
ارسال: #۲
  
RE: مرتبه زمانی یک رابطه بازگشتی
(۲۱ دى ۱۳۹۲ ۱۰:۲۸ ق.ظ)amin222 نوشته شده توسط: سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
سلام دوست عزیز
از درخت بازگشت استفاده میکنیم:
n
n/2 3n/4
n/4 3n/8 9n/16 3n/8
و ...
جمع سطر اول: n
جمع سطر دوم: ۵n/4
جمع سطر سوم: ۲۵n/16
همانطور که میبینید یک دنباله هندسی داریم با q=5/4 و تعداد عناصر این دنباله یا همون تعداد سطر ها لوگاریتم n برمبنای ۴/۳ هست. مجموع این دنباله ۲^n میشود.
۱
ارسال: #۳
  
RE: مرتبه زمانی یک رابطه بازگشتی
دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
ارسال: #۴
  
RE: مرتبه زمانی یک رابطه بازگشتی
(۲۱ دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط: دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
خواهش میکنم ، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که q به توان لگاریتم n برمبنای ۴/۳ هست از فرمول زیر استفاده کنید:
[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
که مقدار بالا به طور تقریبی برایرست با: [tex]n^{1}[/tex]
که در نهایت مجموع سری از مرتبه [tex]n^{2}[/tex] میباشد.
ارسال: #۵
  
RE: مرتبه زمانی یک رابطه بازگشتی
(۲۱ دى ۱۳۹۲ ۰۳:۵۵ ب.ظ)misagh01 نوشته شده توسط:(21 دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط: دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
خواهش میکنم ، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که q به توان لگاریتم n برمبنای ۴/۳ هست از فرمول زیر استفاده کنید:
[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
که مقدار بالا به طور تقریبی برایرست با: [tex]n^{1}[/tex]
که در نهایت مجموع سری از مرتبه [tex]n^{2}[/tex] میباشد.
دستت درد نکنه گرفتم چی شد واقعا ممنون
۱
ارسال: #۶
  
RE: مرتبه زمانی یک رابطه بازگشتی
سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
ارسال: #۷
  
RE: مرتبه زمانی یک رابطه بازگشتی
ارسال: #۸
  
RE: مرتبه زمانی یک رابطه بازگشتی
(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط: سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
سلام
فکر میکنم حق با شماست، ممنون از تذکرتون. با احتساب ۲ بار n/2 فرمول زیر تغییر میکنه :
[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
تبدیل میشه به:
[tex]\frac{7}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{7}{4}}} \simeq n^{1}[/tex]
که در نهایت جواب مجموع سری هندسی با فرمول بالا میشه همون [tex]n^{2}[/tex] .
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۰۴۴ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
|
نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۷۹۳ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۶ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۷۳ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۳,۲۷۰ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۸۲۰ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۵۲ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۷۷۱ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
مرتبه زمانی | Sanazzz | ۰ | ۲,۰۶۵ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
|
مشکل در محاسبه مرتبه ایک سوال | Mr.R3ZA | ۰ | ۱,۹۰۱ |
۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ آخرین ارسال: Mr.R3ZA |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close