Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 61

В перестановке a1… ..an из n различных целых чисел инверсия — это пара (ai, aj), такая что i aj. Если все перестановки одинаково вероятны, каково ожидаемое число инверсий в случайно выбранной перестановке 1… ..n?
(A) n (n — 1) / 2

(B) n (n — 1) / 4
(С) n (n + 1) / 4
(D) 2n [log2 n]

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

There are n(n-1)/2 pairs such that i < j.

For a pair (ai, aj), probability of being inversion is 1/2.

Therefore expected value of inversions = 1/2 * (n(n-1)/2)
                                       = n(n-1)/4

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

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

ВОРОТА | GATE-CS-2003 | Вопрос 61

0.00 (0%) 0 votes