無限循環的大O？

考慮下面的代碼：上面的代碼無限循環的大O？

int value = 0; 

while(getRandomNumber() != 1000) { 
    value++; 
} 

return value;

會是什麼大O（最壞的情況下，最好的情況和平均情況）？

來源

2016-04-22 user2726225

取決於* some_statment'高度*。 –

如果some_statement不能/不會在循環中改變，那麼是的，整個事情是O（無限） –

向算法中添加隨機化將他們的分析從確定性方法改變爲預期方法。在下面的答案中給出更多細節。 –

在這裏你的問題不會使概率：

例如，迭代你的循環的預期數量由下式給出很多意義。首先，大O符號取決於輸入，這裏根本沒有輸入給你的算法。

執行時間取決於您的getRandomNumber的可能值集合及其基礎分佈。

例如，如果您的RNG從[1 to 100]返回數字 - 算法將永遠不會結束。另一方面，如果它僅以相等的概率產生1000和1001，則平均需要2次迭代才能完成。最糟糕的情況是無限的，但它根本沒有任何意義，因爲它不太可能。

來源

2016-04-22 20:43:40

如果some_statement在循環的整個持續時間內並且保持爲假，那麼，是的，循環是無限的並且具有O（無限）複雜度。但是，一旦some_statement成爲真，迴路將變爲有限。它甚至可以是O（1） - 如果some_statement在開始時爲真，則爲常數。

來源

2016-04-22 19:47:38

謝謝。我編輯了代碼。現在if語句依賴於循環內部決定的隨機數，並且返回語句的執行是不可預知的。現在會有什麼結果？ – user2726225

什麼樣的隨機數字？它有什麼機會成爲真假？你需要最壞情況下的複雜性還是平均情況？ –

可以說隨機數是不可預測的。因此，任何時候都可以滿足條件，但條件永遠不可能是真實的。我需要最糟的情況下的複雜性。我不認爲有平均的情況是可能的，但想知道是否可能。 – user2726225

當談到複雜性時，n是以位爲單位的輸入大小。這裏有沒有輸入。所以n是固定的，等於0。所以技術上沒有複雜性，因爲輸入大小不會有任何變化。

但是，您可以問的問題：多少次將循環執行平均，最大或最小...

來源

2016-04-22 19:54:46 fjardon

謝謝。如果我問循環執行次數是多少次，它會是O（∞）？ – user2726225

這真的取決於你的隨機生成器:)如果它不生成1000，它可能是無限的，或者如果它總是返回1000，它可以是單個迭代... https://xkcd.com/221/ – fjardon

@ user2726225你把它插入公式'E [iterations] =（1-p）/ p'其中'p = 1/numberOfPossibleOutcomes' –

最壞的情況是O(∞)，最好的情況是0(1)。
是的，但每個算法都有複雜性O(∞)，因此它不是很有用的信息。

來源

2016-04-22 20:02:20 user3188346

你在找什麼是預計時間複雜度。在您的具體情況下，這是geometric distribution的預期值（平均值）。

E[iterations] = (1 - p)/p

其中p是，恰好有1000

p = P(X=1000)

來源

2016-04-22 20:27:24

這與生日問題無關 –

@SalvadorDali是的，我把它與散列衝突混淆了。這可能沒有意義，但過去一週只有6小時的睡眠時間。 –

摘要

其他人指出良好的信息，但未能解決的東西很重要。只要你引入隨機化，你想看看預期的時間，而不是確定性的分析。要回答你的問題：

最好的情況：Ω(1)
最壞的情況：O(∞)
平均情況：見下面的預期分析。

上最佳案例注意

通告，這是很大的歐米茄，沒有大O（https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation）

預期分析

只要你介紹隨機最好的情況下，，你不再依賴確定性分析。相反，你開始處理「預期分析」。正如Mateen指出的那樣，你的實例可以用幾何分佈來解決。由於我不知道數值範圍，因此您的隨機數函數可以返回（也不是數字的分佈），我們無法直接回答您的問題。 MATEEN的分析看起來不錯，因爲他不認爲你獲得1000

邊的概率注意

對於其他類型的隨機問題，您可以使用其他工具，如Marchov鏈（https://en.wikipedia.org/wiki/Markov_chain）。我見過用於分析隨機在線算法的工具（https://en.wikipedia.org/wiki/Adversary_model），如果您感興趣的話，鏈接應該爲您提供大量的其他鏈接來閱讀。

隨機化的引入爲算法分析增添了一個新的樂趣。希望這可以幫助，並獲得樂趣:)

來源

2016-04-26 22:07:32

無限循環的大O？

回答

相關問題