Введение
Временная сложность алгоритма – это необходимые для его выполнения затраты по времени. Данная характеристика представляет собой функцию, которая каждой входной длине n задачи ставит в соответствие максимальное (среди всех отдельных задач той же длины) время, затрачиваемое алгоритмом на решение этих задач.
Несмотря на то, что функция временной сложности не является полностью определённой до тех пор, пока не зафиксирована схема кодирования, задающая входную длину индивидуальной задачи и не выбрано вычислительное устройство (или его модель), влияющее на время выполнения алгоритма, мы абстрагируемся от этих деталей, так как на самом деле от них существенно не зависит распределение всего многообразия задач на различные классы сложности.
Классификация вычислительных задач по сложности
Часто на практике недостаточно знать, что некоторая задача разрешима с помощью компьютерной программы. Ещё важно правильно оценить ресурсы и составить эффективный алгоритм решения этой задачи.
Главным критерием оптимальности алгоритма является время его выполнения.
Напомним, что время выполнения алгоритма удобно выражать в виде функции от одной переменной, обозначающей размер индивидуальной задачи, т. е. объём входных данных задачи, необходимых для её описания.
В теории алгоритмов существует такое понятие как класс сложности задач, каждый из которых включает в себя вычислительные задачи, однотипные по сложности своего решения.
Перечислим эти классы задач:
- Класс P. Задачи из этого класса могут быть разрешены за полиноминальное время с помощью детерминированной вычислительной машины. Именно такие алгоритмы считаются наиболее эффективными. Примерами задач, относящихся к этому классу, являются задачи, использующие стандартные алгоритмы целочисленного сложения, умножения, деления, нахождения НОД, перемножения матриц, сортировки массивов, поиска данных и некоторые другие алгоритмы.
- Класс E. Это задачи, алгоритмы решения которых имеют экспоненциальную сложность. Например, к этому классу относятся такие задачи, в которых требуется построить все подмножества заданного множества или все поддеревья заданного графа. Экспоненциальные алгоритмы значительно отличаются друг от друга по своей сложности.
- Класс NP. Это класс недетерминированно-полиномиальных алгоритмов. Сюда относятся задачи, в условиях которых не содержатся экспоненциальные исчисления, но в то же время для многих из них так и не разработан эффективный полиномиальный алгоритм решения.
Среди всех задач класса NP можно выделить самые сложные – NP-полные задачи. Такие задачи образуют подмножество типовых задач в классе NP, то есть если для какой-то из них найден полиномиально быстрый алгоритм решения, то и любая другая задача из класса NP может быть решена так же быстро.
Далее перечислены примеры NP-полных задач:
- задача о выполнимости булевых формул;
- кратчайшее решение «пятнашек» размера n × n;
- проблема раскраски графа и составления расписаний;
- задачи с применением методов оптимизации (об оптимальном отборе данных, об эффективном размещении обслуживающих центров, о наиболее выгодной загрузке транспорта или рюкзака, об оптимальном раскрое ткани, бумаги и прочего, а также задачи, связанные с построением эффективных маршрутов и с оптимизацией инвестиционных проектов).
Несмотря на то, что обычно задача считается сложной, если для её решения невозможно создать полиномиальный алгоритм, бывают и такие ситуации, в которых экспоненциальные алгоритмы оказываются довольно эффективными. Например, симплекс-метод, используемый для решения задач линейного программирования.
Экспериментальный метод оценки сложности алгоритма
Этот метод основан на измерении времени выполнения алгоритма на некотором наборе входных данных. При этом используются стандартные средства языка программирования, позволяющие определить системное время компьютера.
Рассмотрим, например язык программирования Java с его встроенным методом System.CurrentTimeMillis (), с помощью которого отсчитывается время с точностью до миллисекунд. Более того, здесь есть возможности и по более точному вычислению времени (до наносекунд) при помощи метода System.nanoTime(), но он работает не на всех платформах.
При проведении эксперимента на ЭВМ, направленного на анализ трудоёмкости (сложности) какого-либо алгоритма, достаточно запомнить время перед началом выполнения алгоритма и зафиксировать его в конце, например, с помощью следующего фрагмента:
Рисунок 1. Код. Автор24 — интернет-биржа студенческих работ
В итоге, после выполнения этого кода, искомое время в наносекундах будет храниться в переменной traceTime.
Быстродействие современных процессоров с тактовой частотой в несколько Гигагерц имеет порядок нескольких десятков миллиардов операций в секунду. При этом время выполнения простых алгоритмов может быть очень малым, а измерение его при помощи такого метода будет иметь большую погрешность. Чтобы её уменьшить можно задать программе выполнить исследуемый фрагмент кода многократно внутри цикла (например, несколько десятков или сотен тысяч раз), а затем полученную величину traceTime разделить на число повторений в цикле этого фрагмента программы.
