Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
1

Сложность в среднем (по числу сравнений)

20.05.2013, 22:17. Просмотров 286. Ответов 0
Метки нет (Все метки)

Не понимаю как: "... По формуле полного математического ожидания имеет для искомого среднего a: a<=p(n-1)+(1-p)(a+n-1). " ??!!1

Вот отрывок из книги:
Массив x1, x2, ..., xn назовем массивом, содержащим большинство, если больше половины его элементов имеют равные значения. Пусть над элементами массивов разрешена операция проверки равенства двух элементов, будем называть эту операцию сравнением. Пусть для данного массива, содержащего большинство, требуется найти i, 1<=i<=n, такое, что значение xi принадлежит большинству значений элементов x1, x2, ..., xn. Один из возможных рандомизированных алгоритмов решения этой задачи состоит в том, что i выбирается случайно (распределение вероятностей равномерного), а затем проверяется, удовлетворяет ли xi поставленному условию, - сравнений на эту проверку уйдет не более n-1. Если xi не подходит, то все повторяется. Сложность в среднем по числу сравнений этого алгоритма не превосходит 2(n-1). В самом деле, пространство всех сценариев разлагается на два события: первая попытка найти нужное i оказывается удачной, и соответственно, эта попытка оказывается неудачной. По формуле полного математического ожидания имеем для искомого среднего a: a<=p(n-1)+(1-p)(a+n-1).
Отсюда a<=1/p(n-1)<2(n-1).
Ладно, понятно, что здесь вероятность того, что выбранное число будет принадлежать большинству массива это: p=N/n, где N - количество большинства массива.
Тогда рассчитывая мат. ожидание (т.е. сложность в среднем) у нас будет два вероятностных события:
1) X=(n-1) - число принадлежит большинству; P = N/n - вероятность этого события;
2) X=(n-1) - число не принадлежит большинству; p=1-N/n - вероятность этого события;
Теперь рассчитаем мат. ожидание (т.е. сложность в среднем): a=p(n-1)+(1-p)(n-1);
Упростим и получим: a=n-1. Вот и все, видно что я где-то лажанул.

P. S. и почему вообще число сравнений не превышает (n-1), если оно может быть и n?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.05.2013, 22:17
Ответы с готовыми решениями:

количество сравнений
Помогите найти количество сравнений в сортировке методом вставками. b1 это...

Подсчитать количество выполненных сравнений и перестановок в лучшем, худшем и в среднем
помогите пожалуйста

Где правильно ставить счетчики сравнений и перестановок, и как считать сложность этих алгоритмов?
написал код двух сортировок, но не уверен, что правильно проставлены...

Как вычислять сложность алгоритма, или найти асимптотическую сложность любой программки?
Например Вычислить x^n по алгоритму быстрого возведения в степень Добавлено...

Упорядочить строки матриц по числу элементов кратных заданному числу
Даны три целочисленные матрица A, B и C. Упорядочить строки матриц по числу...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2013, 22:17

Распечатать числа в диапазоне от 1 до n у которых имеется делитель (не равный числу) кратный числу м
Распечатать числа в диапазоне от 1 до n у которых имеется делитель (не равный...

Цикл: Распечатать числа в диапазоне от 1 до N, у которых имеется делитель (не равный числу), кратный числу M
1.Распечатать числа в диапазоне от 1 до N, у которых имеется делитель (не...

По введенному числу от 1 до 7 назвать соответствующий числу день недели
Решить задачу с использованием оператора выбора. По введенному числу от 1 до 7...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru