Для вычисления оценки сложности алгоритма рассмотрим для начала сложность одной итерации. Выберем в качестве обозначений:

i - номер итерации

m - число ограничений

p - число потоков

τ - время синхронизации

     Шаг 1 имеет достаточно высокую трудоёмкость, если с каждым шагом выполнять упорядочивание, в общем случае i/2. Однако если ввести дополнительную систему индексов - для каждой новой точки хранить номер точки, следующей за ней по порядку, а саму новую точку добавлять в конец массива точек, то сложность заметно сокращается, следует также заметить, что этот новый индекс вычислять не требуется - он берётся из предыдущей итерации алгоритма как номер интервала с максимальной характеристикой. Таким образом, сложность первого шага заключается в вычислении номера первого нарушенного ограничения для новой точки, то есть в худшем случае m, а также синхронизации, время выполнения которой τ.

     Шаг 2 также можно модифицировать для увеличения производительности. Константы Липшица не нужно пересчитывать для всех пар точек, их следует вычислять только для пар, составленных добавляемой точкой и точками, имеющими с добавляемой точкой одинаковый индекс. Вычисление оценок реализовано параллельно, трудоёмкость его i/p. Поиск минимума по результатам всех потоков последователен, его трудоёмкость p. На шаге выполняется две синхронизации.

     Шаг 3 аналогичен по трудоёмкости параллельной части шага 2, его трудоёмкость составляет i/p + τ.

     Шаг 4 аналогичен по трудоёмкости последовательной части шага 2, его трудоёмкость составляет p + τ.

     Шаг 5 имеет трудоёмкость одной операции

     Шаг 6 также имеет трудоёмкость одной операции.

     Таким образом, трудоёмкость i-той итерации составляет

T_i = m + τ + i/p + τ + p + τ + i/p + τ + p +τ + 1 + 1

     Трудоёмкость всего алгоритма составит сумму T_i по всем i от 1 до N, где N - общее число точек, необходимых для достижения заданной точности, то есть

T_p = N·(N/p + m + 5τ + 2p + 2)

К содержанию