En informática , un algoritmo in situ es un algoritmo que opera directamente sobre la estructura de datos de entrada sin requerir espacio adicional proporcional al tamaño de entrada. En otras palabras, modifica la entrada in situ, sin crear una copia separada de la estructura de datos. Un algoritmo que no está in situ a veces se denomina no in situ o fuera de lugar .
En el lugar 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 usa espacio adicional para manipular la entrada, pero puede requerir un espacio adicional pequeño aunque no constante para su operación. 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 en cuanto a si contar o no las longitudes de los índices como parte del espacio utilizado. A menudo, la complejidad del espacio se da en términos de la cantidad 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 los índices y punteros.
Un algoritmo puede o no contar la salida como parte de su uso de espacio. Dado que los algoritmos locales 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 ).
Dado un arreglo a de n elementos, supongamos que queremos un arreglo que contenga los mismos elementos en orden inverso y que desechemos el original. Una forma aparentemente sencilla de hacer esto es crear un nuevo arreglo del mismo tamaño, llenarlo con copias de aen el orden apropiado y luego eliminar a.
función inversa(a[0..n - 1]) asignar b[0..n - 1] para i de 0 a n - 1 b[n − 1 − i] := a[i] volver b
Desafortunadamente, esto requiere O ( n ) espacio adicional para tener las matrices ay bdisponibles simultáneamente. Además, la asignación y la desasignación suelen ser operaciones lentas. Dado que ya no necesitamos a, podemos sobrescribirlo con su propia inversión utilizando este algoritmo in situ 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 floor((n-2)/2) temporal := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp
Como otro ejemplo, muchos algoritmos de ordenamiento reorganizan las matrices en un orden ordenado en el lugar, incluidos: ordenamiento de burbuja , ordenamiento de peine , ordenamiento de selección , ordenamiento de inserción , ordenamiento de montón y ordenamiento de Shell . Estos algoritmos requieren solo unos pocos punteros, por lo que su complejidad espacial es O (log n ) . [1]
Quicksort opera en el lugar sobre los datos que se van a ordenar. Sin embargo, quicksort requiere O (log n ) punteros de espacio de pila para realizar un seguimiento de los subconjuntos en su estrategia de dividir y vencer . En consecuencia, quicksort necesita O (log 2 n ) espacio adicional. Aunque este espacio no constante técnicamente saca a quicksort de la categoría de in situ, quicksort y otros algoritmos que solo necesitan O (log n ) punteros adicionales suelen considerarse 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 en el lugar.
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 lenguajes regulares . [2] De hecho, ni siquiera incluye ninguno de los ejemplos enumerados anteriormente.
Los algoritmos suelen considerarse en L , la clase de problemas que requieren O (log n ) de espacio adicional para estar en su lugar. Esta clase se ajusta más 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 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 existe un algoritmo in situ (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 utilizando 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 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 utilizando un algoritmo aleatorio . Por ejemplo, si uno desea saber si dos vértices en un grafo de n vértices están en el mismo componente conectado del grafo, no se conoce ningún algoritmo simple, determinista y en el lugar para determinar esto. 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 tropecemos con el otro vértice siempre que esté en el mismo componente es muy alta. De manera similar, existen algoritmos aleatorios simples en el lugar para pruebas de primalidad, como la prueba de primalidad de Miller-Rabin , y también hay algoritmos de factorización aleatorios simples en el lugar, como el algoritmo rho de Pollard .
Los lenguajes de programación funcional a menudo desalientan o no admiten algoritmos explícitos in situ que sobrescriban datos, ya que se trata de un tipo de efecto secundario ; en cambio, solo 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 descarta el antiguo, y optimizarán esto en una mutación simple "detrás del capó".
Tenga en cuenta que, en principio, es posible construir cuidadosamente algoritmos locales que no modifiquen los datos (a menos que estos ya no se utilicen), pero esto rara vez se hace en la práctica.