■ DANDC的计算时间 若所分成的两个子问题的规模大致相等,则 DANDO总的 计算时间可用递归关系式表示如下: gn) n足够小 T(n 2T(n/2)+f(n)否则 注: T(n):表示输入规模为η的 DANDO计算时间 g(η):表示对足够小的输入规模直接求解的计算时间 f(n):表示 COMBINE对两个子区间的子结果进行合并 的时间 (该公式针对具体问题有各种不同的变形)◼ DANDC的计算时间 若所分成的两个子问题的规模大致相等，则DANDC总的 计算时间可用递归关系式表示如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注： ➢ T(n)：表示输入规模为n的DANDC计算时间 ➢ g(n)：表示对足够小的输入规模直接求解的计算时间 ➢ f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形）