
48
|
第
3
章
throw new NoSuchElementException("No Max Element in Empty Array.");
}
return maxElement(vals, 0, vals.length);
}
/**
计算
vals[left, right)
的最大元素
*
注意
vals[right]
并不在计算之列
*/
static int maxElement(int[] vals, int left, int right) {
if (right - left == 1) {
return vals[left];
}
//
计算子问题
int mid = (left + right) / 2;
int max1 = maxElement(vals, left, mid);
int max2 = maxElement(vals, mid, right);
//
合并处理
:
从子问题的解中得到当前问题的解
if (max1 > max2) { return max1; }
return max2;
}
例
3-2
中分治算法的时间复杂度是
O
(
n
)
,因为子问题解的合并处理在常数时间内就能完
成。如果这一步需要
O
(
n
)
时间,那么整体的时间复杂度将会上升至
O
(
n
log
n
)
。当然
,
我们也可以不用分治算法,直接遍历数组并且记下当前所找到的最大值。所以,就当是
一个小小的提示吧:分治算法并不总是最快的。
3.6.3 动态规划
动态规划是分治算法的一个衍生,它将一个问题切分成多个更加简单的子问题,然后按 ...