Complejidad temporal para encontrar el n-ésimo número de Fibonacci usando matrices

Question

Complejidad temporal para encontrar el n-ésimo número de Fibonacci usando matrices

matrices
asintóticos
Matemáticas
álgebra lineal
Ciencias de la Computación
números de fibonacci

ceno980

Tengo una pregunta sobre la complejidad temporal de encontrar el n-ésimo número de Fibonacci usando matrices.

Sé que puedes encontrar $F_n$ de:

$\begin{pmatrix} 1 & 1\\ 1 & 0\\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\\ \end{pmatrix}$

Desde arriba, $F_n$ es la entrada en la fila 1, columna 2 de la matriz. He leído en una fuente en línea que elevar la matriz Q de Fibonacci a la potencia de n toma O (n) tiempo. No estoy seguro de por qué este es el caso. ¿Es la multiplicación de matrices una operación que se puede hacer en tiempo constante en las computadoras? Esa es la única razón por la que puedo ver que la operación anterior toma tiempo O (n) (ya que tendría que hacer n-1 multiplicaciones para elevar la matriz Q a la potencia de n). Cualquier idea es apreciada.

enojadoaviano

(Creo que tienes un error tipográfico en la ecuación: ¿el lado derecho no debe elevarse a una potencia?) Sí, ¿cuánto tiempo crees que lleva calcular el producto de dos

2 \times 2

$2 \times 2$ matrices?

ceno980

Sí, mi mal, lo arreglaré. Para calcular el producto de dos matrices de 2 x 2, hay 8 multiplicaciones y 4 sumas involucradas. La multiplicación y la suma toman un tiempo constante, pero dado que hay 12 operaciones involucradas, ¿no significaría esto que el tiempo tomado es O(n)?

usuario65203

Multiplicación de dos matrices de tamaño acotado (aquí

2 \times 2

$2\times2$ ) no puede tomar más que un tiempo constante, simplemente porque no hay

n

$n$ .

usuario65203

Para darle una idea de cómo se calculan eficientemente las potencias de la matriz, considere

A^{2} = A A, A^{4} = A^{2} A^{2}, A^{8} = A^{4} A^{4}, A^{16} = A^{8} A^{8}

$A^2=AA, A^4=A^2A^2,A^8=A^4A^4,A^{16}=A^8A^8$ , entonces por ejemplo

A^{20} = A^{16} A^{4}

$A^{20}=A^{16}A^4$ se obtiene en

5

$5$ multiplica

ceno980

Veo, evaluando

A^{2}

$A^2$ que toma una multiplicación, luego puedes evaluar

A^{4}

$A^4$ en una multiplicación también porque sabes

A^{2}

$A^2$ etcétera.

Respuestas (1)

Complejidad temporal para encontrar el n-ésimo número de Fibonacci usando matrices

(Creo que tienes un error tipográfico en la ecuación: ¿el lado derecho no debe elevarse a una potencia?) Sí, ¿cuánto tiempo crees que lleva calcular el producto de dos $2 \times 2$ matrices?
Sí, mi mal, lo arreglaré. Para calcular el producto de dos matrices de 2 x 2, hay 8 multiplicaciones y 4 sumas involucradas. La multiplicación y la suma toman un tiempo constante, pero dado que hay 12 operaciones involucradas, ¿no significaría esto que el tiempo tomado es O(n)?
Multiplicación de dos matrices de tamaño acotado (aquí $2\times2$ ) no puede tomar más que un tiempo constante, simplemente porque no hay $n$ .
Para darle una idea de cómo se calculan eficientemente las potencias de la matriz, considere $A^2=AA, A^4=A^2A^2,A^8=A^4A^4,A^{16}=A^8A^8$ , entonces por ejemplo $A^{20}=A^{16}A^4$ se obtiene en $5$ multiplica
Veo, evaluando $A^2$ que toma una multiplicación, luego puedes evaluar $A^4$ en una multiplicación también porque sabes $A^2$ etcétera.

tonyk · Answer 1

multiplicando dos $2\times 2$ las matrices se pueden hacer con ocho multiplicaciones y cuatro sumas, así que sí, eso es tiempo constante. (De hecho, se puede hacer en menos multiplicaciones a costa de más adiciones, pero el punto permanece).

Multiplicando un $2\times 2$ matriz por $\begin{pmatrix}1 & 1\\1 & 0\\\end{pmatrix}$ se puede hacer con solo dos adiciones, lo que es aún más rápido.

pero la informática $F_n$ usando $F_n=F_{n-1}+F_{n-2}$ toma solo una suma, entonces, ¿por qué usar matrices?

La respuesta es que la informática $M^n$ para una matriz $M$ en realidad se puede hacer usando $O(\log n)$ multiplicaciones y sumas, utilizando la exponenciación al cuadrado . ¡Échale un vistazo!

La multiplicación y la suma son solo operaciones de tiempo constante si el número de dígitos es fijo, ¿no? Pero el número de dígitos de $F_n$ crece linealmente.
@OscarLanzi Bueno, se necesita $O(n)$ tiempo sólo para leer todos los dígitos de $F_n$ . Entonces, $O(n \log n)$ ¿tal vez?

Complejidad temporal para encontrar el n-ésimo número de Fibonacci usando matrices

ceno980

enojadoaviano

ceno980

usuario65203

usuario65203

ceno980

Respuestas (1)

tonyk

jair taylor

jair taylor

Un límite superior para trace(A2)trace(A2)\text{trace}(A^2) en términos de trace(A)trace(A)\text{trace}(A)

Ax=bAx=bAx=b tiene solución sobre FpFp\Bbb{F}_p para todo primo p ⟹p ⟹p~\implica la existencia de una solución real??

Menor bordeado y rango de una matriz

Límite superior de una expresión elevada a la n-ésima potencia

Cómo encontrar la suma de elementos de eMeMe^M donde MMM es una matriz.

Usando la diagonalización de una simétrica en forma cuadrática

vectores simultáneamente ortogonales en dos formas bilineales diferentes con matrices diagonales

Encuentre todos los valores propios de la matriz AAA sin calcular su c. polinomio

Construya una matriz real para valores propios complejos dados

No negatividad del determinante de una matriz conmutativa