Параллельное программирование



              

Сложность алгоритма и проблема распараллеливания


Ранее уже использовалось понятие сложности. Рассмотрим его полнее.

Пусть задан некоторый алгоритм A. Почти всегда существует параметр n, характеризующий объем его данных. Пусть функция T(n) — время выполнения A, а f — некоторая функция от n. Говорят, что алгоритм A имеет теоретическую (асимптотическую) сложность O(f(n)), если

\frac{T(n)}{f(n)} \xrightarrow[n\rightarrow\infty]{}k
,

где k — действительное.

Если алгоритм выполняется за фиксированное время, не зависящее от размера задачи, говорят, что его сложность равна O(1).

Это определение обобщается в случае, если время выполнения существенно зависит от нескольких параметров. Например, алгоритм, определяющий, входит ли множество m элементов в множество n элементов, может иметь, в зависимости от используемых структур данных, сложность O (m n) или O (m+n).

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

  • максимальную сложность, определяемую значением Tmax(n) — время выполнения алгоритма, когда выбранный набор n данных порождает наиболее долгое время выполнения алгоритма;
  • среднюю сложность, определяемую значением Tср(n) — средним временем выполнения алгоритма, примененного к n произвольным данным.

Эти понятия без труда распространяются на измерение сложности в единицах объема памяти: можно говорить о средней и максимальной пространственной сложности.

Самыми лучшими являются линейные алгоритмы, имеющие сложность порядка an=b. Они называются также алгоритмами порядка O(n) где n — размерность входных данных. Такие алгоритмы действительно существуют. Например, сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое — из m цифр, требует не более max(n, m) сложений и не более max(n, m) запоминаний. Т.е. данный алгоритм имеет сложность порядка O(n+m). Разумеется, это выражение показывает только порядок величины — постоянные факторы в нем не учитываются.




Содержание  Назад  Вперед