تالار گفتمان مانشت

وقتی پیچیدگی زمانی یک تابع رو با (T (n نمایش میدیم، منظورمون بدست آوردن مقدار تابع نیست، بلگه تعداد دفعات تکرار تابع هست.

خوب خالا سوال من اینه:
اگر تابع ما از پیچیدگی زمانی (T (n-1) X T (n-1 داشته باشه. منظور این هست که در هر Tn تابع ذوبار T n-1 خواهد بود یعنی تشکیل یک درخت دودویی کامل میده با مرتبه زمانی (O (2^n و یا منظور این هست که باید مقادیر (T (n-1 در T n-1 بشه؟

توی کتاب (مقسمی صفحه 26) گفته شده (T (n-1) X T (n-1 داری پیچیدیگی زمانی (O (2^n هست. اگر اینطوره یعنی تفاوتی نمی کنه عملگر بین (T (n ها ضرب باشه یا جمع؟

چون برای (T (n-1) + T (n-1 هم پیچیدگی زمانی (O (2^n هست.

منظور محاسبه تعداد جملات هستش،مثلا برای ضرب همون قد باید تعداد جملات رو محاسبه کرد که برای جمع باید محاسبه کرد،دیگه کاری به این که مقدارش چقد میشه نداریم.امیدوارم متوجه شده باشید

نه عزیزم t(n-1) + t(n-1) میشه O(n)

(T(N-1)+T(N-1 یعنی به ازای هر N . تابع T دوبار خودش را فراخوانی میکند پس برابر است با (۲T(N-1 و از مرتبه [tex]2^{\tfrac{N}{1}}[/tex]

ولی برای تابعی مثل (۲T(N-1 چون برای هر N رTیکبار خودش را فراخوانی میکند پس برابر است با( T(N-1 از مرتبه ( O(N

(10 مهر 1391 10:27 ق.ظ)m_sardaari نوشته شده توسط: [ -> ](T(N-1)+T(N-1 یعنی به ازای هر N . تابع T دوبار خودش را فراخوانی میکند پس برابر است با (۲T(N-1 و از مرتبه [tex]2^{\tfrac{N}{1}}[/tex]

ولی برای تابعی مثل (۲T(N-1 چون برای هر N رTیکبار خودش را فراخوانی میکند پس برابر است با( T(N-1 از مرتبه ( O(N

من نمی فهمم اصلا مگه (T(N-1)+T(N-1 با (۲T(N-1 فرق داره ؟اگه درخت بازگشتی اش رو بکشیم که عین همن.مرتبه اش هم این نمی شه

(09 مهر 1391 07:58 ب.ظ)kiantamar نوشته شده توسط: [ -> ]وقتی پیچیدگی زمانی یک تابع رو با (T (n نمایش میدیم، منظورمون بدست آوردن مقدار تابع نیست، بلگه تعداد دفعات تکرار تابع هست.

خوب خالا سوال من اینه:
اگر تابع ما از پیچیدگی زمانی (T (n-1) X T (n-1 داشته باشه. منظور این هست که در هر Tn تابع ذوبار T n-1 خواهد بود یعنی تشکیل یک درخت دودویی کامل میده با مرتبه زمانی (O (2^n و یا منظور این هست که باید مقادیر (T (n-1 در T n-1 بشه؟

توی کتاب (مقسمی صفحه ۲۶) گفته شده (T (n-1) X T (n-1 داری پیچیدیگی زمانی (O (2^n هست. اگر اینطوره یعنی تفاوتی نمی کنه عملگر بین (T (n ها ضرب باشه یا جمع؟

چون برای (T (n-1) + T (n-1 هم پیچیدگی زمانی (O (2^n هست.

به نظرم [tex]T(n)[/tex] یعنی زمان اجرای الگوریتم و نه تعداد دفعات تکرار ,مثلا[tex]T(n)=2T(n-1)[/tex] یعنی زمان اجرای [tex]T(n-1)[/tex] رو حساب کن در 2 ضرب کن و همه میدونیم [tex]2T(n-1)=T(n-1) T(n-1)[/tex] و حاصل عبارت [tex]T(n-1)*T(n-1)[/tex] برابر [tex](T(n-1))^{2}[/tex] می شود و همونطور که میدونید [tex]T(n)=2T(n-1) 1[/tex] مسئله برج هانوی است که در کتاب های یوسفی و مقسمی با جایگذاری حل شده است ولی آیا [tex](T(n-1))^{2}[/tex] با جایگذاری قابل حله؟و یا با هر روش دیگه ای؟اگه کسی حل کرد لطفا حلشو بزاره.من هیچ مثالی برای ضرب دو عبارت زمان اجرای الگوریتم ندیم در کتاب CLRS.
اما ما همیشه عباراتی مثل [tex]T(n)=aT(n-b)[/tex] و یا [tex]T(n)=aT(\tfrac{n}{b})[/tex] داریم این دو فرمول هم در کتابها به این صورت پاسخ داده شدند که[tex]\theta (a^{\frac{n}{b}})[/tex] برای نوع اول و برای نوع دوم معمولا از قضیه master استفاده میشود.

(10 مهر 1391 05:55 ب.ظ)m_gh نوشته شده توسط: [ -> ]

(10 مهر 1391 10:27 ق.ظ)m_sardaari نوشته شده توسط: [ -> ](T(N-1)+T(N-1 یعنی به ازای هر N . تابع T دوبار خودش را فراخوانی میکند پس برابر است با (۲T(N-1 و از مرتبه [tex]2^{\tfrac{N}{1}}[/tex]

ولی برای تابعی مثل (۲T(N-1 چون برای هر N رTیکبار خودش را فراخوانی میکند پس برابر است با( T(N-1 از مرتبه ( O(N

من نمی فهمم اصلا مگه (T(N-1)+T(N-1 با (۲T(N-1 فرق داره ؟اگه درخت بازگشتی اش رو بکشیم که عین همن.مرتبه اش هم این نمی شه

بله فرق داره (T(N-1)+T(N-1 همینطور که میبینید T دوبار فراخوانی شده یه یکبار برای هر کدام از T(N-1) ها پس کلا دوبار در هر فراخوانی t.

ولی (۲T(N-1 هر بار که بخوایم t رو فرواخوانی کنیم فقط یک بار فراخوانی میشه.شما نمیخواین مقدار رو محاسبه کنید فقط میخواید مرتبه رو حساب کنید پس معیار اینه که در هر فراخوانی ]چندبار تابع فراخوانی میشه و در چه زمانی.

مهم اینه که چطور و چند بار t خودشو رو فراخوانی کنه

(11 مهر 1391 08:48 ق.ظ)m_sardaari نوشته شده توسط: [ -> ]

(10 مهر 1391 05:55 ب.ظ)m_gh نوشته شده توسط: [ -> ]

(10 مهر 1391 10:27 ق.ظ)m_sardaari نوشته شده توسط: [ -> ](T(N-1)+T(N-1 یعنی به ازای هر N . تابع T دوبار خودش را فراخوانی میکند پس برابر است با (۲T(N-1 و از مرتبه [tex]2^{\tfrac{N}{1}}[/tex]

ولی برای تابعی مثل (۲T(N-1 چون برای هر N رTیکبار خودش را فراخوانی میکند پس برابر است با( T(N-1 از مرتبه ( O(N

من نمی فهمم اصلا مگه (T(N-1)+T(N-1 با (۲T(N-1 فرق داره ؟اگه درخت بازگشتی اش رو بکشیم که عین همن.مرتبه اش هم این نمی شه

بله فرق داره (T(N-1)+T(N-1 همینطور که میبینید T دوبار فراخوانی شده یه یکبار برای هر کدام از T(N-1) ها پس کلا دوبار در هر فراخوانی t.

ولی (۲T(N-1 هر بار که بخوایم t رو فرواخوانی کنیم فقط یک بار فراخوانی میشه.شما نمیخواین مقدار رو محاسبه کنید فقط میخواید مرتبه رو حساب کنید پس معیار اینه که در هر فراخوانی ]چندبار تابع فراخوانی میشه و در چه زمانی.

مهم اینه که چطور و چند بار t خودشو رو فراخوانی کنه

درسته با هم فرق دارن .ولی هنوز نفهمیدم چه جوری (O (2^n می شه ؟اگه دوبارهم فراخوانی کنی با درخت بازگشتی می شه جمع چندتاn!؟

[tex]t(n)=2t(n-1)[/tex]

[tex]r-2=0[/tex]

[tex]r=2[/tex]

[tex]o(2^{n})[/tex]

دوستمون ahp89 راه حل این شکل توابع رو گفتن

این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)

[tex]n=2^{k}\Rightarrow k=logn[/tex]

[tex]T(2^{K})=2T(2^{K-1}) 2^{K}-1[/tex]
[tex]T(K)=2T(K-1) 2^{K}-1[/tex]
حالا اینو حل میکنیم

---

[tex](k-2)^{_{2}}[/tex]
[tex]c_{1}2^{^{k}} c_{2}k2^{^{k}}[/tex]
:[tex]k=logn[/tex]حالا داشتیم[tex]c_{1}n^{log2} c_{2}logn*n[/tex]

(09 مهر 1391 11:37 ب.ظ)مورتن نوشته شده توسط: [ -> ]نه عزیزم t(n-1) + t(n-1) میشه O(n)

دوست گرامی، اون t(n/2)+t(n/2) هست که میشه teta(n) که برحسب فرمول زیر بدست میاد:

ضمنا کتاب مقسمی بدرد نمی خوره و اشتباه زیاد داره ، اثبات غلط بودن یکبار فراخوانی و دوبار فراخوانی هم بعدا بحث می کنم اگه هم اشتباه کردم اقرار خواهم کرد.
اما توی کتاب CLRS حل مسائل آورده t_n=1 + t_n minus 1 + t_n minus 1 =1+ 2 t_n minus 1 =order_(2^n) minus 1
==
(T (n-1) X T (n-1 هم جوابش میشه order_n^2 که دوستمون بهش اشاره داشتن.
==
در کتاب هادی یوسفی(پوران) داریم :
t_n =2t(n/2)+n = (1+lgn)*n
و داریم:
(t_n=2t(n/2) +logn! =n*log^2(n
==
اگر کسی تا اینجای کار حرفامو قبول داره دکمه ی سپاس رو بزنه.