漸近複雑さのための多変量方程式を解く

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）$ x です。しかし、変数 $ 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）+ 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} 言い換えると、 $$ t（2 ^ a、2 ^ b）= \ begin {ケース} 2 ^ {B + 1} - （B + 2）＆\ text {if} a \ geq b、\\ （B + 2）（2 ^ A-1） - A2 ^ A＆\テキスト{if} b \ geq a。 \ end {ケース} $$ $ m \ geq n $ の場合、これは $ t（m、n）=theta（n）$ 、 $ n> m $ の場合、 $ t（m、n）=theta（m \ log（n / m）+ m）$ 。