拉斯維加斯算法運行時分析

在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

拉斯維加斯算法運行時分析

回答

相關問題