Измерение сложности задачи

Мы начнем с возвращения к изучению эффективности алгоритмов, начатому в разделе 4.6. Там мы применяли ©-представление (большая тета-представле-ние) для классификации алгоритмов в зависимости от времени их выполнения. Мы узнали, что алгоритм сортировки вставкой принадлежит классу 0(и2), алгоритм последовательного поиска — классу Э(и), а алгоритм бинарного поиска — классу @(\gn). Теперь эта классификационная система поможет нам вычислять сложность задач. Наша цель — разработать классификационную систему, при помощи которой можно будет определить, какие проблемы являются более сложными, чем другие, и, в итоге, какие проблемы настолько сложны, что их решение невозможно в практическом смысле.

Причина того, что мы базируем наше текущее исследование на знании эффективности алгоритмов, состоит в том, что мы хотим измерить сложность проблем в терминах сложности их решений. Мы считаем задачу простой, если ее решение просто; сложная задача — это задача, для которой нет простого решения. Обратите внимание: тот факт, что решение задачи является сложным, не означает, что сама проблема сложна. Действительно, у задачи может быть несколько решений, и одно из них просто обязано быть сложным. Следовательно, чтобы утверждать, что проблема сложна, необходимо показать, что ни одно из ее решений не является простым.

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

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

Интерпретацию, которая более точно отражает сложность алгоритма, можно получить, рассматривая алгоритмы с точки зрения машины. В этом контексте мы измеряем сложность алгоритма в терминах времени, необходимого для его выполнения, которое пропорционально количеству требуемых действий. Обратите внимание, что это количество не совпадает с числом команд в написанной программе. Цикл, тело которого состоит из одного оператора печати, но который должен выполниться 100 раз, во время выполнения эквивалентен 100 операторам печати. Следовательно, такая процедура считается более сложной, чем список из 50 отдельно написанных операторов печати, хотя этот список выглядит длиннее в тексте программы. Дело в том, что значение сложности в конечном итоге определяется временем, которое требуется машине для выполнения алгоритма, а не размером программы, представляющей решение.

Таким образом, мы считаем задачу сложной, если для ее решения требуется много времени. Это определение сложности называется временной сложностью (time complexity). Мы уже неявно познакомились с концепцией временной сложности во время изучения эффективности алгоритмов в главе 4 (раздел 4.6). Действительно, изучение эффективности алгоритмов выливается в изучение их временной сложности — это всего лишь две стороны одной медали. То есть «более эффективный» алгоритм равен «менее сложному». Так, в терминах временной сложности, алгоритм последовательного поиска (эффективность которого равна ©(и)) является более сложным решением задачи поиска в списке, чем алгоритм бинарного поиска (чья эффективность равна 0(lg n)).

Применим наши знания сложности алгоритмов в поиске способов определения сложности задач. Мы считаем, что (временная) сложность задачи равна Э(У(гс)), где /(и) — это некоторая математическая функция от п, если существует алгоритм решения этой задачи, временная сложность которого равна Q(f(n)), и не существует других алгоритмов решения с меньшей временной сложностью. То есть (временная) сложность задачи определяется как (временная) сложность ее наилучшего решения. К сожалению, поиск лучшего решения задачи и доказательство, что оно действительно лучшее, — это зачастую сложная проблема сама по себе. В таких ситуациях для обозначения того, что нам известно о сложности задачи, применяется О-представление (вариант в-представления). Точнее, если f(ri) — это математическая зависимость от п и если задачу можно решить алгоритмом класса @(/(п)), то мы говорим, что это задача класса О(/(п)). То есть говоря, что задача принадлежит О(/(и)), мы имеем в виду, что для нее есть решение со сложностью 0(/(и)), но, возможно, существуют и более хорошие решения.