Пусть A[1 ... n] - массив из n различных
чисел. Если i < j и A[i] > A[j], то пара (i, j) называется инверсией A. (Подробнее об инверсиях см. задачу 2-4). Предположим, что каждый элемент A выбран случайно, независимо и равномерно из диапазона от 1 до n. Используйте индикаторные случайные величины для вычисления ожидаемого числа инверсий.
Задача взята из упражнения 5.2-5 в Введении в алгоритмы Кормена. Вот мое рекурсивное решение:
Предположим, что x(i) - число инверсий в a[1..i], а E(i) - ожидаемое значение x(i), тогда E(i+1) можно вычислить следующим образом:
Изображение имеетi+1
позиций для размещения всех чисел, если мы разместим i+1 на первой позиции, то x(i+1) = i + x(i); если мы разместим i+1 на второй позиции, то x(i+1) = i-1 + x(i),.... ..., поэтому E(i+1) = 1/(i+1)*сумма(k) + E(i), где k = [0,i]. В итоге получаем E(i+1) = i/2 + E(i).
Поскольку мы знаем, что E(2) = 0,5, то рекурсивно получаем: E(n) = (n-1 + n-2 + ... + 2)/2 + 0,5 = n* (n-1)/4.
Хотя вышеприведенный вывод кажется правильным, но я все еще не очень уверен в этом. Поэтому я делюсь этим здесь.
Если что-то не так, пожалуйста, поправьте меня.