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

tn)=3t(n/2)+n^2
پیچیدگی زمانیش؟

---

طبق قضیه مسترn^2 که میشه f(n)بیشتر از n^1+سیکما میشه یعنی f(n)میشه o برای قضیه مستر ولی تو جواب تست اصلا بود.

فکر می کنم حالت سه قضیه مستر باشه که مرتبه ش هم تتای n^2 خواهد بود

(27 بهمن 1390 03:49 ب.ظ)mehan نوشته شده توسط: [ -> ]

(27 بهمن 1390 03:17 ب.ظ)saeedeh123 نوشته شده توسط: [ -> ]

(27 بهمن 1390 03:12 ب.ظ)euruse نوشته شده توسط: [ -> ]می شه O(n^2)

منم n^2 زدم

منم زدم n^2

ولی جوابا که O نبود! همش امگا بود که فقط یکیش با امگا درست میشد اونم N^2 logN بود

چرا قضیه 3 من اول n^2 زدم بعد پاک کردم

---

راست میگه neilabak

---

N^2 logN البته اینو اشتباه میگه

---

به خاطر 1+اپسیلن.

(27 بهمن 1390 04:41 ب.ظ)vijay نوشته شده توسط: [ -> ]چرا قضیه ۳ من اول n^2 زدم بعد پاک کردم

---

راست میگه neilabak

---

N^2 logN البته اینو اشتباه میگه

---

به خاطر ۱+اپسیلن.

یعنی چی ؟یعنی n2 میشده بالاخره؟یا n2logn

این تست رو عینشو من ده بار تو ده جای مختلف زدم
میشه N^2
شک نکنید

هم از قضیه‌ی اصلی میشه رفت و هم تعمیم قضیه‌ی اصلی.
[tex]T(n)=3T(\left \lfloor \frac{n}{2} \right \rfloor) n^{2}=\Omega (n^2)[/tex]

چرا اُمگا؟ به خاطر اینکه حد پایین این تابع بازگشتی رو داریم برمی‌داریم.

سلام :
منم این سوال رو n^2 اوردم .فکر کنم n^2درست باشه