Рассчитать большую тета, привязанную к двум рекурсивным вызовам

Question

T (m, n) = 2T (m/2, n) + n, предположим, что T (m, n) является постоянным, если либо m < 2 или n Так что Я не понимаю, может ли эта проблема быть решена с помощью Мастер-теоремы? Если да, то как? Если нет, правильно ли эта таблица?

level # of instances size cost of each level total cost 
0    1  m, n   n    n 
1    2  m/2, n   n    2n 
2    4  m/4, n   n    4n 
i    2^i m/(2^i), n   n    2^i * n 
k    m  1, n   n    n*m 

Спасибо!

Answer 1

Мастер теорема может быть немного излишним здесь и ваш метод решения не плохо (log означает logarithmus базировать 2, c=T(1,n)):

T(m,n)=n+2T(m/2,n)=n+2n+4T(m/4,n)=n*(1+2+4+..+2^log(m))+2^log(m)*c 
     =n*(2^(log(m)+1)-1)+m*c=Theta(n*m) 

Если вы используете мастер теорему обработки n как константа, вы легко получите T(m,n)=Theta(m*C(n)) с константой C в зависимости от n, но в Мастер-теореме вам не расскажет об этой константе C. Если вы слишком умными и невнимательными вы можете легко получить ожог:

T(m,n)=n+2T(m/2,n)=n*(1+2/nT(m/2,n))=n*Theta(2^(log(m/n))) 
     =n*Theta(m/n)=Theta(m) 

И теперь, потому что вы оставили из C(n) на третьем этапе, вы получили неправильный результат!