2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 
Сообщение25.03.2008, 21:16 
PAV писал(а):
а также дополнительно - значение минимального элемента подмножества, который также является индикатором пустоты.


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

 
 
 
 
Сообщение25.03.2008, 21:17 
Аватара пользователя
Да

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

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

 
 
 
 
Сообщение25.03.2008, 21:25 
Аватара пользователя
Что такое O(n)? Дайте, пожалуйста, определение.

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

 
 
 
 
Сообщение25.03.2008, 21:36 
Удаление элемента - как я понимаю - поменять индикатор принадлежности

 
 
 
 
Сообщение25.03.2008, 21:38 
а что такое O(n)? Вероятно, мои знания ошибочны

 
 
 
 
Сообщение25.03.2008, 22:14 
Аватара пользователя
kdm писал(а):
Удаление элемента - как я понимаю - поменять индикатор принадлежности


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

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

kerz-3-06 писал(а):
а что такое O(n)? Вероятно, мои знания ошибочны


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

 
 
 
 
Сообщение25.03.2008, 22:20 
я не совсем понял где хранится этот минимальный элемент....Остальное вроде более менее понятно

 
 
 
 
Сообщение25.03.2008, 22:33 
Аватара пользователя
В еще одной ячейке памяти, дополнительной к существующим $n$ ячейкам.

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

 
 
 
 Re: небольшое усложнение
Сообщение25.03.2008, 23:37 
Аватара пользователя
Егор писал(а):
Если вдруг захочется ещё подобных задач, то вот небольшое усложнение: чтобы удаление элемента тоже происходило за ограниченное время.


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

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

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

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

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group