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

تبدیلات در قضیه اصلی

ارسال:
  

پشتکار پرسیده:

تبدیلات در قضیه اصلی

در معادله زیر
[tex]T(n)=4T(\frac{\sqrt{n}}{3}) log^{2}n[/tex]

برای از بین بردن رادیکال باید [tex]n=2^{m}[/tex]m} قرار بدیم
چرا اینجوری می کنیم؟ و بعدش در کتاب وقتی اینکار رو کرده نوشته [tex]T(2^{m})=4T(2^{\frac{m}{2}}) m^{2}[/tex]
پس کسر ۳ کجا رفته؟؟؟

۰
ارسال:
  

khavar_1365 پاسخ داده:

RE: تبدیلات در قضیه اصلی

سلام دوست مانشتی:
د راینجا چون nما رادیکالی است باید به nتبدیل بشه بخاطر همین با تغییر متغیر این کار کرده وn=2^mفرض کرده که میشه[tex]\sqrt{2^m}=2^m/2[/tex]
که با این روش nرو از زیر رادیکال بیرون و به nاز درجه ۱تبدیل میکنه باز هم برای ساده شدن تغییرمتغیر میده [tex]s(m)=T(2^m)[/tex]
[tex]s(m)=T(2^m)[/tex]که الان رابطه به شکل[tex]s(m)=4s(m/2) m^2[/tex]
تبذیل میشه که از طریق رابطه اصلی قابل حل وهم اینکهn=2^mهم برابرm=logn میباشد.
از۳صرفنطرکرده.
دوستان دیگه هم نطربدن و اگه اشکالی داره اصلاح کنن.

۰
ارسال:
  

پشتکار پاسخ داده:

تبدیلات در قضیه اصلی

خب من اصلا سوالم اینه که چرا n=2^m

ارسال:
  

khavar_1365 پاسخ داده:

RE: تبدیلات در قضیه اصلی

(۲۰ مهر ۱۳۹۰ ۰۱:۳۳ ب.ظ)پشتکار نوشته شده توسط:  خب من اصلا سوالم اینه که چرا n=2^m

هم برای ساده سازی بیشتر nیاهمان عدد زیر رادیکال را توانی از ۲فرض کرده.این که خیلی واضحه برای اینکه قراره باتغییر متغیر حل بشه و ساده سازی لازم رو انجام بده.
بری اینکه nرو از زیر رادیکال بیرون بیاره فرض میکنه که nتوانی از ۲باشه(بخاطر همین گفتهn=2^m و) ساده سازی روانجام میده.
بقیه دوستان هم کمک دوستمون کنند من فقط همینقدر میدونم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

پشتکار پاسخ داده:

RE: تبدیلات در قضیه اصلی

چیزی که خودم بهش رسیدم رو می نویسم و خواهش می کنم دوستان عیبها و درست یا غلط بودنشو بهم بگن:
داریم:
[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) log^{2}n[/tex]

حال برای از بین بردن لگاریتم [tex]n=2^{m}[/tex] را بجای n قرار می دهیم.
پس داریم:
[tex] T(2^{m})=4T(\frac{2^{\frac{m}{2}}}{3}) m^{2} [/tex]

حال از داخل [tex] T() [/tex] لگاریتم می گیریم و داریم:
[tex]S(m)=4S(log{{\frac{2^{\frac{m}{2}}}{3}}}) m[/tex]


که با ساده سازی داریم:
[tex] \frac{m}{2}-log_{2}^{3}=\frac{m}{2}-(1 \varepsilon )[/tex]
که از قسمت اخر می تونیم صرف نظر کنیم و حالا رابطه رو حل می کنیم.Smile
اگه جایی رو اشتباه کردم لطفا دوستان بهم بگن

۰
ارسال:
  

پشتکار پاسخ داده:

تبدیلات در قضیه اصلی

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

۰
ارسال:
  

- 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] گرفتم.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  خرید کتاب زبان اصلی آموزش برنامه نویسی جاوا moslem73421 ۶ ۵,۳۴۴ ۱۴ فروردین ۱۳۹۹ ۰۹:۰۶ ب.ظ
آخرین ارسال: marvelous
  مطالعه کتاب زبان اصلی saharitst ۲ ۲,۳۸۰ ۱۱ اسفند ۱۳۹۸ ۱۱:۳۸ ب.ظ
آخرین ارسال: saharitst
Sad سوال از قضیه ی بیز Nazari76 ۱ ۲,۸۲۹ ۲۶ خرداد ۱۳۹۷ ۰۷:۵۴ ب.ظ
آخرین ارسال: saeed_vahidi
  تشخیص دو قضیه از هم Mr.R3ZA ۵ ۴,۹۰۳ ۳۱ اردیبهشت ۱۳۹۷ ۱۲:۱۴ ق.ظ
آخرین ارسال: pioneer01
  فروش کتاب های منبع اصلی و کنکوری ارشد htninety ۰ ۱,۷۶۲ ۱۱ فروردین ۱۳۹۷ ۰۴:۵۹ ب.ظ
آخرین ارسال: htninety
  دانلود رایگان کتاب «زبان عمومی دکتری زیر ذره بین» مرجع اصلی زبان کنکور دکتری generalenglish ۰ ۳,۶۹۶ ۱۸ اردیبهشت ۱۳۹۶ ۰۹:۴۳ ب.ظ
آخرین ارسال: generalenglish
  دانلود رایگان کتاب «زبان عمومی دکتری زیر ذره بین» مرجع اصلی کنکور دکتری generalenglish ۰ ۹,۳۷۸ ۱۸ اردیبهشت ۱۳۹۶ ۰۹:۳۰ ب.ظ
آخرین ارسال: generalenglish
  توضیح قضیه گرچ گودین یه نفر ۰ ۱,۳۲۴ ۲۰ فروردین ۱۳۹۶ ۱۲:۵۵ ب.ظ
آخرین ارسال: یه نفر
  قضیه یا فرمول حداکثر تعداد دستورات دو آدرسی / یک آدرسی mmm1374 ۲ ۲,۰۵۷ ۰۳ بهمن ۱۳۹۵ ۰۲:۰۰ ب.ظ
آخرین ارسال: Saman
  ۱۵ task اصلی مدیر پروژه نرم افزار ملینا ارشد ۰ ۱,۱۳۰ ۲۰ دى ۱۳۹۵ ۰۹:۱۶ ب.ظ
آخرین ارسال: ملینا ارشد

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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