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

مرتبه زمانی یک رابطه بازگشتی

ارسال:
  

amin222 پرسیده:

مرتبه زمانی یک رابطه بازگشتی

سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

misagh01 پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

(۲۱ دى ۱۳۹۲ ۱۰:۲۸ ق.ظ)amin222 نوشته شده توسط:  سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]

سلام دوست عزیز Smile
از درخت بازگشت استفاده میکنیم:
n
n/2 3n/4
n/4 3n/8 9n/16 3n/8
و ...
جمع سطر اول: n
جمع سطر دوم: ۵n/4
جمع سطر سوم: ۲۵n/16
همانطور که میبینید یک دنباله هندسی داریم با q=5/4 و تعداد عناصر این دنباله یا همون تعداد سطر ها لوگاریتم n برمبنای ۴/۳ هست. مجموع این دنباله ۲^n میشود.
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

amin222 پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

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

ارسال:
  

misagh01 پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

(۲۱ دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط:  دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

خواهش میکنم Smile، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که 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] میباشد.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

amin222 پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

(۲۱ دى ۱۳۹۲ ۰۳:۵۵ ب.ظ)misagh01 نوشته شده توسط:  
(21 دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط:  دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

خواهش میکنم Smile، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که 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] میباشد.

دستت درد نکنه گرفتم چی شد واقعا ممنون
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

raziiiiiiiiiiie پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
نقل قول این ارسال در یک پاسخ

ارسال:
  

amin222 پاسخ داده:

RE: مرتبه زمانی یک رابطه بازگشتی

(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط:  سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟

فکر کنم دوستمون از قلام انداخته ولی درست هست محاسباتش
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

misagh01 پاسخ داده:

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به 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?

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

Feeling left out?


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

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

Feeling left out?


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