Принципы анализа параллельных алгоритмов

При работе с параллельными алгоритмами нас будут интересовать два новых понятия: коэффициент ускорения и стоимость. Коэффициент ускорения параллельного алгоритма показывает, насколько он работает быстрее оптимального последовательного алгоритма. Так, мы видели, что оптимальный алгоритм сортировки требует O(Nlog N) операций. У параллельного алгоритма сортировки со сложностью O(N) коэффициент ускорения составил бы O(log N).

Второе интересующее нас понятие - стоимость параллельного алгоритма, которую мы определяем как произведение сложности алго┐ритма на число используемых процессоров. Если в нашей ситуации алгоритм параллельной сортировки за O(N) операций требует столько же процессоров, каково число входных записей, то его стоимость равна 0(N2). Это означает, что алгоритм параллельной сортировки обходится дороже, поскольку стоимость алгоритма последовательной сортировки на одном процессоре совпадает с его сложностью и равна поэтому О(N log N).