Wie kommt man zu einem nicht ganzzahligen Exponenten in der Zeitkomplexität? (zB

In regelmäßigen Abständen stoße ich auf Sätze wie

"Winograds Variante [20] dieses Algorithmus, dessen asymptotische Komplexität ebenfalls ist, wird berücksichtigt" (von https://www.cise.ufl.edu/~sahni/papers/strassen.pdf )$O(n^{2.81})$

Ich verstehe intuitiv, wie wir zu Komplexitäten wie und weil ich sehen kann, wie die Schleifen und Bäume funktionieren. Aber ich habe keine Ahnung, wie man eine Komplexität mit einer Dezimalstelle ableitet. Kann mir jemand ein Beispiel geben, wie das passiert?$O(n^2)$$O(n \log n)$

Die Laufzeitkomplexität des Strassenschen Algorithmus ist durch die Wiederholung (Mit einem geeigneten Basisfall.) Die Lösung dieser Wiederholung ist T ( n ) = O ( n log 2 7 ) .

Der Strassen-Algorithmus multipliziert zwei Matrizen A , B, indem er sie in jeweils vier ( n / 2 ) × ( n / 2 ) Matrizen zerlegt , wobei sieben lineare Kombinationen der jeweils kleineren Matrizen berechnet werden, beispielsweise ( A i , B i ) i = 1 , … , 7 , rekursives Berechnen von C i = A i B i und Berechnen der vier ( $n \times n$$A,B$$(n/2)\times(n/2)$$(A_i,B_i)_{i=1,\dots,7}$$C_i = A_i B_i$ Matrizen des Ergebnisses durch lineare Kombinationen der Matrizen C i . So entstand diese Laufzeit. Wenn Sie mehr erfahren möchten, gibt es viele Informationen zum Strassen-Algorithmus. Es gibt übrigens asymptotisch schnellere Algorithmen für die Matrixmultiplikation, der aktuelle Champion istLe Gall.$(n/2)\times(n/2)$$C_i$