Нахождение средней сложности случая с вероятностью

Question

Допустим, у нас есть строка 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 имеет равномерное распределение, какова средняя сложность случая половины A. Интуитивно, я считаю, что это len(n), но я не уверен, как это показать. И предположим, что a более вероятно, чем b, и его распределение не является равномерным, как тогда рассчитать средний случай?

Answer 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))