algorithm - guia - qgis manual
¿Qué significa cuando se estipula que el espacio extra permitido es O(1)? (6)
Si se da la condición anterior en una pregunta de programación y la estoy resolviendo mediante recursión, ¿estoy violando las restricciones? ¿Podría ser porque la recursión también usa la pila? ¿Es correcto?
La complejidad de almacenamiento de O (1) simplemente significa que su algoritmo debe usar una cantidad constante de almacenamiento. es decir, debe usar la misma cantidad de almacenamiento en un conjunto de 10 elementos que en 1000.
Probablemente deberías usar la iteración para lograr esto.
En cuanto a las otras respuestas que le dicen que la cantidad de pila que debe usar es O(1) , y debe permanecer constante sea cual sea el tamaño de la entrada, si desea resolver el problema de manera recursiva, solo le deja dos posibilidades :
- Recursividad de profundidad fija, lo que significa limitar el tiempo de repetición de la función.
- Tail-recursividad, lo que significa que la llamada recursiva a la función debe ser lo último que se va a evaluar, por lo tanto, para activar el TCO. (Optimización de la cola de llamada) En términos generales, significa que como la última llamada es la última en la ejecución de funcitones, en lugar de presionar el contexto de la llamada en la pila, el nuevo llamará al contexto de llamada existente, utilizando una constante cantidad de espacio de pila
Si está utilizando la recursión para resolver este problema, está utilizando la pila para pasar datos por el árbol de recursión. En este sentido, normalmente usa más de O(1) espacio.
Estoy de acuerdo con la respuesta aceptada, pero quiero señalar que si está utilizando un lenguaje con optimización de cola de llamada (como clojure), entonces puede resolver problemas con O(1) espacio que utilizará más espacio con un idioma que no lo hace tener esta característica (como java).
Entonces, la respuesta correcta también depende del idioma que se usa.
Si la profundidad de su recursión aumenta dependiendo del tamaño de su entrada (que generalmente lo hace), entonces sí: estaría usando una cantidad ilimitada de memoria de pila. El requisito era resolver el problema con una cantidad fija de memoria.
Si la profundidad de la pila (recursividad) es constante y no cambia con respecto al tamaño de la entrada, entonces una solución recursiva puede ser O(1) espacio extra.
Algunos compiladores pueden hacer una optimización de llamada de cola (TCO) y eliminar llamadas recursivas si son la última instrucción ejecutada en cualquier ruta de código dada a través de una función. Con TCO, no hay gastos generales de memoria relacionados con la pila de llamadas.
Sin embargo, tenga en cuenta que la restricción O (1) se puede imponer para forzarlo a elegir un algoritmo particular (probablemente no recursivo), por lo que depender de la optimización de la cola puede ser poco inteligente incluso si sabe que el compilador que está utilizando tiene hizo la transformación relevante a tu código. Por lo menos, si confía en él, debe decirlo explícitamente y justificar su expectativa de que TCO ocurrirá por referencia a las especificaciones del lenguaje, la documentación del compilador y / o el desmontaje, según corresponda.
extra allowed space is O(1)
significa que su programa puede usar solo una cantidad constante de espacio, digamos C
Siguiendo la definición de big-O, esto significa que el espacio que su programa necesita no puede depender del tamaño de la entrada, aunque C puede hacerse arbitrariamente grande.
Entonces, si la recursión depende de la entrada a (que generalmente es el caso), el espacio que necesita su programa no es O(1) .
Para aclarar más:
Un programa que siempre usa 1 Mb usa O(1) espacio.
Un programa que siempre usa 1 Tb usa O(1) espacio b .
Un programa que usa N Mb , donde N es la entrada, no usa O(1) espacio, (usa O(N) espacio).
Para resumir, cada vez que lea O(1) , simplemente reemplácelo mentalmente con constante .
a. Por ejemplo, foo (n) = foo (n - 1), el espacio de pila necesario aquí para mantener las llamadas de función es O(n)
segundo. Cuando el material en la notación O comenta cómo las constantes ignoradas pueden ser problemáticas, de esto es de lo que están hablando