¿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.