Общее время (time complexity) параллельного алгоритма
Параллельный
алгоритм можно охарактеризовать общим временем. Начнем с оценки числа
вычислительных шагов, включающих в себя все арифметические и логические
операции. Их число в терминах количества данных будет характеризовать
затраченное на вычисления время. Для этого введем систему обозначений
O.
Определение:
f(x)=O(g(x)) тогда и
только тогда, если существуют положительные константы c и
x0 такие, что 0=f(x)=c*g(x) для любых
x>=x0, где f(x) и g(x) функции от
x.
Пример:
Для f(x)=4x2+2x+12: константа
c=6 подходит для формального определения
f(x)=O(x2), поскольку
0<4x2+2x+12=6x2 для x>=3.
Мы можем понимать О( ) как "рост по крайней мере так быстро
как".
Аналогично можно ввести оценку снизу: omega( )
Определение:
f(x)=omega(g(x)) тогда и только
тогда, если существуют положительные константы c и
x0 такие, что 0<=c*g(x)<=f(x) для любых
x>=x0.
[Назад] [Оглавление] [Вперед]
Последнее обновление 21.11.2001 WebMaster