65

Schreiben Sie ein Programm (oder eine Funktion), das / die je nach Ausführung vier häufig auftretende große O- Zeit-Komplexitäten aufweist. In jeder Form nimmt es eine positive ganze Zahl N an, von der Sie annehmen können, dass sie kleiner als 2 ^{31 ist} .

Wenn das Programm in seiner ursprünglichen Form ausgeführt wird, sollte es eine konstante Komplexität aufweisen. Das heißt, die Komplexität sollte Θ (1) oder äquivalent Θ (1 ^ N) sein .
Wenn das Programm umgekehrt und ausgeführt wird, sollte es eine lineare Komplexität haben. Das heißt, die Komplexität sollte Θ (N) oder äquivalent Θ (N ^ 1) sein .
(Dies macht Sinn , da N^1wird 1^Numgekehrt.)
Wenn das Programm verdoppelt , dh auf sich selbst verkettet, und führen Sie es haben sollte exponentielle Komplexität, und zwar 2 ^N . Das heißt, die Komplexität sollte Θ (2 ^ N) sein .
(Dies ist sinnvoll, da das 2In 2^Ndas Doppelte des 1In ist 1^N.)
Wenn das Programm verdoppelt und umgekehrt und ausgeführt wird, sollte es eine polynomielle Komplexität aufweisen, insbesondere N ² . Das heißt, die Komplexität sollte Θ (N ^ 2) sein .
(Dies macht Sinn , da N^2wird 2^Numgekehrt.)

Diese vier Fälle sind die einzigen, die Sie behandeln müssen.

Beachten Sie, dass ich aus Präzisionsgründen die Big-Theta (Θ) -Notation anstelle von Big-O verwende, da die Laufzeiten Ihrer Programme sowohl oben als auch unten durch die erforderlichen Komplexitäten begrenzt sein müssen. Andernfalls würde nur das Schreiben einer Funktion in O (1) alle vier Punkte erfüllen. Es ist nicht so wichtig, die Nuance hier zu verstehen. Wenn Ihr Programm hauptsächlich k * f (N) Operationen für eine Konstante k ausführt, ist dies wahrscheinlich in Θ (f (N)).

Beispiel

Wenn das Originalprogramm wäre
ABCDE
dann sollte das Laufen eine konstante Zeit in Anspruch nehmen. Das heißt, ob der Eingang N 1 oder 2147483647 (2 ³¹ -1) ist oder ein Wert dazwischen, er sollte ungefähr in der gleichen Zeitspanne enden.

Die umgekehrte Version des Programms
EDCBA
sollte in N. ausgedrückt lineare Zeit in Anspruch nehmen. Das heißt, die Zeit, die zum Beenden benötigt wird, sollte in etwa proportional zu N sein. N = 1 dauert also am wenigsten und N = 2147483647 dauert am meisten.

Die doppelte Version des Programms
ABCDEABCDE
Dies bedeutet, dass die Zeit, die zum Beenden benötigt wird, ungefähr proportional zu 2 ^{N sein sollte} . Wenn also N = 1 in ungefähr einer Sekunde endet, würde N = 60 länger als das Alter des Universums brauchen, um zu enden. (Nein, du musst es nicht testen.)

Die doppelte und umgekehrte Version des Programms
EDCBAEDCBA
Die Zeit, die zum Beenden benötigt wird, sollte ungefähr proportional zu N * N sein. Wenn also N = 1 in ungefähr einer Sekunde endet, würde N = 60 ungefähr eine Stunde dauern, um zu beenden.

Einzelheiten

Sie müssen zeigen oder argumentieren, dass Ihre Programme in der von Ihnen angegebenen Komplexität ausgeführt werden. Das Eingeben von Zeitdaten ist eine gute Idee, aber versuchen Sie auch zu erklären, warum die Komplexität theoretisch korrekt ist.
Es ist in Ordnung, wenn in der Praxis die Zeiten, die Ihre Programme einnehmen, nicht perfekt für ihre Komplexität (oder sogar deterministisch) repräsentativ sind. zB Eingabe N + 1 läuft manchmal schneller als N.
Die Umgebung, in der Sie Ihre Programme ausführen, spielt eine Rolle. Sie können grundlegende Annahmen darüber treffen, wie populäre Sprachen niemals absichtlich Zeit in Algorithmen verschwenden. Wenn Sie jedoch beispielsweise wissen, dass Ihre Java-Version die Blasensortierung anstelle eines schnelleren Sortieralgorithmus implementiert , sollten Sie dies berücksichtigen, wenn Sie eine Sortierung durchführen .
Bei aller Komplexität wird angenommen, dass es sich um Worst-Case-Szenarien handelt , nicht um Best-Case- oder Average-Case -Szenarien .
Die räumliche Komplexität der Programme spielt keine Rolle, nur die zeitliche Komplexität.
Die Programme können alles ausgeben. Es kommt nur darauf an, dass sie eine positive ganze Zahl N aufnehmen und die richtigen zeitlichen Komplexitäten aufweisen.
Kommentare und mehrzeilige Programme sind erlaubt. (Sie können davon ausgehen, dass dies aus \r\nGründen der \r\nWindows-Kompatibilität umgekehrt ist .)

Big O Erinnerungen

Vom schnellsten zum langsamsten O(1), O(N), O(N^2), O(2^N)(Reihenfolge 1, 2, 4, 3 oben).

Langsamere Begriffe dominieren immer, z O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))für konstante k. Also O(2) = O(30) = O(1)und O(2*N) = O(0.1*N) = O(N).

Erinnere dich an O(N^2) != O(N^3)und O(2^N) != O(3^N).

Ordentliches großes O-Spickzettel.

Wertung

Dies ist normaler Code Golf. Das kürzeste ursprüngliche Programm (die konstante Zeit eins) in Bytes gewinnt.

code-golf integer source-layout restricted-complexity set-theory Calvins Hobbys
quelle

Hervorragende Frage! Kleiner Punkt: Wir müssen nicht Worst-Case / Best-Case / Average-Case angeben, da die einzige Eingabe, die als Größe N zählt, die Zahl N selbst ist (was übrigens nicht der übliche Begriff der Eingabegröße ist: das wäre Behandle die Eingabe N als Größe log N). Es gibt also nur einen Fall für jedes N, was gleichzeitig der beste, schlechteste und durchschnittliche Fall ist.

ShreevatsaR

5

Es scheint, dass Sie von den üblichen Definitionen der Komplexität abgewichen sind. Wir definieren die zeitliche Komplexität eines Algorithmus immer als Funktion der Größe seiner Eingabe . In dem Fall, in dem die Eingabe eine Zahl ist, ist die Größe der Eingabe der Logarithmus zur Basis 2 dieser Zahl. Das Programm n = input(); for i in xrange(n): passhat also eine exponentielle Komplexität, weil es 2 ** kSchritte ausführt, bei denen k = log_2(n)die Eingabegröße ist. Sie sollten klären, ob dies der Fall ist, da sich dadurch die Anforderungen dramatisch ändern.

wchargin

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

Leistungsprogrammierung: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2) in einem

Beispiel

Einzelheiten

Big O Erinnerungen

Wertung

Antworten:

Python 3 , 102 Bytes

Perl 5, 82 73 71 + 1 (für -n Flag) = 72 Bytes

Eigentlich 20 Bytes

Hauptidee

Erstellung eines individuellen Programms

Gelee , 20 Bytes

Normal:

Rückgängig gemacht:

Verdoppelt

Verdoppelt und umgekehrt

Erläuterung

Befunge-98 , 50 Bytes

Normal

Rückgängig gemacht

Verdoppelt

Verdoppelt und umgekehrt