Complejidad temporal de una función recursiva con dos llamadas.

Considere este código:

def count_7(lst): if len(lst) == 1: if lst[0] == 7: return 1 else: return 0 return count_7(lst[:len(lst)//2]) + count_7(lst[len(lst)//2:]) 

nota: las operaciones de corte serán consideradas como O (1).

Entonces, mi inutación me dice que es O (n * logn), pero estoy luchando para demostrarlo científicamente.
¡Alégrate por ayuda!

Ok, matemáticamente (más o menos) obtengo algo como esto:

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

Generalizando la ecuación:

 T(n) = 2^k * T(n/2^k) + (2^k - 1) * c T(1) = 1 

n/2^k == 1 cuando k == logN entonces:

 T(n) = 2^logN * T(1) + (2^logN - 1) * c 

ya que T(1) = 1 y aplicando propiedades logarítmicas

 T(n) = n * 1 + (n-1) * c T(n) = n + n * c T(n) = n * (1+c) T(n) = O(n) 

Una pista de que esto no es O(n*logn) es que no tiene que combinar los dos subproblemas. A diferencia de mergesort , donde tiene que combinar las dos subarreglas, este algoritmo no tiene que hacer nada con el resultado recursivo, por lo que su tiempo puede expressse como constante c .

ACTUALIZACIÓN: Intuición detrás

Este algoritmo debe ser O (n) porque visita cada elemento de la matriz solo una vez . Puede que no parezca trivial porque la recursión nunca lo es.

Por ejemplo, si divide el problema en dos subproblemas de la mitad del tamaño, cada subproblema se divide también en la mitad del tamaño y continuará hasta que cada subproblema sea del tamaño 1. Cuando termine, tendrá n subproblemas del tamaño 1. , que es n*O(1) = O(n) .

La ruta desde el principio del primer problema hasta que N problemas de tamaño 1 es logarítmica, porque en cada paso se subdivide en dos. Pero en cada paso no hace nada con el resultado, por lo que esto no agrega ninguna complejidad de tiempo a la solución.

Espero que esto ayude

La forma más fácil es asumir que n es un múltiplo de 2 por simplicidad: n = 2 m

La complejidad de tiempo de su algoritmo es (c es una constante):

 t(n) = 2 t(n/2) + c 

Y usando la recursión obtienes:

t(n) = 2 2 t(n/2 2 ) + 2c + c

...

= 2 log(n) t(n/2 log(n) ) + c(2 log(n)-1 + ... + 2 2 + 2 1 + 2 0 )

Lo que puede simplificarse notando que log(n) = m , y por lo tanto 2 log(n) = 2 m = n .

= n + c(2 log(n)-1 + ... + 2 2 + 2 1 + 2 0 )

Finalmente, la sum anterior se puede reducir a 2 log(n) (que es igual a n )

  t(n) = (1 + c) n 

Entonces tu solución es O (n)

Escaneas todos los elementos de la lista una vez, eso es O (n). La única diferencia con un escaneo recursivo simple es el orden en que los escanea. Usted hace 1, n / 2, 2, 3 / 4n, etc … en lugar de 1,2,3 … pero la complejidad es la misma.