rambo

主元素与蒙特卡洛

2015年7月1日 ACM解题 0 Comments

问题：在一个长度为n的数组中，如果有超过[n/2]的元素具有相同的值，那么具有这个值的元素叫做数组的主元素。现在要求给出一种算法，在O(n)时间内判定给定数组是否存在主元素。

首先再次介绍蒙特卡洛算法：

在实际应用中常会遇到一些问题，不论采用确定性算法或随机化算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。

性质：

  • 设p是一个实数，且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。
  • 如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。
  • 如果某个解判定问题的Monte-Carlo算法，当返回true时是一定正确的。则这个算法是偏真的。注意，这里没有定义“偏假”，因为“偏假”和偏真是等价的。因为只要互换算法返回的true和false，“偏假”就变成偏真了。
  • 有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。可以通过下面的例子来理解这句话。

对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出现频次最高的解即可。

如果重复调用一个一致的(1/2+\epsilon)正确的蒙特卡罗算法2m-1次，得到正确解的概率至少为1-\delta，其中，

QQ截图20150701234312

对于一个解所给问题的蒙特卡罗算法MC(x)，如果存在问题实例的子集X使得：

(1)当x\in X时，MC(x)返回的解是正确的；

(2)当x\notin X时，正确解是y_{0}，但MC(x)返回的解未必是y_{0}。

称上述算法MC(x)是偏y_{0}的算法。

重复调用一个一致的，p正确偏y_{0}蒙特卡罗算法k次，可得到一个O(1-(1-p)^{k})正确的蒙特卡罗算法，且所得算法仍是一个一致的偏y_{0}蒙特卡罗算法。

对于任何给定的\epsilon>0，算法majorityMC重复调用[log(1/\epsilon] 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于\epsilon。算法majorityMC所需的计算时间显然是O(nlog(1/\epsilon)。

 

回到我们的问题：如果数组中不存在主元素，则结果一定正确，而如果存在，调用一次得到正确结果的概率不低于1/2。由于偏真，在N次调用中只要返回一次True，就可以认为得到正确结果，所以，调用N此得到正确结果的概率不低于1-(1/2)^{N}，可以看到，随着N的增大，这个概率增加很快，只要调用10次，正确率就可以达到99.9%，重要的是，这个正确率和规模无关，即使数组的元素有1千万亿，只需调用10次，正确率依然是99.9%，这就体现出在数组很大时，Monte-Carlo方法的优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "RandomNumber.h"
#include <iostream>
#include <cmath>
using namespace std;
RandomNumber rnd;
//p正确偏y0蒙特卡洛算法
template <typename Type>
bool Majority(Type *T, int n){
// 产生0 ~ n-1 之间的随机整数
int i = rnd.Random(n) + 1;
Type x = T[i];    // 随机选择数组元素
int k = 0;
for(int j = 0; j < n; ++j)
if(T[j] == x)
++k;
return (k > n/2);
}
// 重复调用算法Majority
template <typename Type>
bool MajorityMC(Type *T, int n, double e){
int k = ceil(log(1.0/e) / log(2.0));
for(int i = 1; i <= k; ++i)
if(Majority(T, n))
return true;
return false;
}
 
int _tmain(int argc, _TCHAR* argv[]){
int arr[10] = {3, 5, 7, 6, 9, 3, 3, 1, 3, 3};
        //e为错误概率
cout << MajorityMC(arr, 10, 0.1) << endl;
system("pause");
return 0;
 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifndef RANDOMNUMBER_H
#define RANDOMNUMBER_H
 
 
const unsigned long maxshort = 65535L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
class RandomNumber{
private:
// 当前种子
unsigned long randSeed;
public:
// 构造函数,默认值0表示由系统自动产生种子
RandomNumber(unsigned long s = 0);
// 产生0 ~ n-1之间的随机整数
unsigned short Random(unsigned long n);
// 产生[0, n-1) 之间的随机实数
double fRandom();
};
 
// 产生种子
RandomNumber::RandomNumber(unsigned long s){
if(s == 0)
randSeed = time(0);    //用系统时间产生种子
else
randSeed = s;
}
 
// 产生0 ~ n-1 之间的随机整数
unsigned short RandomNumber::Random(unsigned long n){
randSeed = multiplier * randSeed + adder;
return (unsigned short)((randSeed >> 16) % n);
}
 
// 产生[0, 1)之间的随机实数
double RandomNumber::fRandom(){
return Random(maxshort) / double(maxshort);
}
#endif // RANDOMNUMBER_H

变形：给定有n个数的数组a，其中有超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高效的算法找出这个数。注意，这里已经给定已知条件，肯定存在这个主元素。

解题思想：

基于主元素个数一定多于非主元素个数的性质,主元素的个数减去其他元素的个数肯定大于零。

设a[0]为主元素mainElement,主元素与其他元素个数差值为difference（计数器）,初值为1。通过比较,如下一个元素与mainElement相同,则difference自增1,否则自减1如果为0,则令后继元素为主元素,并重新赋值difference=1。如此遍历最后肯定得到主元素mainE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define N 10
int _tmain(int argc, _TCHAR* argv[]){
int arr[N] = {3, 5, 7, 3, 9, 3, 3, 1, 3, 3};
// 算法的时间复杂度是O(N)
int mainElement = arr[0];
int difference = 1;
int i = 1;
while(i < N){
if(arr[i]==mainElement){  //当前元素与前一个元素相同时
++difference;
}
else{
--difference; //为0,则令<span style="color: #ff0000;">后继元素</span>为主元素
if(!difference){
mainE = arr[i+1];
++i;//注意，这边已经是后继元素了，所以需要再加1
difference = 1;
}
}
++i;
}
cout<<mainE<<endl;
system("pause");
return 0;
 
}

参考：
1、淘宝张洋博客（算法大神） http://www.cnblogs.com/leoo2sk/archive/2009/05/29/1491526.html