Дано:
- n - количество фамилий в списке.
Найти:
- математическое ожидание числа обменов при сортировке методом пузырька.
Решение:
1. Метод пузырька работает, сравнивая соседние элементы и меняя их местами, если они расположены в неверном порядке. Мы будем искать общее количество обменов, необходимое для сортировки.
2. Обозначим количество пар фамилий, которые должны быть в неверном порядке. Для n фамилий количество пар можно вычислить по формуле:
C(n, 2) = n * (n - 1) / 2.
3. Предположим, что фамилии расположены случайным образом. Вероятность того, что пара фамилий в неверном порядке, равна 1/2, поскольку для любой пары фамилий они могут быть упорядочены двумя способами: в правильном и в неправильном.
4. Таким образом, математическое ожидание количества пар, которые нужно поменять, можно вычислить как:
E = (количество пар) * (вероятность неверного порядка)
E = C(n, 2) * (1/2).
5. Подставим значение количества пар:
E = (n * (n - 1) / 2) * (1/2) = n * (n - 1) / 4.
6. Однако метод пузырька выполняет несколько проходов по списку, и каждый раз, в среднем, по одному обмену может происходить для каждой пары на каждом проходе. Сортировка завершится, когда не будет больше обменов, что в среднем требует O(n^2) обменов.
7. Таким образом, полное математическое ожидание количества обменов в методе пузырька можно оценить следующим образом:
E_total = O(n^2).
8. При детальном рассмотрении, математическое ожидание числа обменов для n фамилий, как правило, приближается к n^2/4.
Ответ:
Математическое ожидание числа обменов при сортировке n фамилий методом пузырька примерно равно n^2 / 4.