Resolvendo uma equação multivariada para complexidade assintótica

Question

Eu tenho uma função $ f (m, n) $ com a complexidade de tempo $ t (m, n) $ caracterizado pela relação de recorrência

$$ \ begin {alinhar} 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 \ final {alinhar} $$

Eu posso ver isso para fixo $ m $ , isto é $ O (n) $ ,e para fixação $ n $ , isto é $ O (m) $ .Mas eu não vejo como posso obter uma expressão que caracteriza o desempenho em termos de variável $ m $ e $ n$ .

Como posso resolver isso para encontrar a complexidade assintótica em termos de $ m $ e $ n $ ?

Answer 1

Suponha a simplicidade que $ m= 2 ^ a $ , $ n= 2 ^ b $ , $ c_0= 1 $ , $ c_1= 0 $ , e os casos de base são $ t (1, \ Cdot)= t (\ Cdot, 1)= 0 $ . Então $$ 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 $$ O número de sumands é $ c=min (A, B) $ e usando essa notação que obtemos \ begin {alinhar} 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). \ final {alinhar} Em outras palavras, $$ T (2 ^ a, 2 ^ b)= \ begin {casos} 2 ^ {B + 1} - (B + 2) & \ Text {\} A \ Geq B, \\ (B + 2) (2 ^ a-1) - A2 ^ a & \ text {\} b \ geq a. \ fim {casos} $$ Quando $ m \ GEQ n $ , isso dá $ t (m, n)=theta (n) $ , e quando $ n> M $ , recebemos $ t (m, n)=theta (m \ log (n / m) + m) $ .