تالار گفتمان مانشت
تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ - نسخه‌ی قابل چاپ

تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ - vijay - 27 بهمن ۱۳۹۰ ۰۱:۵۰ ب.ظ

tn)=3t(n/2)+n^2
پیچیدگی زمانیش؟
طبق قضیه مسترn^2 که میشه f(n)بیشتر از n^1+سیکما میشه یعنی f(n)میشه o برای قضیه مستر ولی تو جواب تست اصلا بود.

مرتبه اجرایی -تست ۹۱ - mfXpert - 27 بهمن ۱۳۹۰ ۰۳:۱۰ ب.ظ

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

RE: مرتبه اجرایی -تست ۹۱ - neilabak - 27 بهمن ۱۳۹۰ ۰۴:۳۰ ب.ظ

(۲۷ بهمن ۱۳۹۰ ۰۳:۴۹ ب.ظ)mehan نوشته شده توسط:  
(27 بهمن ۱۳۹۰ ۰۳:۱۷ ب.ظ)saeedeh123 نوشته شده توسط:  
(27 بهمن ۱۳۹۰ ۰۳:۱۲ ب.ظ)euruse نوشته شده توسط:  می شه O(n^2)

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

مرتبه اجرایی -تست ۹۱ - vijay - 27 بهمن ۱۳۹۰ ۰۴:۴۱ ب.ظ

چرا قضیه ۳ من اول n^2 زدم بعد پاک کردم
راست میگه neilabak
N^2 logN البته اینو اشتباه میگه

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

RE: مرتبه اجرایی -تست ۹۱ - neilabak - 27 بهمن ۱۳۹۰ ۰۷:۱۰ ب.ظ

(۲۷ بهمن ۱۳۹۰ ۰۴:۴۱ ب.ظ)vijay نوشته شده توسط:  چرا قضیه ۳ من اول n^2 زدم بعد پاک کردم
راست میگه neilabak
N^2 logN البته اینو اشتباه میگه

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

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

مرتبه اجرایی -تست ۹۱ - shabgard - 27 بهمن ۱۳۹۰ ۰۷:۵۸ ب.ظ

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

RE: مرتبه اجرایی -تست ۹۱ - Mohammad-A - 30 بهمن ۱۳۹۰ ۱۰:۰۲ ب.ظ

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

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

RE: مرتبه اجرایی -تست ۹۱ - لهمشد - ۱۵ اسفند ۱۳۹۰ ۰۶:۳۴ ب.ظ

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