拉斯维加斯算法运行时分析

在n个元素的数组中，如果n/2是重复元素而其余元素是不同的，我们可以使用拉斯维加斯算法在o（logn）时间内获得重复元素。拉斯维加斯算法运行时分析

还有另外一个问题：做出这个算法所需的重复次数是多少（即logn），即（n/k个重复元素，其中k =？），如果重复元素是root，什么是运行时间（N）？

如果重复的元素是root（n），我的结果表明它不是o（logn），但是我找不到使用拉斯维加斯算法的这个问题的松散界限。帮助将不胜感激。

2012-04-25 user624438

“拉斯维加斯”不是算法;这是一种算法。显而易见的算法是随机地对元素对进行抽样，直到它们匹配。当阵列有一个重复n/2次的元素时，每对的成功概率为（（n/2）/ n）（（n/2-1）/（n-1））= 1/4-0 （1/n），因此预期运行时间为1 /（1/4-0（1/n））= 4 + 0（1/n）= 0（1）个采样对。

由于这可能是功课，你得到弄清楚如何调整分析不同的重复次数。

来源

2012-04-25 15:24:07 123

P.S .:你可能也需要改进这个算法。 – 123 2012-04-25 15:29:08

我知道拉斯维加斯是一种“算法类型”。这里的结果是次线性的时间界限。这是针对线性有序重复元素而保持的。对于root（n），结果是：-logbase（n）。其中base = {（n * root（n））/（n * root（n）-root（n）+1）} ..这对于n> = 2是有效的。如果你在这里发布不同的结果。这不是一项家庭作业，它只是一个很好的问题，我拿起并想分享。谢谢。 :) – user624438 2012-04-26 10:55:48

拉斯维加斯算法运行时分析

回答

相关问题