Encontre a complexidade computacional
Quando se fala do tempo de execução de um algoritmo, é convencional fornecer a função mais simples AsymptoticEqual (big ) para a função exata de tempo de execução. Outra forma de afirmar essa igualdade é que cada função seja tanto AsymptoticLessEqual (big
) e AsymptoticGreaterEqual (big
) que a outra. Esses conceitos são ilustrados no contexto do algoritmo de Strassen, o primeiro algoritmo de multiplicação de matriz subcúbica encontrado.
O algoritmo consiste em quatro etapas: dividindo cada uma das matrizes em 4 submatrizes, formando 14 combinações lineares das 8 submatrizes, multiplicando 7 pares destes e somando os 7 resultados. O tempo
para fazer a multiplicação será, portanto, um tempo constante
para dividir a matriz,
para formar combinações lineares no segundo e quarto passos e
para o terceiro passo.
Resolva a relação de recorrência.
Embora o resultado seja complicado, .
Da mesma forma, e
.
Note que , então o algoritmo é subcúbico.
Compare a taxa de crescimento do algoritmo ingênuo cúbico e do algoritmo de Strassen.