馬爾可夫矩陣的 JavaScript 程式

---

矩陣是一種二維陣列，它以一定數量的行組成，並且每行都有相同數量的列，透過行號和列號，我們可以獲取任何特定索引處的元素。對於馬爾可夫矩陣，每一行的和必須等於 1。我們將實現一個程式碼來建立一個新的馬爾可夫矩陣，並判斷當前給定的矩陣是否為馬爾可夫矩陣。

問題介紹

在給定的問題中，我們必須編寫一個程式碼，使用二進位制資料（即僅使用 0 和 1）生成馬爾可夫矩陣，因為我們知道馬爾可夫矩陣是一個矩陣，其中每一行的和必須等於 1（這並不意味著它只包含二進位制數字），這意味著每一行將只有一個 1，其他元素為 0。

我們將實現的程式只是馬爾可夫矩陣的一種特殊情況。

對於第二個程式碼，我們將得到一個矩陣，並必須找到當前矩陣是否為馬爾可夫矩陣。讓我們看看這兩個程式碼 -

建立馬爾可夫矩陣

在當前部分，我們使用二進位制數字（0 和 1）來建立馬爾可夫矩陣。讓我們先看看方法，然後我們將轉向程式碼實現 -

方法

在此程式碼中，我們將使用 new 關鍵字和 Array 建立一個矩陣。對於陣列的每個索引，我們將再次建立一個數組來填充它。

對於矩陣的每一行，使用隨機函式，我們將獲得列數範圍內的隨機數，並將當前行的該列填充為 1，其他元素填充為 0。

最後，我們將返回矩陣。

示例

// creating a Markov's Matrix using binary digits
// defining the rows and columns
var row = 4
var col = 5
function MarkovMat(row, col){

   // creating an array of size row
   var arr = new Array(row);

   // traversing over the created array
   for(var i = 0; i < row; i++){

      // creating an array of size column
      var brr = new Array(col);
      brr.fill(0) // making every element zero of current array

      // generating random number
      var k = Math.floor(Math.random()*5);

      // marking kth index as 1
      brr[k] = 1

      // adding columns to the current row
      arr[i] = brr;
   }

   // printing the values
   console.log(arr)
}

// calling the function
MarkovMat(row,col)

時間和空間複雜度

在上面的程式碼中，我們遍歷了整個矩陣，並且每次遍歷時都獲取了隨機數，這需要常數時間。因此，上面程式碼的時間複雜度為 O(N*M)，其中 N 是行數，M 是列數。

空間複雜度僅等於矩陣的大小，並且我們沒有使用任何額外的空間。因此，上面程式碼的空間複雜度為 O(N*M)。

檢查當前矩陣是否為馬爾可夫矩陣

在當前部分，我們得到一個矩陣，並必須找到當前矩陣是否為馬爾可夫矩陣。讓我們先看看方法，然後我們將轉向程式碼實現 -

方法

在此程式碼中，我們將簡單地遍歷矩陣，併為每一行獲取其計數。如果當前行的計數為 1，則我們移動到下一行，否則我們將返回當前矩陣不是馬爾可夫矩陣。

示例

// function to check whether the current matrix is
// markov or not
function isMarkov(mat){
   var rows = mat.length
   var col = mat[0].length;

   // checking the sum of each row
   for(var i = 0; i < rows;i++){
      var count = 0;
      for(var j =0; j<col; j++) {
         count += mat[i][j];
      }
      if(count != 1){
         console.log("The given matrix is not Markov's Matrix");
         return
      }
   }
   console.log("The given matrix is Markov's Matrix");
}

// defining the matrix1
matrix1 = [[0.5, 0, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix1: ")
isMarkov(matrix1)

// defining the matrix2
matrix2 = [[0.5, 1, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix2: ")
isMarkov(matrix2)

時間和空間複雜度

在上面的程式碼中，我們遍歷了矩陣並存儲了每一列的總和，使上面程式碼的時間複雜度為 O(N*M)。

我們在上面的程式碼中沒有使用任何額外的空間，使空間複雜度為 O(1)。

結論

在本教程中，我們實現了馬爾可夫矩陣的 JavaScript 程式。對於馬爾可夫矩陣，每一行的和必須等於 1。我們已經實現了一個程式碼，使用隨機數生成函式以 O(N*M) 的時間複雜度和相同空間生成二進位制馬爾可夫矩陣。此外，我們還實現了一個程式碼，該程式碼將檢查當前矩陣是否為馬爾可夫矩陣，時間複雜度為 O(N*M)。