清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 ·但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时,有些子问题被重复计算了许多次。 T(n) T424和2424)TAA4如2)Ta4(4厂(4)T白4(a44Ja4 • 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时，有些子问题被重复计算了许多次。 算法总体思想 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4)