Analyse des durchschnittlichen Fallalgorithmus unter Verwendung der Kolmogorov-Inkompressibilitätsmethode

Die Inkomprimierbarkeitsmethode soll die Analyse von Algorithmen für den Durchschnittsfall vereinfachen. Soweit ich weiß, müssen nicht alle möglichen Eingabekombinationen für diesen Algorithmus berechnet und dann eine durchschnittliche Komplexität abgeleitet werden. Stattdessen wird eine einzelne inkompressible Zeichenfolge als Eingabe verwendet. Da eine inkompressible Zeichenfolge typisch ist, können wir davon ausgehen, dass diese Eingabe als genaue Annäherung an den Durchschnittsfall dienen kann.

Ich bin verloren in Bezug auf die tatsächliche Anwendung der Inkomprimierbarkeitsmethode auf einen Algorithmus. Abgesehen davon bin ich kein Mathematiker, denke aber, dass diese Theorie praktische Anwendungen in der täglichen Programmierung hat.

Letztendlich möchte ich lernen, wie ich den Durchschnittsfall eines bestimmten Algorithmus ableiten kann, sei es trivial oder komplex. Könnte mir bitte jemand zeigen, wie die Methode auf einen einfachen Algorithmus angewendet werden kann? Speichern Sie beispielsweise bei einer Eingabezeichenfolge S alle eindeutigen Zeichen in S und drucken Sie jedes einzeln aus:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

Nehmen Sie eine lineare Suche an, um zu überprüfen, ob das Array ein Element enthält.

Das obige Code-Snippet dient nur der Argumentation. Bessere Algorithmen, mit denen die Theorie demonstriert werden kann, sind natürlich akzeptabel.

Ich habe diese Frage im Juli 2014 auf StackOverflow ( https://stackoverflow.com/q/24619383/3813812 ) gestellt und einige hilfreiche Kommentare erhalten, aber keine eindeutige Antwort. Wie einer der Kommentatoren betonte, ist diese Frage besser für Computer Science StackExchange geeignet, daher frage ich heute hier.

Einige Literatur, die ich überprüft habe, enthält:

1. Eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen von Ming Li und Paul MB Vitányi

2. https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf

3. http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Neben einigen anderen Ressourcen, zu denen ich keine Links habe.

Wenn mein Verständnis der Anwendbarkeit der Kolmogorov-Komplexität ungenau ist oder das, was ich verlange, unpraktisch ist, würde ich eine diesbezügliche Aussage begrüßen.

$k$$\approx \alpha_k/2$$\alpha_k$$\alpha_k$$k$$8\alpha_k + k\log \alpha_k$$8\alpha_k + k\log_2 \alpha_k \geq 8k$$k$$\alpha_k$$256$$128$$k$$k$

$\Theta(n)$$\alpha_k$

Als weiteren Kommentar (aber etwas länger als ein tatsächlicher Kommentar) zur akzeptierten Antwort:

1. Die Kolmogorov-Komplexität (oder algorithmische Komplexität ) befasst sich mit der optimalen Beschreibung von "Strings" (im allgemeinen Sinne von Strings als Folge von Symbolen ).

2. Ein String ist (ausreichend) inkompressibel oder (ausreichend) algorithmisch zufällig, wenn seine (algorithmische) Beschreibung (Kolmogorov-Komplexität K ) nicht kleiner als seine ( Literal- ) Größe ist . Mit anderen Worten, die optimale Beschreibung der Zeichenfolge ist die Zeichenfolge selbst .

3. Das Hauptergebnis der Theorie ist, dass die meisten Zeichenfolgen (algorithmisch) zufällig (oder typisch) sind (was durch Chaitins Arbeit auch mit anderen Bereichen wie Goedels Theoremen zusammenhängt).

4. Die Kolmogorov-Komplexität hängt mit der probabilistischen (oder Shannon-) Entropie zusammen , tatsächlich ist die Entropie eine Obergrenze für KC. Und dies bezieht eine Analyse auf der Grundlage deskriptiver Komplexität auf eine probabilistische Analyse. Sie können austauschbar sein.

5. Manchmal ist es möglicherweise einfacher, eine Wahrscheinlichkeitsanalyse zu verwenden, andere beschreiben die Komplexität (Ansichten derselben sagen wir mal).

In Anbetracht des Vorstehenden wird unter der Annahme einer algorithmisch zufälligen Eingabe in einen Algorithmus Folgendes angenommen:

1. Die Eingabe ist typisch , daher beschreibt die Analyse ein Durchschnittsszenario (Punkt 3 oben).
2. Die Eingabegröße hängt in gewisser Weise mit ihrer Wahrscheinlichkeit zusammen (Punkt 2 oben).
3. Man kann von der algorithmischen Ansicht zur probabilistischen Ansicht übergehen (Punkt 4 oben).