JavaScript Markov矩阵的程序
矩阵是一种2D数组,它由一些行组成,对于每一行,列的数量相同,通过行号和列号,可以获取到任何特定索引的元素。对于Markov矩阵来说,每一行的和必须等于1。我们将实现一个代码来创建一个新的Markov矩阵,并判断当前给定的矩阵是否是一个Markov矩阵。
问题介绍
在给定的问题中,我们需要编写一段代码,通过使用二进制数据(只使用0和1)生成Markov矩阵。我们知道Markov矩阵是一种行的和等于1的矩阵(这并不意味着它只由二进制数组成),也就是说每一行只有一个1,其他元素都是0。
我们将实现的程序只是Markov矩阵的特定情况。
对于第二段代码,我们将给定一个矩阵,需要判断当前矩阵是否是Markov矩阵。让我们看看这两段代码 –
创建Markov矩阵
在当前部分,我们使用二进制数据0和1来创建Markov矩阵。让我们首先了解一下方法,然后再进行代码实现 –
方法
在这段代码中,我们将使用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)
。