Книга Теоретический минимум по Computer Science. Все что нужно программисту и разработчику, страница 50. Автор книги Владстон Феррейра Фило

Онлайн книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

Страница

Мы используем слово множество для описания группы объектов. Например, мы можем назвать S множеством обезьянок-эмодзи:

S = { ,  ,  ,  }.

Рис. III.1. S₁ и S₂ есть подмножества S

Подмножества. Множество объектов, содержащихся в другом множестве, называется подмножеством. Например, обезьянки, показывающие лапы и глаза, составляют подмножество S₁ = { , }. Все обезьянки в S₁ содержатся в S. Мы записываем это так: S₁ S Мы можем сгруппировать обезьянок с лапками и ртами в другом подмножестве: S₂ = { , }.

Объединение. Какие обезьянки принадлежат либо S₁, либо S₂? Ответ: обезьянки в S₃ = { , , }. Новое множество — объединение двух предыдущих. Мы записываем это так: S₃ = S₁ S₂.

Пересечение. Какие обезьянки принадлежат и S₁, и S₂? Ответ: обезьянки в S₄ = { }. Новое множество получается путем пересечения двух предыдущих. Мы записываем это так: S₄ = S₁ S₂.

Степенные множества. Обратите внимание, что S₃ и S₄ одновременно являются подмножествами S. Мы также полагаем, что S₅ = S и пустое множество S₆ = {} являются подмножествами S. Если подсчитать все подмножества S, то вы найдете 2⁴ = 16 подмножеств. Если же рассматривать их все как объекты, то мы можем собрать их в множество. Множество всех подмножеств S называется его степенным множеством:

P_S = {S₁, S₂, S₁₆}.

В разделе «Полный перебор» главы 3 мы представили задачу «Лучшая сделка».

Лучшая сделка У вас есть список цен на золото по дням за какой-то интервал времени. В этом интервале вы хотите найти такие два дня, чтобы, купив золото, а затем продав его, вы получили бы максимально возможную прибыль.

В разделе «Динамическое программирование» той же главы мы показали алгоритм, который решил эту задачу с временной сложностью O(n) и пространственной сложностью O(n). Когда в 1984 году Джей Кэдейн обнаружил эту задачу, он нашел способ решить ее с O(n) по времени и O(1) по пространству:

Страница