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

II. Метод Гаусса

Рассказывают, что как-то раз учитель в начальной школе в качестве наказания поставил Гауссу задачу: просуммировать все числа от 1 до 100. К изумлению учителя, Гаусс нашел ответ (5050) в течение нескольких минут. Его прием состоял в том, чтобы манипулировать порядком элементов удвоенной суммы:

= 10100

Разделив это на 2, мы получим 5050. Мы можем записать так:

.

Следовательно:

В последней строке i отсутствует, поэтому (n + 1) суммируется снова и снова n раз. Следовательно:

III. Множества

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

S = {,  ,  ,  }.

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

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

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

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

Степенные множества. Обратите внимание, что S3 и S4 одновременно являются подмножествами S. Мы также полагаем, что S5 = S и пустое множество S6 = {} являются подмножествами S. Если подсчитать все подмножества S, то вы найдете 24 = 16 подмножеств. Если же рассматривать их все как объекты, то мы можем собрать их в множество. Множество всех подмножеств S называется его степенным множеством:

PS = {S1, S2, . . . , S16}.

IV. Алгоритм Кэдейна

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

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

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

function trade_kadane(prices):

    sell_day ← 1

    buy_day ← 1

    best_profit ← 0

    for each s from 2 to prices.length

        if prices[s] < prices[buy_day]

            b ← s

        else

            b ← buy_day

        profit ← prices[s] - prices[b]

        if profit > best_profit

            sell_day ← s

            buy_day ← b

            best_profit ← profit

    return (sell_day, buy_day)

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