wake-up-neo.com

Unterschiede zwischen zeitlicher und räumlicher Komplexität?

Ich habe gesehen, dass die zeitliche Komplexität in den meisten Fällen mit der räumlichen Komplexität zusammenhängt und umgekehrt. Zum Beispiel bei einer Array-Durchquerung:

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

Es ist leicht zu sehen, dass die Algorithmuskomplexität in Bezug auf die Zeit O (n) ist, aber es scheint mir, dass die Raumkomplexität auch n ist (auch als O (n)?) Dargestellt.

Meine Frage: Ist es möglich, dass ein Algorithmus eine andere zeitliche Komplexität hat als die räumliche Komplexität?

48
Little

Die Komplexitäten Zeit und Leerzeichen stehen nicht miteinander in Beziehung. Sie werden verwendet, um zu beschreiben, wie viel Platz/Zeit Ihr Algorithmus benötigt, basierend auf der Eingabe.

  • Zum Beispiel, wenn der Algorithmus die Komplexität space hat:

    • O(1) - konstant - Der Algorithmus verwendet einen festen (kleinen) Speicherplatz, der nicht von der Eingabe abhängt. Für jede Größe der Eingabe nimmt der Algorithmus den gleichen (konstanten) Platz ein. Dies ist in Ihrem Beispiel der Fall, da die Eingabe nicht berücksichtigt wird und was den Zeit-/Raumbereich des print-Befehls ausmacht.
    • O(n), O(n^2), O(log(n))... - Dies bedeutet, dass Sie zusätzliche Objekte basierend auf der Länge Ihrer Eingabe erstellen. Wenn Sie zum Beispiel eine Kopie jedes Objekts von v erstellen, das in einem Array gespeichert wird und anschließend gedruckt wird, ist O(n)-Speicherplatz erforderlich, wenn Sie n-zusätzliche Objekte erstellen.
  • Im Gegensatz dazu beschreibt die Komplexität time, wie viel Zeit Ihr Algorithmus auf der Grundlage der Länge der Eingabe beansprucht. Nochmal:

    • O(1) - egal wie groß die Eingabe ist, sie benötigt immer eine konstante Zeit - zum Beispiel nur eine Anweisung. Mögen

      function(list l) {
          print("i got a list");
      }
      
    • O(n), O(n^2), O(log(n)) - wiederum basiert sie auf der Länge der Eingabe. Zum Beispiel

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

Beachten Sie, dass die beiden letzten Beispiele O(1) Platz benötigen, da Sie nichts erstellen. Vergleichen Sie sie mit

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

was O(n) Platz beansprucht, weil Sie eine neue Liste erstellen, deren Größe linear von der Größe der Eingabe abhängt.

Ihr Beispiel zeigt, dass die Komplexität von Zeit und Raum unterschiedlich sein kann. Es dauert v.length * print.time, um alle Elemente zu drucken. Das Leerzeichen ist jedoch immer dasselbe - O(1), da Sie keine zusätzlichen Objekte erstellen. Ja, es ist möglich, dass ein Algorithmus eine unterschiedliche Zeit- und Raumkomplexität aufweist, da sie nicht voneinander abhängig sind.

92
stan0

Zeit- und Raumkomplexität sind verschiedene Aspekte bei der Berechnung der Effizienz eines Algorithmus.

Zeitkomplexität befasst sich mit der Ermittlung der Berechnungszeit von Ein Algorithmus ändert sich mit der Größenänderung der Eingabe.

Andererseits beschäftigt sich space complex damit, wie viel (zusätzlicher) Platz wäre für den Algorithmus mit einer Änderung in der .__ erforderlich. Eingabegröße.

Um die zeitliche Komplexität des Algorithmus zu berechnen, besteht der beste Weg darin, zu prüfen, ob die Größe der Eingabe zunimmt. Wird die Anzahl der Vergleichsschritte (oder Rechenschritte) ebenfalls erhöht, und zur Berechnung der Speicherplatzkomplexität ist es am besten, den zusätzlichen Speicherbedarf zu ermitteln Der Algorithmus ändert sich auch mit der Änderung der Größe der Eingabe.

Ein gutes Beispiel wäre Bubble Sort

Nehmen wir an, Sie haben versucht, ein Array mit 5 Elementen zu sortieren. Im ersten Durchgang werden Sie das erste Element mit den nächsten 4 Elementen vergleichen. Im zweiten Durchgang werden Sie das zweite Element mit den nächsten 3 Elementen vergleichen und diesen Vorgang fortsetzen, bis Sie die Liste vollständig aufgebraucht haben. 

Was passiert nun, wenn Sie versuchen, 10 Elemente zu sortieren? In diesem Fall vergleichen Sie zunächst das 1. Element mit den nächsten 9 Elementen, dann das 2. Element mit den nächsten 8 Elementen usw. Wenn Sie also ein N-Element-Array haben, vergleichen Sie zunächst das 1. Element mit N-1 Elementen, dann das 2. Element mit N-2 Elementen und so weiter. Dies führt zu O(N^2) Zeitkomplexität. 

Aber wie sieht es mit der Größe aus? Wenn Sie ein Array mit 5 Elementen oder 10 Elementen sortiert haben, haben Sie zusätzlichen Puffer oder Speicherplatz verwendet. Sie könnten sagen Ja, ich habe eine temporäre Variable verwendet, um den Swap durchzuführen. Hat sich die Anzahl der Variablen jedoch geändert, wenn Sie die Größe des Arrays von 5 auf 10 erhöht haben? Nein. Unabhängig von der Größe der Eingabe werden Sie immer eine einzige Variable für den Swap verwenden. Nun, das bedeutet, dass die Größe der Eingabe nichts mit dem zusätzlichen Platz zu tun hat, den Sie benötigen, was zu O(1) oder konstanter Platzkomplexität führt. 

Als Übung für Sie jetzt die zeitliche und räumliche Komplexität von Merge Sort erforschen.

50
Prateek

Zuallererst ist die Platzkomplexität dieser Schleife O(1) (die Eingabe wird normalerweise nicht berücksichtigt, wenn berechnet wird, wie viel Speicherplatz ein Algorithmus benötigt).

Die Frage, die ich habe, ist also, ob es möglich ist, dass ein Algorithmus eine andere zeitliche Komplexität aufweist als die Raumkomplexität.

Ja, so ist es. Im Allgemeinen stehen die Zeit und die räumliche Komplexität eines Algorithmus nicht miteinander in Beziehung.

Manchmal kann einer auf Kosten des anderen erhöht werden. Dies wird als Raum-Zeit-Kompromiss bezeichnet.

6
NPE

Ja, das ist definitiv möglich. Zum Sortieren von n reellen Zahlen ist O(n) Platz erforderlich, jedoch O(n log n) Zeit. Es ist wahr, dass die Komplexität des Speicherplatzes immer ein lowerbound ist, da die Zeit für die Initialisierung des Speicherplatzes in der Laufzeit enthalten ist.

5
Mangara

Es besteht ein bekannter Zusammenhang zwischen Zeit und Raumkomplexität.

Zuallererst ist die Zeit naheliegend an den Speicherplatz gebunden: Sie können nicht mehr als O(t) Speicherzellen erreichen. Dies wird in der Regel durch die Einbeziehung ausgedrückt

                            DTime(f) ⊆ DSpace(f)

dabei sind DTime (f) und DSpace (f) die Sprachmenge .__, die von einer deterministischen Turing-Maschine rechtzeitig erkannt werden kann .__ (bzw. Leerzeichen) O (f). Das heißt, wenn ein Problem in Zeit O (f) gelöst werden kann, dann kann es auch im Raum O (f) gelöst werden.

Weniger offensichtlich ist die Tatsache, dass der Raum an die Zeit gebunden ist. Angenommen .__, dass Ihnen bei einer Eingabe der Größe n f(n) Speicherzellen, Zur Verfügung stehen, die Register, Caches und alles umfassen. Nachdem Sie diese Zellen geschrieben habenin allmöglichMöglichkeiten, können Sie eventuell Ihre Berechnung abbrechen, ging bereits durch und begann zu schleifen. Auf einem binären Alphabet können F (n) -Zellen auf 2 verschiedene Arten geschrieben werden, was unsere Zeit-Obergrenze angibt: Entweder die Berechnung stoppt innerhalb dieser Grenze, oder Sie können die Beendigung erzwingen, da die Berechnung niemals aufhört.

Dies wird normalerweise in der Aufnahme ausgedrückt

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

für einige Konstante c. Der Grund für die Konstante c ist, dass, wenn L in DSpace (f) ist, Sie nur wissen, dass es in Raum O (f) erkannt wird, während in der vorherigen Argumentation f eine tatsächliche Grenze war. 

Die obigen Beziehungen werden von stärkeren Versionen subsumiert, die nichtdeterministische Berechnungsmodelle umfassen, das heißt, wie sie häufig in Lehrbüchern angegeben werden (siehe beispielsweise Satz 7.4 in Computational .__ Complexity von Papadimitriou).

4
Andrea Asperti

Manchmal sind sie ja verwandt, und manchmal sind sie nicht verwandt. Tatsächlich verwenden wir manchmal mehr Speicherplatz, um schnellere Algorithmen zu erhalten, als bei der dynamischen Programmierung https://www.codechef.com/wiki/tutorial-dynamic-programming Dynamische Programmierung verwendet Memoization oder Bottom-Up, die erste Technik verwendet den Speicher, um sich die wiederholten Lösungen zu merken, damit der Algorithmus sie nicht neu berechnen muss, sondern sie einfach aus einer Liste von Lösungen abruft. und der Bottom-up-Ansatz beginnt mit den kleinen Lösungen und baut darauf auf, um die endgültige Lösung zu erreichen. Hier zwei einfache Beispiele, eines zeigt die Beziehung zwischen Zeit und Raum und das andere zeigt keine Beziehung: Angenommen, wir wollen die Summe aller ganzen Zahlen von 1 bis zu einer gegebenen n ganzen Zahl finden: code1:

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

Dieser Code verwendete nur 6 Bytes aus dem Speicher i => 2, n => 2 und Summe => 2 Bytes, daher ist die Zeitkomplexität O (n), während die Raumkomplexität O(1) code2 ist :

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

Dieser Code verwendet mindestens n * 2 Bytes aus dem Speicher für das Array, daher ist die Platzkomplexität O(n) und die Zeitkomplexität ist auch O (n)

1
Ahmad Hassanat

Die Art und Weise, wie der von einem Algorithmus benötigte Speicherplatz mit der Größe des Problems variiert, das er löst. Die Raumkomplexität wird normalerweise als eine Größenordnung ausgedrückt, z. O (N ^ 2) bedeutet, dass, wenn sich die Größe des Problems (N) verdoppelt, viermal so viel Arbeitsspeicher benötigt wird.

0
Alam