ФУНКЦИЯ СЛОЖНОСТИ АЛГОРИТМА

Понятие эффективности алгоритма

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

Для оценки качества алгоритма вводится понятие сложность алгоритма, или — обратное понятие — эффективность алгоритма. Чем большее время и объем памяти необходимы для реализации алгоритма, тем больше его сложность и, соответственно, ниже эффективность. Сложность алгоритма подразделяется на временную и емкостную. Временная сложность — это критерий, характеризующий временные затраты на реализацию алгоритма. Емкостная сложность — критерий, характеризующий затраты памяти на те же цели. В зависимости от конкретной формы этих критериев сложность алгоритма, в свою очередь, подразделяется на практическую и теоретическую. Практическая временная сложность обычно оценивается во временных единицах (секунды, милисекунды, число временных тактов процессора, число выполнения циклов и т.д.). Практическая емкостная сложность выражается, как правило, в битах, байтах, словах и т.п. Способы представления теоретической сложности алгоритма будут рассмотрены далее.

Перечислим основные факторы, от которых может зависеть сложность алгоритма:

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

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

Этот вопрос очень тщательно прорабатывается в программировании. Эффективность программы является очень важной ее характеристикой. Эта характеристика имеет две составляющие: память (или пространство) и время. Пространственная эффективность измеряется объемом памяти, потребной для выполнения программы. Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Иногда память становится доминирующим фактором в оценке эффективности программ. Однако в последние годы в связи с быстрым удешевлением памяти эта составляющая эффективности постепенно теряет свое значение.

Временная эффективность программы определяется временем, необходимым для ее выполнения. Лучший способ сравнения эффективностей алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и к пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно через количество обрабатываемых данных. Например, некоторый алгоритм может существенно зависеть от размера обрабатываемого массива. Если, скажем, время обработки удваивается с удвоением размера массива, то порядок временной сложности алгоритма определяется как размер массива. Порядок алгоритма — это функция, доминирующая над точным выражением временной сложности. Функция f(n) имеет порядок 0(g(n)), если имеется константа к и счетчик nQ такие, что f(n) (kg(n)) для п > nQ.

Например, известно, что точное время обработки массива определяется из уравнения:

Грубое значение определяется вспомогательной функцией.

Функция сложности (О) выражает относительную скорость алгоритма в зависимости от некоторой переменной (переменных). Существуют три важных правила для определения функции сложности.

  • 1. 0(kf) = Oif). Здесь к обозначает константу, а/— функция. Это правило декларирует, что постоянные множители не имеют значения для определения порядка сложности, например, О (1,5-TV) = О (N).
  • 2. 0(fg) = 0(f)0(g) или 0(f/g) = 0(f)/0(g). Здесь/и g — функции. Из этого правила следует, что порядок сложности произведения двух функций равен произведению их сложностей, например, 0{{ 11-N) ? N) = 0{ 11-N) O(N) = 0(N) • O(N) = O(NN) = 0(N2).
  • 3. Oif + g) равна доминанте 0(f) и 0(g). Из этого правила следует, что порядок сложности суммы функций определяется как порядок доминанты первого и второго слагаемых, т.е. выбирается наибольший порядок, например, 0(N5 + N2) = 0(№).
 
Посмотреть оригинал