Дан массив из n элементов, на которых определено отношение равенства. Постройте как можно более быстрый алгоритм, который определяет, есть ли в массиве элемент, повторяющийся более M(n/2) раз, где M(n/2) - наибольшее целое, не превосходящее число n/2.

задан 16 Фев '16 20:14

Дан массив из n элементов, на которых определено отношение равенства.

можно подумать, что бывает массив, где отношение равенства не определено :D

Ладно, самый простой и стандартный вариант - отсортировать и проверить. Асимптотика известна. А можно ли быстрее?

(16 Фев '16 21:15) Trumba

Бывает массив на котором равенство не определено (конкретно в языке C++), например массив объектов-фигур или еще каких нибудь экзотических классов (В C# все объекты имеют hashcode. По нему можно сравнивать, но это не гарантирует равенства). Поэтому сортировать мы не можем, так как на элементах задано лишь отношения равенства, а не больше-меньше. С $%С\cdot n\cdot log(n)$% асимптотикой алгоритм придумать не сложно. Тут уже будет интересно минимизировать асимптотическую константу C.

(16 Фев '16 21:43) abc

Поэтому сортировать мы не можем, так как на элементах задано лишь отношения равенства, а не больше-меньше.

Точно, облом. Можно его ввести искусственно, но это изврат.

Бывает массив на котором равенство не определено (конкретно в языке C++), например массив объектов-фигур или еще каких нибудь экзотических классов

это все - проблемы конкретно сиплюсплюса. Если $%X$% - множество, то его декартова диагональ $%X_==\{(x,x): x\in X\}$% - отношение равенства на $%X$% - вполне конструктивна. Бывает неразрешимость равенства, но это - уже другой вопрос, в таком случае и об алгоритмах речи не идет.

(16 Фев '16 22:41) Trumba
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×192
×113
×47

задан
16 Фев '16 20:14

показан
468 раз

обновлен
16 Фев '16 22:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru