Vergleich aller array-Elemente - C-Algorithmus

Ich habe eine matrix m * n und für jede Zeile, die ich brauche, um zu vergleichen, alle Elemente unter Ihnen.
Für jedes paar, die ich finde, werde ich eine Funktion aufrufen, die gehen, um einige Berechnungen auszuführen.

Beispiel:

my_array -> {1, 2, 3, 4, 5, ...}

I take 1 and I have: (1,2)(1,3)(1,4)(1,5)
I take 2 and I have: (2,1)(2,3)(2,4)(2,5)
and so on

Mit C schrieb ich dies:

for (i=0; i<array_length; i++) {
    for (k=0; k<array_length; k++) {
        if (i==k) continue;

           //Do something
        }
    }
}

Ich Frage mich, ob ich verwenden kann, ein Algorithmus mit geringerer Komplexität.

  • Ohne Kenntnis der konkreten Berechnungen, die Sie tun, es gibt keine Möglichkeit zu sagen, was optimiert werden kann.
  • So haben Sie wirklich eine matrix, oder sind Sie nur reden über Permutationen von kleinen natürlichen zahlen?
  • Es gibt n^2 Paare, so dass Sie nicht tun können besser als n^2...
InformationsquelleAutor user2219580 | 2013-03-28
  1. 5

    Nein, es ist O(n^2) durch die definition [ zu lange um hier zu erklären, aber glauben Sie mir (-: ]

    Aber Sie können verringern die Anzahl der Iterationen von der Hälfte :

    for (i=0; i<array_length; i++) {
    for (k=i+1; k<array_length; k++) { //<-- no need to check the values before "i"
           //Do something
           //If the order of i and k make a different then here you should:
           //'Do something' for (i,k) and 'Do something' for (k,i)
        }
    }
}
    • Ihre Reduktion wird davon ausgegangen, dass x Betrieb y ist das gleiche wie y operation x, in anderen Worten, die operation ist kommutativ. Wenn es nicht können Sie nicht reduzieren, wie es das.
    • Yep, kann ich nicht verwenden, weil es nicht kommutativ
    • Ich füge die Bemerkung in der "Etwas Tun". Sie können in den internen code zu tun (x,y) and (y,x) in der gleichen iteration.
    • dann sind Sie genau das gleiche tun, wird die for-Schleife selbst ist nicht das problem, die Bedienung ist
    • Das stimmt, aber die Frage nicht erklären, dass vor...
    • auch wenn du gehst, um k aus i+1 Sie können die drop -if.
    • Wieder, ich ' m nur raten, die Bedeutung hier. so zum beibehalten des ursprünglichen Verhaltens im Falle das gleiche element ist die Wiederholung mehr als einmal im array.
    • wiederholte Elemente sind keine Auswirkungen auf das Problem. i und k sind Indizes, die if wird nie wahr sein.

    InformationsquelleAutor Roee Gavirel
  2. 3

    Gibt es mehrere Dinge, die Sie tun könnten, aber die sind moeglich ist und was nicht hängt von der array Natur und die Formel, die Sie anwenden. Komplexität wird wahrscheinlich unverändert bleiben oder sogar wachsen, auch wenn die Berechnung gemacht werden kann schneller gehen, es sei denn, die Formel hat eine komplexe Abhängigkeit auf seine Argumente, in dem Fall zu einer Abnahme in der Komplexität kann erreichbar sein.

    Auch von AO(N^a) BO(N^b) mit b > ein (höhere Komplexität) noch Wert, verfolgt zu werden, für einige Reihe von N, wenn B hinreichend kleiner als A.

    In keiner bestimmten Reihenfolge:

    • wenn die matrix hat mehrere wiederholte Elemente, es kann sein, bequem zu verwenden eine caching-Funktion:

      Ergebnis function(arg1, arg2) {
      int i = index(arg1, arg2); //in Abhängigkeit der Werte, die es werden könnten
      //so etwas wie arg1*(MAX_ARG2+1) + arg2;
      if (!gespeichert[i]) { //gespeichert und die Werte sind reserviert und initialisiert
      //irgendwo anders - oder in diese Funktion mit ein
      //static-flag.
      gespeichert[i] = 1;
      Werte[i] = true_function(arg1, arg2);
      }
      return Werte[i];
      }

      Dann haben Sie einen Speicher-overhead proportional zur Anzahl der verschiedenen Paare
      von Werten zur Verfügung. Der Aufruf-overhead O(|arg1|*|arg2|), aber in manchen Situationen
      (z.B. true_function() ist teuer) die Einsparungen mehr als kompensieren die zusätzliche Komplexität.

      • hacken Sie die Formel in Stücke (nicht möglich für jeder Formel) und Ausdrücken, wie:

        F(x,y) = G(x) op-H(y) op J(x,y)

      dann kann man O(max(M,N)) Zyklus pre-Berechnung der G[] und H[]. Das hat auch O(M+N) Speicher Kosten. Es ist nur bequem, wenn die rechnerische Ausgaben Unterschied zwischen F und J ist signifikant. Oder Sie tun könnte:

      for (i in 0..N) {
    g = G(array[i]);
    for (j in 0..N) {
        if (i != j) {
            result = f(array[i], array[j], g);
        }
    }
}

      bringt einige der Komplexität von O(N^2) auf O(N).

      • den ersten beiden Techniken sind nutzbar, im tandem, wenn G() und H() sind praktisch cache (begrenzte Reichweite der Argumentation, teuer-Funktion).

      • finden Sie ein "Recht" zu verknüpfen F(a, b) mit F(a+c, b+d). Dann führen Sie den caching-Algorithmus wesentlich effizienter zu gestalten, und dabei die gleichen Berechnungen. Diese Verschiebungen einiger Komplexität von O(N^2) auf O(N) oder auch O(log N), so dass während der gesamten Kosten ist immer noch quadratisch, es wächst viel langsamer, und eine höhere Schranke für N praktisch wird. Wenn F sich einer höheren Ordnung der Komplexität als Konstante in (a,b), dies kann auch reduzieren Sie diese, um (als ein extremes Beispiel: angenommen, F ist iterativ in a und/oder b).

    InformationsquelleAutor LSerni
  3. 2

    Nein, Sie bekommen nur geringer Rechenaufwand, wenn Sie Kenntnis von dem Inhalt des Arrays, und die Semantik der operation zu optimieren Ihren Algorithmus.

    • Denn OP hat zum vergleichen jedes element mit anderen und es gibt mXn Elemente und damit mXn Vergleiche, es ist keine Frage der Verbesserung der Komplexität.
    • hängt davon ab, was das eigentliche Ziel der Funktion ist, möglicherweise sind nicht alle Vergleiche notwendig sind.
    • Es ist eine Feste mathematische Formel (tut mir Leid, aber ich kann nicht die Inhalte veröffentlichen...). Ich Speichere in der matrix Werte von 0 bis 250 oder einen char von A-C.
    • Dann können wir Ihnen helfen.
    InformationsquelleAutor wich
Schreibe einen Kommentar