Решение многомерного уравнения для асимптотической сложности

Question

У меня есть функция $ f (m, n) $ со временным сложностью $ t (m, n) $ характеризуется отношением рецидива

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

Я вижу, что для фиксированного $ m $ , это $ O (n) $ ,И для фиксированного $ n $ , это $ O (M) $ .Но я не вижу, как я могу получить выражение, которое характеризует производительность с точки зрения переменной $ m $ и $ n$ .

Как я могу решить это, чтобы найти асимптотическую сложность с точки зрения $ m $ и $ n $ ?

Answer 1

Предположим, что простота, что $ m= 2 ^ a $ , $ 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) $ и используя эту обозначение, которое мы получаем \ begin {align} T (2 ^ a, 2 ^ b) &= b + 2 (b-1) + 4 (b-2) + \ cdots + 2 ^ {c-1} (b-c + 1) \\ &= (1 + 2 + \ CDOT + 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} Другими словами, $$ T (2 ^ a, 2 ^ b)= \ начать {случаи} 2 ^ {b + 1} - (b + 2) & \ text {Если} a \ geq b, \\ (B + 2) (2 ^ A-1) - A2 ^ A & \ Text {Если} b \ geq a. \ end {случаи} $$ Когда $ m \ geq n $ , это дает $ t (m, n)=theta (n) $ , а когда $ n> m $ , мы получаем $ t (m, n)=theta (m \ Журнал (N / M) + M) $ .