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.