未知概率的計算複雜度

-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

未知概率的計算複雜度

回答

相關問題