recorrer - C#- complejidad de tiempo para generar todos los pares en una matriz

programa que imprima numeros pares e impares en c++

Question

Dado un conjunto de números, genera todos los pares únicos.

Por ejemplo, dado [ 1, 2, 3, 4, 5 ] el par de números únicos sería:

(1, 2), (1, 3), (1, 4), (1, 5)

(2, 3), (2, 4), (2, 5)

(3, 4), (3, 5)

(4, 5)

Mi solución es la siguiente:

int[] numbers = new int[] { 1, 2, 3, 4, 5 };
HashSet<Pair> pairs = new HashSet<Pair>();

for(int i = 0; i < numbers.Length; i++)
{
    for(int j = i + 1, j < numbers.Length; j++)
    {
        pairs.Add(new Pair(numbers[i], numbers[j]));
    }
}

Creo que la complejidad del tiempo para esto se ve como O (n ² - 1) restando 1 porque la iteración de j es siempre 1 más corta que i

Después de investigar un poco este tipo de problema, no puedo encontrar respuestas definitivas sobre si esto se puede hacer más rápido. ¿Hay mejores soluciones que O (n ² - 1)?

Answer 1

Creo que la complejidad del tiempo para esto se ve como O (n2 - 1) restando 1 porque la iteración de j es siempre 1 más corta que i

Si importaba (la notación en O grande usualmente solo escribe el término con el crecimiento más rápido), allí tiene iteraciones de i sobre [0, n) cada una con una iteración de j sobre [i + 1, n), por lo que el número de iteraciones es (n ∙ (n-1)) / 2 no n²-1.

Además, su edición al cambiar a HashSet en lugar de a la lista cambia la ejecución en el peor de los casos, aunque no el valor amortizado . Si Pair.GetHashCode () siempre devolviera el mismo valor, lo habría subido a O (n³), como en los casos en que las colisiones son comunes, la inserción de conjuntos de hash se convierte en O (n) en lugar de constante.

Answer 2

Esta es un área de un algoritmo de triángulo .

Tienes N entradas y quieres un triángulo de salidas .

Tu triángulo de salida tiene una altura de N-1 y un ancho de N-1 .

Area of a triangle = height * width / 2
                   = (N-1)  * (N-1) / 2
                   = (N^2 - 2N + 1) / 2

O(n^2 - n) siempre será el costo mínimo / óptimo del algoritmo!

Answer 3

Una de las maneras de pensar acerca de "hay una manera más rápida de resolver el problema" es mirar el tamaño de la salida para algún formato específico (que considere "probablemente el más grande / más difícil de resolver").

Si la salida es O(n^2) , entonces no puede resolver el problema más rápido que en O(n^2) , porque tiene que gastar al menos O(1) para cada salida.

Puede ver el patrón allí, si tiene 5 números en formato [1, 2, 3, 4, 5] , los pares únicos toman

4 pairs in first row
3 pairs in second row
2 pairs...
1 pair

porque se ven como

(1, 2), (1, 3), (1, 4), (1, 5)

(2, 3), (2, 4), (2, 5)

(3, 4), (3, 5)

(4, 5)

Si tiene 20 variables en matriz (en formato [1, 2, 3,... 18, 19, 20] ), será como sigue:

19 pairs
18 pairs
...
2 pairs
1 pair

Por lo tanto, el tamaño de salida es (n-1) + (n-2) + (n-3) ... + 3 + 2 + 1 . Tienes que sumarlo (mira cómo sumar la serie) y el resultado es O(n^2)

¿Qué fue probado?

Que el peor de los casos es POR LO MENOS O(n^2) .

También tenga en cuenta que, en este momento, no sabemos cuál es la complejidad del peor de los casos: el algoritmo puede ser incluso más lento (solo encontramos que algunas entradas toman O(n^2) ). Sabemos con certeza que al menos estos datos toman O(n^2) . Puede ser más rápido o más lento para diferentes entradas.

Conlusión : tenemos pruebas de que el algoritmo toma al menos O(n^2) tiempo (como el peor de los casos), usted creó un algoritmo que se ejecuta en un máximo de O(n^2) tiempo (como se describe en la publicación de spyc) = Tienes algoritmo óptimo.

Información adicional para la solución de OP: Detectar colisiones con HashSet es solo "pseudoConstante" y solo para números pequeños y "algo de suerte". Se necesita O(n) para una gran cantidad de números. Así que puede terminar en n^2 salida y cada uno de ellos tarda hasta n en procesarse, lo que lleva a n^3 complejidad.

Puedes resolverlo preprocesando la tarea:

1) Clasifíquelo: solo toma n log n , por lo que no afecta a n^2 todos modos

2) Eliminar números que se repiten más de dos veces [1, 3, 3, 3, 5] -> [1, 3, 3, 5] , es O(n)

3) Luego usa tu algoritmo con esta actualización:

3.1) al comienzo de for i ciclo for i : if (number[i] == number[i-1]) continue;

3.2) Al comienzo de for j ciclo for j : Recordar el último par. Cuando agregue un nuevo par, mire al último par y verifique si es el mismo o no. Si es así, continue;

Ejemplo:

Input: [1, 3, 3, 5]

1)i=0, j=1, number[0]=1, number[1]=3 -> add (1, 3)
2)i=0, j=2, number[0]=1, number[2]=3 -> same as last pair, use continue
3)i=0, j=3, number[0]=1, number[3]=5 -> add (1, 5)
4)i=1, j=2, number[1]=3, number[2]=3 -> add (3, 3)
5)i=1, j=3, number[1]=3, number[3]=5 -> add (3, 5)
6)i=2, before go to j-cycle, check number[i] === number[i-1] It is true, use continue

Answer 4

Va como sigue:

first for loop - O(n)
    second for loop - O(n-1)

Óptima complejidad de tiempo:

• A pesar de que esa iteración es insignificante, debe calcular la complejidad de tiempo para el peor de los casos, que es

También puede usar el coeficiente binomial para permutaciones, para obtener el número de permutaciones de una cadena determinada. Por ejemplo:

Si tiene 6 dígitos {0,1,2,3,4,5} (n = 6), y quiere saber cuántas permutaciones diferentes puede hacer, es decir: (3,5), (5,3) etc ... entonces (k = 2, dos dígitos en cada grupo), la cantidad de permutaciones será:

diferentes permutaciones, tenga en cuenta que en este caso (3,5), (5,3) se cuentan de forma individual, por lo que el orden de todo es importante. Si desea que (5,3) y (3,5) se cuenten como una combinación , la ecuación es la siguiente:

Ejemplo de implementación, calculando permutaciones!

static long factorial(long x) // calcs the factorial TimeCmplx = O(n)
{
    if (x == 1)
        return x;
    return x * factorial(x - 1);
}

static long permutations(long n , long k) //Check that (n , k) >= 0
{            
    // Permutations , n!/(n-k)!
    return factorial(n) / factorial(n - k);
}