Programação de potência: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2), tudo em um

65

Escreva um programa (ou função) que exiba quatro complexidades comuns de tempo grande, dependendo de como é executado. De qualquer forma, ele recebe um número inteiro positivo N, que você pode assumir que seja menor que 2 31 .

  1. Quando o programa é executado em sua forma original , ele deve ter complexidade constante . Ou seja, a complexidade deve ser Θ (1) ou, equivalentemente, Θ (1 ^ N) .

  2. Quando o programa é revertido e executado, ele deve ter complexidade linear . Ou seja, a complexidade deve ser Θ (N) ou, equivalentemente, Θ (N ^ 1) .
    (Isso faz sentido, pois N^1é 1^Nrevertido.)

  3. Quando o programa é duplicada , isto é concatenado a si mesma, e executá-lo deverá ter exponencial complexidade, especificamente 2 N . Ou seja, a complexidade deve ser Θ (2 ^ N) .
    (Isso faz sentido, pois o 2in 2^Né o dobro do 1in 1^N.)

  4. Quando o programa é dobrado e invertida e executá-lo deverá ter polinomial complexidade, especificamente N 2 . Ou seja, a complexidade deve ser Θ (N ^ 2) .
    (Isso faz sentido, pois N^2é 2^Nrevertido.)

Esses quatro casos são os únicos com os quais você precisa lidar.

Observe que, para maior precisão, estou usando a notação teta grande (Θ) em vez de O grande, porque os tempos de execução dos seus programas devem ser limitados acima e abaixo pelas complexidades necessárias. Caso contrário, apenas escrever uma função em O (1) satisfaria todos os quatro pontos. Não é muito importante entender as nuances aqui. Principalmente, se o seu programa estiver executando operações k * f (N) por alguma constante k, é provável que esteja em Θ (f (N)).

Exemplo

Se o programa original fosse

ABCDE

então executá-lo deve levar tempo constante. Ou seja, se a entrada N é 1 ou 2147483647 (2 31 -1) ou qualquer valor intermediário, ela deve terminar aproximadamente na mesma quantidade de tempo.

A versão invertida do programa

EDCBA

deve levar um tempo linear em termos de N. Ou seja, o tempo necessário para terminar deve ser aproximadamente proporcional a N. Portanto, N = 1 leva menos tempo e N = 2147483647 leva mais.

A versão duplicada do programa

ABCDEABCDE

deve ter tempo two-to-the-N em termos de N. Ou seja, o tempo que leva para terminar deve ser aproximadamente proporcional a 2 N . Portanto, se N = 1 termina em cerca de um segundo, N = 60 levaria mais tempo que a idade do universo para terminar. (Não, você não precisa testá-lo.)

A versão duplicada e invertida do programa

EDCBAEDCBA

deve levar um tempo ao quadrado em termos de N. Ou seja, o tempo que leva para terminar deve ser aproximadamente proporcional a N * N. Portanto, se N = 1 termina em cerca de um segundo, N = 60 levaria cerca de uma hora para terminar.

Detalhes

  • Você precisa mostrar ou argumentar que seus programas estão sendo executados nas complexidades que você diz que são. Fornecer alguns dados de temporização é uma boa ideia, mas também tente explicar por que teoricamente a complexidade está correta.

  • Tudo bem se, na prática, o tempo gasto pelos seus programas não for perfeitamente representativo de sua complexidade (ou mesmo determinística). por exemplo, a entrada N + 1 às vezes pode ser mais rápida que N.

  • O ambiente em que você está executando seus programas é importante. Você pode fazer suposições básicas sobre como as linguagens populares nunca perdem tempo intencionalmente em algoritmos, mas, por exemplo, se você conhece sua versão específica do Java implementa a classificação por bolhas em vez de um algoritmo de classificação mais rápido , leve isso em consideração se fizer alguma classificação .

  • Para todas as complexidades aqui, assuma que estamos falando de cenários de pior caso , não de melhor ou médio.

  • A complexidade do espaço dos programas não importa, apenas a complexidade do tempo.

  • Os programas podem produzir qualquer coisa. É importante que eles recebam o número inteiro positivo N e tenham as complexidades de tempo corretas.

  • Comentários e programas multilinhas são permitidos. (Você pode assumir que o \r\nreverso é \r\npara compatibilidade com o Windows.)

Big O Reminders

Do mais rápido para o mais lento O(1), O(N), O(N^2), O(2^N)(peça 1, 2, 4, 3 acima).

Termos mais lentos sempre dominam, por exemplo O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))para constante k. Então O(2) = O(30) = O(1)e O(2*N) = O(0.1*N) = O(N).

Lembre-se O(N^2) != O(N^3)e O(2^N) != O(3^N).

Grande folha de dicas.

Pontuação

Este é o código normal de golfe. O programa original mais curto (o tempo constante) em bytes vence.

code-golf integer source-layout restricted-complexity set-theory Passatempos de Calvin
fonte
Excelente pergunta! Ponto secundário: não precisamos especificar o pior caso / o melhor caso / o caso médio, porque a única entrada que conta como tamanho N é o próprio número N (que BTW não é a noção usual de tamanho de entrada: isso trate a entrada N como sendo do tamanho log N). Portanto, há apenas um caso para cada N, que é simultaneamente o melhor, o pior e o caso médio.
ShreevatsaR 5/17
5
Parece que você se desviou das definições usuais de complexidade. Sempre definimos a complexidade do tempo de um algoritmo em função do tamanho de sua entrada . No caso em que a entrada é um número, o tamanho da entrada é o logaritmo de base 2 desse número. Portanto, o programa n = input(); for i in xrange(n): passtem complexidade exponencial, porque executa 2 ** ketapas, onde k = log_2(n)está o tamanho da entrada. Você deve esclarecer se esse é o caso, pois altera drasticamente os requisitos.
Wchargin #

Respostas:

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

Experimente online!

Isso é de O (1 ^ n), pois é isso que o programa faz:

  • avaliar a entrada
  • crie a matriz [0]
  • imprima

Invertida:


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

Experimente online!

Isso é de O (n ^ 1), pois é isso que o programa faz:

  • avaliar a entrada
  • crie a matriz [0] * entrada (0 repetido quantas vezes a entrada)
  • imprima

Dobrado:

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

Experimente online!

Isso é de O (2 ^ n), pois é isso que o programa faz:

  • avaliar a entrada
  • crie a matriz [0]
  • imprima
  • tente avaliar a entrada
  • falhou
  • crie a matriz [0] * (2 ^ entrada) (0 repetido quantas vezes 2 ^ entrada)
  • imprima

Dobrado e 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

Experimente online!

Isso é de O (n ^ 2), pois é isso que o programa faz:

  • avaliar a entrada
  • crie a matriz [0] * entrada (0 repetido quantas vezes a entrada)
  • imprima
  • tente avaliar a entrada
  • falhou
  • crie o array [0] * (entrada ^ 2) (0 repetido quantas vezes a entrada ao quadrado)
  • imprima
Freira Furada
fonte
Por que não fica aguardando a interação do usuário quando há várias chamadas para input()?
Jonathan Allan
11
É uma brecha que "fim da transmissão" é transmitido no final da transmissão?
Freira vazando 04/04
11
Você pode explicar isso?
Brain Guider
11
Re: o argumento "fim do arquivo", você está olhando para trás. Quando você está usando um terminal, os pedidos de entrada são interrompidos porque há algo conectado a ele; ctrl-D pode ser enviado para enviar explicitamente nenhuma entrada. Se a entrada estiver conectada a um arquivo vazio (como o TIO faz se você deixar a caixa de entrada vazia) ou se estiver conectada a um arquivo em que todas as entradas foram lidas, não há necessidade de a solicitação de entrada fazer alguma coisa; já sabe que não há entrada. No UNIX / Linux, "final do arquivo" e "nenhuma entrada disponível" são indistinguíveis nos arquivos regulares.
3
Para o primeiro caso, ké a entrada e lé uma, então você ainda está computando 1**k, certo? O que deve levar O(log(k))tempo, apesar do fato de que você e eu e todo mundo sabemos antecipadamente que é um?
Richard Rast
18

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

Tenho certeza de que posso jogar mais (muito) isso, mas é hora de dormir, passei bastante tempo depurando como está e tenho orgulho do que tenho até agora.

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

O programa em si não usa a entrada e apenas avalia uma sequência que começa com um comentário e, em seguida, faz uma única substituição de sequência, portanto isso é claramente em tempo constante. É basicamente equivalente a:

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

Dobrado:

#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/#//;

O bit que realmente leva tempo exponencial é o segundo eval: avalia o comando say for(1..2**$_), que lista todos os números de 1 a 2 ^ N, que claramente leva tempo exponencial.

Invertida:

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

Isso (ingenuamente) calcula a soma da entrada, o que claramente leva tempo linear (já que cada adição é em tempo constante). O código que realmente é executado é equivalente a:

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

A última linha é apenas para que, quando esses comandos forem repetidos, leve tempo quadrático.

Invertida e dobrada:

;//#/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#

Isso agora pega o somatório do somatório da entrada (e o adiciona ao somatório da entrada, mas tanto faz). Como ele solicita N^2adições, isso leva tempo quadrático. É basicamente equivalente a:

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

A segunda linha encontra a soma da entrada, fazendo Nadições, enquanto a quarta faz summation(N)adições, o que é O(N^2).

Chris
fonte
Ótimo! Fazer isso em um idioma convencional teria sido difícil! Isso tem o meu voto positivo!
Arjun
Bem feito, isso é muito bom. Você provavelmente quis dizer em $x.=q;##say...vez de $x.=q;#say...(com dois em #vez de 1). (Isso explicaria por que você contou 76 bytes em vez de 75). Além disso, você deve contar o -nsinalizador em seu número de bytes, pois seu programa não faz muito sem ele.
Dada
@ Dadá acidentalmente transpus evalos s///comandos e. Se você fizer o evalprimeiro, precisará apenas desse #. Boa pegada!
314 Chris
@ Chris Right, funciona de fato. Você pode omitir o último #: produtos $x=~s/#//;invertidos ;//#/s~=x$, que no seu contexto não fazem nada, como faria com um líder #. (Eu ainda não testei). Independentemente disso, tenha um +1!
Dada
@ Dadada captura boa, mais uma vez!
21417 Chris
17

Na verdade , 20 bytes

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

Experimente online!

Entrada: 5

Resultado:

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

Invertida:

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

Experimente online!

Resultado:

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

Dobrado:

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

Experimente online!

Resultado:

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]

Dobrado e revertido:

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

Experimente online!

Resultado:

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]

Ideia principal

Na verdade, é uma linguagem baseada em pilha.

  • abcé um programa que possui complexidade O (1 n ) e seu duplo possui complexidade O (2 n ).
  • defé um programa que possui complexidade O (n 1 ) e seu duplo possui complexidade O (n 2 ).

Então, minha submissão é "abc"ƒ"fed"onde ƒé avaliar. Dessa forma, "fed"não será avaliado.

Geração de programa individual

O pseudocódigo do primeiro componente ;(1╖╜ⁿr:

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

O pseudocódigo do segundo componente ;(1╖╜ⁿ@r:

register += 1 # register is default 0
print(range(input**register))
Freira Furada
fonte
Eu nunca pensei que isso seria possível! Bom trabalho, senhor! +1
Arjun
@Arjun Obrigado por sua apreciação.
Leaky Nun
Isso é excelente e realmente desafia o desafio por não usar os comentários da IMO. Impressionante!
ShreevatsaR
11
Bem, isso realmente tem comentários ... as cordas são unevaluated e são NOPs ...
Leaky Nun
4

Gelatina , 20 bytes

Parcialmente inspirado na solução Leaky Nun's Actually .

As novas linhas iniciais e finais são significativas.

Normal:


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

Experimente online!

Entrada: 5

Resultado: 

610

Invertida:


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

Experimente online!

Entrada: 5

Resultado:

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

Dobrado


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

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

Experimente online!

Entrada: 5

Resultado:

[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

Dobrado e invertido


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

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

Experimente online!

Entrada: 5

Resultado:

[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

Explicação

A chave aqui está Ŀ, o que significa "chama o link no índice n como uma mônada". Os links são indexados de cima para baixo começando em 1, excluindo o link principal (o mais baixo). Ŀtambém é modular; portanto, se você tentar ligar para o número 7 do link 5, na verdade, chamará o link 2.

O link chamado neste programa é sempre o do índice 10 ( ⁵), independentemente da versão do programa. No entanto, qual link está no índice 10 depende da versão.

O ⁵que aparece depois de cada um Ŀestá lá, para não quebrar quando invertido. O programa irá errar no momento da análise, se não houver um número antes Ŀ. Ter um ⁵depois é um nilad fora do lugar, que vai direto para a saída.

A versão original chama o link ‘, que calcula n + 1.

A versão reversa chama o link R, que gera o intervalo 1 .. n.

A versão duplicada chama o link 2*R, que calcula 2 n e gera o intervalo 1 .. 2 n .

A versão dobrada e revertida chama o link ²R, que calcula n 2 e gera o intervalo 1 .. n 2 .

Gato de negócios
fonte
4

Befunge-98 , 50 bytes

Normal

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

Este é de longe o programa mais simples dos 4 - os únicos comandos executados são os seguintes:

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

Este programa faz algumas coisas irrelevantes antes de pressionar um comando "virar à direita" ( ]) e uma seta. Em seguida, ele atinge 2 comandos "take input". Como existe apenas 1 número na entrada e como o TIO trata &s, o programa é encerrado após 60 segundos. Se houver 2 entradas (e porque eu posso, sem adicionar bytes), o IP passaria para a função "finalizar programa".

Experimente online!

Invertida

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

Este é um pouco mais complicado. os comandos relevantes são os seguintes:

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

que é 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

A parte importante aqui é a parte :. 1-:!k@. É útil porque, se colocarmos a complexidade correta na pilha antes de executar em uma complexidade de tempo menor, podemos obter a desejada. Isso será usado nos 2 programas restantes dessa maneira.

Experimente online!

Dobrado

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

E o comando relevante são:

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

Este programa entra em 2 loops. Primeiro, segue o mesmo caminho que o programa normal, que coloca 1 e N na pilha, mas, em vez de passar para o segundo &, o IP salta sobre um comentário em um loop que empurra 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

Os outros bits da linha 4 são pulados usando ;s

Depois que (2 ^ N) é empurrado para a pilha, movemos uma linha para baixo no loop de impressão mencionado acima. Por causa do primeiro loop, a complexidade do tempo é Θ (N + 2 ^ N), mas isso se reduz a Θ (2 ^ N).

Experimente online!

Dobrado e invertido

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

Os comandos relevantes:

;&^

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

 @>:*[

  :

Isso funciona quase de forma idêntica ao programa invertido, mas N^2não é retirado da pilha, porque a primeira linha da segunda cópia do programa é anexada à última linha da primeira, o que significa que o comando drop ( $) nunca é executado , então entramos no loop de impressão N^2na parte superior da pilha.

Experimente online!

MildlyMilquetoast
fonte