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

1. ВВЕДЕНИЕ В РАЗРАБОТКУ И АНАЛИЗ АЛГОРИТМОВ

1.1. Вычисление веса двоичного вектора

Рассмотрим последовательность элементов х = (xi, …, х_п), где каждый элемент Xi может принимать значения 0 и 1, ж» € {0,1}. Назовем последовательность х n-мерным двоичным век­тором с элементами (координатами) Xj, а весом И^(х) вектора х — число его ненулевых элементов. Тогда сформулируем задачу.

Задача 1.1. Найти вес двоичного вектора х = (a?i,… ,х_п)-На первый взгляд, задача нахождения веса вектора может быть решена тривиально, простым последовательным рассмотре­нием элементов вектора и сравнением их с нулем. То же самое может быть также записано как вычисление

п

W(x) = 5>«.                               (1.1)

t=l

Вычисления в (1.1) — пример решения задачи методом пе­ребора, т.е. имея конечное множество объектов, рассматриваем их один за другим (перебираем), возможно выполняя при этом какие-то действия или вычисления для нахождения искомого от­вета.

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

Определение 1.1

Для двух функций /(га) и g(ri) запишем /(га) = 0(g(n)), если

С > 0,                                            (1.2)

п^со д(п) для некоторой константы С.

Определение 1.2

Для двух функций /(га) и д(п) запишем /(га) = о(з(га)), если

lim Щ = 0.                                             (1.3)

п-^оо

Обозначения О(-) и о(), введенные определениями 1.1 и 1.2, позволяют оценивать скорость роста функции /(га) относительно скорости роста функции д(п). Часто с помощью этих обозначе­ний оценивают сложность того или иного алгоритма, где га — раз­мерность задачи (параметр, непосредственно влияющий на слож­ность); д(п) — некоторая известная функция (линейная, степен­ная, логарифмическая, экспоненциальная и т.д.), а /(га) — слож­ность алгоритма. В случае выполнения (1.2) говорят, что функ­ция /(га) «растет, как» функция д(п) или «имеет порядок» д(п). В случае выполнения (1.3) говорят, что функция /(га) «растет мед­леннее, чем» функция д(п) или «имеет порядок, меньший, чем» д(п). Например, функция /(га) = 2га + 1 имеет порядок О(та), а функция /(га) = Зга³ + 5га² 4- 2 имеет порядок 0(га³).

В качестве /(га) может рассматриваться как число некоторых элементарных действий, операций (или, проще говоря, требуемое «время» выполнения), так и объем данных, которые необходи­мо хранить (требуемая «память»). Критерии время/память часто могут обмениваться одно на