Algoritmo in situ - In-place algorithm

En informática , un algoritmo in situ es un algoritmo que transforma la entrada sin una estructura de datos auxiliar . Sin embargo, se permite una pequeña cantidad de espacio de almacenamiento adicional para las variables auxiliares. La salida suele sobrescribir la entrada a medida que se ejecuta el algoritmo. Un algoritmo in situ actualiza su secuencia de entrada solo mediante el reemplazo o el intercambio de elementos. Un algoritmo que no está en el lugar a veces se llama no en el lugar o fuera de lugar .

In situ puede tener significados ligeramente diferentes. En su forma más estricta, el algoritmo solo puede tener una cantidad constante de espacio adicional , contando todo, incluidas las llamadas a funciones y los punteros . Sin embargo, esta forma es muy limitada ya que simplemente tener un índice para una matriz de longitud n requiere O (log n ) bits. En términos más generales, en el lugar significa que el algoritmo no utiliza espacio extra para manipular la entrada, pero puede requerir un espacio extra pequeño, aunque no constante, para su funcionamiento. Por lo general, este espacio es O (log n ) , aunque a veces se permite cualquier cosa en O ( n ) . Tenga en cuenta que la complejidad del espacio también tiene opciones variadas sobre si contar o no las longitudes del índice como parte del espacio utilizado. A menudo, la complejidad del espacio se da en términos del número de índices o punteros necesarios, ignorando su longitud. En este artículo, nos referimos a la complejidad del espacio total ( DSPACE ), contando 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 la longitud de índices y punteros.

Un algoritmo puede contar o no la salida como parte de su uso de espacio. Dado que los algoritmos in situ suelen sobrescribir su entrada con la salida, no se necesita espacio adicional. Al escribir la salida en una 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 las reducciones de espacio logarítmico , es más típico ignorar siempre el espacio de salida (en estos casos, es más esencial que la salida sea de solo escritura ).

Ejemplos de

Dada una matriz a de n elementos, suponga que queremos una matriz que contenga los mismos elementos en orden inverso y deshacerse del original. Una forma aparentemente simple de hacer esto es crear una nueva matriz de igual tamaño, llenarla con copias aen el orden apropiado y luego eliminarla a.

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

Desafortunadamente, esto requiere O ( n ) espacio extra para tener las matrices ay bdisponibles simultáneamente. Además, la asignación y la desasignación suelen ser operaciones lentas. Como ya no lo necesitamos a, podemos sobrescribirlo con su propia inversión usando este algoritmo en el lugar que solo necesitará un número constante (2) de enteros para las variables auxiliares iy tmp, sin importar cuán grande sea la matriz.

 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

Como otro ejemplo, muchos algoritmos de clasificación reorganizan las matrices en un orden ordenado en el lugar, que incluyen: clasificación de burbujas , clasificación de peine , clasificación de selección , clasificación de inserción , clasificación de pila y clasificación de Shell . Estos algoritmos requieren solo unos pocos punteros, por lo que su complejidad espacial es O (log n ) .

Quicksort opera en el lugar de los datos que se van a clasificar. Sin embargo, la ordenación rápida requiere O (log n ) punteros de espacio de pila para realizar un seguimiento de los subarreglos en su estrategia de dividir y conquistar . En consecuencia, la clasificación rápida necesita O (log ² n ) espacio adicional. Aunque este espacio no constante técnicamente elimina la ordenación rápida de la categoría en el lugar, la ordenación rápida y otros algoritmos que necesitan solo O (log n ) punteros adicionales generalmente se consideran algoritmos en el lugar.

La mayoría de los algoritmos de selección también están implementados, aunque algunos reorganizan considerablemente la matriz de entrada en el proceso de encontrar el resultado final de tamaño constante.

Algunos algoritmos de manipulación de texto, como recortar y revertir, pueden realizarse in situ.

En complejidad computacional

En la teoría de la complejidad computacional , la definición estricta de algoritmos in situ incluye todos los algoritmos con complejidad espacial O (1) , la clase DSPACE (1). Esta clase es muy limitada; es igual a los idiomas regulares . De hecho, ni siquiera incluye ninguno de los ejemplos enumerados anteriormente.

Por lo general, consideramos algoritmos en L , la clase de problemas que requieren O (log n ) espacio adicional, para estar en su lugar. Esta clase está más en línea con 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 la ordenación rápida debido a sus llamadas recursivas.

La identificación de 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 una ruta entre dos nodos en un gráfico no dirigido , un problema que requiere O ( n ) espacio adicional utilizando algoritmos típicos como la búsqueda en profundidad primero (un bit visitado para cada nodo). Esto, a su vez, produce algoritmos in situ para problemas como determinar si un gráfico es bipartito o probar si dos gráficos tienen el mismo número de componentes conectados . Consulte SL para obtener más información.

Papel de la aleatoriedad

En muchos casos, los requisitos de espacio de un algoritmo se pueden reducir drásticamente mediante el uso de un algoritmo aleatorio . Por ejemplo, digamos que deseamos saber si dos vértices en una gráfica de n vértices están en el mismo componente conectado de la gráfica. No existe un algoritmo in situ simple, determinista conocido para determinar esto, pero si simplemente comenzamos en un vértice y realizamos una caminata aleatoria de aproximadamente 20 n ³ pasos, existe la posibilidad de que nos encontremos con el otro vértice siempre que sea en el mismo componente es muy alto. De manera similar, existen algoritmos simples aleatorios en el lugar para las pruebas de primalidad, como la prueba de primaria de Miller-Rabin , y también hay algoritmos simples de factorización aleatoria en el lugar, como el algoritmo rho de Pollard . Consulte RL y BPL para obtener más información sobre este fenómeno.

En programación funcional

Los lenguajes de programación funcional a menudo desalientan o no admiten algoritmos explícitos en el lugar que sobrescriben datos, ya que este es un tipo de efecto secundario ; en cambio, solo permiten la construcción de nuevos datos. Sin embargo, los buenos compiladores de lenguaje funcional a menudo reconocerán cuando se crea un objeto muy similar a uno existente y luego se desecha el antiguo, y lo optimizarán en una simple mutación "bajo el capó".

Tenga en cuenta que, en principio, es posible construir cuidadosamente algoritmos in situ que no modifiquen los datos (a menos que los datos ya no se utilicen), pero esto rara vez se hace en la práctica. Ver estructuras de datos puramente funcionales .

Ver también

• Tabla de algoritmos de clasificación en el lugar y fuera del lugar

Referencias