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

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

S = {

Рис. III.1. 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) по пространству: