Beweisen Sie das für eine allgemeine Datenstruktur - die Operationen Extract_min () und Insert (x) kosten $ \ Omega (\ log n) $?

  • Ich habe folgendes Problem erhalten:

    Angenommen, eine Datenstruktur $ M $ basiert auf Vergleichen und unterstützt die folgenden Methoden auf a Zahlengruppe $ S $:

    • $ \ text {Einfügen} (x) $ - $ x $ zu $ ​​S $ hinzufügen
    • $ \ text {Extract_min} () $ - Entfernen Sie das minimale Element in $ S $ und geben Sie es zurück.

    Wir können mit implementieren Ein Haufen der oben genannten Methoden in $ O (\ log n) $. Wir betrachten jedoch ein größeres Bild, ein allgemeiner Fall, in dem wir nicht garantieren, dass $ M $ tatsächlich ein Haufen ist. Beweisen Sie, dass unabhängig davon, welche Art von Datenstruktur $ M $ ist, dass mindestens eine der von $ M $ unterstützten Methoden $ \ Omega (\ log n) $ verwenden muss. p>

    Meine Lösung:

    Jeder auf Vergleichen basierende Sortieralgorithmus muss mindestens im schlimmsten Fall vorliegen $ \ Omega (n \ log n) $ - Wir beweisen das anhand eines Entscheidungsbaums: Wenn wir einen bestimmten Algorithmus, der auf Vergleichen basiert, als einen binären Baum betrachten, bei dem jeder Scheitelpunkt eine Compare-Methode zwischen zwei Elementen:

    • Wenn das erste Element größer ist als das zweite Element, gehen wir zum linken Kind
    • Wenn das zweite Element größer ist als das erste Element, gehen wir zum richtigen Kind.

    Am Ende haben wir es $ n! $ sind die Optionen zum Sortieren der Elemente.

    Die Höhe des Baums ist $ h $, dann:

    $$ 2 ^ h \ ge n! \ quad \ Longrightarrow \ quad \ log (2 ^ h) & gt; = \ log (n!) \ quad \ Longrightarrow \ quad h \ ge \ log (n!) \ quad \ Longrightarrow \ quad h = \ Omega (n \ log n) $$

    Wenn dann ein $ \ Omega (n \ log n) $ Worst-Case für $ n $ -Elemente vorliegt, haben wir einen $ \ Omega ( \ log n) $ für ein einzelnes Element.

    Ich bin mir bezüglich dieser Lösung nicht sicher, daher würde ich mich über Korrekturen oder alles, was Sie sich wünschen, sehr freuen.

    26 June 2012
    Raphael
1 answer
  • Ich glaube nicht, dass Ihr Beweis gültig ist, da er nur Bäume und einen bestimmten Baumtyp berücksichtigt. Wenn es einen Algorithmus mit einer kleineren unteren Grenze für das, was Sie beschreiben, gäbe, hätten wir einen Sortieralgorithmus, der schneller als $ \ Omega (n \ log n) $ ist, unabhängig davon, welche der beiden Operationen $ \ log n $ ist. Das Problem reduziert sich somit auf den Beweis, dass das Sortieren nicht schneller als $ \ Omega (n \ log n) $ sein kann. Dies ist ein klassischer Beweis, den Sie online finden können.

    23 June 2012
    Raphael