Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

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 × 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 grandes, isto é, o custo quando estas dimensões crescem infinitamente.

Exemplo 4.2.1 (Produto escalar-vetor). Qual o custo para multiplicar um escalar por um vetor?

Solução. Seja a e x n, temos que

ax = [a × x1,a × x2,...,a × xn] (4.44)

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

C = n flops. (4.45)

Exemplo 4.2.2 (Produto vetor-vetor). Qual o custo para calcular o produto interno x y?

Solução. Sejam x,y n, temos que

x y = x1 × y1 + x2 × y2 + ... + xn × yn (4.46)

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

C := (n) + (n - 1) = 2n - 1 flops (4.47)

Exemplo 4.2.3 (Produto matriz-vetor). Qual o custo para calcular o produto de matriz por vetor Ax?

Solução. Sejam A n×n e x n, temos que

a11 a12 a1n a n1 ann x1 x n = a11 × x1 + a12x2 + ... + a1n × xn a n1 × x1 + an2x2 + ... + ann × xn (4.48)

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 é1

C := n (2n - 1) = 2n2 - n flops. (4.50)

À medida que n , temos

O(2n2 - n) = O(2n2) = O(n2) flops. (4.51)

Exemplo 4.2.4 (Produto matriz-matriz). Qual o custo para calcular o produto de duas matrizes A e B?

Solução. Sejam A,B n×n temos que

a11 a12 a1n a n1 ann b11 b12 b1n b n1 bnn = d11 d12 d1n d n1 dnn (4.52)

onde o elemento dij é o produto da linha i de A pela coluna j de B,

dij = ai1 × b1j + ai2 × b2j + ... + ain × bnj (4.53)

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

C = n × n × (2n - 1) = 2n3 - n2 flops. (4.55)

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!