Las Vegas算法第二种定义：永不犯错 In the second approach to defining Las Vegas algorithms we allow the an- swer"?"15 We say that a randomized algorithm A is a Las Vegas algorithm computing a problem F if for every input instance x of F, 多数情况下正 确，且：可以 Prob(A(e)=F(x)》≥2 保持沉默但永 不犯错 Pob(A()=?)=1-Prob(A()=F(》≤2 In this second approach one may consider TimeA(n)as the time complex- ity of A because the nature of this second approacn is to stop after TimeA(x) the (worst case)time complexity of A is TimeA(n)=max {TimeA(x)x is an input of size n}:Las Vegas算法第二种定义：永不犯错 多数情况下正 确，且：可以 保持沉默但永 不犯错