PDF《(19)的解决 *》

3 元素的势 元素 u 的势 C( u) =|r[u]|- |r* [u]|. 其中 r[u]表示 r 中比 u 大的元素的集合, r* [u]表示 r 中比u小的元素的集合. 在算法实现中, 如果先比较势差较小的元素对, 就可能把更多的元素对标记为不需要比较. 以图

2 为例, 图U上的偏序 r, |U|=10, e( r) =252<

28 .如果使用 Wells 算法, 需要比较

25 个元素对, 若 先比较势差小的元素对,则只需要比较

13 个元素

308 对, 运行时间减少了约一半. 3.3.2 需要将偏序加入 Rc 时才查找等价偏序 Wells 算法中, 每次进行比较以后, 首先会在 Rc 中查找 r1 和r2 的等价偏序,目的是希望找到等价偏 序, 从而避免计算 r1 和r2 的线性扩展数. 但实验数据 的统计表明, 找到等价偏序的概率是很小的.以计 算S( 13) 为例, 找到等价偏序的概率约为 1/25, 而计 算S( 19) 时还不到 1/50.但在计算 S( 13) 时, 这个查 找过程占用了总运行时间的 20%以上. 作者对 Wells 算法进行了如下改进: 在一次比较 以后, 直接计算 r1 和r2 的线性扩展数, 只在需要把 r1 或r2 加入 Rc 时, 才检查 Rc 中是否存在等价偏序.实 验表明, 在计算 S( 13) 时, 改进算法使运行时间减少 了20%左右. 3.4 计算 Rc* 的算法 PS 算法 Wells 算法和 Peczarski 算法都是要在所建........