Wie Zeitkomplexität in der großen O-Notation für folgende Array-Doppel-Lookup

berechnen Was wird Zeit Komplexität des folgenden Algorithmus sein? Kann jemand helfenWie Zeitkomplexität in der großen O-Notation für folgende Array-Doppel-Lookup

public class Util 
{ 

    public static int GetDistance(int[] array) 
    { 
     //Find the max seperation of two same numbers inside an array for example 
     // {1,2,4,1,5,9,0,4,15,1,2} should return 9 (position of '1' at 9th and 0th location) 

     int N = array.Length; 
     int maxDistance=0; 
     for (int i = 0; i < N; i++) 
     { 
      for (int j = (N-1); j > i; j--) 
      { 
       if (array[j]==array[i]) 
        if(maxDistance < (j-i)) 
         maxDistance = j- i; 
      }//End of inner for 

     }//End of for 
     System.Console.WriteLine("maxDistance " + maxDistance); 
     return maxDistance ; 
    } //End of Function 

} //End of Class

Quelle

2016-07-25 Ash

Sie betrachten die innere Schleife (die Operation innerhalb der inneren Schleife nehmen konstante Zeit). Die innere Schleife wird exakt N-1-i mal ausgeführt.

Dann wird die äußere Schleife genau N mal ausgeführt, mit steigenden Werten von i. Die Gesamtarbeitslast umfasst

Ausführungen des inneren Körpers. Diese Summe ist eine Dreieckszahl, und es ist keine große Sache, zu zeigen, dass es

(N-1).N/2

Dies entspricht O (N²).

Quelle

2016-07-25 09:46:16

es, dass die Zeit Komplexität Darstellung von O bedeutet (N²) ist gleich wie O ((N²-N)/2) & delta; Dann – Ash

Natürlich. Für große N ist N im Vergleich zu N² vernachlässigbar. –

Sie haben zwei for-Schleifen, die N-mal iterieren (die zweite ist auch Auswirkung durch die Zahl N, dh N größer, die Iterationszahl größer).

Innerhalb der Schleife ist die Operation O (1) Sie also total haben O (1) * O (N^2) = O (N^2)

Quelle

2016-07-25 15:34:11 yfeng

Bedeutet dies, dass die Darstellung der Zeitkomplexität von O (N²) dieselbe ist wie für O ((N²-N)/2)? Dies bedeutet, dass Big-O-Notation ist kein guter Vergleichsparameter als die folgenden Schleifen hat auch die gleiche Zeit Komplexität, aber 50% mehr Zyklus – Ash

Big-O ist ein guter Vergleich für was ist es, dh die allgemeine Leistung des Algorithmus , besonders gegenüber großen N. Wenn Sie über die reale Welt Leistung von etwas Code nachdenken, müssen Sie ** Profil ** es. Es kann leicht Fälle geben, in denen O (N^2) O (N) übertrifft, wenn die Eingabe N nicht groß genug für die echten Eingabedaten ist und wenn die Komplexität dieses O (N) -Codes weit über dem Preis von N^liegt 2 im ersten Code. Zum Beispiel, wenn Sie nur etwa 1e6 von ganzen Zahlen verwenden, mit zufälligen Einfügen und Entfernen in C++, ist 'Vektor ' schneller (O (N^2)) als doppelt verkettete Liste (O (N)) (wegen Cache-Misses) . – Ped7g

die innere Schleife iteriert nicht N-mal jedes Mal –

Wie Zeitkomplexität in der großen O-Notation für folgende Array-Doppel-Lookup

Antwort

Verwandte Themen