Cuando es una relación de recurrencia lineal

Question

En http://www.cs.fsu.edu/~lacher/courses/COT5405/spring07/notes2.html, se dice que $T(n) = aT(n/b) + f(n) $ es recurrencia no lineal.

Pero creo que es lineal ya que es lineal en $T(n)$ $T(n/b)$.

Así que me preguntaba ¿cómo se define una recurrencia lineal?

Gracias y saludos!

Answer 1

Un lineal de la recurrencia de la relación no tiene términos con más de un factor recurrente.

Es decir,

$$T(n) = T(n-1)T(n-2) + T(n-3)$$

no es lineal debido a que el plazo $T(n-1)T(n-2)$, pero

$$T(n) = T(n/2) + T(n/3) + 1$$

es lineal.

Una de recurrencia es de orden finito es aquel en que el número de pasos atrás que uno toma " son especificadas por una constante (que es finito). Así

$$T(n) = T(n-1) +1$$

es de orden finito, pero

$$T(n) = T(n/2) +1$$

no es.

Una recurrencia tiene coeficientes constantes si, naturalmente, todos los coeficientes son constantes. Así

$$T(n) = n(T(n-1) + T(n-2))$$

no cuenta con coeficientes constantes, pero

$$T(n) = 2 T(n/2)T(n-1) + n^2 $$

tiene coeficientes constantes.

Una recurrencia es homogéneo si todos los términos tienen un factor que es recurrente. Así

$$T(n) = n^2 T(n-1)T(n-2) + T(n-3)^3$$

es homogénea, sino

$$T(n) = T(n-1) + 1 $$

no ha homogénea.

Así que en mi idioma, $T(n)=aT(n/b)+f(n)$ es lineal, pero no de orden finito y no homogénea (y sería ortogonalmente llamado dividir y conquistar la recurrencia).

Esas son las definiciones que me siga (y aprendido de algún lugar - textos sobre matemáticas discretas - creo Rosen, Liu, Tucker). Si esas son las notas de una clase que está tomando, me gustaría ir con esa definición, mientras que usted está tomando la clase, y ser muy conscientes de que otros textos de uso de diferentes significados.

Como una adición, estas definiciones son útiles, cualquiera que sea su desajuste con lo que se puede esperar, si coinciden con la terminología utilizada en otros ...oh... duh... la terminología para las recurrencias se basa en que de ecuaciones diferenciales lineales. Bastante mucho la misma cosa.