۰
subtitle
ارسال: #۱
تغییر متغیر
لطفاً این رو به روش تغییر متغیر حل کنید:
[tex]T(n)=4T(\frac{\sqrt{n}}{3}) \log^2n[/tex]
[tex]T(n)=4T(\frac{\sqrt{n}}{3}) \log^2n[/tex]
۱
ارسال: #۲
RE: تغییر متغیر
به جای n می ذاریم [tex]3^k[/tex]
اونوقت معادله به فرم زیر در میاد
[tex]T(3^k)=4T(\frac{\sqrt{3^k}}{3}) \log^2{3^k}=4T(3^{\frac{k}{2}-1}) k^2\log^23[/tex]
[tex]G(k)=4G(\frac{k}{2}-1) k^2[/tex]
برای راحتی حل این معادله هم فکر کنم باید اون -۱ را بی خیال شد چون به هر حال هر بار k تقسیم بر دو می شود و بعد منهای یک می شود پس به هر حال چون بر ۲ تقسیم می شود مرتبه را خیلی کم و لگاریتمی می کند و اون منهای یک تاثیر چندانی ندارد و اگر معادله را به صورت زیر در نظر بگیریم:
[tex]G(k)<4G(\frac{k}{2}) k^2[/tex]
مرتبه ی G کمتر از [tex]k^2\log k[/tex]
بنابراین مرتبه ی f کمتر از [tex]\log^2n\ast\log\log n[/tex] خواهد بود
اما یه احتمال دیگه هم هست این که بگیم اگر معادله ی G به صورت
[tex]G(k)=4G(\frac{k}{2}) K^2[/tex] می بود اونوقت از مرتبه ی [tex]k^2\log k[/tex] می شد چون از قضیه مستز مزتبه ی اون بازگشت کسری با [tex]k^2[/tex] برابر می شد پس باید تو یه لگاریتم ضرب می کردیم
ما این جا معادله ی g اون بازگشت کسری ش کمتره پس مرتبه ی بازگشت کسری آن از [tex]k^2[/tex] کمتر است پس نیازی به ضرب کردن تو لگاریتم نداره پس از مرتبه [tex]k^2[/tex] است
به نظر من بهترین جواب اینه که بگیم [tex]\log^2n<=T(n)<\log^2n\ast\log\log n[/tex]
اونوقت معادله به فرم زیر در میاد
[tex]T(3^k)=4T(\frac{\sqrt{3^k}}{3}) \log^2{3^k}=4T(3^{\frac{k}{2}-1}) k^2\log^23[/tex]
[tex]G(k)=4G(\frac{k}{2}-1) k^2[/tex]
برای راحتی حل این معادله هم فکر کنم باید اون -۱ را بی خیال شد چون به هر حال هر بار k تقسیم بر دو می شود و بعد منهای یک می شود پس به هر حال چون بر ۲ تقسیم می شود مرتبه را خیلی کم و لگاریتمی می کند و اون منهای یک تاثیر چندانی ندارد و اگر معادله را به صورت زیر در نظر بگیریم:
[tex]G(k)<4G(\frac{k}{2}) k^2[/tex]
مرتبه ی G کمتر از [tex]k^2\log k[/tex]
بنابراین مرتبه ی f کمتر از [tex]\log^2n\ast\log\log n[/tex] خواهد بود
اما یه احتمال دیگه هم هست این که بگیم اگر معادله ی G به صورت
[tex]G(k)=4G(\frac{k}{2}) K^2[/tex] می بود اونوقت از مرتبه ی [tex]k^2\log k[/tex] می شد چون از قضیه مستز مزتبه ی اون بازگشت کسری با [tex]k^2[/tex] برابر می شد پس باید تو یه لگاریتم ضرب می کردیم
ما این جا معادله ی g اون بازگشت کسری ش کمتره پس مرتبه ی بازگشت کسری آن از [tex]k^2[/tex] کمتر است پس نیازی به ضرب کردن تو لگاریتم نداره پس از مرتبه [tex]k^2[/tex] است
به نظر من بهترین جواب اینه که بگیم [tex]\log^2n<=T(n)<\log^2n\ast\log\log n[/tex]
ارسال: #۳
RE: تغییر متغیر
(۱۹ مهر ۱۳۹۳ ۰۳:۰۶ ق.ظ)fatemeh69 نوشته شده توسط: به جای n می ذاریم [tex]3^k[/tex]چرا بجای n گذاشتید [tex]3^k[/tex] ؟
اونوقت معادله به فرم زیر در میاد
[tex]T(3^k)=4T(\frac{\sqrt{3^k}}{3}) \log^2{3^k}=4T(3^{\frac{k}{2}-1}) k^2\log^23[/tex]
[tex]G(k)=4G(\frac{k}{2}-1) k^2[/tex]
.......
به نظر من بهترین جواب اینه که بگیم [tex]\log^2n<=T(n)<\log^2n\ast\log\log n[/tex]
تو کتاب پارسه اینجوری نوشته:
اگر m = logn پس [tex]n=2^m[/tex]
[tex]T(2^m)=4T(2^{\frac{m}{2}}) m^2[/tex]
حالا [tex]S(m)=T(2^m)[/tex] :
[tex]S(m)=4S(\frac{m}{2}) m^2[/tex]
بعد با قضیه اصلی (master) حلش میکنه و در آخر به همون جواب شما رسیده.
[tex]T(n)=\theta(\log^2n\: \log\log n)[/tex]
من میخواستم ببینم با مخرج ۳ چیکار کرده؟
اگه ممکنه هم اینو جواب بدید هم روش خودتون رو توضیح بدید.
ارسال: #۴
RE: تغییر متغیر
(۲۰ مهر ۱۳۹۳ ۰۱:۴۷ ب.ظ)Aurora نوشته شده توسط:(19 مهر ۱۳۹۳ ۰۹:۳۷ ق.ظ)Ametrine نوشته شده توسط: چرا بجای n گذاشتید [tex]3^k[/tex] ؟
تو کتاب پارسه اینجوری نوشته:
اگر m = logn پس [tex]n=2^m[/tex]
[tex]T(2^m)=4T(2^{\frac{m}{2}}) m^2[/tex]
حالا [tex]S(m)=T(2^m)[/tex] :
[tex]S(m)=4S(\frac{m}{2}) m^2[/tex]
بعد با قضیه اصلی (master) حلش میکنه و در آخر به همون جواب شما رسیده.
[tex]T(n)=\theta(\log^2n\: \log\log n)[/tex]
من میخواستم ببینم با مخرج ۳ چیکار کرده؟
اگه ممکنه هم اینو جواب بدید هم روش خودتون رو توضیح بدید.
مطمئنید مخرج سوال ۳ بوده؟ اگر این طوری حل کرده شاید مخرج سوال ۲ بوده!
آره ، ۳ نوشته. اگه امکانش بود عکس میذاشتم : )
شاید اشتباه شده!
۰
ارسال: #۵
RE: تغییر متغیر
احتمالا اشتباه نوشته شده و اصلا مخرجی نداشته ببنید من به این خاطر ۳ به توان k گذاشتم که وقتی تقسیم بر ۳ می شود تنها تغییرش این باشد که یکی از توان سه کم شود و فرم بدی پیدا نکند و به همان فرم سه به توان یه چیزی باشد
ارسال: #۶
RE: تغییر متغیر
(۲۱ مهر ۱۳۹۳ ۰۱:۳۴ ق.ظ)fatemeh69 نوشته شده توسط: احتمالا اشتباه نوشته شده و اصلا مخرجی نداشته ببنید من به این خاطر ۳ به توان k گذاشتم که وقتی تقسیم بر ۳ می شود تنها تغییرش این باشد که یکی از توان سه کم شود و فرم بدی پیدا نکند و به همان فرم سه به توان یه چیزی باشد
سلام.حالتون خوبه؟؟؟؟
این سوال برای سال ۸۸ هستش صورت سوال هم کاملا درسته
من به دو روش حل این سوال رو دیدیم.هم تغییر متغیر دو به توان ان هم تغییر متغیر توان سه به توان ان
ارسال: #۷
RE: تغییر متغیر
(۲۱ مهر ۱۳۹۳ ۰۲:۱۵ ب.ظ)Aurora نوشته شده توسط:(21 مهر ۱۳۹۳ ۰۹:۵۷ ق.ظ)miladcr7 نوشته شده توسط:(21 مهر ۱۳۹۳ ۰۱:۳۴ ق.ظ)fatemeh69 نوشته شده توسط: احتمالا اشتباه نوشته شده و اصلا مخرجی نداشته ببنید من به این خاطر ۳ به توان k گذاشتم که وقتی تقسیم بر ۳ می شود تنها تغییرش این باشد که یکی از توان سه کم شود و فرم بدی پیدا نکند و به همان فرم سه به توان یه چیزی باشد
سلام.حالتون خوبه؟؟؟؟
این سوال برای سال ۸۸ هستش صورت سوال هم کاملا درسته
من به دو روش حل این سوال رو دیدیم.هم تغییر متغیر دو به توان ان هم تغییر متغیر توان سه به توان ان
اگر امکان داره جواب با تغییر متغیر دو رو هم بزارید.
فکر کنم منظورشون همون روشی هست که من از کتاب پارسه گذاشتم.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close