厦门大学---算法分析研讨——6.ppt

Ｎ后问题 整数因子分解 整数因子分解 用于整数因子分割的split算法 private static void split(n) { 　int m = (int)Math.floor(Math.sqrt((double)n)); for(int i=2;i=m;i++) if(n%i==0) return I; return 1; } 分析 分析 对于解整数因子分解问题，目前还没有找到多项式时间算法； 算法split(n)是对1~x的所有整数进行试除而得到范围在1~x2的任意整数的因子分割； 基于拉斯维加斯算法的整数因子分解问题求解方案 Pollard算法——用split(n)算法相同的工作量可以得到在在1~x４范围内整数的因子分割． 实例说明 线性时间选择 跳跃表 线性时间选择 跳跃表 线性时间选择 线性时间选择 问题所在：选择合适的划分基准 对于选择问题，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。 舍伍德型选择算法 随机选择一个组元素作为划分基准，既保证算法的线性时间平均性能，又可以避免计算中位数的麻烦。 Select算法分析 Select算法分析 如何得到？ 考虑这种情况：无论n是奇数还是偶数，T(n/2)都出现2次 结论 结论 非递归的舍伍德型选择算法Select可以在O(n)平均时间内找出ｎ个输入元素中的第ｋ小元素 提示 对于某些确定性算法，可以将其改造成舍伍德算法，使得该算法以高概率对任何实例均有效。 对于某些不能直接改造的情况，可以借助预处理技术，不改变原有的确定性算法，而仅对其输入元素进行随机洗牌，同样可以收到舍伍德算法的效果。 线性时间选择 跳跃表 跳跃表 跳跃表 如果用有序链表来表示一个含有ｎ个元素的有序集合Ｓ，则在最坏情况下，有哪些信誉好的足球投注网站Ｓ中的一个元素需要Ω(n)计算时间。为了跳高效率，可以在部分结点处增加附加指针来提高有哪些信誉好的足球投注网站性能（借助这些附加指针，可以跳过链表中的若干结点，从而加快有哪些信誉好的足球投注网站速度）。这种增加了向前附加指针的有序链表称为跳跃表。 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 举例说明 没有附加指针的有序链表 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 增加附加指针后的有序链表——跳跃表 如何进行有哪些信誉好的足球投注网站？ ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 问题：如何在该跳跃表中有哪些信誉好的足球投注网站元素８？ 如何在该跳跃表中有哪些信誉好的足球投注网站元素８？ ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 元素８位置 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 元素８位置 ？ 元素８不在集合Ｓ中 有序链表?跳跃表 存在的问题 应在哪些结点增加附加指针，增加多少？ ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 随机算法的引入 解决方案 采用随机化方法来确定附加指针的增加结点位置和数量。使得跳跃表可以在O(logn)平均时间内支持关于有序集的有哪些信誉好的足球投注网站、插入和删除等运算操作。 实现方案参看教材256 ２ ３ ５ ７ ＮＩＬ 11 13 17 19 23 0 1 2 如何保持附加指针的平衡性，如何随机生成新插入结点的级别 附加指针的平衡性 可用于指导附加指针的设置 解决方案 具体实现说明请参看教材page254 随机生成新插入结点的级别 解决方案 在完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针 方案 事先确定一个实数p(0p1)，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例为p。 在插入一个新结点时，先将其结点级别初始化为0，然后随机反复产生一个[0，1]间的随机实数q。 如果qp，则使新结点级别增加1，直到q=p为止。 为避免出现过大的结点级别，用log1/pn作为新结点级别的上界 ——参看教材255 跳跃表的算法实现 跳跃表的算法实现 参看教材259 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 拉斯维加斯算法 拉斯维加斯算法(Las Vegas) 能够显著改进算法的有效性，对某些目前还找不到有效算法的问题，也能得到较为满意的算法 不会得到不正确的解，但有时找不到问题的解　 通常用boolean型方法来表示拉斯维加斯算法 找到解，返回true; 未找到解，返回false; 此时，可以对同一实例再次调用相同的算法 由随机算法的性质决定 效率分析 Public static void obstinate( Object x, Object y) { 　boole