Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
v1212186
0 / 0 / 0
Регистрация: 07.06.2015
Сообщений: 4
1

Алгоритм упорядочивания нескольких множеств за O(n)

07.06.2015, 20:29. Просмотров 896. Ответов 2
Метки нет (Все метки)

Здравствуйте! Прошу помощи со следующей задачей:
Пусть Si,...,Sk множества чисел, лежащих между 1 и n, и сумма мощностей всех множеств равна n. Опишите алгоритм сложности O(n), упорядочивающий каждое из множеств.

Идей вообще никаких нет. Вот есть у нас какое-то количество множеств (получается можем рассматривать их как массивы). Всего у нас n элементов, которые хаотично разбросаны по этим множествам. И как за линейное время я их должен сортировать? Единственный вариант выходит только при идеальной сортировке за O(m) времени (m-кол-во элементов в произвольном множестве). Тогда просто сортируем по очереди все эти множества и получим O(n). Но я уверен, что это неправильное решение.

PS Я ведь вообще правильно понял смысл задания, надеюсь?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2015, 20:29
Ответы с готовыми решениями:

Объединение нечетких множеств. Алгоритм вычислений
Всем доброго дня! Возникла следующая задача: найти объединение двух нечетких множеств ,...

Написать алгоритм упорядочивания данных из файла
Задание: написать алгоритм упорядочивания данных из файла (целые числа, количество элементов не...

Составить программу упорядочивания последовательности 3 данных чисел а b, c по возрастанию с использованием подпрограммы-процедуры упорядочивания
Составить программу упорядочивания последовательности 3 данных чисел а b, c по возрастанию с...

Восстановить алгоритм разбиения множеств по имеющемуся коду
Здравствуйте. Нашел тут на форуме решение задачи "разбить числовое множество на два подмножества...

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

2
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,502
08.06.2015, 09:17 2
Складываем все числа в массив от 1 до n. Затем "достаём" из него отсортированные множества.
Если все числа гарантированно разные ("Всего у нас n элементов, которые хаотично разбросаны по этим множествам."), то можно писать в массив номер множества. Если возможны повторы, то придётся писать в массив количества и обнулять массив при переходе к следующему множеству.
1
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
08.06.2015, 09:18 3
Лучший ответ Сообщение было отмечено v1212186 как решение

Решение

зафиксируем порядок, в котором рассматриваем массивы. http://www.cyberforum.ru/cgi-bin/latex.cgi?S1, \ \ldots \ , \ Sk

заведем массив http://www.cyberforum.ru/cgi-bin/latex.cgi?a[] на http://www.cyberforum.ru/cgi-bin/latex.cgi?N чисел. пройдем по всем мн-вам. пусть мы сейчас просматриваем элемент http://www.cyberforum.ru/cgi-bin/latex.cgi?k-ого мн-ва и он равен http://www.cyberforum.ru/cgi-bin/latex.cgi?x. тогда присвоим http://www.cyberforum.ru/cgi-bin/latex.cgi?a[x] = k.

после того, как обошли все множества, у нас есть полностью заполненный массив http://www.cyberforum.ru/cgi-bin/latex.cgi?a[], в котором каждое число знает, из какого оно множества. пройдем по элементам массива http://www.cyberforum.ru/cgi-bin/latex.cgi?a[], перебирая индексы от 1 до http://www.cyberforum.ru/cgi-bin/latex.cgi?N. пусть массивы http://www.cyberforum.ru/cgi-bin/latex.cgi?S_i сейчас пусты. рассматриваем http://www.cyberforum.ru/cgi-bin/latex.cgi?i-ый элемент массива http://www.cyberforum.ru/cgi-bin/latex.cgi?a[]. положим в самую левую пустую позицию массива http://www.cyberforum.ru/cgi-bin/latex.cgi?S_{a[i]} число http://www.cyberforum.ru/cgi-bin/latex.cgi?i.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2015, 09:18

Доказать равенство множеств с помощью основных законов алгебры множеств
Доказать равенство множеств, преобразуя множества к одинаковому виду помощью основных ...

Поменять местами значения множеств a и b без использования дополнительных множеств
оставить программу, которая меняет местами значения множеств a и b без использования дополнительных...

Составить программу, меняющую местами значения множеств A и B без использования дополнительных множеств
Здравствуйте, уважаемые программисты! Не знаю, куда еще обращаться, на следующей неделе экзамен, а...


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

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

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