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

Линейный алгоритм для массива с большинством

27.05.2013, 19:12. Просмотров 386. Ответов 0
Метки нет (Все метки)

Ребят, выручайте)
Вообще уже не первый раз пишу по этому поводу, но ни какого результата нет :/
Да и сам, ни чего полезного не получил за эти несколько дней, которые я попусту потратил на эту задачу.

Следует сравнить сложности в среднем двух алгоритмов: рандомизированный и линейный. Ну про рандомизированный - собственно понятно, я так думаю, хотя ниже я скинул немного инфы про него.

Кликните здесь для просмотра всего текста
Массив 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).


Что значит линейный?! А это значит, что сложность выполнения данного алгоритма в среднем должна быть линейной, т.е. T(n)<=C*n, где С - это некая константа (например 19).
Есть предположение, что данный алгоритм можно найти, используя метод "отсечения и поиска", хотя это может быть и ошибочным предположением

И да, чуть не забыл, вот условие задачи:
Для массива содержащего большинство, найти i (1 ≤ i ≤ n), такое что xi принадлежит большинству значений элементов {x1, x2, …, xn}.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.05.2013, 19:12
Ответы с готовыми решениями:

Массив с большинством
Получил задания сравнить рандомизированный и линейный алгоритмы на массиве с...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный...

Составить линейный алгоритм для вычисления выражения
Необходимо составить линейный алгоритм для вычисления выражения ...

Линейный алгоритм
Вычислить координаты точки, делящей отрезок а1 а2 в отношении n1:n2 по...

Линейный алгоритм
Помогите пожалуйста решить линейный алгоритм. Задача на фото во вложении

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

Линейный алгоритм
При x=1,67; y=-7,6; z=3,89∙10-4 найти значение R. Написал код, но ответ выдает...

Линейный алгоритм
Помогите пожалуйста с задачей. Не могу понять суть написания формулы.

Линейный алгоритм
В трехначном числе зачеркнули его последнюю цифру. Когда в образованном при...


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

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

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