Средний случай двоичного счетчика

Question

INCREMENT(A) 
i = 0 
while i< A.length and A[i] ==1 
    A[i]=0 
    i=i+1 
if i< A.length 
    A[i]=1 

Я сейчас изучает амортизируется анализ самостоятельно, и я имею в виду различия между средним анализа конкретных случаев и амортизируется анализ, который я знаю, что амортизированная стоимость бинарной операции счетчика INCREMENT (Array) , есть O (1), но что, если я хочу проанализировать средний случай INCREMENT? Я предполагаю, что среднее количество бит, которое нам нужно перевернуть, равно n/2, где n - это общее количество бит, но я видел ответ в Average Case Time Complexity Analysis of Binary Counter Increment, что для меня не имеет большого смысла. Может кто-нибудь объяснить? Это будет полезно, потому что я действительно знаю, что ответить: D

Answer 1

Я предполагаю, что «среднее» означает, что мы выбираем случайный массив из 0 и 1 длины n с равной вероятностью, чтобы выбрать каждый возможный вариант. Это эквивалентно установке каждого из элементов n массива в 0 с вероятностью 1/2 и до 1 с такой же вероятностью.

Какова вероятность того, что тело цикла while будет выполнено хотя бы один раз? Он равен 1/2 (он выполняется тогда и только тогда, когда первый элемент массива равен 1). Какова вероятность того, что тело цикла будет выполняться как минимум дважды? Вероятность того, что первые два элемента равны 1, равна 1/2 * 1/2 = 1/4 (так как вероятности того, что первый и второй элементы равны единице, независимы). По индукции мы можем показать, что вероятность того, что тело цикла while выполняется не менее i раз (1 <= i <= n), равна (1/2)^n.

Это означает, что он сделает одну итерацию с вероятностью 1/2, еще одну итерацию с вероятностью 1/4, еще одну итерацию с вероятностью 1/8 и так далее. Таким образом, ожидаемое значение числа итераций составляет sum for 1 <= i <= n (1/2)^i, которое ограничено сверху суммой бесконечных рядов 1/2+1/4+1/8+..., которая равна 1 (это, очевидно, постоянная). Все остальные операции, кроме цикла while, выполняются постоянным числом раз, независимо от ввода. Таким образом, общая временная сложность в среднем постоянна.