未知概率的计算复杂度

-3

假设有一份工作，并且有许多工人可用。下面的代码可能是一个糟糕的优化想法。但它只是为了分析复杂性。未知概率的计算复杂度

A is a set of N worker 
while (A is not empty) 
{ 
    B=empty set 
    foreach a1 in A 
    { 
    foreach a2 in A 
    { 
     b= merge(a1, a2) 
     if (b works better than a1 **and** b works better than a2) 
      add b to B 
    } 
    } 
    A=B 
}

问题是，“b比a1和a2好”的概率是未知的。那么，如何估计上面代码的时间复杂度呢？

来源

2016-05-03 Yumi F

什么是'合并（）'，什么是'B'？ – fjardon

看起来像恒定时间的操作。所以这没关系。 –

@Nico Schertler。感谢您指出问题。我纠正了代码，A在while循环内更新。合并（）表示a1和a2合并为一组工作人员。也就是说，'A'最初包含一群单身工人。然后，'A'逐渐包含更大的群体。假设复杂度被计为'if'语句的数量。 –

-1

对于两个内部循环，复杂度与概率无关，“b比a1和a2更好”。
但是，代码似乎有点破，因为我没有发现有退出，而循环。不考虑而循环，时间复杂性将是

O（A1 * A2）= O（N^2）。

递推方程将是

T（N）= T（N-1）+ C

来源

2016-05-07 02:48:00

未知概率的计算复杂度

回答

相关问题