JavaScript-Programm zur Überprüfung, ob die Matrix eine obere Dreiecksform hat

Eine obere Dreiecksmatrix ist eine quadratische Matrix mit der gleichen Anzahl an Zeilen und Spalten und allen Elementen unterhalb der Hauptdiagonale von der ersten Zelle (in der oberen linken Ecke) bis zur letzten Zelle (in der oberen Ecke). linke Ecke) untere rechte Ecke) ist Null. Das obere Dreieck bedeutet, dass die im unteren Dreieck vorhandenen Elemente Null sind. Wir werden einen geeigneten Code implementieren und die zeitlichen und räumlichen Komplexitäten werden erklärt und diskutiert.

Beispiel

Input1:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
Output1: Yes,

Erklärung: Wir können sehen, dass die Hauptdiagonale die Elemente 1, 5, 8 und 1 enthält und alle Zellen unterhalb der Hauptdiagonale den Wert Null haben.

Input2:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
]
Output1: No

Erklärung: Wir können sehen, dass die Hauptdiagonale die Elemente 1, 5, 8 und 1 enthält und alle Zellen unterhalb der Hauptdiagonale Werte ungleich Null haben, da die zweite Spalte der letzten Zeile Werte ungleich Null enthält.

Methode

Wir haben das obige Beispiel gesehen. Schauen wir uns nun die Schritte zur Implementierung des Codes an:

Zuerst erstellen wir eine Funktion, in der wir die angegebene Matrix übergeben. Wir werden nur den unteren Teil der Hauptdiagonale der Matrix durchlaufen, d. h. jede Zelle (i,j), in der j kleiner als i ist. Wenn wir eine Zelle mit einem Wert ungleich Null finden, geben wir „false“ zurück, andernfalls geben wir letztendlich „true“ zurück.

Beispiel

// function to traverse over the matrix
function check(mat){

   // getting total number of rows of matrix
   var rows = mat.length
   
   // traversing over the section present above the main diagonal
   for(var i = 0; i < rows; i++){
      for(var j = 0; j < i; j++){
         if(mat[i][j] != 0){
            return false;
         }
      }
   }
   return true;
}

// defining the matrix
var mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

// updating matrix
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
      ]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

Ausgabe

The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 0, 0, 1 ] ]
The given matrix is an upper triangular matrix
The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 1, 0, 1 ] ]
The given matrix is not an upper triangular matrix

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Anzahl der Zeilen der gegebenen Matrix ist. Dies liegt daran, dass wir die Matrix nur einmal durchlaufen.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um zu überprüfen, ob eine bestimmte Matrix eine obere Dreiecksmatrix ist. Das obere Dreieck bedeutet, dass die im unteren Dreieck vorhandenen Elemente Null sind. Wir iterieren über die Zellen in der Matrix, bei denen die Anzahl der Spalten kleiner als die Anzahl der Zeilen ist, mit einer zeitlichen Komplexität von O(N*N) und einer räumlichen Komplexität von O(1).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zur Überprüfung, ob die Matrix eine obere Dreiecksform hat. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!