سلام
دوستان خوب این دو مثال رو بخونید:
![[تصویر: 246509_untitled_2.jpg]](https://img.manesht.ir/246509_untitled_2.jpg)
خوندید؟
مگه در مورد دوم مثل اولی نمیایم به جای رادیکالn بنویسیم n تقسیم بر ۲ و جواب بشه :
[tex]T(n)= T(\frac{n}{2}) T(\frac{n}{2}) n =2T(\frac{n}{2}) n \Rightarrow T(n)= O(nlogn)[/tex]
البته از روش های دیگه جواب درست رو بدست میارم ولی با استدلالی که خودش گفته نه!
ممنون میشم راهنمایی فرمایید.
(۱۶ بهمن ۱۳۹۲ ۰۷:۵۸ ق.ظ)fulgent نوشته شده توسط: سلام
دوستان خوب این دو مثال رو بخونید:
خوندید؟
مگه در مورد دوم مثل اولی نمیایم به جای رادیکالn بنویسیم n تقسیم بر n و جواب بشه :
[tex]T(n)= T(\frac{n}{2}) T(\frac{n}{2}) n =2T(\frac{n}{2}) n \Rightarrow T(n)= O(nlogn)[/tex]
البته از روش های دیگه جواب درست رو بدست میارم ولی با استدلالی که خودش گفته نه!
ممنون میشم راهنمایی فرمایید.
فایل پیوست رو چرا نمیبینم؟؟
(۱۶ بهمن ۱۳۹۲ ۰۸:۲۷ ق.ظ)Good! نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۷:۵۸ ق.ظ)fulgent نوشته شده توسط: سلام
دوستان خوب این دو مثال رو بخونید:
خوندید؟
مگه در مورد دوم مثل اولی نمیایم به جای رادیکالn بنویسیم n تقسیم بر n و جواب بشه :
[tex]T(n)= T(\frac{n}{2}) T(\frac{n}{2}) n =2T(\frac{n}{2}) n \Rightarrow T(n)= O(nlogn)[/tex]
البته از روش های دیگه جواب درست رو بدست میارم ولی با استدلالی که خودش گفته نه!
ممنون میشم راهنمایی فرمایید.
فایل پیوست رو چرا نمیبینم؟؟
حالا دیدم
میگه چون T(n^1/2) خیلی از T(n) کوچیکتره واسه همین حذفش میکنیم!
شما از راه حلهای دیگه چطور به دست میارین؟؟
(۱۶ بهمن ۱۳۹۲ ۰۸:۲۷ ق.ظ)Good! نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۷:۵۸ ق.ظ)fulgent نوشته شده توسط: سلام
دوستان خوب این دو مثال رو بخونید:
خوندید؟
مگه در مورد دوم مثل اولی نمیایم به جای رادیکالn بنویسیم n تقسیم بر n و جواب بشه :
[tex]T(n)= T(\frac{n}{2}) T(\frac{n}{2}) n =2T(\frac{n}{2}) n \Rightarrow T(n)= O(nlogn)[/tex]
البته از روش های دیگه جواب درست رو بدست میارم ولی با استدلالی که خودش گفته نه!
ممنون میشم راهنمایی فرمایید.
فایل پیوست رو چرا نمیبینم؟؟
(۱۶ بهمن ۱۳۹۲ ۰۸:۲۷ ق.ظ)Good! نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۷:۵۸ ق.ظ)fulgent نوشته شده توسط: سلام
دوستان خوب این دو مثال رو بخونید:
خوندید؟
مگه در مورد دوم مثل اولی نمیایم به جای رادیکالn بنویسیم n تقسیم بر n و جواب بشه :
[tex]T(n)= T(\frac{n}{2}) T(\frac{n}{2}) n =2T(\frac{n}{2}) n \Rightarrow T(n)= O(nlogn)[/tex]
البته از روش های دیگه جواب درست رو بدست میارم ولی با استدلالی که خودش گفته نه!
ممنون میشم راهنمایی فرمایید.
فایل پیوست رو چرا نمیبینم؟؟
حالا دیدم
میگه چون T(n^1/2) خیلی از T(n) کوچیکتره واسه همین حذفش میکنیم!
شما از راه حلهای دیگه چطور به دست میارین؟؟
این مثالو از کجا اوردین؟؟
من منظور سوالتون رو نفهمیدم
ولی زمانی که رابطه ما چند بازه ای هست و نمیشه با تغییر متغیر اونو اصلاح کرد ، سعی میکنیم از جملات خود رابطه کمک بگیریم و معمولا سعی میکنیم جملاتی که حد پایین هستند را صرف نظر کنیم و از جملات حد بالاتر به جای اونها استفاده کنیم
ولی یه فرقی بین مثال اول و دوم هست
در مثال اول ، مقدار n/6 و n/3 خیلی از هم دور نیست و میشه به جای n/6 از n/3 استفاده کرد به همین خاطر ۲T(n/3 مینویسیم
ولی در مورد دومی مقدار رادیکال n خیلی پایین تر از n/2 هست (برای nهای خیلی بزرگ) به همین خاطر نمیشه به جای رادیکال n از n/2 استفاده کرد و نمیشه رابطه رابطه را به این شکل خلاصه کرد ۲T(n/2 .
اینکه به جای رادیکال n بذاریم n تقسیم بر n را نفهمیدم یعنی چه. تو مثال اول اصلا چنین کاری نکرده
متشکرم
متوجه شدم
(۱۶ بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)fulgent نوشته شده توسط: متشکرم
متوجه شدم
ببخشید میشه بگین این مثالو از کجا اوردین؟
