Lösung einer multivariaten Gleichung für asymptotische Komplexität

Question

Ich habe eine Funktion $ F (m, n) $ mit Zeitkomplexität $ t (m, n) $ $ gekennzeichnet durch die Rezidivrasse

$$ \ beginnen {ALIGN} T (m, \ n) &= 2t \ bigl (\ frac {m} {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 (m, \ 0) &= 1 \ end {richten} $$

Ich kann sehen, dass für Fixe $ M $ , dies ist $ o (n) $ ,Und für Fixed $ N $ , ist dies $ o (m) $ .Aber ich sehe nicht, wie ich einen Ausdruck erhalten kann, der die Leistung in Bezug auf Variable $ M $ und $ n auszeichnet$ .

Wie kann ich dies lösen, um die asymptotische Komplexität in Bezug auf $ M $ und $ n $

Answer 1

Angenommen, für die Einfachheit halber, dass $ M= 2 ^ A $ , $ n= 2 ^ B $ , $ c_0= 1 $ , $ C_1= 0 $ , und die Basisfälle sind $ t (1, \ cdot)= t (\ cdot, 1)= 0 $ . Dann $$ T (2 ^ a, 2 ^ b)= 2t (2 ^ {A-1}, 2 ^ {B-1}) + B= 4t (2 ^ {A-2}, 2 ^ {B-2}) + B + 2 (B-1)=CDs $$ Die Anzahl der Summien ist $ C=min (a, b) $ , und verwenden wir diese Notation \ beginnen {ALIGN} T (2 ^ a, 2 ^ b) &= B + 2 (B-1) + 4 (B-2) + \ CDOTS + 2 ^ {C-1} (B-C + 1) \\ &= (1 + 2 + \ CDS + 2 ^ {C-1}) B - 2 ^ 1 (1) - 2 ^ 2 (2) - \ CDs - 2 ^ {C-1} (C-1) \\ & Hat (2 ^ c-1) b - 2 ^ c c + 2 (2 ^ c-1) \\ &= 2 ^ C (B + 2-C) - (B + 2). \ END {ALIGN} Mit anderen Worten, $$ T (2 ^ a, 2 ^ b)= \ begin {cases} 2 ^ {B + 1} - (B + 2) & \ Text {if} a \ geq b, \\ (B + 2) (2 ^ A-1) - A2 ^ A & \ Text {if} b \ geq a. \ ENDE {Hüllen} $$ Wenn $ m \ geq n $ , gibt dies $ t (m, n)=theta (n) $ , und wenn $ n> m $ , erhalten wir $ t (m, n)=theta (m \ Protokoll (n / m) + m) $ .