Unterschied zwischen O(m+n) und O(mn)?

War ich versucht zu finden, die Komplexität eines Algorithmus über verschiedene Ansätze. Mathematisch stieß ich auf ein O(m+n) und anderen O(mn) Ansatz. Aber ich bin nicht in der Lage zu begreifen, oder zu sagen, diese sichtbar zu machen. Es ist nicht so, ich schau Sie an und Holen Sie sich die "Ahh! Das ist, was 's Los" - Gefühl! Kann sich das jemand erklären mit eigenen Beispielen oder einem anderen tool?

  • Und ich verstehe, dass, wenn m=n dann von Ihnen ist O(n^2), während die andere bleibt O(n). Aber ich bin nicht perfekt greifen das Konzept!
  • Zu verstehen, alle Big O-notation? Ich bin nicht sicher, was "begreifen das Konzept bedeutet". Ein Beispiel, wenn zwei Variablen gehalten werden, in der Grenzen ist für Fälle wie Radix sort - zu berücksichtigen, dass in solchen Algorithmus k (m) ist immer noch relevant, auch als N (n) ist eine Konstante.
InformationsquelleAutor Dubby | 2014-05-27
  1. 4

    Meine Empfehlung für die Suche nach intuition Gedankenexperimente wie folgt:

    Erste, erkennen, dass m und n sind zwei verschiedene Messungen des input -. Vielleicht waren Sie die Längen der beiden input-streams, die Längen der Seiten eines matrix oder die Anzahl der zwei verschiedene Attribute die gleiche Datenstruktur, wie edge-und node-count des gleichen Graphen oder ähnliche Maßnahmen.

    Die intuition ist, dass big-O drückt eine Schranke für die wahr Laufzeit (oder einige andere Aspekte wie den Vergleich zählen oder Platzbedarf) eines Algorithmus in Bezug auf eine einfache Funktion - Anruf, dass R(m, n) - multipliziert mit einer willkürlichen Konstante. Ignorieren wir die Konstanten Faktoren und denke, dass alle algorithmen, begrenzt durch das gleiche R, wie eine Familie durch den Aufruf Ihrer Laufzeiten O( R(m, n) ).

    Folglich, big O(m + n) sagt, dass die wahre Laufzeit ist begrenzt durch eine Funktion R(m,n) = C(m + n) für geeignet große m und n. Für die graph-Beispiel, das sagt, dass die tatsächliche Laufzeit des Algorithmus wird begrenzt durch ein Vielfaches der Summe der Anzahl der Ecken und Kanten.

    Kann man sich den bounding-Funktion als graph, in 3d mit den Achsen m, n und R(m,n). Oder Sie können denken von Diagrammen:

    R(m,n) = m + n
--------------
m=  1  2  3  4
n=1 1  2  3  4
  2 3  4  5  6
  3 4  5  6  7
  4 5  6  7  8

    Für R(m,n) = mn, müssen Sie

    R(m,n) = mn
--------------
m=  1  2  3  4
n=1 1  2  3  4
  2 2  4  6  8
  3 3  6  9 12
  4 4  8 12 16

    Als 3d-Grafik, die erste Funktion ist eine Ebene und die zweite ist eine viel schneller wachsende Funktion in fast allen Punkten. Dies bedeutet, dass, wenn m und n groß genug, einen O(mn) gebunden wird letztlich größer sein (entsprechend einem Programm möglicherweise langsamer) als eine O(m+n), weil die Konstanten bedeutungslos geworden.

    Ein Beispiel für die Kosten des schnellen Wachstums, nehmen wir an, eine O(m+n) - Algorithmus hat einen zusätzlichen Konstanten Faktor von 3 in seiner Laufzeit gebunden (so dass es möglicherweise sehr langsam auf kleine inputs im Vergleich zu den algorithmen oben):

    R(m,n) = 3(m + n)
--------------
m=   1  2  3  4
n=1  3  9 12 15
  2  9 12 15 18
  3 12 15 18 21
  4 15 18 21 24

    Also die O(m + n) sieht wie es ist gebunden ist, ist weniger eingeschränkt als die O(mn), eine in der obigen Tabelle. Aber Blick auf den Fall m=n=100. Hier Schranke in der O(m + n) Algorithmus 3(m + n) = 600. Aber der O(mn) Algorithmus mit kleinen Konstanten-gebunden mn = 10000. Klar, Sie wollen die ersten, wenn m und n groß sind.

    @Anonym erhoben ein feiner Punkt auf der ursprünglichen version dieses Artikels, die verwirrt big-O und big-Theta. Big-O befasst sich nur mit Grenzen oder oberen Grenzen auf die Menge, die gemessen wird. Dies bedeutet beispielsweise, dass jeder O(n) Algorithmus auch O(n log n) und O(n^2). Wenn die Reale Laufzeit ist begrenzt durch die langsamer wachsende Funktion ist, ist es auch begrenzt, indem alle schneller wachsenden Märkten.

    Doch es ist durchaus üblich, für Menschen zu sagen: "dieser algorithmen ist O(n)", während die Bedeutung, die der gebunden ist engen. Das heißt, dass Cn eine Obere Schranke für die Laufzeit für einige Konstanten C und Dn ist auch eine untere Schranke für einige andere Konstante D (und entsprechend großen n). Solch eine enge gebunden ist, ist richtig angegeben, wie Theta(n), nicht O(n). Die Laufzeit von Theta(R(m, n)) - Algorithmus (grob) proportional zu R(m, n).

    Werde ich hinzufügen, schließlich, dass es gibt viele Fälle, in denen Sie nicht ignorieren können Konstanten. Es existieren viele algorithmen in der Literatur, die asymptotisch "schneller" als diejenigen, die in die gemeinsame Nutzung, aber habe Konstanten so groß, dass für praktische problem und Größen, Sie sind immer zu langsam. "Computational geometry" hat viele Beispiele. Radix 2 Art ist eine andere. Es ist Theta(n), in der Praxis aber eine gute quicksort (Theta(n log n) average case) wird schlagen es auf-arrays der Größe bis zu mindestens 10^8 zahlen.

    • O(f) nicht die Klasse von Funktionen, die sich aus f durch einen Konstanten Faktor, sondern es ist die Klasse der Funktionen, die asymptotisch begrenzt durch ein konstantes Vielfaches von f. Dies macht einige der diese Antwort falsch ist (zum Beispiel: für große m und n eine O(mn) Algorithmus wird immer länger dauern als O(m+n) ein). Ich downvoted die Antwort, denn während viel von dieser Antwort ist gut, ich glaube, insgesamt ist es nicht hilfreich, weil es fügt nur zur Verwirrung von big-O.
    • Fair genug. Meine Erklärung war für big-Theta. Ich habe korrigiert es.
    InformationsquelleAutor Gene
  2. 9

    O(m+n) Beispiel:

    for(int i = 0, i < m, i++)
    //code
for(int j = 0, j < n, j++)
    //code

    m Iterationen von code geschehen. Dann n Iterationen des Codes passiert.

    O(mn) Beispiel:

    for(int i = 0, i < m, i++)
    for(int j = 0, j < n, j++)
        //code

    Für jede iteration m haben wir n Iterationen der code. Vorstellen der Iteration über eine nicht-quadratische 2D-array.

    m und n nicht unbedingt gleich den gleichen Wert. Wenn Sie hat gleich den selben Wert, dann für O(m+n):

    O(m+n) => O(m+m) => O(2m) => O(m)

    Ich würde empfehlen, sich auf diese Frage/Antwort, um zu verstehen, dass der Letzte übergang.

    Und für O(mn):

    O(mn) => O(mm) => O(m^2)
    • Es ist gut, dass Sie gab Beispiele von O(m+n) und O(mn), und ich denke, wenn es war klar, dass diese Beispiele dann wäre dies ein ausgezeichneter start für eine Antwort. Der Letzte Absatz ist verwirrend, und ich denke, es ist nicht hilfreich für Menschen auf der Suche für ein Verständnis von big-O zu Lesen.
    • Angenommen wir haben einen Graphen dargestellt als ein angrenzens Liste mit N Knoten und E Kanten. Warum also dauert es O(N+E) zu besuchen aller Knoten und nicht O(N*E)? Wir brauchen literarischen Iteration über das array der Größe E für jeden Knoten(N).
    • Es gibt bereits answers, die erklären, dass.
    InformationsquelleAutor But I'm Not A Wrapper Class
  3. 0

    O(m+n) ist viel (eine Größenordnung) schneller als O(mn).

    O(m+n) - Algorithmus könnte eine sein, die iteriert 2 Sätze und hat eine Konstante Zeit (O(1)) - operation auf jedes element.

    O(mn) Algorithmus könnte einer sein, der wiederholt den ersten Satz und führt eine lineare Suche (O(n)) für das entsprechende element in der zweiten Gruppe.

    O(mn) Algorithmus ist wahrscheinlich das, was die Professoren rufen würde Der Naive Ansatz

    InformationsquelleAutor David Carpenter
Schreibe einen Kommentar