PUERTA | PUERTA-CS-2002 | Pregunta 35

Considere el siguiente algoritmo para buscar un número dado x en una array no ordenada A[1…..n] que tiene n valores distintos:

   1. Choose an i uniformaly at random from 1..... n;
   2. If A[i] = x then Stop else Goto 1; 

Suponiendo que x está presente en A, ¿cuál es el número esperado de comparaciones realizadas por el algoritmo antes de que termine?
(A) n
(B) n – 1
(C) 2n
(D) n/2

Respuesta: (A)
Explicación:

Si recuerdas las preguntas sobre monedas y dados, puedes adivinar la respuesta a las anteriores.

A continuación se muestra la prueba de la respuesta.

Sea E el número esperado de comparaciones. El valor de E es la suma de la siguiente expresión para todos los casos posibles.

number_of_comparisons_for_a_case * probability_for_the_case 

Caso 1

  If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n

Caso 2

  If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n

Caso 3

  If A[i] is found in the third attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*(n-1)/n*1/n

En realidad, hay infinitos casos de este tipo. Entonces, tenemos las siguientes series infinitas para E.

E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)

Después de multiplicar la ecuación (1) por (n-1)/n, obtenemos

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Restando (2) de (1), obtenemos

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

La expresión del lado derecho es un GP con infinitos elementos. Apliquemos la fórmula de la suma (a/(1-r))

  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n

Cuestionario de esta pregunta