حل معادلة متعددة المتغيرات للتعقيد مقارب

Question

لدي وظيفة $ f (m، n) $ مع الوقت تعقيد $ t (m، n) $ تتميز بعلاقة تكرار

$$ \ ابدأ {align} T (M، \ n) &= 2t \ bigl (\ frac {m} {2} {2}، \ frac {n} {2} \ bigr) + c_0 \ log n + c_1. \\ T (M، \ 1) &= t \ bigl (\ frac {m} {2}، 1 \ bigr) + c_1 \\ T (0، \ n) &= 1 \\ T (م، \ 0) &= 1 \ نهاية {محاذاة} $

أستطيع أن أرى ذلك للحصول على $ m $ ، هذا $ O (n) $ ،ولأداة الثابتة $ n $ ، هذا $ O (M) $ .لكنني لا أرى كيف يمكنني الحصول على تعبير يميز الأداء من حيث المتغير $ m $ و $ n$ .

كيف يمكنني حل هذا للعثور على التعقيد الزائد من حيث $ m $ و $ n $ ؟

Answer 1

لنفترض للبساطة أن $ m= 2 ^ $ $ ، $ n= 2 ^ b $ ، $ c_0= 1 $ ، $ c_1= 0 $ ، والحالات الأساسية هي $ t (1، \ cdot)= t (\ cdot، 1)= 0 $ . ثم $$ T (2 ^ a، 2 ^ b)= 2T (2 ^ {a-1}، 2 ^ {b-1}) + b= 4t (2 ^ {a-2}، 2 ^ {b-2}) + B + 2 (B-1)=cdots $ عدد الأسفناد هو $ c=min (a، b) $ ، واستخدام هذه التدوين نحصل عليه \ ابدأ {align} T (2 ^ a، 2 ^ b) &= b + 2 (b-1) + 4 (b-2) + \ cdots + 2 ^ ^ {c-1} (b-c + 1) \\ &= (1 + 2 + CDOTS + 2 ^ ^ {c-1}) B - 2 ^ 1 (1) - 2 ^ 2 (2) - \ cdots - 2 ^ ^ {c-1} (c-1) \\ &= (2 ^ c-1) b - 2 ^ c c + 2 (2 ^ c-1) \\ &= 2 ^ C (B + 2-C) - (B + 2). \ END {محاذاة} بعبارات أخرى، $$ ر (2 ^ أ، 2 ^ ب)= \ ابدأ {الحالات} 2 ^ {b + 1} - (b + 2) & \ text {if} a \ geq b، \\ (B + 2) (2 ^ A-1) - A2 ^ A & \ Text {IF} B \ GEQ A. \ نهاية {الحالات} $ عندما $ m \ geq n $ ، وهذا يعطي $ t (m، n)=theta (n) $ ، وعند $ n> m $ ، نحصل على $ t (m، n)=theta (m \ سجل (n / m) + m) $ .