Estoy tratando de analizar este código a continuación. Deseo calcular tanto la complejidad como la cantidad de operaciones / iteraciones (lo que conduce a la complejidad). Mi conjetura es que la complejidad es O (n ^ 2), ya que he anidado para bucles. Sin embargo, dentro del ciclo interno, los valores están cambiando, reemplazando lugares. ¿Esta operación no hace que el algoritmo repita las cosas más de una vez y, por lo tanto, es más que O (n ^ 2), o solo es posible con un bucle while? ¿Cómo encuentro el número exacto de iteraciones/operaciones realizadas?
for (int i = 0; i < b.Length; i++) { for (int j = i + 1; j < b.Length; j++) { if (b[i] > b[j]) { t = b[i]; b[i] = b[j]; b[j] = t; } } }El bucle exterior tiene iteraciones b.length . Llamemos a eso n .
El ciclo interno tiene n - i - 1 iteraciones.
El número total de iteraciones del ciclo interno es
(n - 1) + (n - 2) + ... + 1 = n * (n -1) / 2 = O(n^2). Cada iteración del ciclo interno realiza un trabajo constante, como máximo 1 condición + 3 asignaciones, por lo que el tiempo total de ejecución es O(n^2) .
El número exacto de operaciones depende de la entrada, ya que la entrada determina cuántas veces se cumple la condición.
El número de bucles está controlado por b.length que es una constante y las variables de índice i y j. Siempre que no se entrometa con i y j dentro del bucle, la complejidad sigue siendo la misma.