
310
|
第
11
章
仔细检查表中最后两列数据,可以看到当
W
= 175
时,近似解是最优解的
60%
。随着
W
的增加,近似解越来越接近最优解,而且比最优解快近
1000
倍。
表
11
-
3
:背包问题衍生算法的性能比较
W
无限背包算法时间 无限背包近似算法时间 最优解 近似解
175 0.00256 0.00011 175 103
351 0.00628 0.00011 351 309
703 0.01610 0.00012 703 618
1407 0.03491 0.00012 1407 1339
2815 0.07320 0.00011 2815 2781
5631 0.14937 0.00012 5631 5562
11263 0.30195 0.00012 11263 11227
22527 0.60880 0.00013 22527 22454
45055 1.21654 0.00012 45055 45011
11.3 并行算法
并行算法通过创建和管理线程,能够更好地利用已有资源。
例
11-4
给出了在第
4
章讨论过的
快速排序
的
Java
实现,这个实现假设
partition
方法
能够根据中枢点将数组分成两个子数组。回忆一下第
4
章,
pivotIndex
左边的值都小于
等于中枢点,而右边的都大于等于中枢点。
例
11-4
:快速排序的
Java
实现
public class MultiThreadQuickSort<E extends Comparable<E>> ...