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

دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم

ارسال:
۰۹ بهمن ۱۳۹۰, ۱۱:۵۹ ب.ظ (آخرین ویرایش در این ارسال: ۱۰ بهمن ۱۳۹۰ ۱۱:۳۹ ب.ظ، توسط - rasool -.)
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم
هوالعلیم

یک سوال ترکیبی و حدودا متوسط (تست کنکور ۸۸)

[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) Log^{2}n[/tex]


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: sohrablou , *farnaz*
ارسال:
۱۰ بهمن ۱۳۹۰, ۱۱:۰۵ ب.ظ (آخرین ویرایش در این ارسال: ۱۱ بهمن ۱۳۹۰ ۱۲:۱۱ ق.ظ، توسط - rasool -.)
دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم
این سوال با من.

فکر می کنم اینطوری حل می شه:

ابتدا تغییر متغیر [tex]n=3^{m}\Leftrightarrow m=Log _{3}^{n}[/tex] رو انجام می دیم. داریم‌:

[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) Log^{2}n=T(3^{m})=4T(3^{\frac{m}{2}-1}) m^{2}\Rightarrow S(m)=4S(\frac{m}{2}-1) m^{2}\approx S(m)=4S(\frac{m}{2}) m^{2}[/tex]

که حالا با استفاده از قضیه اصلی می رسیم به‌: [tex]O(m^{2}Logm)[/tex]

و در نهایت با جایگزینی داریم:

[tex]O(Log^{2}n Log logn)[/tex]



پ ن‌: البته من برای راحتی کار و نیز چون بحث مرتبه هستش‌، گاها در حل سوال [tex]Log _{3}^{n}\approx Log _{2}^{n}[/tex] گرفتم.


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mehman , fallah_o68 , Ametrine
ارسال:
۱۰ بهمن ۱۳۹۰, ۱۱:۳۳ ب.ظ (آخرین ویرایش در این ارسال: ۱۰ بهمن ۱۳۹۰ ۱۱:۳۴ ب.ظ، توسط Mohammad-A.)
RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم
ببخشید یک سؤال:
من تا اینجا رو پیش رفتم٬ اما بعدش شک کردم که از قضیه‌ی مستر میشه حل کرد یا نه.
یعنی اگر گاهی داشته باشیم:‌ [tex]\small \dpi{80} S(\frac{m}{2}-1)[/tex] می‌تونیم برای مرتبه‌ی زمانی [tex]\small \dpi{80} S(\frac{m}{2})[/tex] در نظر بگیریم؟

چون به هر حال٬ توی رابطه‌ی اول٬ داره در هر بازگشت٬ یکی هم کم میشه (علاوه بر اینکه تقسیم میشه)

Yesterday is History, Tomorrow is a Mystery but Today is a Gift
That is why it's called the Present
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۰ بهمن ۱۳۹۰, ۱۱:۵۰ ب.ظ (آخرین ویرایش در این ارسال: ۱۱ بهمن ۱۳۹۰ ۱۲:۱۳ ق.ظ، توسط - rasool -.)
دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم
به نظرم:
در اکثر مواقع میشه چنین کاری رو انجام داد.دلیل حذف اون مقدار مثلا دو هم این هست که ما قراره مرتبه به دست بیاریم و تو مرتبه ما با n های بزرگ سروکار داریم پس مقادیر ثابت تاثیر چندانی ندارن. و نیز نسبت به اون تقسیم بر دو کردن‌، این منهای یک قابل چشم پوشی خواهد بود.
در نتیجه اگه فرضا سوالی رو می خواستیم با قضیه اصلی یا درخت یا ... حل کنیم و این عدد رو داشت (چه بعلاوه و چه منها) می شه از اون صرفنظر کرد .
(البته منظورم وقتی هستش که مثل اینجا کسر داریم و گرنه در مورد غیر کسر بدیهیه که این عدد تاثیر داره)

--------------------------------------------------------------------------
به هر حال منتظر نظرات اساتید گرامی هستیم.

-----------------------------------------------------------------------------------

پ ن‌: جا داره در مورد این نکته از آقای mfxpert تشکر کنم.


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mohammad-A , Mehman
ارسال:
۱۱ بهمن ۱۳۹۰, ۱۱:۱۹ ق.ظ
RE: دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم
(۱۰ بهمن ۱۳۹۰ ۱۱:۵۰ ب.ظ)yaali نوشته شده توسط:  به نظرم:
در اکثر مواقع میشه چنین کاری رو انجام داد.دلیل حذف اون مقدار مثلا دو هم این هست که ما قراره مرتبه به دست بیاریم و تو مرتبه ما با n های بزرگ سروکار داریم پس مقادیر ثابت تاثیر چندانی ندارن. و نیز نسبت به اون تقسیم بر دو کردن‌، این منهای یک قابل چشم پوشی خواهد بود.
در نتیجه اگه فرضا سوالی رو می خواستیم با قضیه اصلی یا درخت یا ... حل کنیم و این عدد رو داشت (چه بعلاوه و چه منها) می شه از اون صرفنظر کرد .
(البته منظورم وقتی هستش که مثل اینجا کسر داریم و گرنه در مورد غیر کسر بدیهیه که این عدد تاثیر داره)

فکر کنم بشه اینطور استدلال کرد‌: چون می تونیم علامت براکت( سقف و کف )درون پراتنز رابطه مثلا (T(n) = 2(n/b رو برداریم و با توجه به اینکه تقسیم یک عدد ثابت بر عدد دیگه بالاخره بعد از تعداد متناهی مرتبه به عددی کچکتر از ۱ تبدیل میشه پس این عدد درون براکت حذف میشه‌، پس میتونیم بدون نگرانی این مقدار ثابت رو حذف کنیم.
پس ما مدام داریم اون عدد ثابت و n رو بر b تقسیم میکنیم ،در واقع n خیلی بزرگه و معلوم نیست در n/b کی به شرط مرزی برسیم اما یک عدد ثابت مثل a در طی تعداد متناهی وقتی بر b تقسیم میشه‌، میشه یه عدد کوچک و این عدد کوچک درون براکت برابر صفر هست . Smile

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Star دوره موضوعی --> حل روابط بازگشتی --> روابط دهم - rasool - ۲ ۱,۶۷۲ ۰۲ بهمن ۱۳۹۳ ۱۱:۴۵ ب.ظ
آخرین ارسال: mostafa2012
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه ششم - rasool - ۸ ۲,۸۷۴ ۰۱ آبان ۱۳۹۲ ۰۹:۰۷ ق.ظ
آخرین ارسال: Mänu
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - rasool - ۵ ۲,۰۳۳ ۱۳ مهر ۱۳۹۲ ۰۲:۲۵ ب.ظ
آخرین ارسال: vojoudi
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هفتم - rasool - ۱ ۱,۴۹۷ ۱۱ بهمن ۱۳۹۰ ۰۳:۰۶ ب.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه پنجم - rasool - ۱ ۱,۷۰۱ ۱۱ بهمن ۱۳۹۰ ۱۱:۱۸ ق.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هشتم - rasool - ۱ ۱,۸۷۰ ۱۰ بهمن ۱۳۹۰ ۰۸:۰۷ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه چهارم - rasool - ۱ ۱,۴۳۳ ۱۰ بهمن ۱۳۹۰ ۰۸:۰۰ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه دوم - rasool - ۱ ۱,۸۶۶ ۱۰ بهمن ۱۳۹۰ ۰۱:۳۴ ب.ظ
آخرین ارسال: Mohammad-A
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۵۴۰ ۰۸ آبان ۱۳۹۰ ۱۱:۱۲ ب.ظ
آخرین ارسال: sasanlive
  مرتبه این تابع بازگشتی از چه راهی بدست میاید ahmadi_development ۵ ۲,۸۶۸ ۱۸ مهر ۱۳۹۰ ۰۵:۳۷ ب.ظ
آخرین ارسال: sasanlive

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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