Risolvere un'equazione multivariata per la complessità asintotica

Question

Ho una funzione $ f (m, n) $ con complessità del tempo $ t (m, n) $ caratterizzato dalla relazione di recidiva

$$ \ Begin {allinea} 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 {allinea} $$

Posso vederlo per fisso $ m $ , questa è $ o (n) $ ,e per fisse $ N $ , questa è $ o (m) $ .Ma non vedo come posso ottenere un'espressione che caratterizza le prestazioni in termini di variabile $ m $ e $ n$ .

Come posso risolvere questo per trovare la complessità asintotica in termini di $ m $ e $ N $ ?

Answer 1

Supponiamo di semplicità che $ m= 2 ^ a $ , $ n= 2 ^ B $ , $ c_0= 1 $ , $ c_1= 0 $ , e i casi base sono $ t (1, \ clot)= t (\ cdot, 1)= 0 $ . Poi $$ 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 $$ Il numero di riassunti è $ c=min (a, b) $ , e usando questa notazione che otteniamo \ Begin {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 {allinea} In altre parole, $$ T (2 ^ a, 2 ^ b)= \ Begin {casi} 2 ^ {B + 1} - (B + 2) & \ Text {IF} A \ GeQ B, \\ (B + 2) (2 ^ A-1) - A2 ^ A & \ Text {IF} B \ Geq A. \ end {casi} $$ Quando $ m \ geq n $ , questo dà $ t (m, n)=theta (n) $ e quando $ n> m $ , otteniamo $ t (m, n)=theta (m \ Log (n / m) + m) $ .