¿Es la complejidad temporal de las declaraciones for, while y if anidadas la misma? Supongamos que a se da como una matriz de longitud n .
for _ in range(len(a)): for _ in range(len(a)): do_somethingLa declaración for anterior será O(n²).
i = 0 while i < len(a) * len(a): do_something i += 1A primera vista, el ciclo anterior puede considerarse como O(n), pero al final creo que también es O(n²).
¿Tengo razón?
¿Tengo razón?
¡Sí!
El doble bucle:
for _ in range(len(a)): for _ in range(len(a)): do_something tiene una complejidad de tiempo de O(n) * O(n) = O(n²) porque cada bucle se ejecuta hasta n .
El bucle único:
i = 0 while i < len(a) * len(a): do_something i += 1 tiene una complejidad de tiempo de O(n * n) = O(n²), porque el bucle se ejecuta hasta i = n * n = n² .
De hecho, todavía es O (n ^ 2). Eso es especialmente claro cuando observa el ciclo que tiene iteraciones len(a)*len(a).
Usted "aplanó" los bucles, pero no cambió la cantidad de trabajo, por lo tanto, es solo un cambio "estilístico" y no tiene impacto en la complejidad.
Necesitamos determinar la complejidad del tiempo en función de la cantidad de operaciones que llevan a cabo las construcciones en mi humilde opinión. No sería correcto generalizar y decir que ciertos bucles tienen una complejidad de tiempo particular.
La complejidad de tiempo de los bucles for anidados generalmente sería O (n al cuadrado), no siempre. Algunos bucles for anidados involucrados también pueden tener una complejidad O(n). una sola declaración if generalmente sería O (1) ya que solo está haciendo comparaciones básicas. while loop podría ser cualquier cosa dependiendo de su condición de salida.
Si bien podría ser útil tener en cuenta generalizaciones como estas, siempre debemos verificar la cantidad de operaciones realizadas para determinar la complejidad.
Permítanme complementar las otras respuestas.
¿Cambia la complejidad del tiempo cuando dos bucles anidados se reescriben en un solo bucle?
Si hacen el mismo trabajo, la complejidad no cambia. :-) Si lo hace, entonces (al menos) uno de ellos está haciendo un trabajo innecesario.
Me disculpo si voy demasiado lejos, pero déjame adivinar: Tu pensamiento fue:
Si ese es su pensamiento, solo necesita un ajuste: para el bucle único, si "n" es la longitud del bucle , tenga en cuenta que n = len(a) * len(a); si cambia el significado de "n" de un problema a otro, no puede comparar (para los bucles anidados, n = len(a)). En cualquier caso, ambos códigos tienen una complejidad O(len(a) * len(a)), que es lo que ya encontraste.
Complejidad de tiempo denota aprox. límite superior de tiempo para cualquier programa. Calculemos matemáticamente la Complejidad del Tiempo para ambos y compruébelo.
Para bucle:
for _ in range(len(a)): for _ in range(len(a)): do_somethingEl bucle for externo se ejecuta O (len (a)) veces y el bucle for interno se ejecuta O (len (a)). Que se ejecuta independientemente del bucle for externo durante O (len (a)) tiempo.
toma n=len(a)
Podemos derivar la siguiente función:
F(n) = 1*n +2*n +3*n +4*n +..........+(n-1)*n+n*n (if n starts from 1) F(n) = n(1+2++3+4+....+(n-1)+n) F(n) = n*(n+(n+1)/2) (Sum of n Natural Numbers) F(n) = n^2 + 2*n + n/2 (After Solving the Equation) F(n) = O(n^2)Para bucle Mientras
i = 0 while i < len(a) * len(a): do_something i += 1Podemos deducirlo directamente ya que se ejecutará en:
len(a)*len(a) = n*n=O(n^2)Podemos decir que Ambos tienen aproximadamente el mismo tiempo de ejecución, por lo que la Complejidad sigue siendo la misma.