Powerprogramming: O (1 ^ N), O (N 1), O (2 ^ N), O (N 2) tout en un

65

Ecrivez un programme (ou une fonction) qui présente quatre grandes complexités de temps O communes, en fonction de la manière dont il est exécuté. Quelle que soit sa forme, il prend un entier positif N que vous pouvez supposer inférieur à 2 31 .

  1. Lorsque le programme est exécuté dans sa forme d' origine, sa complexité doit être constante . C'est-à-dire que la complexité devrait être (1) ou, de manière équivalente, (1 ^ N) .

  2. Lorsque le programme est inversé et exécuté, il doit avoir une complexité linéaire . C'est-à-dire que la complexité devrait être (N) ou, de manière équivalente, Θ (N ^ 1) .
    (Cela a du sens puisque N^1est 1^Ninversé.)

  3. Lorsque le programme est doublé , ce concaténé à lui - même, et l' exécuter devrait avoir exponentielle la complexité, en particulier 2 N . C'est-à-dire que la complexité devrait être (2 ^ N) .
    (Cela a du sens puisque l' 2in 2^Nest le double de l' 1in 1^N.)

  4. Lorsque le programme est doublé , inversé et exécuté, il doit présenter une complexité polynomiale , en particulier N 2 . C'est-à-dire que la complexité devrait être (N ^ 2) .
    (Cela a du sens puisque N^2est 2^Ninversé.)

Ces quatre cas sont les seuls dont vous avez besoin.

Notez que pour plus de précision, j'utilise la notation thêta grosse () au lieu de la lettre grand O car les exécutions de vos programmes doivent être limitées à la fois par le haut et par le bas par la complexité requise. Sinon, écrire une fonction dans O (1) satisferait les quatre points. Il n’est pas très important de comprendre la nuance ici. Principalement, si votre programme effectue des opérations k * f (N) pour une constante k alors il est probable qu'il se trouve dans Θ (f (N)).

Exemple

Si le programme initial était

ABCDE

puis cela devrait prendre un temps constant. En d'autres termes, que l'entrée N soit égale à 1 ou 2147483647 (2 31 -1) ou à une valeur quelconque, elle doit se terminer à peu près dans le même temps.

La version inversée du programme

EDCBA

devrait prendre un temps linéaire en termes de N. Autrement dit, le temps nécessaire pour terminer doit être approximativement proportionnel à N. Donc, N = 1 prend le moins de temps et N = 2147483647, le plus.

La version doublée du programme

ABCDEABCDE

devrait prendre le temps de deux à la N en termes de N. C'est, le temps qu'il faut mettre fin devrait être à peu près proportionnelle à 2 N . Donc, si N = 1 se termine dans environ une seconde, N = 60 prendra plus de temps que l'âge de l'univers pour se terminer. (Non, vous n'avez pas à le tester.)

La version doublée et inversée du programme

EDCBAEDCBA

devrait prendre un temps carré en termes de N. Autrement dit, le temps nécessaire pour terminer doit être à peu près proportionnel à N * N. Donc, si N = 1 se termine dans environ une seconde, N = 60 prend environ une heure pour se terminer.

Détails

  • Vous devez montrer ou argumenter que vos programmes fonctionnent dans les complexités que vous dites être. Donner des données temporelles est une bonne idée, mais essayez également d’expliquer pourquoi la complexité est théoriquement correcte.

  • C'est bien si, en pratique, les temps que prennent vos programmes ne sont pas parfaitement représentatifs de leur complexité (ou même déterministes). Par exemple, l'entrée N + 1 peut parfois courir plus vite que N.

  • L'environnement dans lequel vous exécutez vos programmes est important. Vous pouvez faire des suppositions de base sur le fait que les langages populaires ne perdent jamais intentionnellement du temps dans des algorithmes. Par exemple, si vous savez que votre version de Java implémente le tri à bulle au lieu d'un algorithme de tri plus rapide , vous devez en tenir compte si vous effectuez un tri. .

  • Pour toutes les complexités, supposons ici que nous parlons des pires scénarios , et non des cas optimaux ou moyens.

  • La complexité spatiale des programmes n'a pas d'importance, seule la complexité temporelle.

  • Les programmes peuvent sortir n'importe quoi. Il importe seulement qu’ils prennent le nombre entier positif N et aient les complexités temporelles correctes.

  • Les commentaires et les programmes multilignes sont autorisés. (Vous pouvez supposer que la compatibilité avec Windows \r\nest inversée \r\n.)

Big O Rappels

Du plus rapide au plus lent O(1), O(N), O(N^2), O(2^N)(ordre 1, 2, 4, 3 ci-dessus).

Les termes les plus lents dominent toujours, par exemple O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))pour constante k. Alors O(2) = O(30) = O(1)et O(2*N) = O(0.1*N) = O(N).

Rappelez O(N^2) != O(N^3)- vous et O(2^N) != O(3^N).

Neat Big O Cheat Sheet.

Notation

C'est un code de golf normal. Le programme original le plus court (le temps constant un) en octets l'emporte.

code-golf integer source-layout restricted-complexity set-theory Les passe-temps de Calvin
la source
Excellente question! Point mineur: il n’est pas nécessaire de spécifier le cas le plus défavorable / le meilleur des cas / le cas moyen, car la seule entrée qui compte comme taille N est le nombre N lui-même (BTW n’est pas la notion habituelle de taille d’entrée: cela traiter l’entrée N comme étant de taille log N). Donc , il n'y a qu'un un cas pour chaque N, qui est en même temps le meilleur, le pire et le cas moyen.
ShreevatsaR
5
Il semble que vous ayez dévié des définitions habituelles de la complexité. Nous définissons toujours la complexité temporelle d'un algorithme en fonction de la taille de son entrée . Dans le cas où l'entrée est un nombre, la taille de l'entrée est le logarithme en base 2 de ce nombre. Ainsi, le programme n = input(); for i in xrange(n): passa une complexité exponentielle, car il prend des 2 ** kétapes, où k = log_2(n)est la taille d'entrée. Vous devez préciser si c'est le cas, car cela change radicalement les exigences.
wchargin

Réponses:

36

Python 3 , 102 octets

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

Essayez-le en ligne!

C'est de O (1 ^ n), puisque c'est ce que fait le programme:

  • évaluer l'entrée
  • créer le tableau [0]
  • imprime le

Renversé:


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

Essayez-le en ligne!

C'est de O (n ^ 1), puisque c'est ce que fait le programme:

  • évaluer l'entrée
  • crée le tableau [0] * entrée (0 répété autant de fois que l'entrée)
  • imprime le

Doublé:

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

Essayez-le en ligne!

C'est de O (2 ^ n), puisque c'est ce que fait le programme:

  • évaluer l'entrée
  • créer le tableau [0]
  • imprime le
  • essayer d'évaluer l'entrée
  • échouer
  • crée le tableau [0] * (2 ^ entrée) (0 répété autant de fois que 2 ^ entrée)
  • imprime le

Doublé et inversé:


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

Essayez-le en ligne!

C'est de O (n ^ 2), puisque c'est ce que fait le programme:

  • évaluer l'entrée
  • crée le tableau [0] * entrée (0 répété autant de fois que l'entrée)
  • imprime le
  • essayer d'évaluer l'entrée
  • échouer
  • crée le tableau [0] * (entrée ^ 2) (0 répété autant de fois que l'entrée est au carré)
  • imprime le
Fuite Nun
la source
Pourquoi ne reste-t-il pas en attente d'une interaction de l'utilisateur lorsqu'il y a plusieurs appels input()?
Jonathan Allan
1
C'est une faille que "la fin de la transmission" est transmise à la fin de la transmission?
Leaky Nun
1
Pouvez-vous l'expliquer?
Brain Guider
1
Re: l'argument "fin de fichier", vous regardez les choses en arrière. Lorsque vous utilisez un terminal, les demandes d’entrée sont bloquées, car quelque chose s’y connecte; Ctrl-D peut être envoyé pour envoyer explicitement aucune entrée. Si l'entrée est connectée à un fichier vide (comme TIO le fait si vous laissez la zone de saisie vide), ou si elle est connectée à un fichier dans lequel toutes les entrées ont été lues, la requête d'entrée n'a pas besoin de faire quoi que ce soit; il sait déjà qu'il n'y a pas d'entrée. Sous UNIX / Linux, "fin du fichier" et "aucune entrée disponible" ne peuvent pas être distingués des fichiers normaux.
3
Dans le premier cas, il ks’agit de l’entrée, et lc’est le cas, vous calculez donc toujours 1**k, non? Ce qui devrait prendre du O(log(k))temps, malgré le fait que vous et moi et tout le monde sachions d'avance qu'il en est un?
Richard Rast
18

Perl 5, 82 73 71 + 1 (pour l'indicateur -n) = 72 octets

Je suis certain de pouvoir jouer au golf beaucoup plus, mais il est l'heure d'aller au lit, j'ai passé assez de temps à déboguer tel quel et je suis fier de ce que j'ai jusqu'ici.

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

Le programme lui-même n'utilise pas l'entrée, il évalue simplement une chaîne commençant par un commentaire, puis effectue une substitution de chaîne unique, ce qui est clairement en temps constant. C'est fondamentalement équivalent à:

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

Doublé:

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

Le bit qui prend réellement un temps exponentiel est la deuxième évaluation: il évalue la commande say for(1..2**$_), qui répertorie tous les nombres de 1 à 2 ^ N, ce qui prend clairement un temps exponentiel.

Renversé:

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

Ceci (naïvement) calcule la somme de l'entrée, ce qui prend clairement un temps linéaire (puisque chaque addition est en temps constant). Le code qui est réellement exécuté est équivalent à:

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

La dernière ligne est juste pour que, lorsque ces commandes sont répétées, cela prenne du temps quadratique.

Renversé et doublé:

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

Ceci prend maintenant la somme de la somme de l'entrée (et l'ajoute à la somme de l'entrée, mais peu importe). Comme cela fait des N^2ajouts d' ordre , cela prend du temps quadratique. C'est fondamentalement équivalent à:

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

La deuxième ligne trouve la somme des entrées, en effectuant des Najouts, tandis que la quatrième effectue des summation(N)ajouts, ce qui est O(N^2).

Chris
la source
Génial! Faire cela dans une langue courante aurait été difficile! Cela a mon vote positif!
Arjun
Bien fait, c'est plutôt sympa. Vous avez probablement voulu dire $x.=q;##say...au lieu de $x.=q;#say...bien (avec deux #au lieu de 1). (Cela expliquerait pourquoi vous avez compté 76 octets au lieu de 75). De plus, vous devriez compter le -ndrapeau dans votre compte intermédiaire, car votre programme ne fait pas grand chose sans.
Dada
@ Dada I a accidentellement transposé evalles s///commandes et. Si vous faites le evalpremier, vous n’avez besoin que du premier #. Bonne prise!
Chris
@ Chris Right, ça marche vraiment. Vous pourrez peut-être omettre le dernier #: $x=~s/#//;produit inversé ;//#/s~=x$, ce qui dans votre contexte ne fait rien, comme il le ferait avec un interlocuteur principal #. (Je ne l'ai pas testé cependant). Quoi qu'il en soit, ayez un +1!
Dada
@Dada Belle prise encore une fois!
Chris
17

En fait , 20 octets

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

Essayez-le en ligne!

Contribution: 5

Sortie:

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

Renversé:

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

Essayez-le en ligne!

Sortie:

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

Doublé:

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

Essayez-le en ligne!

Sortie:

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]

Doublé et inversé:

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

Essayez-le en ligne!

Sortie:

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]

Idée principale

En fait, c'est un langage basé sur la pile.

  • abcest un programme qui a une complexité O (1 n ), et son double a une complexité O (2 n ).
  • defest un programme qui a une complexité O (n 1 ) et son double a une complexité O (n 2 ).

Ensuite, ma soumission est "abc"ƒ"fed", où ƒest évaluer. De cette façon, "fed"ne sera pas évalué.

Génération de programme individuel

Le pseudocode du premier composant ;(1╖╜ⁿr:

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

Le pseudocode du deuxième composant ;(1╖╜ⁿ@r:

register += 1 # register is default 0
print(range(input**register))
Fuite Nun
la source
Je n'ai jamais pensé que cela serait même possible! Excellent travail, monsieur! +1
Arjun
@Arjun Merci pour votre appréciation.
Leaky Nun
C'est excellent et relève vraiment le défi en n'utilisant pas les commentaires de l'OMI. Impressionnant!
ShreevatsaR
1
Eh bien cela a en fait des commentaires ... les chaînes ne sont pas évaluées et sont des NOPs ...
Leaky Nun
4

Gelée , 20 octets

Inspiré en partie par la solution Leaky Nun's Actually .

Les nouvelles lignes de début et de fin sont significatives.

Ordinaire:


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

Essayez-le en ligne!

Contribution: 5

Sortie: 

610

Renversé:


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

Essayez-le en ligne!

Contribution: 5

Sortie:

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

Doublé


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

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

Essayez-le en ligne!

Contribution: 5

Sortie:

[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

Doublé et renversé


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

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

Essayez-le en ligne!

Contribution: 5

Sortie:

[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

Explication

La clé est ici Ŀ, ce qui signifie "appelle le lien à l'index n en tant que monade". Les liens sont indexés de haut en bas à partir de 1, à l’exclusion du lien principal (le plus bas). Ŀest également modulaire, donc si vous essayez d’appeler le lien numéro 7 sur 5 liens, vous appellerez en fait le lien 2.

Le lien appelé dans ce programme est toujours celui de l'index 10 ( ⁵), quelle que soit sa version. Cependant, le lien à l'index 10 dépend de la version.

Le ⁵qui apparaît après chaque Ŀest là pour qu'il ne casse pas lorsqu'il est inversé. Le programme affichera une erreur lors de l'analyse s'il n'y a pas de numéro avant Ŀ. Avoir un ⁵après c'est un nilad hors de propos, qui va directement à la sortie.

La version d'origine appelle le lien ‘, qui calcule n + 1.

La version inversée appelle le lien R, qui génère la plage 1 .. n.

La version doublée appelle le lien 2*R, qui calcule 2 n et génère la plage 1 .. 2 n .

La version doublée et inversée appelle le lien ²R, qui calcule n 2 et génère la plage 1 .. n 2 .

Chat d'affaires
la source
4

Befunge-98 , 50 octets

Ordinaire

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

C'est de loin le programme le plus simple des 4 - les seules commandes exécutées sont les suivantes:

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

Ce programme effectue des opérations irrévocables avant de frapper une commande "tournez à droite" ( ]) et une flèche. Ensuite, il frappe 2 commandes "prendre entrée". Comme il n'y a qu'un seul nombre en entrée et à cause de la façon dont TIO traite les &s, le programme se ferme après 60 secondes. S'il y a 2 entrées (et parce que je peux sans ajouter d'octets), l'IP irait dans la fonction "fin du programme".

Essayez-le en ligne!

Renversé

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

Celui-ci est un peu plus compliqué. les commandes pertinentes sont les suivantes:

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

ce qui équivaut à

;&^                   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 partie importante ici est le :. 1-:!k@bit. C'est utile car tant que nous plaçons la complexité correcte sur la pile avant d'exécuter dans une complexité temporelle inférieure, nous pouvons obtenir celle désirée. Ceci sera utilisé dans les 2 programmes restants de cette manière.

Essayez-le en ligne!

Doublé

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

Et les commandes pertinentes sont:

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

Ce programme se déroule en 2 boucles. Premièrement, il suit le même chemin que le programme normal, qui insère 1 et N dans la pile, mais au lieu d’enrouler autour de la seconde &, l’IP saute par-dessus un commentaire dans une boucle qui pousse 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

Les autres bits de la ligne 4 sont sautés en utilisant ;s

Après que (2 ^ N) soit poussé sur la pile, nous descendons d’une ligne dans la boucle d’impression susmentionnée. En raison de la première boucle, la complexité temporelle est (N + 2 ^ N), mais elle se réduit à Θ (2 ^ N).

Essayez-le en ligne!

Doublé et renversé

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

Les commandes pertinentes:

;&^

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

 @>:*[

  :

Ceci fonctionne presque à l'identique du programme inversé, mais N^2n'est pas extrait de la pile, car la première ligne de la deuxième copie du programme est ajoutée à la dernière ligne de la première, ce qui signifie que la commande de suppression ( $) n'est jamais exécutée. , nous passons donc dans la boucle d’impression avec N^2en haut de la pile.

Essayez-le en ligne!

MildlyMilquetoast
la source