Wird eine geglättete Analyse außerhalb der Wissenschaft verwendet?

Question

Tat das Geglättete Analyse Finden Sie den Weg in die Hauptstromanalyse von Algorithmen? Ist es für Algorithmus -Designer üblich, eine geglättete Analyse auf ihre Algorithmen anzuwenden?

Answer 1

Ich könnte mich irren, aber ich betrachte die geglättete Analyse als einen Weg dazu erklären Das Verhalten von Algorithmen, die schlechte theoretische Garantien haben (simplex, k-means usw.). Ich bin mir nicht sicher, was es bedeuten würde verwenden Geglättete Analyse in der Praxis, außer um die Verwendung einer bestimmten Heuristik mit schlechtster Leistung zu rechtfertigen ("Meine Heuristik hat ein bla bla schlimmstes Verhalten, aber eine geglättete Analyse zeigt, dass sie in der Praxis gut abschneiden wird usw.))

Answer 2

Die Art und Weise, wie Menschen Algorithmen in der realen Welt analysieren, unterscheidet sich stark von der Wissenschaft. Während in der Wissenschaft ist es das Ziel, eine nachweislich korrekte Obergrenze in der Laufzeit zu finden, im wirklichen Leben ist es das Ziel, zu verstehen, wie der Algorithmus funktioniert und welche Verbesserungen die Laufzeit verbessern können. Es gibt zwei Hauptmethoden, die in der Wissenschaft verboten sind, aber in der Praxis verwendet werden:

• Die Annäherungsmethode. Hier verwenden Sie viele vereinfachte Annahmen, um zu versuchen, die Laufzeit eines Algorithmus zu prognostizieren. Ähnlich wie theoretische Physiker (früher).
• Experimentieren. Sie führen Ihren Algorithmus aus und messen mehrere Statistiken - wie viel Zeit für jedes Teil, wie oft jede Funktion genannt wurde, wie oft wurde jeder Zweig ausgeführt und so weiter. Diese Informationen können verwendet werden, um den Algorithmus zu optimieren. Experimente werden auch verwendet, um herauszufinden, ob einige Annäherungen bei der Analyse der Algorithmusarbeit in der Praxis durchgeführt werden oder nicht.

Ich denke jedoch nicht, dass es sehr häufig ist, einen Algorithmus in der Praxis zu analysieren, außer in einer verwandten akademischen Veröffentlichung einen Fülltext hinzuzufügen. Der Schwerpunkt liegt entweder auf Software-Engineering oder auf der Optimierung auf niedriger Ebene, abhängig vom Gegenstand.

Schließlich ist eine geglättete Analyse eine Heuristik, die verwendet werden kann, um zu erklären, warum Algorithmen in der Praxis besser funktionieren als ihr schlimmster Fall - nämlich da einige der Eingaben in gewissem Sinne "zufällig" sind. Diese Heuristik kann verwendet werden, um das Verhalten des Algorithmus zu approximieren, wenn man die Annäherungsmethode verwendet.