Was wäre die zeitliche Komplexität des folgenden Algorithmus?

Question

class AllSubMatrices { 

    int a[][] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, 
      { 21, 22, 23, 24, 25 } }; 

    AllSubMatrices() { 
    } 

    int printSum(int r, int c, int len) { 

     int sum = 0; 

     for (int i = r; i < (r + len); i++) { 
      for (int j = c; j < (c + len); j++) { 
       sum = sum + a[i][j]; 
      } 
     } 

     return sum; 
    } 

    public void allSubMatrices() { 
     for (int l = 1; l <= a[0].length; l++) { 
      for (int i = 0; i <= (a[0].length - l); i++) { 
       for (int j = 0; j <= (a.length - l); j++) { 
        System.out.println(printSum(i, j, l)); 
       } 
      } 
     } 
    } 
} 

Was wäre die zeitliche Komplexität aller SubMatrices? Das Buch, das ich beziehe (Cracking das Coding-Interview) erwähnt o (n^4). Aber das überzeugt mich nicht, da alle Schleifen nicht N-mal laufen, sondern von 1 bis N variabel sind. Ich denke, es sollte o (n^2) sein.

Answer 1

Ich denke, es ist sogar O (n^5). Ich habe keinen genauen Beweis, aber eine Illustration. Wenn Sie nur die Schritte der Schleifen zählen erhalten Sie:

sum(1 <= l <= n){sum(1 <= i <= n - l){sum(1 <= j <= n - l){ j^2 }}} 

Die drei Summen eine dreieckige Figur beschreiben, die durch einen Würfel geschnitten (tetraeder) entsteht. Das Volumen dieser Figur wächst wie O ( n^3) mit der Summe der Quadrate der vollständige Formel wächst wie O (n^5).

Answer 2

Wenn hier n = width = height ist, dann kann es nicht O (n^2) sein, denn wenn wir alle externen Schleifen nur in allen Submatrizen verwenden, sind sie bereits O (n^3). Die zwei inneren Schleifen in printSum sind interessanter, sie sind im Grunde l^2 Operationen, wobei l die Variable der äußersten Schleife ist, die von 1 bis n zählt. Wenn wir nur eine äußere Schleife plus den printSum - Aufruf zählen, ist die Anzahl der Operationen eine Summe aller Quadrate von n Zahlen, die n^3/3 + n^2/2 + n/6 ist, dh O (n^3). Wenn wir zwei weitere Schleifen hinzufügen, wird es O (n^5) sein.

Answer 3

printSum(_, _, len) tut len^2 Ergänzungen sum

Dann werden die Breite und die Höhe der Anordnung unter der Annahme gleich, und den Aufruf der Breite/Höhe des Arrays n, die Gesamtkomplexität ist:

sum(sum(sum(l^2 for j=0..n-l) for i=0..n-l) for l=1..n). 
= sum((n-l+1)^2 * l^2 for l=1..n). 

Wolfram Alpha Verwendung zu vereinfachen gibt:

1/30 * n * (n + 1) * (n^3 + 4n^2 + 6n + 4) 

Das ist O (n^5).

Übrigens hat der Code in der Frage ein Problem. Es sieht so aus, als wäre es geschrieben, um nicht-quadratische Matrizen zu unterstützen (und tatsächlich ist die Beispielmatrix 4x5). Aber der Code funktioniert nicht richtig, wenn die Breite kleiner als die Höhe ist, da l nur 1 bis a[0].length reicht. Korrekt wäre ein Bereich zwischen 1 und max(a[0].length, a.length). Wenn Sie den Inhalt des Buchs korrekt darstellen, sind das zwei Fehler im selben Problem.