Programación de potencia: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2) todo en uno

65

Escriba un programa (o función) que exhiba cuatro complejidades comunes de tiempo de O grande dependiendo de cómo se ejecute. En cualquier forma, toma un número entero positivo N que puede suponer que es menor que 2 31 .

  1. Cuando el programa se ejecuta en su forma original , debe tener una complejidad constante . Es decir, la complejidad debe ser Θ (1) o, de manera equivalente, Θ (1 ^ N) .

  2. Cuando el programa se invierte y ejecuta, debe tener una complejidad lineal . Es decir, la complejidad debe ser Θ (N) o, de manera equivalente, Θ (N ^ 1) .
    (Esto tiene sentido ya que N^1se 1^Ninvierte).

  3. Cuando se programa un doble , es decir, concatenado a sí mismo, y ejecutarlo debe tener exponencial complejidad, específicamente 2 N . Es decir, la complejidad debe ser Θ (2 ^ N) .
    (Esto tiene sentido ya que el 2en 2^Nes el doble de la 1en 1^N.)

  4. Cuando el programa se duplicó y revirtió y ejecutarlo debe tener polinomio complejidad, específicamente N 2 . Es decir, la complejidad debe ser Θ (N ^ 2) .
    (Esto tiene sentido ya que N^2se 2^Ninvierte).

Estos cuatro casos son los únicos que necesita manejar.

Tenga en cuenta que, para mayor precisión, estoy usando la notación theta grande (Θ) en lugar de la gran O porque los tiempos de ejecución de sus programas deben estar limitados tanto por encima como por debajo de las complejidades requeridas. De lo contrario, solo escribir una función en O (1) satisfaría los cuatro puntos. No es demasiado importante entender los matices aquí. Principalmente, si su programa está haciendo operaciones k * f (N) para alguna k constante, entonces es probable que esté en Θ (f (N)).

Ejemplo

Si el programa original fuera

ABCDE

luego ejecutarlo debería llevar un tiempo constante. Es decir, si la entrada N es 1 o 2147483647 (2 31 -1) o cualquier valor intermedio, debe terminar aproximadamente en la misma cantidad de tiempo.

La versión inversa del programa.

EDCBA

debería llevar un tiempo lineal en términos de N. Es decir, el tiempo que tarda en terminar debe ser aproximadamente proporcional a N. Por lo tanto, N = 1 toma menos tiempo y N = 2147483647 toma más.

La versión duplicada del programa.

ABCDEABCDE

debe tomar tiempo de dos-a-la N en términos de N. Es decir, el tiempo que se necesita para terminar debe ser aproximadamente proporcional a 2 N . Entonces, si N = 1 termina en aproximadamente un segundo, N = 60 tomaría más tiempo que la edad del universo para terminar. (No, no tienes que probarlo).

La versión duplicada y revertida del programa.

EDCBAEDCBA

debería tomar el tiempo al cuadrado en términos de N. Es decir, el tiempo que tarda en terminar debe ser aproximadamente proporcional a N * N. Entonces, si N = 1 termina en aproximadamente un segundo, N = 60 tardaría aproximadamente una hora en terminar.

Detalles

  • Debe mostrar o argumentar que sus programas se ejecutan en las complejidades que usted dice que son. Dar algunos datos de tiempo es una buena idea, pero también trate de explicar por qué teóricamente la complejidad es correcta.

  • Está bien si en la práctica los tiempos que toman sus programas no son perfectamente representativos de su complejidad (o incluso deterministas). por ejemplo, la entrada N + 1 a veces puede correr más rápido que N.

  • El entorno en el que ejecuta sus programas sí importa. Puede hacer suposiciones básicas sobre cómo los lenguajes populares nunca pierden tiempo intencionalmente en algoritmos, pero, por ejemplo, si sabe que su versión particular de Java implementa el ordenamiento de burbujas en lugar de un algoritmo de ordenamiento más rápido , entonces debe tener eso en cuenta si hace algún ordenamiento .

  • Para todas las complejidades aquí, supongamos que estamos hablando de los peores escenarios , no el mejor de los casos o el caso promedio.

  • La complejidad espacial de los programas no importa, solo la complejidad del tiempo.

  • Los programas pueden generar cualquier cosa. Solo importa que tomen el entero positivo N y que tengan las complejidades de tiempo correctas.

  • Se permiten comentarios y programas multilínea. (Puede suponer que \r\nrevertido es \r\npor compatibilidad con Windows).

Big O Recordatorios

De más rápido a más lento es O(1), O(N), O(N^2), O(2^N)(orden 1, 2, 4, 3 arriba).

Los términos más lentos siempre dominan, por ejemplo O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))para constante k. Así O(2) = O(30) = O(1)y O(2*N) = O(0.1*N) = O(N).

Recuerda O(N^2) != O(N^3)y O(2^N) != O(3^N).

Cuidadosamente grande O hoja de trucos.

Puntuación

Este es el código normal de golf. El programa original más corto (el de tiempo constante) en bytes gana.

code-golf integer source-layout restricted-complexity set-theory Pasatiempos de Calvin
fuente
Excelente pregunta! Punto menor: no tenemos que especificar el peor de los casos / el mejor de los casos / el caso promedio, porque la única entrada que cuenta como tamaño N es el número N en sí (que por cierto no es la noción habitual de tamaño de entrada: eso sería tratar la entrada N como un registro de tamaño N). Por lo tanto, solo hay un caso para cada N, que es simultáneamente el mejor, el peor y el caso promedio.
ShreevatsaR
55
Parece que te has desviado de las definiciones habituales de complejidad. Siempre definimos la complejidad temporal de un algoritmo en función del tamaño de su entrada . En el caso donde la entrada es un número, el tamaño de la entrada es el logaritmo de base 2 de ese número. Entonces, el programa n = input(); for i in xrange(n): passtiene una complejidad exponencial, ya que toma 2 ** kpasos, donde k = log_2(n)está el tamaño de entrada. Debe aclarar si este es el caso, ya que cambia drásticamente los requisitos.
wchargin

Respuestas:

36

Python 3 , 102 bytes

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Pruébalo en línea!

Esto es de O (1 ^ n), ya que esto es lo que hace el programa:

  • evaluar la entrada
  • crear la matriz [0]
  • Imprímelo

Invertido:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Pruébalo en línea!

Esto es de O (n ^ 1), ya que esto es lo que hace el programa:

  • evaluar la entrada
  • crear la matriz [0] * de entrada (0 repetido tantas veces como la entrada)
  • Imprímelo

Doblado:

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Pruébalo en línea!

Esto es de O (2 ^ n), ya que esto es lo que hace el programa:

  • evaluar la entrada
  • crear la matriz [0]
  • Imprímelo
  • intenta evaluar la entrada
  • fallar
  • crear la matriz [0] * (2 ^ entrada) (0 repetido tantas veces como 2 ^ entrada)
  • Imprímelo

Doblado y revertido:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Pruébalo en línea!

Esto es de O (n ^ 2), ya que esto es lo que hace el programa:

  • evaluar la entrada
  • crear la matriz [0] * de entrada (0 repetido tantas veces como la entrada)
  • Imprímelo
  • intenta evaluar la entrada
  • fallar
  • crear la matriz [0] * (entrada ^ 2) (0 repetido tantas veces como la entrada al cuadrado)
  • Imprímelo
Monja permeable
fuente
¿Por qué no se cuelga esperando la interacción del usuario cuando hay varias llamadas a input()?
Jonathan Allan
1
¿Es un vacío que el "final de la transmisión" se transmite al final de la transmisión?
Leaky Nun
1
¿Puedes explicarlo?
Brain Guider
1
Re: el argumento de "fin de archivo", estás viendo las cosas al revés. Cuando usa una terminal, las solicitudes de entrada se bloquean porque hay algo conectado a ella; ctrl-D se puede enviar para enviar explícitamente ninguna entrada. Si la entrada está conectada a un archivo vacío (como lo hace TIO si deja el cuadro de entrada vacío), o si está conectado a un archivo donde se ha leído toda la entrada, no es necesario que la solicitud de entrada haga nada; ya sabe que no hay entrada. En UNIX / Linux, "fin de archivo" y "no hay entrada disponible" no se pueden distinguir en los archivos normales.
3
Para el primer caso, kes la entrada y les una, así que todavía estás computando 1**k, ¿verdad? ¿Qué debería tomar O(log(k))tiempo, a pesar de que tú y yo y todos sabemos de antemano que es uno?
Richard Rast
18

Perl 5, 82 73 71 + 1 (para el indicador -n) = 72 bytes

Estoy seguro de que puedo jugar esto (mucho) más, pero es hora de dormir, he pasado suficiente tiempo depurando como está, y de todos modos estoy orgulloso de lo que tengo hasta ahora.

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

El programa en sí no usa la entrada, y solo evalúa una cadena que comienza con un comentario y luego realiza una sola sustitución de cadena, por lo que esto es claramente en tiempo constante. Básicamente es equivalente a:

$x="#";
eval $x;
$x=~s/#//;

Doblado:

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

El bit que realmente toma tiempo exponencial es la segunda evaluación: evalúa el comando say for(1..2**$_), que enumera todos los números del 1 al 2 ^ N, que claramente toma tiempo exponencial.

Invertido:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

Esto (ingenuamente) calcula la suma de la entrada, que claramente toma tiempo lineal (ya que cada adición es en tiempo constante). El código que realmente se ejecuta es equivalente a:

$x+=$_ for(1..$_);
$_=$x;

La última línea es solo para que cuando se repitan estos comandos tome tiempo cuadrático.

Invertido y doblado:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

Esto ahora toma la suma de la suma de la entrada (y la agrega a la suma de la entrada, pero lo que sea). Como ordena N^2adiciones, esto lleva tiempo cuadrático. Básicamente es equivalente a:

$x=0;
$x+=$_ for(1..$_);
$_=$x;
$x+=$_ for(1..$_);
$_=$x;

La segunda línea encuentra la suma de la entrada, haciendo Nadiciones, mientras que la cuarta hace summation(N)adiciones, que es O(N^2).

Chris
fuente
¡Excelente! ¡Hacer eso en un lenguaje convencional hubiera sido difícil! ¡Esto tiene mi voto a favor!
Arjun
Bien hecho, esto es bastante bueno. Probablemente quisiste decir en $x.=q;##say...lugar de $x.=q;#say...sin embargo (con dos en #lugar de 1). (Eso explicaría por qué contó 76 bytes en lugar de 75). Además, debe contar la -nbandera en su bytecount, ya que su programa no hace mucho sin ella.
Dada
@Dada accidentalmente transpuse el evaly los s///comandos. Si haces lo evalprimero solo necesitas el uno #. ¡Buena atrapada!
Chris
@ Chris Derecha, funciona de hecho. Es posible que pueda omitir el último #: $x=~s/#//;producciones invertidas ;//#/s~=x$, que en su contexto no hace nada, como lo haría con un líder #. (No lo he probado sin embargo). En cualquier caso, ¡ten un +1!
Dada
@Dada ¡Buena captura una vez más!
Chris
17

En realidad , 20 bytes

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Pruébalo en línea!

Entrada: 5

Salida:

rⁿ@╜╖1(;
[0]
5

Invertido:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Pruébalo en línea!

Salida:

rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5

Doblado:

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Pruébalo en línea!

Salida:

rⁿ@╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
rⁿ@╜╖1(;
rⁿ@╜╖1(;
[0]

Doblado y revertido:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Pruébalo en línea!

Salida:

rⁿ╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
rⁿ╜╖1(;
rⁿ╜╖1(;
[0, 1, 2, 3, 4]

Idea principal

En realidad es un lenguaje basado en pila.

  • abces un programa que tiene complejidad O (1 n ), y su doble tiene complejidad O (2 n ).
  • defes un programa que tiene complejidad O (n 1 ), y su doble tiene complejidad O (n 2 ).

Entonces, mi sumisión es "abc"ƒ"fed", donde ƒse evalúa. De esa manera, "fed"no será evaluado.

Generación de programa individual.

El pseudocódigo del primer componente ;(1╖╜ⁿr:

register += 1 # register is default 0
print(range(register**input))

El pseudocódigo del segundo componente ;(1╖╜ⁿ@r:

register += 1 # register is default 0
print(range(input**register))
Monja permeable
fuente
¡Nunca pensé que esto sería posible! ¡Buen trabajo, señor! +1
Arjun
@Arjun Gracias por tu apreciación.
Leaky Nun
Esto es excelente y realmente está a la altura del desafío al no utilizar comentarios de la OMI. ¡Increíble!
ShreevatsaR
1
Bueno, esto en realidad tiene comentarios ... las cuerdas no están evaluadas y son NOP ...
Leaky Nun
4

Jalea , 20 bytes

En parte inspirado por la solución de Leaky Nun en realidad .

Las nuevas líneas iniciales y finales son significativas.

Normal:


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Pruébalo en línea!

Entrada: 5

Salida: 

610

Invertido:


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Pruébalo en línea!

Entrada: 5

Salida:

[1, 2, 3, 4, 5]10

Doblado


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Pruébalo en línea!

Entrada: 5

Salida:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]10

Doblado e invertido


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Pruébalo en línea!

Entrada: 5

Salida:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]10

Explicación

La clave aquí está en Ŀ, que significa "llama al enlace en el índice n como una mónada". Los enlaces se indexan de arriba a abajo a partir de 1, excluyendo el enlace principal (el más bajo). Ŀtambién es modular, por lo que si intenta llamar al enlace número 7 de 5 enlaces, en realidad llamará al enlace 2.

El enlace que se llama en este programa siempre es el que se encuentra en el índice 10 ( ⁵) sin importar la versión del programa que sea. Sin embargo, qué enlace está en el índice 10 depende de la versión.

Lo ⁵que aparece después de cada uno Ŀestá allí para que no se rompa cuando se invierte. El programa generará un error en tiempo de análisis si no hay un número antes Ŀ. Tener un ⁵after es un nilad fuera de lugar, que solo va directamente a la salida.

La versión original llama al enlace ‘, que calcula n + 1.

La versión inversa llama al enlace R, que genera el rango 1 .. n.

La versión duplicada llama al enlace 2*R, que calcula 2 n y genera el rango 1 .. 2 n .

La versión duplicada e inversa llama al enlace ²R, que calcula n 2 y genera el rango 1 .. n 2 .

Gato de negocios
fuente
4

Befunge-98 , 50 bytes

Normal

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

Este es, con mucho, el programa más simple de los 4: los únicos comandos que se ejecutan son los siguientes:

\+]
  !
  : @
&$< ^&;

Este programa hace algunas cosas irreverentes antes de presionar un comando "girar a la derecha" ( ]) y una flecha. Luego golpea 2 comandos "tomar entrada". Debido a que solo hay 1 número en la entrada y a la forma en que TIO trata el &s, el programa sale después de 60 segundos. Si hay 2 entradas (y porque puedo sin agregar bytes), la IP viajaría a la función "finalizar programa".

Pruébalo en línea!

Invertido

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Este es un poco más complicado. Los comandos relevantes son los siguientes:

;&^  $
  >:*[
;< $#]#; :. 1-:!k@
  :

que es equivalente a

;&^                   Takes input and sends the IP up. the ; is a no-op
  :                   Duplicates the input.
  >:*[                Duplicates and multiplies, so that the stack is [N, N^2
     $                Drops the top of the stack, so that the top is N
     ]#;              Turns right, into the loop
         :.           Prints, because we have space and it's nice to do
            1-        Subtracts 1 from N
              :!k@    If (N=0), end the program. This is repeated until N=0
;< $#]#;              This bit is skipped on a loop because of the ;s, which comment out things

La parte importante aquí es el :. 1-:!k@bit. Es útil porque siempre que empujemos la complejidad correcta a la pila antes de ejecutarla en un tiempo menor, podemos obtener la deseada. Esto se utilizará en los 2 programas restantes de esta manera.

Pruébalo en línea!

Doblado

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

Y los comandos relevantes son:

\+]
  !
  :
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;

Este programa entra en 2 bucles. Primero, sigue el mismo camino que el programa normal, que empuja 1 y N a la pila, pero en lugar de &pasar al segundo , la IP salta un comentario en un bucle que empuja 2^N:

        vk!:    If N is 0, go to the next loop.
      -1        Subtract 1 from N
 +  :\          Pulls the 1 up to the top of the stack and doubles it
  ]#            A no-op
\               Pulls N-1 to the top again

Los otros bits en la línea 4 se saltan usando ;s

Después de empujar (2 ^ N) en la pila, nos movemos hacia abajo en una línea hacia el bucle de impresión antes mencionado. Debido al primer bucle, la complejidad del tiempo es Θ (N + 2 ^ N), pero eso se reduce a Θ (2 ^ N).

Pruébalo en línea!

Doblado e invertido

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Los comandos relevantes:

;&^

;< $#]#; :. 1-:!k@

 @>:*[

  :

Esto funciona casi de manera idéntica al programa invertido, pero N^2no se elimina de la pila, porque la primera línea de la segunda copia del programa se agrega a la última línea de la primera, lo que significa que el comando soltar ( $) nunca se ejecuta , así que vamos al ciclo de impresión con N^2en la parte superior de la pila.

Pruébalo en línea!

Levemente Milquetoast
fuente