Estoy leyendo esta publicación en Big-O
Dice que el siguiente código es O (n ^ 2):
bool ContainsDuplicates(String[] strings)
{
for(int i = 0; i < strings.Length; i++)
{
for(int j = 0; j < strings.Length; j++)
{
if(i == j) // Don't compare with self
{
continue;
}
if(strings[i] == strings[j])
{
return true;
}
}
}
return false;
}
Pero no puedo entender por qué.
El bucle interno hace algo constante.
Entonces es la suma de 1 .... N de una constante. es decir, número constante O (1).
El bucle externo es la suma sobre el O (1).
Entonces me imagino que es n * O (1).
Creo que estoy malentendido algo aquí.
No creo que todos los bucles anidados signifiquen O (n ^ 2), ¿verdad?
algorithms
performance
complexity
big-o
usuario10326
fuente
fuente
i+1lugar de0. Como está escrito, en el peor de los casos (sin engaños) 1/2 las comparaciones son redundantes.O(N), este código en realidad estaríaO(N^2 * M)donde M es la longitud de las cadenas.Respuestas:
Tu error es con el bucle interno. Hace algo constante n veces, por lo que es O ( n ). El bucle externo hace el bucle interno n veces, por lo que es O ( n × n ) u O ( n 2 ).
En general, si el número de iteraciones que realiza un bucle depende del tamaño de la entrada, es O ( n ). Y si k tales bucles están anidados, es O ( n k ).
fuente
ContainsDuplicatesno es muy probable que la función / método de la pregunta se use con cromosomas completos.Si la longitud de la cadena es
n, la prueba ifi == jse ejecutará n ^ 2 veces. El orden de un algoritmo es el orden de cualquier parte que tenga el orden más alto. Como 'i' se compara con 'j' n ^ 2 veces, el orden del algoritmo no puede ser menor queO(n^2).Para una 'n' muy grande, duplicar 'n' cuadruplicará el tiempo de ejecución.
fuente
i==jun O (1)?Estás malinterpretando lo que significa una operación constante.
Una operación constante es una operación que siempre se ejecuta en una cantidad fija de tiempo independiente de la entrada que recibe.
i == j es una operación constante porque ejecuta esta declaración en una cantidad de tiempo fija. Digamos que toma 1 unidad de tiempo.
Pero esta operación constante se realiza (no de valores de i) * (no de valores de j) veces. Digamos que i y j se ejecutan 10 veces cada uno. Luego, por cálculo, se requieren 100 unidades de tiempo para completar i == j cuando se encuentra en un bucle anidado. Por lo tanto, variará a medida que varían los valores de i y j.
Podemos estar seguros de que i == j se realizará en 1 unidad de tiempo, pero no podemos saber cuántas veces se realizará i == j.
Si se realiza n veces, tardará n unidades de tiempo. El bucle externo ejecuta el bucle interno n veces. Entonces, en esencia, i == j las operaciones se realizan n ^ 2 veces.
Todos los bucles anidados significan O (n ^ (no de bucles anidados)). Aquí O significa el límite superior, lo que significa que el código se ejecutará en menos o igual que el valor de O (). Esta es la garantía de que no tomará más tiempo que eso, pero puede tomar menos tiempo, no más.
fuente
Los bucles anidados ejecutan O ( i 1 * i 2 * ... * i n ), donde n es el número de bucles anidados e i x es el número de iteraciones en el bucle x . (O, para decirlo de otra manera, es el producto del número de iteraciones en cada uno de los bucles).
Su par de bucles itera sobre la misma matriz dos veces, que por coincidencia es O (n * n) u O (n 2 ).
Lo que sucede dentro del bucle más interno se trata como constante porque va a suceder siempre. La notación Big-O no se trata realmente de medir el rendimiento del código lineal, se trata más bien de hacer comparaciones relativas de cómo se comportan los algoritmos iterativos cuando se les da n elementos de entrada para tratar. Ciertas operaciones que en realidad no hacen ninguna iteración (como un push o pop en una pila) se clasifican como O (1) porque manejan un elemento de los datos.
fuente