Algoritmo Paralelo - Análise

A análise de um algoritmo nos ajuda a determinar se o algoritmo é útil ou não. Geralmente, um algoritmo é analisado com base em seu tempo de execução(Time Complexity) e a quantidade de espaço (Space Complexity) Isso requer.

Como temos sofisticados dispositivos de memória disponíveis a um custo razoável, o espaço de armazenamento não é mais um problema. Conseqüentemente, a complexidade do espaço não recebe tanta importância.

Algoritmos paralelos são projetados para melhorar a velocidade de computação de um computador. Para analisar um algoritmo paralelo, normalmente consideramos os seguintes parâmetros -

Complexidade de tempo (tempo de execução),
Número total de processadores usados, e
Custo total.

Complexidade de tempo

A principal razão por trás do desenvolvimento de algoritmos paralelos foi reduzir o tempo de computação de um algoritmo. Assim, avaliar o tempo de execução de um algoritmo é extremamente importante na análise de sua eficiência.

O tempo de execução é medido com base no tempo gasto pelo algoritmo para resolver um problema. O tempo total de execução é calculado a partir do momento em que o algoritmo começa a ser executado até o momento em que ele para. Se todos os processadores não iniciam ou terminam a execução ao mesmo tempo, então o tempo total de execução do algoritmo é o momento em que o primeiro processador inicia sua execução até o momento em que o último processador interrompe sua execução.

A complexidade de tempo de um algoritmo pode ser classificada em três categorias−

Worst-case complexity - Quando a quantidade de tempo exigida por um algoritmo para uma determinada entrada é maximum.
Average-case complexity - Quando a quantidade de tempo exigida por um algoritmo para uma determinada entrada é average.
Best-case complexity - Quando a quantidade de tempo exigida por um algoritmo para uma determinada entrada é minimum.

Análise Assintótica

A complexidade ou eficiência de um algoritmo é o número de etapas executadas pelo algoritmo para obter a saída desejada. A análise assintótica é feita para calcular a complexidade de um algoritmo em sua análise teórica. Na análise assintótica, um grande comprimento de entrada é usado para calcular a função de complexidade do algoritmo.

Note - Asymptoticé uma condição em que uma linha tende a encontrar uma curva, mas elas não se cruzam. Aqui, a linha e a curva são assintóticas entre si.

A notação assintótica é a maneira mais fácil de descrever o tempo de execução mais rápido e mais lento possível para um algoritmo usando limites altos e limites baixos de velocidade. Para isso, usamos as seguintes notações -

Notação Big O
Notação Omega
Notação teta

Notação Big O

Em matemática, a notação Big O é usada para representar as características assintóticas das funções. Ele representa o comportamento de uma função para grandes entradas em um método simples e preciso. É um método de representar o limite superior do tempo de execução de um algoritmo. Ele representa o tempo mais longo que o algoritmo pode levar para concluir sua execução. A função -

f (n) = O (g (n))

se existirem constantes positivas c e n₀ de tal modo que f(n) ≤ c * g(n) para todos n Onde n ≥ n₀.

Notação Omega

A notação Omega é um método de representar o limite inferior do tempo de execução de um algoritmo. A função -

f (n) = Ω (g (n))

se existirem constantes positivas c e n₀ de tal modo que f(n) ≥ c * g(n) para todos n Onde n ≥ n₀.

Notação Theta

A notação Theta é um método de representar o limite inferior e o limite superior do tempo de execução de um algoritmo. A função -

f (n) = θ (g (n))

se existirem constantes positivas c₁, c₂, e n₀ de modo que c1 * g (n) ≤ f (n) ≤ c2 * g (n) para todos n Onde n ≥ n₀.

Aceleração de um Algoritmo

O desempenho de um algoritmo paralelo é determinado pelo cálculo de sua speedup. A aceleração é definida como a razão entre o tempo de execução do pior caso do algoritmo sequencial mais rápido conhecido para um problema específico e o tempo de execução do pior caso do algoritmo paralelo.

speedup =

Pior caso de tempo de execução do sequencial conhecido mais rápido para um problema particular / Pior caso de tempo de execução do algoritmo paralelo

Número de processadores usados

O número de processadores usados é um fator importante na análise da eficiência de um algoritmo paralelo. O custo para comprar, manter e operar os computadores é calculado. Quanto maior o número de processadores usados por um algoritmo para resolver um problema, mais caro se torna o resultado obtido.