Algorithmen: Wie addiere ich O (n) und O (nlog (n))?

22

Ich habe den folgenden Algorithmus, der Duplikate findet und entfernt:

public static int numDuplicatesB(int[] arr) {
    Sort.mergesort(arr);
    int numDups = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) {
            numDups++;
} }
    return numDups;
}

Ich versuche, die schlimmste zeitliche Komplexität zu finden. Ich weiß, dass Mergesort ist nlog(n), und in meiner for-Schleife iteriere ich über den gesamten Datensatz, sodass dies als gilt n. Ich bin mir jedoch nicht sicher, was ich mit diesen Zahlen anfangen soll. Soll ich sie einfach zusammenfassen? Wenn ich das machen würde, wie würde ich es machen?

algorithms algorithm-analysis big-o Chopper zeichnen lion4
quelle
1
Randnotiz: Sie könnten eine Hash-Tabelle verwenden, um dies in O (n) in Abhängigkeit von den Speicheranforderungen zu tun.
CorsiKa

Antworten:

67 
O(n) + O(n log(n)) = O(n log(n))

Für die Komplexität von Big O ist alles, was Sie interessiert, der vorherrschende Begriff. n log(n)dominiert n, das ist also der einzige Begriff, den Sie interessieren.

Justin Cave
quelle
4
Eine andere Möglichkeit, darüber nachzudenken, besteht darin, sich vorzustellen, dass Ihre O (n) -Verarbeitung tatsächlich O (n log n) war, als hätten Sie zwei unabhängige Sortierungen durchgeführt. Dann hätten Sie 2 * O (n log n). Aber Konstanten verschwinden, und Sie sind wieder bei O (n log n).
Jonathan Eunice
4
@ Jonathan Während dies in der Praxis funktioniert, ist es sehr richtig, dass O (n) nicht gleich O (n log (n)) ist, daher würde ich nicht raten, dies regelmäßig zu verwenden.
Aza
17
@Emrakul eigentlich finde ich die Argumentation sowohl theoretisch als auch praktisch fundiert. O (n) ist eine richtige Teilmenge von O (n log (n)). Wenn also f (n) zu O (n) gehört, gehört es auch zu O (n log (n)).
Emory
17
Es sollte beachtet werden, dass wenn wir sagen, f(n) is O(g(n))was wir wirklich sagen, dass die Funktion ist f is a member of the set of functions that grows at the rate of at most g(n) over the long term. Dies bedeutet, dass alle Mitglieder von O(n)auch Mitglieder von sind O(n*log(n)). Die +in-Ausdrücke wie O(f(n)) + O(g(n))beziehen sich tatsächlich auf set union (welche von Ihnen wirklich pedantisch sind, sollten Sie wirklich verwenden use).
Lie Ryan
3
Ursprünglich @LieRyan, ist es nicht gesetzt Vereinigung, sondern Satz Summe: A + B = { a + b | a in A, b in B }. Es kommt vor, dass dies für Mengen der Form O(g(n))dasselbe ist wie für Mengenvereinigung , da eine der Mengen immer eine Teilmenge der anderen ist und beide für Summen unveränderlich sind (dh A + A = A). (Hoppla, Nate hat im Wesentlichen dasselbe geschrieben).
Paŭlo Ebermann
56

Lassen Sie uns darüber nachdenken und uns an die Definition von erinnern O. Die, die ich verwenden werde, ist für die Grenze im Unendlichen.

Sie haben Recht, wenn Sie angeben, dass Sie zwei Operationen mit entsprechenden asymptotischen Grenzen von ausführen O(n)und O(nlog(n))diese jedoch zu einer einzigen Grenze kombinieren, ist dies nicht so einfach wie das Hinzufügen der beiden Funktionen. Sie wissen, dass Ihre Funktion mindestens O(n)Zeit und auch mindestens O(nlog(n))Zeit benötigt. Die Komplexitätsklasse für Ihre Funktion ist also wirklich die Vereinigung von O(n)und ist O(nlog(n))aber O(nlog(n))eine Obermenge von, O(n)also wirklich ist es gerecht O(nlog(n)).

davidk01
quelle
12
+1 das sollte die Antwort sein. Es beschreibt die Antwort genauer unter Verwendung von compsci-Begriffen.
5

Wenn du es auf lange Sicht darlegen würdest, würde es ungefähr so ​​aussehen:

Angenommen, die Gesamtzeit ist: a + bn log (n), wobei a und b Konstanten sind (Terme niedrigerer Ordnung werden ignoriert).

Wenn n gegen unendlich geht (an + bn log (n)) / n log (n) -> a / log (n) + b -> b

Die Gesamtzeit ist also O (bn log (n)) = O (n log (n)).

richardb
quelle
2

Beginnen Sie mit der Definition von O ():

O (n log n) bedeutet "kleiner als C n log n, wenn n groß ist".

O (n) bedeutet "kleiner als D n, wenn n groß ist".

Wenn Sie beide addieren, ist das Ergebnis kleiner als C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).

Wenn im Allgemeinen f (n)> C g (n) für großes n und etwas C> 0 ist, dann ist O (f (n)) + O (g (n)) = O (f (n)). Und nachdem Sie einige Fälle mit der Definition von O () bearbeitet haben, wissen Sie, was Sie können und was nicht.

gnasher729
quelle
1

Die große O-Notation wird als eine Menge definiert:

Bildbeschreibung hier eingeben

So Bildbeschreibung hier eingebenenthält alle Funktionen, die - von einem beliebigen großen Ausgangspunkt Bildbeschreibung hier eingeben- immer kleiner als g.

Wenn Sie nun eine Funktion haben, die aktiviert ist, Bildbeschreibung hier eingebenund dann eine andere ausführen, die langsamer als g ansteigt, steigt sie mit Sicherheit langsamer als 2 g an. Wenn Sie also etwas langsamer als g ausführen, ändert sich die Komplexitätsklasse nicht.

Formeller:

f, h \ in \ mathcal {O} (g) \ Rightarrow (f + h) \ in \ mathcal {O} (g)

Das können Sie leicht beweisen.

TL; DR

Es ist immer noch n log (n)

Martin Thoma
quelle