Pergunta

The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":

Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \ldots, A[n]$, until either it finds $A[i] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.

Suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-time running time of this algorithm?

Let $X$ be a random variable denoting the number of comparisons.

$$ \begin{align*} E(X) &= \sum_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\ &= \sum_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right) \end{align*} $$

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top