Лекция 1.

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

Сложность программы

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

Def. Пусть имеются две функции ( ) и ( ), при этом , : N → N, тогда считается, что ( ) =

( ( )), если > 0 0 : > 0 ( ) ≤ · ( ).

Поясним определение выше. Говорят, что функция является -большим от функции , если она растет не быстрее, чем функция , домноженная на константу (сколь угодно большую, заметьте). Также можно считать, что функция ограничена функцией , домноженной на константу. Для понимания предлагается рассмотреть несколько примеров.

Примеры.

1.Пусть ( ) = , а ( ) = 2, тогда очевидно, что ( ) = ( ( )). Например, пусть = 1, а0 = 2, тогда = ( ) < · ( ) = ( ) = 2, что верно для ≥ 2.

2.Пусть ( ) = , а ( ) = + , где — многочлен степени , N, N. Тогда также нетрудно показать, что ( ) = ( ( )). Для скептически настроенных читателей проведем подробный анализ. Введем две функции 1( ) = и 1( ) = + . Тогда из курса математического анализа известно, что 1 и 1 , то есть можно перейти только к асимптотическому сравнению мономов старших степеней. Более того, мы имеем право опустить константы, так как они кроются в определении -большого. То есть задача сведена к доказательству соотношения= ( + ). Далее рассуждение аналогично первому примеру.

Def. Пусть имеются две функции ( ) и ( ), при этом , : N → N, тогда считается, что ( ) = Θ( ( )), если 1, 2 > 0 0 : > 0 1 · ( ) ≤ ( ) ≥ 2 · ( ).

Упражнение. Докажите, что если ( ) = ( ( )) и ( ) = ( ( )), то ( ) = ( ( )).

Сразу обозначим множество классов, которые мы будем использовать для анализа

Теперь мы готовы перейти к оценке параметров. Здесь и далее мы будем все оценивать в асимптотических обозначениях, не стремясь найти 0 и из определений выше. В ходе анализа алгоритмов мы будем пользоваться следующими допущениями

1. Память вычислителя безгранична.

2. Доступ к произвольному блоку памяти происходит за (1) времени.

Рекуррентные соотношения

Теорема (Мастер-теорема) (б/д). Пусть зафиксированы константы ≥ 1, > 1, ( ) — некоторая функция, а ( ) определена рекуррентно

( )

( ) = + ( )

Тогда верны следующие утерждения

1.Если ( ) = ( log − ) для некоторой константы > 0, то ( ) = Θ ( log ).

2.Если ( ) = ( log ), то ( ) = Θ ( log · log ).

3. Если ( ) = ( log + ) для некоторой константы > 0 и

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

Теперь мы готовы перейти к анализу алгоритмов.

Бинарный поиск

Пусть имеется монотонный предикат ( ), то есть

И перед нами стоит задача отыскать это 0. Например, задача проверки наличия элемента в отсортированном массиве. В данном случае предикат будет звучать как ( ) = 1 [ ] ≥ .

Note. По теореме о промежуточных значениях из курса матанализа данная задача разрешима, причем единственным образом.

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

1.Вычислим ( ), где — середина массива.

2.Если ( ) = 0, то 0 > , иначе 0 ≤ . Таким образом, можно перейти лишь к половине массива и повторить шаги заново для нового массива.

Проведем анализ такого алгоритма преполагая, что время вычисления предиката равно ( ( )) и ≤ ( ) ≤ ( ). Тогда нетрудно построить рекурренту

( )

( ) = 2 + ( ( )) = ( ) = ( ( ) · log )

Упражнение. Докажите соотношение выше.

В случае задачи выше ( ) = (1), то есть итоговое время составит (log ), что заметно лучше наивного прохода, работающего за ( ).

Пример: Дан отсортированный по возрастанию массив 1, . . . , . Надо выбрать ≥ 2 чисел

1 , . . . , так, чтобы min( − −1 ) оказался максимален.

≤

( ) = 1, если можно добиться значения в . Тогда начиная с некоторого момента значения в добиться нельзя. Нам как раз нужно найти вот этот вот максимальный , который еще достижим. Воспользуемся идеей выше.

Переформулируем задачу. Можно ли выбрать элементы так, чтобы min( − −1 ) ≥ ? Если да, то

≤

ответ хотя бы , иначе меньше. Осталось разобраться, как вычислять этот предикат.

1 всегда выгодно брать, поэтому возьмем его. Следующим элементом возьмем наименьший, который хотя бы 1 + . Тогда, если удалось выбрать объектов, то выбор с возможен. Это верно и в