algorithm - rapper - ¿Diferencias entre complejidad de tiempo y complejidad de espacio?

big o rapper

Question

He visto que en la mayoría de los casos la complejidad del tiempo está relacionada con la complejidad del espacio y viceversa. Por ejemplo, en un recorrido de matriz:

for i=1 to length(v)
print (v[i])
endfor

Aquí es fácil ver que la complejidad del algoritmo en términos de tiempo es O (n), pero me parece que la complejidad del espacio también es n (¿también se representa como O (n)?).

Mi pregunta: ¿ es posible que un algoritmo tenga una complejidad de tiempo diferente a la complejidad del espacio?

Answer 1

A veces sí están relacionadas, y otras veces no están relacionadas, en realidad usamos más espacio para obtener algoritmos más rápidos, como en la programación dinámica https://www.codechef.com/wiki/tutorial-dynamic-programming la programación dinámica utiliza memorización o De abajo hacia arriba, la primera técnica usa la memoria para recordar las soluciones repetidas, por lo que el algoritmo no necesita volver a calcularlo, sino que se obtiene de una lista de soluciones. y el enfoque de abajo hacia arriba comienza con las pequeñas soluciones y se construye para alcanzar la solución final. Aquí, dos ejemplos simples, uno muestra la relación entre el tiempo y el espacio, y el otro no muestra ninguna relación: supongamos que queremos encontrar la suma de todos los enteros de 1 a un n entero dado: código1:

sum=0
for i=1 to n
sum=sum+1
print sum

Este código utilizó solo 6 bytes de la memoria i => 2, n => 2 y suma => 2 bytes, por lo que la complejidad del tiempo es O (n), mientras que la complejidad del espacio es O (1) código2:

array a[n]
a[1]=1
for i=2 to n
a[i]=a[i-1]+i
print a[n]

Este código utilizó al menos n * 2 bytes de la memoria para la matriz, por lo que la complejidad del espacio es O (n) y la complejidad del tiempo también es O (n)

Answer 2

En primer lugar, la complejidad del espacio de este bucle es O(1) (la entrada generalmente no se incluye al calcular la cantidad de almacenamiento que requiere un algoritmo).

Entonces, la pregunta que tengo es si es posible que un algoritmo tenga una complejidad de tiempo diferente de la complejidad del espacio.

Sí lo es. En general, el tiempo y la complejidad espacial de un algoritmo no están relacionados entre sí.

A veces uno puede ser aumentado a expensas del otro. Esto se llama compensación espacio-temporal .

Answer 3

Existe una relación muy conocida entre el tiempo y la complejidad del espacio.

En primer lugar, el tiempo es un obvio límite para el consumo de espacio: en el tiempo t no puede alcanzar más de O (t) celdas de memoria. Esto suele expresarse mediante la inclusión.

 DTime(f) ⊆ DSpace(f)

donde DTime (f) y DSpace (f) son el conjunto de idiomas reconocibles por una máquina de Turing determinística en el tiempo (respectivamente, espacio) O (f). Es decir, si un problema puede resolverse en el tiempo O (f), entonces también puede resolverse en el espacio O (f).

Menos evidente es el hecho de que el espacio proporciona un límite al tiempo. Supongamos que, en una entrada de tamaño n, tiene a su disposición f (n) celdas de memoria, que incluyen registros, cachés y todo. Después de haber escrito estas celdas de todas las formas posibles , eventualmente puede detener su cálculo, ya que de lo contrario volvería a ingresar a una configuración por la que ya pasó, comenzando a hacer un ciclo. Ahora, en un alfabeto binario, las celdas f (n) pueden escribirse en 2 ^ f (n) formas diferentes, lo que le da a nuestro límite superior de tiempo: o el cálculo se detendrá dentro de este límite, o puede forzar la terminación, ya que el cálculo nunca se detendrá

Esto suele expresarse en la inclusión.

 DSpace(f) ⊆ Dtime(2^(cf))

para alguna constante c. la razón de la constante c es que si L está en DSpace (f) solo sabe que se reconocerá en el Espacio O (f), mientras que en el razonamiento anterior, f fue un límite real.

Las relaciones anteriores están subsumidas por versiones más sólidas, que incluyen modelos de computación no deterministas, es así como se expresan con frecuencia en los libros de texto (véase, por ejemplo, el teorema 7.4 en Complejidad computacional por Papadimitriou).

Answer 4

La complejidad del tiempo y el espacio son diferentes aspectos del cálculo de la eficiencia de un algoritmo.

La complejidad del tiempo se ocupa de descubrir cómo cambia el tiempo de cálculo de un algoritmo con el cambio en el tamaño de la entrada.

Por otro lado, la complejidad del espacio se ocupa de averiguar cuánto espacio (extra) necesitaría el algoritmo con el cambio en el tamaño de entrada.

Para calcular la complejidad de tiempo del algoritmo, la mejor manera es verificar si aumentamos el tamaño de la entrada, si el número de comparación (o pasos computacionales) también aumentará y para calcular la complejidad del espacio, la mejor opción es ver los requisitos de memoria adicionales de El algoritmo también cambia con el cambio en el tamaño de la entrada.

Un buen ejemplo podría ser del tipo Bubble .

Digamos que intentaste ordenar una matriz de 5 elementos. En la primera pasada, compararás el primer elemento con los siguientes 4 elementos. En la segunda pasada, comparará el segundo elemento con los siguientes 3 elementos y continuará este procedimiento hasta que haya agotado por completo la lista.

Ahora, ¿qué pasará si intentas ordenar 10 elementos? En este caso, comenzará comparando el primer elemento con los siguientes 9 elementos, luego el segundo con los siguientes 8 elementos y así sucesivamente. En otras palabras, si tiene una matriz de elementos N, comenzará comparando el primer elemento con los elementos N-1, luego el segundo elemento con los elementos N-2 y así sucesivamente. Esto resulta en una complejidad de tiempo O(N^2) .

Pero qué pasa con el tamaño. Cuando ordenó la matriz de 5 elementos o de 10 elementos, ¿utilizó un búfer adicional o espacio de memoria? Se podría decir que sí , usé una variable temporal para hacer el intercambio. Pero, ¿cambió la cantidad de variables cuando aumentó el tamaño de la matriz de 5 a 10. No, independientemente de cuál sea el tamaño de la entrada, siempre usará una sola variable para hacer el intercambio. Bueno, esto significa que el tamaño de la entrada no tiene nada que ver con el espacio adicional que requerirá, lo que resultará en O(1) o complejidad de espacio constante.

Ahora, como un ejercicio para usted, investigue sobre la complejidad de tiempo y espacio del tipo de combinación

Answer 5

La forma en que la cantidad de espacio de almacenamiento requerido por un algoritmo varía con el tamaño del problema que está resolviendo. La complejidad del espacio normalmente se expresa como un orden de magnitud, por ejemplo, O (N ^ 2) significa que si el tamaño del problema (N) se duplica, se necesitará cuatro veces más espacio de almacenamiento de trabajo.

Answer 6

Las complejidades de time y space no están relacionadas entre sí. Se utilizan para describir cuánto espacio / tiempo ocupa su algoritmo en función de la entrada.

• Por ejemplo, cuando el algoritmo tiene una complejidad de espacio de:

  • O(1) - constante - el algoritmo usa una cantidad fija (pequeña) de espacio que no depende de la entrada. Para cada tamaño de la entrada, el algoritmo tomará la misma cantidad (constante) de espacio. Este es el caso en su ejemplo, ya que la entrada no se tiene en cuenta y lo que importa es el tiempo / espacio del comando de print .
  • O(n) , O(n^2) , O(log(n)) ...: indican que crea objetos adicionales en función de la longitud de la entrada. Por ejemplo, crear una copia de cada objeto de v almacenándola en una matriz e imprimirla después ocupa espacio O(n) medida que crea n objetos adicionales.

• En contraste, la complejidad del tiempo describe cuánto tiempo consume su algoritmo en función de la longitud de la entrada. Otra vez:

  • O(1) : no importa qué tan grande sea la entrada, siempre lleva un tiempo constante, por ejemplo, solo una instrucción. Me gusta

    function(list l) {
    print("i got a list");
    }

  • O(n) , O(n^2) , O(log(n)) : de nuevo, se basa en la longitud de la entrada. Por ejemplo

    function(list l) {
    for (node in l) {
    print(node);
    }
    }

Tenga en cuenta que los dos últimos ejemplos toman espacio O(1) , ya que no creas nada. Compararlos con

function(list l) {
list c;
for (node in l) {
c.add(node);
}
}

que ocupa espacio O(n) porque crea una nueva lista cuyo tamaño depende del tamaño de la entrada de forma lineal.

Su ejemplo muestra que la complejidad del tiempo y el espacio puede ser diferente. Se necesita v.length * print.time para imprimir todos los elementos. Pero el espacio es siempre el mismo: O(1) porque no crea objetos adicionales. Entonces, sí, es posible que un algoritmo tenga una complejidad de tiempo y espacio diferente, ya que no dependen entre sí.

Answer 7

Sí, esto es definitivamente posible. Por ejemplo, clasificar n números reales requiere O(n) espacio, pero O(n log n) tiempo. Es cierto que la complejidad del espacio es siempre una complejidad de tiempo de límite inferior , ya que el tiempo para inicializar el espacio se incluye en el tiempo de ejecución.