Anzahl der Vergleich im Schlimmsten Fall das Zusammenführen von Zwei Sortierten Arrays?

Gegeben zwei sortierte arrays A, B mit Größe n und m. Ich bin auf der Suche nach schlimmsten Anzahl von Vergleich verschmilzt, dass diese beiden arrays.

1) n+m-1

2) max(n,m)

3)min (m,n)

4) mn

Ich weiß, das ist keine gute Frage, weil der merge-Algorithmus nicht erwähnt, aber ich denke, Die normalen merge-sort Algorithmus - merge-Schritt mit normal gelten n + m -1 Vergleiche, wo eine Liste der Größe n und und die andere Liste ist von der Größe m. Mit diesem Algorithmus ist der einfachste Ansatz zum kombinieren von zwei sortierten Listen. jeder Experte der mir helfen konnte, bin ich im Recht, indem Sie (1)?

InformationsquelleAutor Prof. Kosi Noura | 2015-03-13
  1. 2

    Diese können leicht gefunden werden, sich von der Dokumentation:

    Komplexität

    Bei den meisten std::distance(first1, last1) + std::distance(first2, last2) - 1 Vergleiche.

    Also No. 1 ist. (Ja, es wird davon ausgegangen, dass die standard-Ausschuss bekam der Komplexität Recht, aber das ist nicht weit hergeholt.)

    Option 4 ist offensichtlich falsch, weil n + m - 1 wächst langsamer als n*m, so haben wir schon eine bessere Schätzung.

    Option 3 ist falsch, mit diesem Gegenbeispiel:

    [4], [1, 2, 6, 7]

    braucht mindestens zwei Vergleiche. Option 2 Gegenbeispiel:

    [1,6], [2,5]

    müssten 3 Vergleiche:

    1 < 2?, 6 < 2?, 6 < 5?
    • ist es möglich, weitere Details hinzufügen ?
    • Sind Sie auf der Suche nach einem mathematischen Beweis für die Komplexität? Ich denke, das ist nicht on-topic hier. (Obwohl das wahrscheinlich nicht schwer.)
    • Nein, zum Beispiel, warum mn nicht korrekt? der Algorithmus nicht mentined !!
    • "Option 4 ist offensichtlich falsch, weil n + m - 1 wächst langsamer als n*m, also es ist schon besser einschätzen." warum, wenn langsamer, nicht besser einschätzen?
    • Was? n+m-1 ist bereits ein worst-case-Schätzung und n+m-1 <= n*m für die positiven ganzen zahlen (die Sie sollten in der Lage sein zu arbeiten, auf Ihre eigenen). So n*m nicht die korrekte Schätzung, denn wir fanden schon eine bessere Obere Schranke. Ich hoffe, dass klärt, ich verstehe nicht, Ihren Kommentar überhaupt.
    InformationsquelleAutor Baum mit Augen
  2. 2

    Vorausgesetzt, m < n, mindestens m Vergleiche und maximal n+m-1 Vergleiche (worst case). Vorausgesetzt, alle Elemente der kleinsten Liste kommen zuerst, die minimale Anzahl von vergleichen ist min (n, m). Unter der Annahme, dass durch einfachste Sie bedeuten im besten Fall, dann Antwort 3 die richtige Antwort. Antwort 1 ist korrekt, für den schlimmsten Fall.

    InformationsquelleAutor Tarik
Schreibe einen Kommentar