Дискретная математика(Хранение множеств)

[kdm]

Как хранить подмножества множества {1..n}, используя память O(n)? При этом действуют следующие ограничения на время выполения операций:
Сделать пустым Cn
Проверить принадлежность C
Добавить C
Удалить Cn
Минимальный элемент C
Проверка пустоты C

Никак не могу сообразить, в чем это можно хранить? Подскажите немного )

[PAV]

Используйте массив длины $n$, хранящий индикаторы принадлежности элемента к подмножеству, а также дополнительно - значение минимального элемента подмножества, который также является индикатором пустоты.

[kerz-3-06]

PAV писал(а):

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

У нас есть массив из n эл-тов и мы еще где-то должны хранить этот индикатор?

[PAV]

Да

[kerz-3-06]

так у нас же память O(n), это и есть сам массив. Или я что-то не понимаю?

[kdm]

в таком случае "Удалить" у нас вроде выполняется за время С?

[PAV]

Что такое O(n)? Дайте, пожалуйста, определение.

Опишите алгоритм удаления элемента, как Вы его видите.

[kdm]

Удаление элемента - как я понимаю - поменять индикатор принадлежности

[kerz-3-06]

а что такое O(n)? Вероятно, мои знания ошибочны

[PAV]

kdm писал(а):

Удаление элемента - как я понимаю - поменять индикатор принадлежности

А как же минимальный элемент, который хранится отдельно?

Добавлено спустя 4 минуты:

kerz-3-06 писал(а):

а что такое O(n)? Вероятно, мои знания ошибочны

Функция $f(n)$ является O(n), если $\frac{f(n)}{n}$ ограничено некоторой константой. Проще говоря, $f(n)$ растет не быстрее, чем пропорционально $n$.

[kdm]

я не совсем понял где хранится этот минимальный элемент....Остальное вроде более менее понятно

[PAV]

В еще одной ячейке памяти, дополнительной к существующим $n$ ячейкам.

[Егор]

Если вдруг захочется ещё подобных задач, то вот небольшое усложнение: чтобы удаление элемента тоже происходило за ограниченное время.

[PAV]

Егор писал(а):

Если вдруг захочется ещё подобных задач, то вот небольшое усложнение: чтобы удаление элемента тоже происходило за ограниченное время.

Честно говоря, я не могу сообразить как. Тогда у меня получается, что добавление становится O(n).

[Егор]

PAV писал(а):

Честно говоря, я не могу сообразить как. Тогда у меня получается, что добавление становится O(n).

Да, это я погорячился. Вряд ли можно сделать добавление элемента, удаление элемента и значение минимального элемента за O(1). Представлял себе массив указателей на узлы отсортированного двусвязного списка, но тогда, действительно, добавление будет за время O(n).

Говорят, будто куча Фибоначчи обеспечивает добавление за O(1) и удаление за O(log(n)).