Comment se retrouve-t-on avec un exposant non entier en complexité temporelle? (par exemple,

Je rencontre périodiquement des phrases comme

"Variante de Winograd [20] de cet algorithme, dont la complexité asymptotique est également $O(n^{2.81})$sont considérés "(à partir de https://www.cise.ufl.edu/~sahni/papers/strassen.pdf )

Je comprends intuitivement comment nous nous retrouvons avec des complexités comme $O(n^2)$ et $O(n \log n)$parce que je peux voir comment les boucles et les arbres fonctionnent. Mais je n'ai aucune idée de comment on finit par dériver une complexité avec une décimale. Quelqu'un peut-il me donner un exemple de la façon dont cela se produit?

La complexité du temps d'exécution de l'algorithme de Strassen est donnée par la récurrence

L'algorithme de Strassen multiplie deux $n \times n$ matrices $A,B$ en les décomposant en quatre $(n/2)\times(n/2)$ matrices chacune, calculant sept combinaisons linéaires des plus petites matrices chacune, disons $(A_i,B_i)_{i=1,\dots,7}$, calcul récursif $C_i = A_i B_i$et calculer les quatre $(n/2)\times(n/2)$ matrices du résultat en prenant des combinaisons linéaires des matrices $C_i$. C'est ainsi que ce temps de course a vu le jour. Si vous voulez en savoir plus, il y a beaucoup d'informations sur l'algorithme de Strassen. Il existe d'ailleurs des algorithmes asymptotiquement plus rapides pour la multiplication matricielle, le champion actuel étant Le Gall .