المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:الگوریتم ها:سوال ۳

تحلیل پیچیدگی

نامساوی ‎$T(n) \geq T(a)T(n-a)a(n-a)$‎ به ازای هر ‎$1 \leq a \leq n-1$‎ برقرار است. در ضمن می‌دانیم ‎$T(1)=T(2)=1$‎. ثابت کنید که ‎$T(n) = \Omega(2^{2n}/4n^2)$‎.


ابزار صفحه