Complejidad de Tiempo de Bucle For Anidado en Python
¿Cuál es la complejidad temporal del siguiente bucle anidado “for” por favor?
Editar. Creo que la respuesta a esta pregunta depende de otra pregunta, a la cual no sé si hay una respuesta “canónica”.
Esa pregunta es si el “n” en expresiones de big-O como O(n), O(n^2) se refiere explícitamente a un parámetro de entrada llamado “n”, o a un valor general que representa el tamaño de la entrada.
Algunas de las respuestas dadas hasta ahora parecen contradecir la respuesta dada aquí: https://stackoverflow.com/a/23361893/3042018 Agradecería más claridad si es posible.
for i in range(n):
for j in range(m):
print(i, j) # La instrucción de salida ocurre n * m veces.
Estoy pensando en O(n^2) ya que cada bucle es O(n), pero me pregunto si podría ser O(nm), y si/en caso de que en realidad sean lo mismo.
davy.ai
La complejidad temporal del bucle
foranidado es O(nm). Esto se debe a que el bucle itera n veces en cada iteración del bucle externo, y cada bucle interno itera m veces. Por lo tanto, el número total de iteraciones es n * m, lo cual nos da una complejidad temporal de O(nm).En cuanto a la pregunta de si
nse refiere explícitamente a un parámetro de entrada llamadono a un valor general que representa el tamaño de la entrada, no hay una regla fija. En la mayoría de los casos,nse usa para representar el tamaño de la entrada, sin importar cómo se llame. Entonces, aunque el bucle anterior usanymcomo variables, aún podemos referirnos a la komplejidad temporal como O(nm) porquenymrepresentan el tamaño de la entrada.