En informática , un algoritmo in situ es un algoritmo que opera directamente en la estructura de datos de entrada sin requerir espacio adicional proporcional al tamaño de entrada. En otras palabras, modifica la entrada en el lugar, sin crear una copia separada de la estructura de datos. Un algoritmo que no está en el lugar a veces se denomina fuera de 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, in situ significa que el algoritmo no utiliza espacio adicional para manipular la entrada, pero puede requerir un espacio adicional pequeño, aunque no constante, para su funcionamiento. Por lo general, este espacio es O (log n ) , aunque a veces se permite cualquier valor en o ( n ) . Tenga en cuenta que la complejidad del espacio también tiene opciones variadas en cuanto a 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 total del espacio ( 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 los índices y punteros.
Un algoritmo puede contar o no la salida como parte de su uso de espacio. Dado que los algoritmos locales generalmente sobrescriben su entrada con la salida, no se necesita espacio adicional. Al escribir la salida en una memoria de solo escritura o en una secuencia, puede ser más apropiado considerar únicamente 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 ).
Dada una matriz a de n elementos, supongamos que queremos una matriz que contenga los mismos elementos en orden inverso y deseche el original. Una forma aparentemente sencilla de hacer esto es crear una nueva matriz de igual tamaño, llenarla con copias aen el orden apropiado y luego eliminarla a.
función inversa(a[0..n - 1]) asignar b[0..n - 1] para i de 0 a n - 1 segundo[norte − 1 − yo] := un[yo] regresar b
Desafortunadamente, esto requiere O ( n ) espacio adicional para tener las matrices adisponibles bsimultáneamente. Además, la asignación y desasignación suelen ser operaciones lentas. Como ya no lo necesitamos a, podemos sobrescribirlo con su propia inversión usando este algoritmo local que solo necesitará un número constante (2) de números enteros para las variables auxiliares iy tmp, sin importar cuán grande sea la matriz.
función reverse_in_place(a[0..n-1]) para i desde 0 hasta piso((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 orden in situ, incluidos: clasificación de burbujas , clasificación de peine , clasificación de selección , clasificación de inserción , clasificación de montón y clasificación de Shell . Estos algoritmos requieren sólo unos pocos punteros, por lo que su complejidad espacial es O (log n ) . [1]
Quicksort opera in situ sobre los datos que se van a ordenar. Sin embargo, la clasificación rápida requiere punteros de espacio de pila O (log n ) para realizar un seguimiento de los subarreglos en su estrategia de dividir y conquistar . En consecuencia, la ordenación rápida necesita O (log 2 n ) espacio adicional. Aunque este espacio no constante técnicamente elimina la ordenación rápida de la categoría in situ, la ordenación rápida y otros algoritmos que solo necesitan O (log n ) punteros adicionales generalmente se consideran algoritmos in situ.
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 e invertir, se pueden realizar in situ.
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 . [2] De hecho, ni siquiera incluye ninguno de los ejemplos enumerados anteriormente.
Los algoritmos generalmente se consideran 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 todavía excluye la ordenación rápida debido a sus llamadas recursivas.
Identificar los algoritmos locales con L tiene algunas implicaciones interesantes; por ejemplo, significa que existe un algoritmo local (bastante complejo) para determinar si existe una ruta entre dos nodos en un gráfico no dirigido , [3] un problema que requiere O ( n ) espacio adicional usando algoritmos típicos como profundidad -primera búsqueda (un bit visitado por cada nodo). Esto, a su vez, produce algoritmos implementados para problemas como determinar si un gráfico es bipartito o probar si dos gráficos tienen el mismo número de componentes conectados .
En muchos casos, los requisitos de espacio de un algoritmo se pueden reducir drásticamente mediante el uso de un algoritmo aleatorio . Por ejemplo, si uno desea saber si dos vértices en un gráfico de n vértices están en el mismo componente conectado del gráfico, no existe ningún algoritmo simple, determinista e in situ conocido para determinarlo. Sin embargo, si simplemente comenzamos en un vértice y realizamos un recorrido aleatorio de aproximadamente 20 n 3 pasos, la probabilidad de que nos topemos con el otro vértice siempre que esté en el mismo componente es muy alta. De manera similar, existen algoritmos simples aleatorios in situ para pruebas de primalidad, como la prueba de primalidad de Miller-Rabin , y también existen algoritmos simples de factorización aleatoria in situ, como el algoritmo rho de Pollard .
Los lenguajes de programación funcional a menudo desaconsejan o no admiten algoritmos explícitos in situ que sobrescriben datos, ya que esto es un tipo de efecto secundario ; en cambio, sólo permiten que se construyan nuevos datos. Sin embargo, los buenos compiladores de lenguajes funcionales 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 locales que no modifiquen los datos (a menos que los datos ya no se utilicen), pero esto rara vez se hace en la práctica.