¿Existe una forma de generar matemáticamente un índice determinado en una matriz de sumas de permutaciones ordenadas, dada un conjunto fuente, en tiempo O(1) o O(log N)?

Se me proporciona un conjunto de enteros de tamaño N en orden ascendente. Para mayor simplicidad, este conjunto “arr” es el siguiente: [a0, a1, a2, …, aN]. Necesito el conjunto de la suma de todos los pares ai y aj, permitiendo duplicados: [a0 + a0, a0 + a1, a0 + a2, …, a1 + a0, a1 + a1, … aN + aN], tamaño N^2. Sin embargo, lo necesito en orden para realizar una búsqueda binaria (en tiempo O(log(N^2))) sin tener que generar el conjunto completo, lo cual tomaría un tiempo de O(N^2 log(N^2)). Dado que una búsqueda binaria solo necesita los valores del conjunto en ciertos índices, me preguntaba si existe una función matemática para determinar el valor del conjunto de suma permutada ordenado dada un índice específico (por ejemplo, value(3) devolvería ak + am), permitiéndome realizar una búsqueda binaria en el conjunto sin generarlo por completo. Estaba pensando en algo como:

int value(int index) { return arr[index/N] + arr[index%N]; }

pero esto no toma en cuenta que el valor de arr[i] + arr[k] puede ser mayor que arr[i+1] + arr[k-5], por ejemplo, a pesar de que arr[i+1] > arr[i]. En resumen, ¿existe alguna forma de particionar en menos de O(N) tiempo para este caso especial de conjunto? Para mis propósitos, también aceptaría una solución que genere el conjunto completo y ordenado en menos de O(N^2) tiempo.

davy.ai

July 23, 2023 at 7:38 pm

Solución para encontrar el arreglo de suma de permutaciones ordenado

Para generar el arreglo de suma de permutaciones ordenado, necesitamos calcular la suma de todas las posibles parejas de elementos del arreglo dado arr. Si generamos este arreglo completo, tomaría tiempo O(N^2).

Para realizar una búsqueda binaria en el arreglo de suma de permutaciones ordenado, necesitamos generar este arreglo en orden. En lugar de generar el arreglo completo, podemos calcular el valor del arreglo de suma de permutaciones ordenado dado un índice específico utilizando el siguiente enfoque.

Podemos ver que la suma de una pareja de elementos del arreglo arr es máxima cuando tomamos el primer elemento del final del arreglo y el segundo elemento del final del arreglo. Por lo tanto, el valor máximo del arreglo de suma de permutaciones ordenado sería arr[N-1] + arr[N-1].

De manera similar, el valor mínimo del arreglo de suma de permutaciones ordenado sería arr[0] + arr[0].

Ahora, podemos aplicar una búsqueda binaria en este arreglo 1D. Para cualquier índice dado en el arreglo de suma de permutaciones ordenado, valor(i), podemos encontrar la pareja correspondiente ai y aj utilizando la siguiente fórmula:

ai = arr[i/N]
aj = arr[i%N]

Este enfoque reduce la complejidad temporal de generar el arreglo de suma de permutaciones ordenado a O(N log N), y podemos realizar la búsqueda binaria en O(log(N^2)).

Alternativamente, si no nos preocupamos por la complejidad temporal de generar el arreglo de suma de permutaciones ordenado, podemos usar el siguiente código para generar el arreglo completo en O(N^2) de tiempo.

suma_permutacion_ordenada = []
for i in range(N):
    for j in range(N):
        suma_permutacion_ordenada.append(arr[i] + arr[j])
suma_permutacion_ordenada.sort()

Esto nos dará el arreglo de suma de permutaciones ordenado, y podemos realizar la búsqueda binaria en él en O(log(N^2)) de tiempo.

Answer

davy.ai

July 23, 2023 at 7:38 pm
Solución para encontrar el arreglo de suma de permutaciones ordenado

Para generar el arreglo de suma de permutaciones ordenado, necesitamos calcular la suma de todas las posibles parejas de elementos del arreglo dado arr. Si generamos este arreglo completo, tomaría tiempo O(N^2).

Para realizar una búsqueda binaria en el arreglo de suma de permutaciones ordenado, necesitamos generar este arreglo en orden. En lugar de generar el arreglo completo, podemos calcular el valor del arreglo de suma de permutaciones ordenado dado un índice específico utilizando el siguiente enfoque.

Podemos ver que la suma de una pareja de elementos del arreglo arr es máxima cuando tomamos el primer elemento del final del arreglo y el segundo elemento del final del arreglo. Por lo tanto, el valor máximo del arreglo de suma de permutaciones ordenado sería arr[N-1] + arr[N-1].

De manera similar, el valor mínimo del arreglo de suma de permutaciones ordenado sería arr[0] + arr[0].

Ahora, podemos aplicar una búsqueda binaria en este arreglo 1D. Para cualquier índice dado en el arreglo de suma de permutaciones ordenado, valor(i), podemos encontrar la pareja correspondiente ai y aj utilizando la siguiente fórmula:
```
ai = arr[i/N]
aj = arr[i%N]
```
Este enfoque reduce la complejidad temporal de generar el arreglo de suma de permutaciones ordenado a O(N log N), y podemos realizar la búsqueda binaria en O(log(N^2)).

Alternativamente, si no nos preocupamos por la complejidad temporal de generar el arreglo de suma de permutaciones ordenado, podemos usar el siguiente código para generar el arreglo completo en O(N^2) de tiempo.
```
suma_permutacion_ordenada = []
for i in range(N):
    for j in range(N):
        suma_permutacion_ordenada.append(arr[i] + arr[j])
suma_permutacion_ordenada.sort()
```
Esto nos dará el arreglo de suma de permutaciones ordenado, y podemos realizar la búsqueda binaria en él en O(log(N^2)) de tiempo.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

¿Existe una forma de generar matemáticamente un índice determinado en una matriz de sumas de permutaciones ordenadas, dada un conjunto fuente, en tiempo O(1) o O(log N)?

Answer

davy.ai

Solución para encontrar el arreglo de suma de permutaciones ordenado