Einfach "der maximale Wert in array" und Komplexität von Berechnungen

Ich bin ziemlich neu auf dieses Zeug und ich brauche deine Hilfe.

Ich sollte den Aufbau einer effizienten einfache Algorithmus gibt den maximalen Wert in einem array mit Größe n enthält die zahlen 1,2,...n mit Wiederholungen.

Dann habe ich bestimmt die beste Laufzeit, die Durchschnittliche Laufzeit und die schlechteste Laufzeit.

Also ich habe zwei Fragen:

  1. Zunächst bin ich versucht zu verstehen, was ist die Idee, dass eine effiziente Lösung für diese einfachen Algorithmus. Soweit ich das verstanden habe, sollte ich nur eine einfache Schleife von 1 bis n und suchen nach dem maximalen Wert. Ist die "effizienteste" Algorithmus weist darauf hin, dass, Wenn ich den Wert von n in dem array kann ich aufhören zu suchen, mehr Werte, denn dies ist der höchste Wert im array?

  2. Wie Ermittle ich die beste Laufzeit und die Durchschnittliche Laufzeit mit der Tatsache, während in die Berechnung der durchschnittlichen Laufzeit, dass Es eine gleichmäßige Verteilung.
    Das heißt, jede Zelle im array hat eine chance von 1/n der maximale Wert.

Vielen Dank im Voraus!

  • Klingt wie Hausaufgaben... was haben Sie kommen mit so weit? Hinweis: sortierte arrays O(1) Laufzeit, um die max - /min-Werte.
  • Aber die Bestimmung der array sortiert O(n) 😐
  • so einfach ziehen Sie die max/min-Werte auf beliebige array.
  • das array ist nicht sortiert. Ich bin nicht die eine Lösung, aber eine Erklärung für die konkrete Antwort. Als für das, was ich kam so weit, ich schrieb in meiner Frage.
  • wahrscheinlich mit #1 ist, dass man NICHT wissen KANN, was die max/min-Werte im array sind, bis Sie haben gescannt, das gesamte array, oder im Voraus wissen, dass das array vorsortiert. z.B. für beliebige "weiß nicht, ob sortierten arrays", es ist eine O(n) - operation zu bekommen, dass die max/min-Wert gesetzt.
  • Ja, natürlich, Es ist O(n). aber die Tatsache, es sind nur zahlen zwischen 1..n ermöglicht es mir, dass der Algorithmus ein wenig effizienter, indem Sie aufhören zu suchen, in Fall fand ich den Wert n ein. richtig?
  • "Der maximale Wert in einem array mit Größe n enthält die zahlen 1,2,...n mit Wiederholungen" ist offensichtlich n, nicht wahr?
  • Es enthält zahlen zwischen 1...n (nicht alle). Auch die Tatsache, dass es sein könnte, Wiederholungen impliziert nicht alle zahlen immer zeigen.

InformationsquelleAutor SyndicatorBBB | 2012-10-31
  1. 7

    Besten Fall - das finden der max-element als das erste (O(1)), worst-case - es ist das Letzte element überprüft (O(n)).

    Der schwierige Teil ist der Durchschnitt der Fall ist.

    Finden Sie die durchschnittlichen Fall - wir müssen die erwartet Anzahl der Iterationen!

    Da kann man aufhören, nachdem Sie finden das maximum, das wir teilen das problem in zwei Teile:

    1. [0,n-1): Da im Durchschnitt (unter der Annahme gleichmäßige unabhängigen Verteilung für jedes element) - Anzahl n hat Wahrscheinlichkeit 1/n in jedem Ort, dann ist die erwartete Anzahl der Iterationen, die für diesen Teil ist 1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n 1

      Die obige Formel ergibt sich eine hässliche Formel, die O(n)
    2. Das Letzte element wird überprüft, ob sich die ersten n-1 Elemente nicht enthalten der Wert n: so müssen Sie zu den oben genannten n* ((n-1)/n)^(n-1), die O(n) sowie (lim unendlich ist 1/e * n).

    Diese Summen in O(n) Durchschnittliche Zeit, die Lösung.

    (1): Die Formel für jedes element ist j*((n-1)/n)^(j-1) * (1/n) weil:

    • j - für die Anzahl der Elemente zu überprüfen (Anzahl der Iterationen)
    • ((n-1)/n)^(j-1) - Die Wahrscheinlichkeit, dass es keine n im vorherigen Elemente
    • (1/n) - Wahrscheinlichkeit, diese Zahl ist n.
    • Wow @amit ich habe keine Worte. So schön zu setzen. Wirklich zu schätzen dies.
    • Die "Duplikate" etwas sagt, dass es nicht eine zufällige permutation. Nur n zufällige ganze zahlen im Bereich von 1..n.
    • Der Begriff permutation falsch war, aber beachten Sie, dass die caclulation nicht davon ausgehen permutation - es wird angenommen, gleichmäßige Verteilung für jedes element - so (jedes element) hat 1/n chance, die max, und (n-1)/n nicht, um es zu sein. Ich werde die richtige Terminologie. Vielen Dank für Ihren Kommentar.
    • Warum ist das im besten Fall O(1)? Sie können nicht sicher sein, dass jede ein element in einem array ist der max, ohne zu wissen, was im rest des Arrays...
    • Beachten Sie, dass die Frage besagt, dass der array contains the numbers 1,2,...n with repetitions. Der beste Fall ist eigentlich: Lesen Sie das erste element, es ist n, und gibt es zurück. Das ist O(1).
    InformationsquelleAutor amit
  2. 2

    Der Algorithmus funktioniert wie folgt: zunächst wählen Sie eine Nummer (in diesem Fall wähle ich die erste Zahl des Arrays und so tun, es ist das max, dann Vergleiche ich es mit der nächsten Nummer und wenn es größer ist nehme ich, dass als der neue max, bis ich fertig bin mit der Suche im array), wird der nächste code ist in C:

    #include <stdio.h>
#define SIZE 100

typedef struct{
    int val;
    int loc;
} find;

/* Functions declaration (Prototype) */
find maxFinder( int * const a );

int main( void )
{
    int response[ SIZE ]=
       { 1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100 };

    printf( "The max number is %d located in the index %d.\n", maxFinder( response ).val, maxFinder( response ).loc );
    return 0;
}

 find maxFinder( int * const a )
 {
    /* Local Variables initialization & declaration */
    int i;
    find result;

    result.loc = 0;
    result.val = *( a + 0 );

    for( i = 1; i < SIZE; i++ ){
        if ( result.val < *( a + i ) ){
            result.loc = i;
            result.val = *( a + i );
        }
    }
    return result;
 }
    • Sollten Sie nicht verwenden die Tatsache, dass die zahlen zwischen 1... GRÖßE?
    • GRÖßE ist ein konstanter Wert ist, dass müssen Sie erklären, in meinem Fall sind es 100.
    • In diesem Fall SIZE = n, und Ihre Werte sind zwischen 1...n. Dies ist nicht ein allgemeiner Fall, als Sie gezeigt haben.
    • Es ist der Allgemeine Fall, nur ändern, GRÖßE, wie Sie möchten, und es Durchsuchungen von 0 (das erste element des Arrays, bis der array-Oberflächen (n-1)
    • Danke @Alberto
    • Bonsanto: Kannst du die code in Javascript / PHP! bitte

    InformationsquelleAutor Alberto Bonsanto
  3. 2

    Wenn es keine Vorherige information über die array - (es ist z.B. sortiert), dann gibt es auch keine worst-case oder best-case, und Sie müssen scan alle Elemente, um herauszufinden, die Max, und es dauert O(n) Zeit.

    Auch die Kenntnis der Wahrscheinlichkeitsverteilung der erste max-Wert für jede Zelle ist nutzlos, im Allgemeinen (es sei denn, es verringert Ihre Suche Raum. z.B., Wenn Sie wissen, dass nur Konstante Anzahl von Zellen nicht-null-Wahrscheinlichkeit, das max-Wert, dann brauchen Sie nur zu suchen, die Zellen und es dauert Konstante Zeit). So, in der Regel

    Best-case-Laufzeit = Worst-case-Laufzeit = Durchschnittliche Laufzeit = O(n)

    InformationsquelleAutor nmoses
  4. 1

    Die schlechtesten und die besten Fälle sind einfach. Der Durchschnittliche Fall ist interessanter. Blick auf die Wikipedia-Seite für Die Geometrische Verteilung.

    • Im besten Fall - in Fall ist es das erste element : O(1) und worst-case : O(n) , ist das richtig?
    • Basierend auf Ihre Kommentare, die Sie scheinen, wie Sie sind selbstbewusst und verstehen Sie die Idee. Gehen Sie mit Ihrem Instinkt 🙂
    • Danke @japreiss
    InformationsquelleAutor japreiss
Schreibe einen Kommentar