probability - 用概率求平均案例复杂度

Question

假设我们有一个字符串 n，它可以用“a”s 或“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 具有均匀分布，那么 halfA 的平均案例复杂度是多少。直觉上，我相信它是 len(n) 但我不确定如何展示它。假设a比b更有可能，并且它不是均匀分布，那么我如何计算平均情况呢？

score 1 · Accepted Answer

对于任何分布。

最佳情况：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))

1 回答 1