查找平均個案複雜度的概率

假設我們有一個字符串n，可以填充「a」或「b」s，例如：n =「aaabbbab」，「ababababab」等等。我們定義一個名爲查找平均個案複雜度的概率

HalfA(n): 
    count a = 0; 
    for each i in n: 
    if n == 'a' 
     i++; 
    if i >= n.length/2 
     return true 
    return false

功能，如果n具有均勻分佈的，什麼是哈勒法的平均情況下的複雜性。直覺上，我相信它是len（n），但我不確定如何顯示它。假設a比b更可能，並且它不是一個均勻分佈，那麼如何計算平均情況呢？

2013-10-21 user65663

它是'len（n）'。在絕對最好的情況下，每個角色都是'a'。在這種情況下仍然是'O（len（n）/ 2）= O（len（n））' – Cruncher

謝謝。正如我所提到的，我知道它的len（n），但我不知道如何顯示它。如果它不是一個統一的分佈，並且p（a）= .8和p（b）= .2或者某個東西 – user65663

無論您使用哪種分佈，它仍然至少需要n/2個步驟。最多n步。在這種情況下，分佈變化不大。 – Cruncher

適用於任何分銷。

最佳情況：n =「a *」。這將採取len(n)/2步驟，所以最好的情況是：O(len(n))

最壞的情況：n =「b *」。這將需要len(n)步驟，因爲您必須通過整個陣列。所以最壞的情況是O(len(n))

平均情況受最佳情況和最壞情況限制。那就是，O(len(n)) <= average case <= O(len(n))。因此，平均個案複雜度爲O(len(n))

2013-10-21 14:38:21 Cruncher

回答