Algoritmo in situ

En informática , un algoritmo in situ es aquel que opera directamente sobre la estructura de datos de entrada sin requerir espacio adicional proporcional al tamaño de la entrada. En otras palabras, modifica la entrada directamente, sin crear una copia separada de la estructura de datos. Un algoritmo que no es in situ se denomina a veces no in situ o fuera de lugar .

El término "in situ" puede tener significados ligeramente diferentes. En su forma más estricta, el algoritmo solo puede tener una cantidad constante de espacio adicional , incluyendo llamadas a funciones y punteros . Sin embargo, esta forma es muy limitada, ya que simplemente tener un índice a un array de longitud n requiere O (log n ) bits. En términos más generales, "in situ" significa que el algoritmo no usa espacio adicional para manipular la entrada, pero puede requerir un pequeño espacio adicional, aunque no constante, para su operación. Por lo general, este espacio es O (log n ) , aunque a veces se permite cualquier valor en o ( n ) . Cabe señalar que la complejidad espacial también presenta diversas opciones en cuanto a si se incluyen o no las longitudes de los índices como parte del espacio utilizado. A menudo, la complejidad espacial se expresa en términos del número de índices o punteros necesarios, sin tener en cuenta su longitud. En este artículo, nos referimos a la complejidad espacial total ( DSPACE ), que incluye las longitudes de los punteros. Por lo tanto, los requisitos de espacio aquí tienen un factor log n adicional en comparación con un análisis que ignora las longitudes de los índices y punteros.

Un algoritmo puede o no considerar la salida como parte de su uso de espacio. Dado que los algoritmos in situ generalmente sobrescriben su entrada con la salida, no se necesita espacio adicional. Al escribir la salida en memoria de solo escritura o en un flujo, puede ser más apropiado considerar solo el espacio de trabajo del algoritmo. En aplicaciones teóricas, como reducciones de espacio logarítmico , es más común ignorar siempre el espacio de salida (en estos casos es más esencial que la salida sea de solo escritura ).

Dado un arraya de n elementos, supongamos que queremos un array que contenga los mismos elementos en orden inverso y eliminar el original. Una forma aparentemente sencilla de hacerlo es crear un nuevo array del mismo tamaño, llenarlo con copias del original aen el orden apropiado y luego eliminar el original a.

función inversa(a[0..n - 1]) asignar b[0..n - 1] para i desde 0 hasta n - 1 b[n − 1 − i] := a[i] return b

Unfortunately, this requires O(n) extra space for having the arrays a and b available simultaneously. Also, allocation and deallocation are often slow operations. Since we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant number (2) of integers for the auxiliary variables i and tmp, no matter how large the array is.

function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp

As another example, many sorting algorithms rearrange arrays into sorted order in-place, including: bubble sort, comb sort, selection sort, insertion sort, heapsort, and Shell sort. These algorithms require only a few pointers, so their space complexity is O(log n).^[1]

Quicksort operates in-place on the data to be sorted. However, quicksort requires O(log n) stack space pointers to keep track of the subarrays in its divide and conquer strategy. Consequently, quicksort needs O(log²n) additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only O(log n) additional pointers are usually considered in-place algorithms.

Most selection algorithms are also in-place, although some considerably rearrange the input array in the process of finding the final, constant-sized result.

Some text manipulation algorithms such as trim and reverse may be done in-place.

In computational complexity theory, the strict definition of in-place algorithms includes all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular languages.^[2] In fact, it does not even include any of the examples listed above.

Los algoritmos suelen considerarse en L , la clase de problemas que requieren un espacio adicional de O (log n ) para su procesamiento in situ. Esta clase se ajusta mejor a la definición práctica, ya que permite números de tamaño n como punteros o índices. Sin embargo, esta definición ampliada aún excluye el algoritmo Quicksort debido a sus llamadas recursivas.

Identificar los algoritmos in situ con L tiene algunas implicaciones interesantes; por ejemplo, significa que hay un algoritmo in situ (bastante complejo) para determinar si existe un camino entre dos nodos en un grafo no dirigido , ^{[ 3 ]} un problema que requiere O ( n ) espacio adicional usando algoritmos típicos como la búsqueda en profundidad (un bit visitado para cada nodo). Esto a su vez produce algoritmos in situ para problemas como determinar si un grafo es bipartito o probar si dos grafos tienen el mismo número de componentes conexas .

En muchos casos, los requisitos de espacio de un algoritmo pueden reducirse drásticamente utilizando un algoritmo aleatorio . Por ejemplo, si se desea saber si dos vértices en un grafo de n vértices están en el mismo componente conexo del grafo, no existe un algoritmo simple, determinista e in situ conocido para determinar esto. Sin embargo, si simplemente comenzamos en un vértice y realizamos un recorrido aleatorio de aproximadamente 20 n ³ pasos, la probabilidad de que encontremos el otro vértice, siempre que esté en el mismo componente, es muy alta. De manera similar, existen algoritmos aleatorios in situ simples para pruebas de primalidad, como la prueba de primalidad de Miller-Rabin , y también existen algoritmos aleatorios in situ simples de factorización, como el algoritmo rho de Pollard .

Los lenguajes de programación funcional suelen desaconsejar o no admitir algoritmos explícitos que sobrescriban datos, ya que esto es un tipo de efecto secundario ; en su lugar, solo permiten la creación de nuevos datos. Sin embargo, los buenos compiladores de lenguajes funcionales suelen reconocer cuando se crea un objeto muy similar a uno existente y luego se descarta el anterior, y optimizan esto para convertirlo en una simple mutación internamente.

Cabe señalar que, en principio, es posible construir cuidadosamente algoritmos que no modifiquen los datos (a menos que estos ya no se utilicen), pero esto rara vez se hace en la práctica.

• Tabla de algoritmos de ordenación in situ y no in situ