OBSERVAÇÃO - Esclarecimento aos leitores: Aproveitamos este texto da página (desativada) do Site do IME-USP do ano de 2005 por ser simples, mas com conteúdo substancial. Notem que o exemplo prático aqui é o determinar a Ordem de Complexidade de Algoritmos que venham a ter um “Procedure” (em Português, Procedimento) para determinar o produto de duas matrizes quadradas de ordem n (n linhas por n colunas). Isto significa que estamos interessados em calcular o tempo computacional T(n) para cada n. Mas se as duas matrizes envolvidas no produto de matrizes não fossem quadradas! Teríamos que determinar a Ordem de Complexidade para este novo procedimento (produto de matrizes não quadradas).

 

Em breve, estaremos abordando com mais amplidão este exemplo e variações dele, fornecendo a resposta para a Determinação da Ordem de Complexidade em questão. Só para se ter idéia de como abordando um novo Procedimento e, por conseguinte o novo Algoritmo envolvido, o problema pode mudar significativamente. Pensemos em procedimentos sugeridos abaixo:

 

1. Procedimento: Produto de duas (02) Matrizes quadradas de ordem n (n linhas e n colunas); T(n)=? , ou seja O(f(n))=? ou seja, qual é a expressão para f(n) - Um Polinômio, uma exponencial ou qual função envolvendo  a variável n é a mais apropriada?

2. Procedimento: Produto de duas (02) Matrizes de ordem n x m (n linhas e m colunas);

     T(n,m)=? , ou seja O(f(n,m))=? ou seja, qual é a expressão para f(n,m) - Um Polinômio, uma exponencial ou qual função envolvendo duas variáveis n e m é a mais apropriada?

1. Procedimento: Produtos de Matrizes A1, A2,...,Ap ou seja A1xA2x...xAp, onde cada matriz tem ordem, por exemplo nxm; mxq; qxr; ...e assim por diante até a ordem da matriz Ap - portanto, produtos sucessíveis de P matrizes.

    T(n,m,q,r,..,p)=? , ou seja O(f(n,m,q,r,...,P))=? ou seja, qual é a expressão para f(n,m,q,r,...,P) - Um Polinômio, uma exponencial ou qual função envolvendo as variáveis n,m,q,r,...,P é a mais apropriada? Bastante complexo este problema! Mas existe solução para ele – veja um pouco a respeito deste "procedure" no link:

           http://www.lia.ufc.br/~pargo/disciplinas/cana111/index.php/Manuscritos/Matrizes

 

1. Procedimento: Dada uma matriz quadrada A de ordem n, e o procedimento de obter o produto de AxAxAx...xA com m parcelas aparecendo  a Matriz A neste produto, isto é      .

     T(n,m)=? , ou seja O(f(n,m))=? ou seja, qual á expressão para f(n,m) - Um Polinômio, uma exponencial ou qual função envolvendo duas variáveis n e m é a mais apropriada?