Berechnung der Zeitkomplexität

Ich denke, das erste, was bei diesem Problem auffällt, ist, dass n ziemlich groß sein muss, da es vier Minuten dauerte, um die Zahlen zu sortieren. Zum Beispiel habe ich Quicksort verwendet, um Milliarden von Zahlen auf meinem Computer zu sortieren, und das dauerte knapp 3 Minuten. Also n ist wahrscheinlich ungefähr 1 Milliarde (geben oder nehmen eine Größenordnung).

Da n sehr groß ist, ist es wahrscheinlich angemessen, diese Laufzeit als c*n*lg(n) für eine Konstante c zu approximieren, da die Terme niedrigerer Laufzeit der Laufzeit-Erweiterung für einen so großen Wert nicht relevant sein sollten %Code%. Wenn wir n verdoppeln, erhalten wir den folgenden Multiplikator der Laufzeit im Vergleich zur ursprünglichen Laufzeit:

Hier ist n der Logarithmus unter einer beliebigen Basis und lg() ist die Log-Basis log_n() .

Erstens, da wir angenommen haben, dass n groß ist, wäre eine mögliche Vorgehensweise, n als 0 zu approximieren, sodass der Laufzeitmultiplikator als 2 approximiert würde und die Gesamtlaufzeit als 8 Minuten approximiert würde.

Alternativ, da wir log_n(2) wahrscheinlich innerhalb einer Größenordnung kennen, wäre eine andere Möglichkeit, den Multiplikator für einen wahrscheinlichen Wert von n zu approximieren:

• Wenn n = 100 Millionen, dann würden wir den Multiplikator als 2.075 und die Gesamtlaufzeit als 8.30 Minuten approximieren.
• Wenn n = 1 Milliarde, dann würden wir den Multiplikator als 2.067 und die Gesamtlaufzeit als 8.27 Minuten approximieren.
• Wenn n = 10 Milliarden, dann würden wir den Multiplikator als 2.060 und die Gesamtlaufzeit als 8.24 Minuten approximieren.

Beachten Sie, dass große Änderungen in unserer Approximation von n ziemlich kleine Änderungen in der Approximation der Gesamtlaufzeit ergeben.

Es ist erwähnenswert, dass, obwohl dies auf dem Papier gut aussieht, in der Praxis architektonische Überlegungen dazu führen können, dass sich die tatsächlichen Laufzeiten von denen unterscheiden, die wir hier berechnet haben. Wenn der Algorithmus beispielsweise nach Verdoppelung der Datengröße eine Menge Paging auslöst, könnte die Laufzeit sehr viel höher sein als die ~ 8 Minuten, die wir hier angenähert haben.

Die bereitgestellten Informationen sind unvollständig .

Beweis:

Die algorithmische Komplexität sei O(nlogn) . Dies bedeutet die benötigte Zeit, t = c*nlogn .

Daher haben wir die folgenden Gleichungen:

• 4 = c*n*logn
• t = c*(n2)*log(n2) , wobei t die erforderliche Antwort ist
• n2 = 2*n2

Anzahl der Variablen = 4 ( n , n2 , t , c )
Anzahl der eindeutigen Gleichungen = 3
Da wir mindestens 4 Gleichungen für 4 Variablen benötigen, sind die bereitgestellten Informationen unvollständig.

Das hört sich nach einer absolut schrecklichen Prüfungsfrage an, die wahrscheinlich von jemandem geschrieben wurde, der nicht wirklich versteht, worum es in der Big-O-Notation eigentlich geht. Es ist viel falsch daran - vieles wurde bereits in anderen Antworten angesprochen.

Das größte Problem ist, dass die Big-O-Notation keine direkte Beziehung zu Echtzeit bietet. Es wirft eine riesige Menge an Informationen aus, die benötigt werden, um die eigentliche Frage zu beantworten, die gestellt wird.

Die anderen Antworten hier haben darauf hingewiesen, dass die Frage keinen Hinweis darauf gibt, wie viele Elemente in der ursprünglichen Menge von Eingaben vorhanden waren, nur dass es in der zweiten Menge doppelt so viele Elemente gibt und dass diese Informationen für eine Antwort geben. Aber es gibt ein paar Dinge, die sie nicht erwähnt haben ...

Zuerst ignoriert Big-O Overheads des Algorithmus. Es könnte der Fall sein, dass der verwendete Algorithmus tatsächlich 3,5 Minuten für die Einrichtung benötigt, unabhängig davon, wie viele Eingaben er empfängt, und dass für den ursprünglichen Satz von Eingaben die tatsächliche Verarbeitungszeit nur ungefähr 30 Sekunden betrug. Das wird die Berechnung der Zeit für eine beliebige Anzahl von Eingaben ernsthaft beeinflussen.

Aber so schlimm diese Unterlassung ist, Big-O geht noch weiter.

Sehen Sie sich dieses Zitat von Wikipedia an:

  

In der typischen Verwendung wird die formale Definition der O-Notation nicht direkt verwendet; Vielmehr wird die O-Notation für eine Funktion f durch die folgenden Vereinfachungsregeln abgeleitet:

     

• Wenn f (x) eine Summe mehrerer Terme ist, wird derjenige mit der größten Wachstumsrate beibehalten und alle anderen weggelassen.
  
• Wenn f (x) ein Produkt mehrerer Faktoren ist, werden alle Konstanten (Terme im Produkt, die nicht von x abhängen) weggelassen.
  

Dies bedeutet, dass die Zeitberechnung mehrere Begriffe enthalten kann, die letztendlich verworfen werden. Was ist, wenn der Algorithmus c * (n + n * log(n)) -Zeit benötigt, um ohne Overhead abgeschlossen zu werden? In der Big-O-Notation ist es immer noch O(nlogn) .

Die einzige Antwort, die für die Prüfungsfrage wirklich möglich ist, ist "etwas länger als 4 Minuten". Wir können nichts mehr als das ohne viel mehr Informationen wissen. Speziell:

• Was ist der Aufwand?
• Wie hoch sind die Zeitkosten pro Vorgang?
• Über wie viele Gegenstände reden wir?
• Welche anderen Begriffe wurden weggelassen?

Alle Antworten außer Anmol Singh Jaggi sind falsch.

Zunächst ist es einfach zu sehen, dass diese Information nicht ausreicht, um eine Antwort zu erhalten . Und deshalb:

Alles, was Sie tun müssen, ist eine Gleichung zu lösen. Wenn die zeitliche Komplexität Ihres Algorithmus O (n logn) ist, dann ist die erste Gleichung, die Sie haben:

wo n in der Größe Ihrer Liste. Wenn sie möchten, dass Sie herausfinden, wie viel Zeit Sie benötigen, um den Algorithmus für die Größe doppelt so groß zu beenden, wollen sie im Grunde x finden:

Also im Grunde müssen Sie ein System von 2 Gleichungen mit 3 unbekannten lösen. Dies hat entweder 0 Antworten (nicht in unserem Fall) oder unendlich viele Antworten.

Nun musst du deine c1 annehmen. Wenn c1 = 1, dann

Durch Einsetzen von n in die zweite Gleichung erhalten Sie: x = 13.5 . Also 13 und eine halbe Minute.

Aber noch einmal, diese Antwort haben wir angenommen, dass c1 gleich 1 ist, wenn Sie einen anderen konstanten Faktor haben, erhalten Sie eine andere Antwort.

Ich mag @ Amitojs Argumentation, aber ich würde es verallgemeinern.

Lassen Sie n0 = die Anzahl der Elemente, die zu einer Laufzeit von 4 Minuten führen, und n1 = 2 * n0 . Dann haben wir

Wir versuchen,

n1 / n0 ist immer = 2.

Als n0 = & gt; unendlich, das Limit von log n1 / log n0 wird auf 1 gesetzt.

Also, wenn n0 größer wird, ist die Grenze von t 4 mins * 2 = 8 mins .