среднее время выполнения алгоритма линейного поиска

Question

Я пытаюсь вывести среднее время выполнения для детерминированного алгоритма линейного поиска. Алгоритм ищет элемент x в несортированном массиве A в порядке A [1], A [2], A [3] ... A [n]. Он останавливается, когда находит элемент x или продолжается, пока не достигнет конца массива. Я искал в википедии , и был дан ответ (n + 1) / (k + 1), где k - это количество раз, когда x присутствует в массиве. Я подошел по-другому и получаю другой ответ. Кто-нибудь может дать мне правильное доказательство, а также сообщить мне, что не так с моим методом?

E(T)= 1*P(1) + 2*P(2) + 3*P(3) ....+ n*P(n) where P(i) is the probability that 
                   the algorithm runs for 'i' time (i.e. compares 'i' elements).
P(i)= (n-i)C(k-1) * (n-k)! / n! 
Here, (n-i)C(k-1) is (n-i) Choose (k-1). As the algorithm has reached the ith 
step, the rest of k-1 x's must be in the last n-i elements. Hence (n-i)C(k-i).
(n-k)! is the total number of ways of arranging the rest non x numbers, and n! 
is the total number of ways of arranging the n elements in the array.

Я не получаю (n + 1) / (k + 1) при упрощении.

Answer 1

Вот решение, которое использует термины Кормена: Пусть S будет набором других n-k элементов.
Пусть индикатор случайной величины Xi=1, если мы встретим i '-ый элемент из набора S в ходе нашего исполнения.
Pr{Xi=1}=1/(k+1) и, следовательно, E[Xi]=1/(k+1).
Пусть индикатор случайная переменная Y=1, если мы встретим какой-либо из k элементов, которые мы ищем в ходе нашего выполнения.
Pr{Y=1}=1 и, следовательно, E[Y]=1.
Пусть случайная величина X=Y+X1+X2+...X(n-k) будет суммой элементов, которые мы встреча в ходе нашей казни.
E[X]=E[Y+X1+X2+...X(n-k)]=E[Y]+E[X1]+E[X2]+...E[X(n-k)]=1+(n-k)/(k+1)=(n+1)/(k+1).

Answer 2

Вы забыли учесть перестановки k копий x. Правильное определение P(i) равно

P(i) = (n-i)C(k-1) * k! * (n-k)! / n! = (n-i)C(k-1) / nCk.
                     ^^

Я передам вещи Математике:

In[1]:= FullSimplify[Sum[i Binomial[n-i, k-1]/Binomial[n, k], {i, 1, n}], 0 <= k <= n]

        1 + n
Out[1]= -----
        1 + k

---

Чтобы пояснить мой комментарий ниже: предположим, что все элементы различны, пусть X - это набор совпадений, а Y - множество не совпадений. По предположению, | X | = k и | Y | = н-к. Ожидаемое количество чтений равно сумме по элементам e вероятности того, что e прочитано.

При заданном наборе элементов S каждый элемент в S предшествует всем остальным с вероятностью 1 / | S |.

Элемент x в X читается тогда и только тогда, когда он предшествует любому другому элементу X, что составляет вероятность 1 / k. Общий вклад элементов в X равен | X | (1 / k) = 1.

Элемент y в Y читается тогда и только тогда, когда он предшествует каждому элементу X, что является вероятностью 1 / (k + 1). Общий вклад элементов в Y равен | Y | (1 / (k + 1)) = (n-k) / (k + 1).

У нас есть 1 + (n-k) / (k + 1) = (n + 1) / (k + 1).