Was ist amortisierten Analyse von algorithmen?

Wie unterscheidet es sich von asymptotischen Analyse? Wenn Sie es verwenden, und warum?

Ich ve Lesen Sie einige Artikel, die zu haben scheinen, geschrieben worden, wie diese:

aber ich habe immer noch nicht voll verstanden diese Konzepte.

So, kann bitte jemand vereinfacht es für mich?

InformationsquelleAutor der Frage GrowinMan | 2012-06-19

  1. 75

    Amortisierten Analyse nicht naiv multiplizieren Sie die Anzahl der Aufrufe mit den schlechtesten Fall für einen Aufruf.

    Beispielsweise für ein dynamisches array, die verdoppelt in der Größe, wenn nötig, ganz normaler asymptotische Analyse würde zu dem Schluss, dass das hinzufügen eines Elements zu den it-Kosten O(n), denn es könnte zum wachsen brauchen, und kopieren Sie alle Elemente in das neue array. Amortisierten Analyse berücksichtigt, dass, um zu wachsen, n/2 Elemente müssen Hinzugefügt wurden, ohne dass ein wachsen seit dem letzten wachsen, so dass das hinzufügen ein Element wirklich dauert nur O(1) - (Kosten von O(n) ist fortgeführten über n/2 Aktionen).

    Amortisierten Analyse ist nicht das gleiche wie eine "Durchschnittliche Leistung" - amortisierten Analyse gibt einen schwer garantierenwas die Leistung wird tun, wenn Sie so viel Aktionen.

    InformationsquelleAutor der Antwort harold

  2. 38

    Gibt es eine Menge Antworten auf "was", aber keiner "warum".

    Als jeder andere hat gesagt, asymptotische Analyse, wie sich die Leistung einer bestimmten operation skaliert auf einen großen Datensatz. Amortisierten Analyse ist, wie etwa der Durchschnitt der Leistung aller Operationen, die auf einem großen Datensatz skaliert. Amortisierten Analyse gibt nie schlimmer Grenzen als asymptotische, und manchmal gibt viel bessere.

    Wenn Sie sich mit der Gesamt-Laufzeit von mehr Arbeit, desto besser die Grenzen der amortisierten Analyse sind wahrscheinlich das, was Sie über Pflege. Das ist der Grund, warum Skriptsprachen (zum Beispiel) sind oft froh, zu wachsen, arrays und hash-Tabellen durch einen Faktor, obwohl, dass ist eine teure operation. (Die wachsen kann eine O(n) Betrieb, aber abgeschrieben ist O(1) denn Sie tun es nur selten.)

    Wenn Sie das tun, Echtzeit-Programmierung (einzelne Operationen müssen abgeschlossen werden, die in vorhersehbarer Zeit), dann die Grenzen besser aus fortgeführten Analyse keine Rolle. Es spielt keine Rolle, ob der Betrieb im Durchschnitt war schnell, wenn Sie nicht, um es zu beenden in der Zeit zurück zu bekommen und passen Sie die Band, bevor Sie es schneiden zu weit...

    Welche Angelegenheiten in Ihrem Fall ist, hängt von genau das, was Ihre Programmier-problem ist.

    InformationsquelleAutor der Antwort btilly

  3. 23

    Asymptotische Analyse

    Dieser Begriff bezieht sich auf die Analyse des Algorithmus die Leistung unter der Annahme, dass die Daten, die der Algorithmus operiert auf (die Eingang) ist, laienhaft ausgedrückt, "groß genug, so dass es größer wird sich nicht ändern, den Abschluss". Obwohl die genaue Größe der Eingabe nicht angegeben werden müssen (wir brauchen nur eine Obere Schranke), die Daten, die sich hat angegeben werden.

    Beachten Sie, dass wir haben bisher nur darüber gesprochen, die Methode Analyse; haben wir nicht genau festgelegt, welche Menge wir analysieren (Zeit-Komplexität? Speicherplatz-Komplexität?), und weder haben wir festgelegt, welche Metrik wir sind interessiert an (worst case? im besten Fall? Durchschnittliche?).

    In der Praxis der Begriff asymptotische Analyse Häufig bezieht sich auf Obere Schranke Zeit Komplexität eines Algorithmus, d.h. die worst-case performance, gemessen durch die "total running time", die, vertreten durch die big-Oh notation (z.B. ein Sortieralgorithmus sein könnten O(nlogn)).

    Amortisierten Analyse

    Dieser Begriff bezieht sich auf die Analyse des Algorithmus die Leistung basiert auf einer spezifischen Sequenz von Operationen, die Ziele der worst-case-Szenario --, amortized analysis bedeutet, dass die Metrik schlimmsten Fall die Leistung (obwohl es noch nicht sagen, die Menge gemessen wird). Um diese Analyse durchzuführen, müssen wir angeben, die Größe der Eingang, aber wir müssen Sie nicht machen keine Annahmen über die form.

    In juristischer Hinsicht, amortized analysis, ist die Kommissionierung eine beliebige Größe für den Eingang und dann auf "spielen" der Algorithmus. Wann immer eine Entscheidung, die davon abhängt, die Eingabe muss gemacht werden, das Schlimmste Weg ist taken1. Nachdem der Algorithmus ausgeführt wurde, nach Abschluss teilen wir die berechnete Komplexität durch die Größe der Eingabe bis zum fertigen Produkt führen.

    1note: um genau Zu sein, ist der schlechteste Weg dass ist theoretisch möglich. Wenn Sie einen Vektor an, der dynamisch verdoppelt in der Größe jedes mal, wenn seine Kapazität erschöpft ist, der "worst case" bedeutet nicht, davon auszugehen, dass Sie müssen doppelklicken Sie auf jeder einsetzen, da die Einschübe sind so verarbeitet, als eine Sequenz. Wir dürfen (und müssen) verwenden Sie den bekannten Zustand mathematisch zu eliminieren, da viele "noch schlimmere" Fälle, wie wir können, auch während der Eingabe bleibt unbekannt.

    Der wichtigste Unterschied

    Den entscheidenden Unterschied zwischen asymptotischen und amortisierten Analyse ist, dass die erstere ist abhängig von der Eingabe selbst, während die letztere ist abhängig von der Reihenfolge der Operationen, die der Algorithmus ausführen soll.

    Daher:

    • asymptotische Analyse erlaubt uns zu behaupten, dass die Komplexität des Algorithmus wenn es über eine best/worst/average case-Eingaben der Größe N nähert sich begrenzt ist durch eine Funktion F(N) --, wobei N eine variable ist, die
    • amortisierten Analyse erlaubt uns zu behaupten, dass die Komplexität des Algorithmus wenn es gegeben ist, einen Eingang von unbekannten Eigenschaften, aber bekannter Größe N ist nicht schlechter als der Wert einer Funktion F(N) --, wobei N eine bekannten Wert

    InformationsquelleAutor der Antwort Jon

  4. 10

    Die Antwort ist kurz und bündig definiert der erste Satz der Fortgeführten Analyse Kapitel in dem Buch - Einführung in Algorithmen:

    In einem amortisierten Analysedie Zeit, die erforderlich ist zum durchführen einer Sequenz von
    Daten-Struktur-Operationen gemittelt wird über alle Vorgänge
    durchgeführt.

    Vertreten wir die Komplexität eines Programms Wachstum durch Asymptotische Analyse - die bounding-das Programm ist das Wachstum durch eine Funktion und die Definition der worst -, best-oder durchschnittlichen Fall.

    Aber das kann irreführend sein, in Fällen, in denen es nur einen einzigen Fall, wo das Programm die Komplexität einen Spitzenwert erreicht, aber im Allgemeinen, das Programm braucht nicht viel Rechenleistung.

    Daher macht es mehr Sinn, den Durchschnitt der Kosten über eine Sequenz von Operationen, obwohl eine einzelne operation kann teuer sein. Dies ist Amortisierten Analyse!

    Amortisierten Analyse ist, eine Alternative zu Asymptotische Verfahren zum berechnen der Komplexität. Es hilft uns die Berechnung einer mehr wahre Komplexität in Bezug auf die Praktikabilität, so zu vergleichen und zu entscheiden, zwischen zwei oder mehreren algorithmen.

    InformationsquelleAutor der Antwort Kunal Vyas

  5. 5

    Die beste Referenz, die ich bisher gefunden habe, für das Verständnis der amortisierten Analyse von algorithmen, ist in dem Buch Einführung in Algorithmenthird edition, Kapitel 17: "Amortisierten Analyse". Es ist alles da, erklärt viel besser als das, was gefunden werden kann, die in einem Stack-Überlauf-post. Sie finden das Buch in der Bibliothek von jedem anständigen Universität.

    InformationsquelleAutor der Antwort Óscar López

  6. 2

    Reguläre asymptotische Analyse beschäftigt sich mit der performance einer einzelnen operation asymptotisch, als eine Funktion der Größe des Problems. Die O () - notation ist, was zeigt eine asymptotische Analyse.

    Amortisierten Analyse (die auch eine asymptotische analysis) sieht die insgesamt Leistung von mehreren Operationen auf einer gemeinsamen datastructure.

    Der Unterschied ist, amortized analysis in der Regel beweist, dass der insgesamt erforderliche Berechnung für M Operationen eine höhere performance gewährleisten als M-mal den schlimmsten Fall für den einzelnen Betrieb.

    Z.B. eine einzelne operation auf einem splay-Baum der Größe N bis zu O(N) Zeit. Jedoch, eine Sequenz von M Operationen auf einem Baum der Größe N ist begrenzt durch O( M(1+log N) + N log N ) Zeit, die in etwa O(log N) pro operation. Beachten Sie jedoch, dass einer amortisierten Analyse ist viel strenger als ein "average-case" - Analyse: es beweist, dass mögliche Folge von Operationen erfüllen Ihre asymptotische worst-case.

    InformationsquelleAutor der Antwort comingstorm

  7. 1

    Amortisierten Analyse befasst sich mit den Gesamtkosten über eine Reihe von Auflagen von der routine und den Vorteilen, die gewonnen werden können dort. Zum Beispiel die Suche nach einem unsortierten array der n Elemente, die für ein einzelnes Spiel kann bis zu n Vergleiche und damit ist o(n) Komplexität. Jedoch, wenn wir wissen, den gleichen array wird gesucht werden m Elemente, wiederholen Sie die gesamte Aufgabe wäre dann die Komplexität O(m*n). Allerdings, wenn wir Sortieren das array im Voraus, die Kosten O(n log(n)), und die aufeinanderfolgenden Suche nur O(log(n)) für ein sortiertes array. So beliefen sich die fortgeführten Anschaffungskosten für m Elemente mit der Einnahme dieses Ansatzes ist O(n*log(n) + m*log(n)). Wenn m >= n, entspricht dies O(n log(n)) durch die vor-Sortierung im Vergleich zu O(n^2) für nicht Sortieren. Damit die amortisierten Kosten ist billiger.

    Einfach ausgedrückt, indem die Ausgaben ein wenig extra früh auf, wir können eine Menge sparen später.

    InformationsquelleAutor der Antwort Shane MacLaughlin

Schreibe einen Kommentar