Resolviendo una ecuación multivariada para la complejidad asintótica.

Question

Tengo una función $ f (m, n) $ con la complejidad del tiempo $ t (m, n) $ caracterizado por la relación de recurrencia

$$ \ comienzan {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 {align} $$

Puedo ver que para el $ m $ , esto es $ o (n) $ ,y para el $ n $ , este es $ o (m) $ .Pero no veo cómo puedo obtener una expresión que caracteriza el rendimiento en términos de variable $ m $ y $ n$ .

¿Cómo puedo resolver esto para encontrar la complejidad asintótica en términos de $ m $ y $ n $ ?

Answer 1

Supongamos para la simplicidad que $ m= 2 ^ a $ , $ n= 2 ^ b $ , $ c_0= 1 $ , $ c_1= 0 $ , y los casos de base son $ t (1, \ cdot)= t (\ cdot, 1)= 0 $ . Luego $$ 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 $$ El número de sumandos es $ c=min (a, b) $ y usando esta notación que obtenemos \ comienzan {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 {align} En otras palabras, $$ T (2 ^ a, 2 ^ b)= \ comienzan {casos} 2 ^ {B + 1} - (B + 2) & \ Text {if} A \ GEQ B, \\ (B + 2) (2 ^ a-1) - A2 ^ A & \ texto {if} b \ geq a. \ End {casos} $$ Cuando $ m \ geq n $ , esto le da $ t (m, n)=theTa (n) $ , y cuando $ n> m $ , obtenemos $ t (m, n)=theta (m \ log (n / m) + m) $ .