Esforço computacional de algoritmos

$\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$$x_\text{opt}$$x_0$$x_\text{opt}.$$x$$\epsilon-$$\mathcal{O}$

Suponha que existam dois algoritmos iterativos $\mathcal{A}_1$ e $\mathcal{A}_2$ para encontrar uma solução $\epsilon-$ close de $\mathcal{O}$ com as seguintes propriedades:

1. Para qualquer $\epsilon > 0,$ o esforço computacional total, ou seja, o esforço necessário por iteração $\times$ o número total de iterações, para encontrar uma solução $\epsilon-$ close é o mesmo para ambos os algoritmos.
2. O esforço por iteração para $\mathcal{A}_1$ é $O(n),$ exemplo, enquanto que o $\mathcal{A}_2$ é $O(n^2).$

Existem situações em que um prefere um algoritmo ao outro? Por quê?

Normalmente, é muito difícil, se não impossível, implementar uma versão paralela de um algoritmo iterativo que paraleliza as iterações. A conclusão de uma iteração é um ponto de sequência natural. Se um algoritmo requer menos iterações, mas mais trabalho por iteração, é mais provável que esse algoritmo possa ser efetivamente implementado em paralelo.

Um exemplo disso é a programação linear, em que o método da barreira primária-dupla (ponto interior) normalmente usa apenas algumas dezenas de iterações, mesmo para problemas muito grandes, mas o trabalho por iteração é bastante extenso. Em comparação, várias versões do método simplex normalmente exigem muito mais iterações, mas o trabalho por iteração é menor. Na prática, implementações paralelas de métodos de pontos interiores mostraram eficiência paralela muito melhor do que implementações paralelas do método simplex.

Eu posso pensar em algumas possibilidades:

Se ambos os algoritmos reduzirem monotonicamente o erro a cada iteração, talvez seja preferível que alguns tenham iterações mais baratas, pois oferecem mais opções sobre quando parar a iteração.

Se é trabalho e tempo, mas memória, você pode preferir se for grande. pode até ser grande o suficiente para fazer com que você selecione pois o uso da memória tem mais chances de restringi-lo aqui.$\mathcal{A}_1$$O(n)$$O(n^k)$$\mathcal{A}_2$$k$$k=2$$\mathcal{A}_2$

Isso provavelmente se aplica se estamos falando sobre otimização ou qualquer outra classe de problema iterativo.