4.2 Complexidade de algoritmos em álgebra linear

---

Nesta seção, discutiremos um importante conceito em teoria de algoritmos, a complexidade, isto é, uma medida do custo ou eficiência do algoritmo.

Dados dois algoritmos diferentes para resolver o mesmo problema, como podemos escolher qual desses algoritmos é o melhor? Se pensarmos em termos de eficiência (ou custo computacional), queremos saber qual desses algoritmos consome menos recursos para realizar a mesma tarefa.

Em geral podemos responder esta pergunta de duas formas: em termos de tempo ou de espaço.

Quando tratamos de eficiência espacial, queremos saber quanta memória (em geral RAM) é utilizada pelo algoritmo para armazenar os dados, sejam eles matrizes, vetores ou escalares.

Quando tratamos de eficiência temporal, queremos saber quanto tempo um algoritmo demanda para realizar determinada tarefa. Vamos nos concentrar neste segundo conceito, que em geral é o mais difícil de tratar.

Naturalmente o tempo vai depender do tipo de computador utilizado. É razoável pensar que o tempo vai ser proporcional ao número de operações de ponto flutuante (flops) feitas pelo algoritmo (observe que o tempo total não depende apenas disso, mas também de outros fatores como memória, taxas de transferências de dados da memória para o cpu, redes,...). Entretanto vamos nos concentrar na contagem do número de operações (flops) para realizar determinada tarefa.

No passado (antes dos anos 80), os computadores demoravam mais tempo para realizar operações como multiplicação e divisão, se comparados à adição ou à subtração. Assim, em livros clássicos eram contados apenas o custo das operações $\times$ e $∕$. Nos computadores atuais as quatro operações básicas demandam aproximadamente o mesmo tempo. Não obstante, como na maioria dos algoritmos de álgebra linear, o número de multiplicações e divisões é proporcional ao número somas e subtrações (pois a maioria dessas operações podem ser escritas como a combinações de produtos internos), é justificável dizer que o tempo de computação continua podendo ser estimado pelo número de multiplicações e divisões. Desta forma, na maior parte deste material, levaremos em conta somente multiplicações e divisões, a não ser que mencionado o contrário.

Teremos em mente que a ideia é estimar o custo quando lidamos com vetores e matrizes muito grande, isto é, o custo quando estas dimensões crescem infinitamente.

Solução. Seja $a\in ℝ$ e $x\in {ℝ}^n$, temos que

$$ax=\left[a\times x_1,a\times x_2,...,a\times x_n\right]$$

(4.56)

usando $n$ multiplicações, ou seja, um custo computacional, $C$, de

$$C=n\text{ flops}.$$

(4.57)

Solução. Sejam $x,y\in {ℝ}^n$, temos que

$$x\cdot y=x_1\times y_1+x_2\times y_2+...+x_n\times y_n$$

(4.58)

São realizadas $n$ multiplicações (cada produto $x_i$ por $y_i$) e $n-1$ somas, ou seja, o custo total de operações é de

$$C:=\left(n\right)+\left(n-1\right)=2n-1\text{ flops}$$

(4.59)

Solução. Sejam $A\in {ℝ}^{n\times n}$ e $x\in {ℝ}^n$, temos que

$$\left[\begin{array}{ccc}\hfill a_{11}\hfill & \hfill a_{12}\hfill & \hfill \cdots a_{1n}\hfill \\ \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill a_{n1}\hfill & \hfill \hfill & \hfill \cdots a_{nn}\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill ⋮\hfill \\ \hfill x_n\hfill \end{array}\right]=\left[\begin{array}{c}\hfill a_{11}\times x_1+a_{12}{x}_2+...+a_{1n}\times x_n\hfill \\ \hfill ⋮\hfill \\ \hfill a_{n1}\times x_1+a_{n2}{x}_2+...+a_{nn}\times x_n\hfill \end{array}\right]$$

(4.60)

Para obter o primeiro elemento do vetor do lado direito, devemos multiplicar a primeira linha de $A$ pelo vetor coluna $x$. Note que esse é exatamente o custo do produto vetor-vetor do exemplo anterior. Como o custo para cada elemento do vetor do lado direito é o mesmo e temos $n$ elementos, teremos que o custo para multiplicar matriz-vetor é¹

$$C:=n\cdot \left(2n-1\right)=2n^2-n\text{ flops}.$$

(4.62)

À medida que $n\to \infty$, temos

$$\mathcal{O}\left(2n^2-n\right)=\mathcal{O}\left(2n^2\right)=\mathcal{O}\left(n^2\right)\text{ flops.}$$

(4.63)

Solução. Sejam $A,B\in {ℝ}^{n\times n}$ temos que

$$\left[\begin{array}{ccc}\hfill a_{11}\hfill & \hfill a_{12}\hfill & \hfill \cdots a_{1n}\hfill \\ \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill a_{n1}\hfill & \hfill \hfill & \hfill \cdots a_{nn}\hfill \end{array}\right]\left[\begin{array}{ccc}\hfill b_{11}\hfill & \hfill b_{12}\hfill & \hfill \cdots a_{1n}\hfill \\ \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill b_{n1}\hfill & \hfill \hfill & \hfill \cdots b_{nn}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill c_{11}\hfill & \hfill c_{12}\hfill & \hfill \cdots c_{1n}\hfill \\ \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill c_{n1}\hfill & \hfill \hfill & \hfill \cdots c_{nn}\hfill \end{array}\right]$$

(4.64)

onde o elemento $d_{ij}$ é o produto da linha $i$ de $A$ pela coluna $j$ de $B$,

$$d_{ij}=a_{i1}\times b_{1j}+a_{i2}\times b_{2j}+...+a_{i2}\times b_{2j}$$

(4.65)

Note que este produto tem o custo do produto vetor-vetor, ou seja, $2n-1$. Como temos $n\times n$ elementos em $D$, o custo total para multiplicar duas matrizes é²

$$C=n\times n\times \left(2n-1\right)=2n^3-n^2\text{ flops.}$$

(4.67)