Число шагов выполнения компараторов сортировки-слияния при использовании нечетно-четного слияния Бэтчера на p процессорах оценивается как:
Общее время сортировки n элементов методом нечетно-четного слияния Бэтчера на p процессорах оценивается как:
Как соотносятся времена сортировки одного и того же массива с помощью алгоритмов простой вставки и слияния:
Эффективность параллельного алгоритма сортировки n элементов на p процессорах с помощью сетей нечетно-четного слияния Бэтчера в предположении нулевой латентности и нулевого времени на передачу данных равна:
Алгоритму пузырьковой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:
Алгоритму сортировки слиянием в наихудшем случае наиболее точно соответствует оценка числа операций:
Алгоритму быстрой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:
число операций при решении трехдиагональной системы из N линейных уравнений методом прогонки пропорционально:
Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:
Отметьте сети, правильно сортирующие любой массив из 4-х элементов с помощью компараторов слияния (a,b) выполняющих сравнение-перестановку элементов с номерами a и b:
