Учитывая массив из целых чисел, каждый элемент в массиве может быть увеличен на фиксированное число с некоторой вероятностью , . Я должен найти ожидаемое количество перестановок, которые будут иметь место для сортировки массива с помощью пузырьковой сортировки .
Я пробовал следующее:
Вероятность для элемента для может быть легко вычислена из заданных вероятностей.
Используя вышесказанное, я рассчитал ожидаемое количество свопов как:
double ans = 0.0; for ( int i = 0; i < N-1; i++ ){ for ( int j = i+1; j < N; j++ ) { ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.
В основном я пришел к этой идее, потому что ожидаемое количество свопов можно рассчитать по количеству инверсий массива. Таким образом, используя данную вероятность, я вычисляю, будет ли число поменяно местами с числом .A [ j ]
Обратите внимание, что исходные элементы массива могут быть в любом порядке, отсортированы или не отсортированы. Тогда каждое число может измениться с некоторой вероятностью. После этого мне нужно рассчитать ожидаемое количество свопов.
Я уже писал подобный вопрос, но он не имел всех ограничений.
Я не получил никаких хороших подсказок о том, нахожусь ли я даже на правильном пути или нет, поэтому я перечислил все ограничения здесь. Пожалуйста, дайте мне несколько советов, если я думаю о проблеме неправильно.
источник
Ответы:
Пусть определяется следующим образом:BubbleSort
Учитывая некоторую перестановку , говорят , что инверсия произошла, если x j < x ix1,⋯,xn xj<xi для некоторого Мы видим , что B U Ь б л е S O R T выполняет проверку инверсии для каждой пары, и если да, то выполняет своп. Пусть X будет количеством свопов. Нетрудно увидеть, в худшем случае есть X = ( ni<j. BubbleSort X возможны перестановки. Но нас интересует ожидаемый случай, который мы можем вычислить, определивXв терминах инверсий вBubbleSort.X=(n2) X BubbleSort
Пусть теперь где I i j - переменная индикатора, для которой существует инверсия для некоторой пары ( i , j ) . Ожидание определяется как E [ X ]X=∑j∑i<jIij Iij (i,j) E[X]=E[∑j∑i<jIij]=∑j∑i<jE[Iij] , Теперь нам нужно определить .P{Iij}
Принимая любую возможную перестановку в качестве входных данных, каждая с одинаковой вероятностью, можно показать, что . Причина этого заключается в том, что при любой возможной перестановке половина времениxj<xiи половина времениxi<xjдляi≠j.P{Iij}=12 xj<xi xi<xj i≠j
источник