Wie können wir beweisen, dass die Laufzeitgrenze eines Algorithmus eng ist?

Question

Angenommen, wir können beweisen, dass ein Algorithmus, der mit einer Eingabe der Größe n aufgerufen wird, in der Zeit O(f(n)) läuft.

Ich möchte beweisen, dass diese Laufzeitgrenze eng ist. Zwei Fragen:

1. Wäre es nicht ausreichend, einen speziellen Eingang zu geben und zu zeigen, dass die Laufzeit mindestens f(n) ist?
2. Ich habe gelesen, dass eine Möglichkeit, die Dichtheit zu beweisen, "die Sortierung darauf zu reduzieren" ist. Ich habe keine Ahnung, was von diesem

Answer 1

gemeint ist Wäre es nicht eine spezielle Input zu geben genügen und zeigen, dass die Lauf Zeit mindestens f (n)?

Ja, Sie unter der Annahme, sprechen über die worst case Komplexität.
Wenn Sie sprechen über Worst-Case-Komplexität - und Sie haben bewiesen, es läuft in O(f(n)), wenn Sie eine Eingabe finden, die "schlechter" als C*f(n)) für einige Konstante C - Sie effektiv bewiesen, dass der Algorithmus (im schlimmsten Fall Leistung) ist In Ω(f(n)), und seit O(f(n)) [intersection] Ω(f(n)) = Theta(f(n)) bedeutet dies, dass Ihr Algorithmus unter Worst-Case-Analyse in Theta(f(n)) ausgeführt wird.
Hinweis, dass es tatsächlich eine „Familie“ von Beispielen sein sollte, denn wenn ich „ja behaupten, aber dies nur für kleine n Werte korrekt sind, und nicht für n>N (für einige N), können Sie mir, dass dies zeigen Familie von Beispielen erstreckt sich auch auf den Fall, in dem n>N, und nach wie vor gültig.

Symmetrisch, wenn Sie einen Algorithmus bewiesen hat besten Fall Leistung von Ω(f(n)), und Sie etwas Eingang gefunden, die „besser“ (schneller) als C*f(n)) für einige läuft Konstante C, Sie haben effektiv bewiesen, dass der Algorithmus Theta(f(n)) im besten Fall Analyse ist.

Dieser Trick funktioniert NICHT für die durchschnittliche Fallanalyse - wo Sie die erwartete Laufzeit berechnen sollten, und ein einzelnes Beispiel ist nicht hilfreich.

Ich habe gelesen, dass eine Möglichkeit zum Nachweis der Dichtheit ist, " Sortierung zu reduzieren". Ich habe keine Ahnung, was von diesen

gemeint ist dies geschehen wird eine viel stärkere Behauptung zu beweisen, dass gibt es keinen Algorithmus (überhaupt), die ein Problem bei der gewünschten Zeit lösen können.
Die gemeinsame Nutzung ist es anzunehmen, ist einige Blackbox Algorithmus A, die in irgendeiner o(g(n)) Zeit abläuft, und dann A verwenden, um einen Sortieralgorithmus zu bauen, die in o(nlogn) Zeit abläuft. Da die Sortierung Ω(nlogn) Problem ist, haben wir einen Widerspruch, und wir können schließen, dass Annahmen über A falsch sind, und es kann nicht in der gewünschten Zeit ausgeführt werden.

Dies hilft uns, eine stärkere Behauptung zu beweisen: Nicht nur unser Algorithmus hat diese untere Grenze, sondern ALLE Algorithmen, die das spezifische Problem lösen, haben diese untere Grenze.

Answer 2

ad 1 .: Ja, aber Sie müssen solche Eingabe der Größe n für jedes n finden können. Ein Beispiel der Größe 3, das in 9 Schritten bearbeitet wird, beweist nicht wirklich etwas.

ad 2 .: Wenn Sie eine Sequenz von Elementen so ändern können, dass Ihr Algorithmus sie effektiv sortiert (Sie erhalten nach einer gewissen Verarbeitung der Ausgabe eine sortierte Sequenz), haben Sie die Sortierung darauf reduziert. Und weil das Sortieren (durch Vergleich) nicht schneller als O (n log (n)) sein kann, kann dies verwendet werden, um zu beweisen, dass Ihr Algorithmus nicht schneller als O (n log (n)) sein kann.

Natürlich können die Eingabe- und Ausgabeverarbeitungsfunktionen nicht langsamer oder gleich O (n log (n)) sein, damit dieses Argument gültig ist. Andernfalls könnten Sie das Array sortieren und einen O (1) -Algorithmus beweisen das gibt nur das Eingabe-Array zurück, ist tatsächlich mindestens O (n log (n)) :).