Рубрики

ВОРОТА | GATE-CS-2002 | Вопрос 35

Рассмотрим следующий алгоритм поиска заданного числа x в несортированном массиве A [1… ..n], имеющем n различных значений:

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

Предполагая, что x присутствует в A, каково ожидаемое количество сравнений, выполненных алгоритмом до его завершения?
(A) n
(B) n — 1
(С) 2n
(D) н / 2

Ответ: (А)
Объяснение:

Если вы помните вопросы о монетах и игральных костях, вы можете просто угадать ответ на вышеуказанный вопрос.

Ниже приведено доказательство ответа.

Пусть ожидаемое количество сравнений равно E. Значение E представляет собой сумму следующего выражения для всех возможных случаев.

number_of_comparisons_for_a_case * probability_for_the_case 

Дело 1

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

Дело 2

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

Дело 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

На самом деле таких случаев бесконечно много. Итак, мы имеем следующие бесконечные ряды для E.

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

Умножив уравнение (1) на (n-1) / n, получим

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)

Вычитая (2) из (1), получим

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

Выражение справа — это GP с бесконечными элементами. Применим формулу суммы (a / (1-r))

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

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2002 | Вопрос 35

0.00 (0%) 0 votes