0

文字列 n があるとします。これには、"a" または "b" を入力できます。例: 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 よりも可能性が高く、均一な分布ではないと仮定すると、どのように平均ケースを計算すればよいでしょうか?

4

1 に答える 1

1

任意の配布用。

最良のケース: 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-21T14:38:21.267 に答える