Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
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 动态规划
动态规划是分治算法的一个衍生,它将一个问题切分成多个更加简单的子问题,然后按 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221