Анализ наиболее неблагоприятного случая

Сложность алгоритмов

 

 

Анализ сложности алгоритмов

 

Многие современные программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают. Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. Эта лекция посвящена анализу сложности алгоритмов. Как специалист, работавший как в области академической науки, так и над созданием коммерческого программного обеспечения, я считаю этот инструмент по-настоящему полезными на практике. Надеюсь, что после сегодняшней лекции вы сможете применить его к собственному коду, чтобы сделать его ещё лучше.

Мы уже знаем, что существуют инструменты, измеряющие, насколько быстро работает код. Это программы, называемые профайлерами (profilers), которые определяют время выполнения в миллисекундах, помогая нам выявлять узкие места и оптимизировать их. Но, хотя это и полезный инструмент, он не имеет отношения к сложности алгоритмов. Сложность алгоритма — это то, что основывается на сравнении двух алгоритмов на идеальном уровне, на котором игнорируются низкоуровневые детали вроде реализации языка программирования, «железа», на котором запущена программа, или набора команд в данном процессоре. Подсчёт миллисекунд тут мало поможет. Вполне может оказаться, что плохой алгоритм, написанный на низкоуровневом языке (например, ассемблере), будет намного быстрее, чем хороший алгоритм, написанный на языке программирования высокого уровня (например, на Python или C++). Так что пришло время определиться, что же такое «лучший алгоритм» на самом деле.

Алгоритм — это программа, которая представляет собой исключительно вычисление, без других часто выполняемых компьютером вещей — сетевых задач или пользовательского ввода-вывода. Анализ сложности позволяет нам узнать, насколько быстра эта программа, когда она совершает вычисления. Примерами чисто вычислительных операций могут послужить операции над числами с плавающей точкой (сложение и умножение), поиск заданного значения из находящейся в ОЗУ базы данных, или определение игровым искусственным интеллектом движения своего персонажа таким образом, чтобы он передвигался только на короткое расстояние внутри игрового мира. Очевидно, что вычисления встречаются в компьютерных программах повсеместно.

Анализ сложности также позволяет нам объяснить, как будет вести себя алгоритм при возрастании входного потока данных. Если наш алгоритм выполняется одну секунду при 1000 элементах на входе, то как он себя поведёт, если мы удвоим это значение? Будет работать также быстро, в полтора раза быстрее или в четыре раза медленнее? В практике программирования такие предсказания крайне важны. Например, если мы создали алгоритм для web-приложения, работающего с тысячей пользователей, и измерили его время выполнения, то используя анализ сложности, мы получим весьма неплохое представление о том, что случится, когда число пользователей возрастёт до двух тысяч. Для соревнований по построению алгоритмов анализ сложности также даст нам понимание того, как долго будет выполняться наш код на наибольшем из тестов для проверки его правильности. Так что если мы определим общее поведение нашей программы на небольшом объёме входных данных, то сможем получить хорошее представление и о том, что будет с ней при больших потоках данных.

Давайте начнём с простого примера: поиска максимального элемента в массиве.

 

Пример. Подсчёт инструкций

Максимальный элемент массива можно найти с помощью простейшего отрывка кода.

int M = A[0];

for(int i = 0; i < n; ++i)

{

if(A[i] >= M)

{

   M = A[i];

}

}

 

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

· присваивать значение переменной,

· находить значение конкретного элемента в массиве,

· сравнивать два значения,

· инкрементировать значение,

· складывать,

· вычитать,

· умножать,

· делить.

 

Мы будем полагать, что ветвление (выбор между if и else частями кода после вычисления if-условия) происходит мгновенно, и не будем учитывать эту инструкцию при подсчёте.

Для первой строки в приведенном коде:

int M = A[0];

требуются две инструкции: для поиска A[0] и для присвоения значения M (мы предполагаем, что n всегда как минимум равно 1). Эти две инструкции будут требоваться алгоритму вне зависимости от величины n.

Инициализация цикла for тоже будет происходить постоянно, что даёт нам ещё две команды: присвоение и сравнение:

i = 0; i < n;

Всё это происходит до первого запуска for. После каждой новой итерации мы будем иметь на две инструкции больше: инкремент i и сравнение для проверки, не пора ли нам останавливать цикл:

++i; i < n;

Таким образом, если мы проигнорируем содержимое тела цикла, то количество инструкций у этого алгоритма 4 + 2 n — четыре на начало цикла for и по две на каждую итерацию, которых мы имеем n штук.

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

Для цикла for с пустым телом f (n) = 4 + 2 n.

 

 

Анализ наиболее неблагоприятного случая

В теле цикла мы имеем операции поиска в массиве и сравнения, которые происходят всегда:

if (A[ i ] >= M) {...

Но тело if может запускаться, а может и нет, в зависимости от актуального значения из массива. Если произойдёт так, что A[ i ] >= M, то у нас запустятся две дополнительные команды - поиск в массиве и присваивание:

M = A[ i ]

Мы уже не можем определить f (n) так легко, потому что теперь количество инструкций зависит не только от n, но и от конкретных входных значений. Например, для A = [1, 2, 3, 4] программе потребуется больше команд, чем для A = [4, 3, 2, 1].

 

Когда мы анализируем алгоритмы, мы чаще всего рассматриваем наихудший сценарий. Каким он будет в нашем случае? Когда алгоритму потребуется больше всего инструкций до завершения? Ответ: когда массив упорядочен по возрастанию, как, например, A = [1, 2, 3, 4]. Тогда M будет переприсваиваться каждый раз, что даст наибольшее количество команд. Теоретики имеют для этого причудливое название — анализ наиболее неблагоприятного случая, который является ничем иным, как просто рассмотрением максимально неудачного варианта. Таким образом, в наихудшем случае в теле цикла из нашего кода запускаются четыре инструкции, и мы имеем f (n) = 4 + 2 n + 4 n = 6 n + 4.