前提：

拉斯维加斯属于概率算法的一种，那么对于概率算法就需要了解概率算法的特点和概率算法和确定性算法的区别。

我理解的概率算法和确定性算法的区别：

确定性算法对于每个输入实例的执行步骤，执行结果都是一定的。但概率算法是不定的。对于确定性算法有“平均执行时间”，对于概率算法有“期望执行时间”。

平均执行时间：输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间。

期望执行时间：反复解同一个输入实例所花的平均时间。

概率算法的特点：

1.不可再现性：在同一个输入实例上，每次执行结果不尽相同。

2.分析困难:要求又概率论，统计学和数论的知识。

Las Vegas算法是概率算法的一种。

特点：算法获得的答案必定正确，但有时它仍根本就找不到答案。找不到答案时或者说陷入僵局时，可以重复运行算法，每次都有独立的机会求出解。所以成功的概率随着执行时间的增加而增加。

Las Vegas算法一般能比确定性算法更有效率，夸张的时候甚至是对于每一个输入实例都是如此。但它大的缺点是：算法的时间上界可能不存在，并且是在排除较小实例和特别好使的实例概率很小从而忽略不计的这两情况下，算法的时间上界不存在。

可以采用LV(x,y,success)来表示算法运行。

x:输入实例;

y:返回参数;

success:布尔值，true表示成功，false表示失败。

对于LV算法有如下定义：

p(x):对于实例x，算法成功的概率

s(x):算法成功时的期望时间

e(x):算法失败时的期望时间

由于LV算法并不是每次都能求解出解。所以有顽固算法，知道求解出解为止，该算法如下：

Obstinate(x){

repeat LV(x,y,success);

until success;

return y;

}

那么如果用t(x)来表示Obstinate算法找到一个正确解的期望时间。则

解释一下就是：t(x):找到正确解的期望时间，但是LV算法会有概率失败，那么找到正确解的期望时间就等于成功的概率乘以成功的期望时间+失败的概率乘（失败的期望时间+下一次正确解的期望时间）。由于下一次正确解的期望时间和这一次之间时完全独立的，所以也是t(x)。

Las Vegas算法的应用：皇后问题。