Анализ алгоритма помогает нам определить, является ли алгоритм полезным или нет. Как правило, алгоритм анализируется на основе времени его выполнения (сложность времени) и количества пространства (сложность пространства), которое ему требуется.
Поскольку у нас есть сложные запоминающие устройства, доступные по разумной цене, пространство для хранения больше не является проблемой. Следовательно, космическая сложность не так важна.
Параллельные алгоритмы предназначены для повышения скорости вычислений на компьютере. Для анализа параллельного алгоритма мы обычно рассматриваем следующие параметры:
- Сложность времени (время выполнения),
- Общее количество используемых процессоров, и
- Общая стоимость.
Сложность времени
Основной причиной разработки параллельных алгоритмов было сокращение времени вычисления алгоритма. Таким образом, оценка времени выполнения алгоритма чрезвычайно важна при анализе его эффективности.
Время выполнения измеряется на основе времени, затраченного алгоритмом на решение проблемы. Общее время выполнения рассчитывается с момента начала выполнения алгоритма до момента его остановки. Если все процессоры не запускают или не завершают выполнение одновременно, то общее время выполнения алгоритма — это момент, когда первый процессор начал выполнение, до того момента, когда последний процессор прекратил выполнение.
Временную сложность алгоритма можно разделить на три категории:
-
В худшем случае сложность — когда количество времени, необходимое алгоритму для данного ввода, максимально .
-
Сложность среднего случая — когда количество времени, требуемое алгоритмом для заданного ввода, является средним .
-
Сложность в лучшем случае — когда количество времени, необходимое алгоритму для заданного ввода, минимально .
В худшем случае сложность — когда количество времени, необходимое алгоритму для данного ввода, максимально .
Сложность среднего случая — когда количество времени, требуемое алгоритмом для заданного ввода, является средним .
Сложность в лучшем случае — когда количество времени, необходимое алгоритму для заданного ввода, минимально .
Асимптотический анализ
Сложность или эффективность алгоритма — это количество шагов, выполняемых алгоритмом для получения желаемого результата. Асимптотический анализ проводится для расчета сложности алгоритма при его теоретическом анализе. В асимптотическом анализе большая длина входных данных используется для вычисления функции сложности алгоритма.
Примечание. Асимптотика — это состояние, при котором прямая имеет тенденцию встречаться с кривой, но они не пересекаются. Здесь линия и кривая асимптотичны друг другу.
Асимптотическая запись — это самый простой способ описать самое быстрое и самое медленное время выполнения алгоритма с использованием высоких и низких ограничений по скорости. Для этого мы используем следующие обозначения —
- Обозначение Big O
- Обозначение омега
- Тэта нотация
Обозначение Big O
В математике обозначение Big O используется для представления асимптотических характеристик функций. Он представляет поведение функции для больших входных данных простым и точным методом. Это метод представления верхней границы времени выполнения алгоритма. Он представляет собой наибольшее количество времени, которое алгоритм может занять для завершения своего выполнения. Функция —
f (n) = O (g (n))
если существуют положительные постоянные c и n 0, такие что f (n) ≤ c * g (n) для всех n, где n ≥ n 0 .
Обозначение омега
Нотация Omega — это метод представления нижней границы времени выполнения алгоритма. Функция —
f (n) = Ω (g (n))
если существуют положительные постоянные c и n 0, такие что f (n) ≥ c * g (n) для всех n, где n ≥ n 0 .
Тэта нотация
Тета-нотация — это метод представления как нижней, так и верхней границы времени выполнения алгоритма. Функция —
f (n) = θ (g (n))
если существуют положительные постоянные c 1 , c 2 и n 0, такие что c1 * g (n) ≤ f (n) ≤ c2 * g (n) для всех n, где n ≥ n 0 .
Ускорение алгоритма
Производительность параллельного алгоритма определяется путем расчета его ускорения . Ускорение определяется как отношение времени выполнения наихудшего случая самого быстрого известного последовательного алгоритма для конкретной задачи к времени наихудшего случая выполнения параллельного алгоритма.
Количество используемых процессоров
Количество используемых процессоров является важным фактором при анализе эффективности параллельного алгоритма. Стоимость покупки, обслуживания и запуска компьютеров рассчитывается. Чем больше число процессоров, используемых алгоритмом для решения задачи, тем дороже становится полученный результат.
Общая стоимость
Общая стоимость параллельного алгоритма является продуктом сложности времени и количества процессоров, используемых в этом конкретном алгоритме.
Общая стоимость = сложность времени × количество используемых процессоров
Следовательно, эффективность параллельного алгоритма составляет —