在矩阵中求数字序列的复杂性

方法和示例贯穿

如果我们创建第二个网格,在其中存储可以从每个单元格向上执行的步骤的数量,我们就可以更有效地完成这项工作。让我们用这个例子:

3 1 2 5               - - - -
4 2 5 6               - - - -
5 3 4 7               - - - -
6 7 5 4               - - - -

我们从第一个单元格(左上角3)开始,检查它是否有值为4的邻居,如果有,我们移动到该单元格并查找值为5的邻居,依此类推;我们会陷入值为7的单元格。我们用1标记最后一个位置,然后向后走,标记单元格2、3、4和5:

3 1 2 5    x - - -    5 - - -
4 2 5 6    x - - -    4 - - -
5 3 4 7    x - - -    3 - - -
6 7 5 4    x x - -    2 1 - -

我们现在知道左上角的单元格是5步向上序列的开始。然后我们切换到下一个未标记的单元格,即3右侧的1;它有两个相邻的单元格,值为2;我们首先向右移动,然后在2处卡住。我们将该单元格标记为1,并返回起始点,临时标记为2。

3 1 2 5    - x x -    5 2 1 -
4 2 5 6    - - - -    4 - - -
5 3 4 7    - - - -    3 - - -
6 7 5 4    - - - -    2 1 - -

现在,我们从起点沿着第二条路径,向下到2和3,然后向右到4,然后有两个相邻的5;我们尝试先向下5,然后卡在该单元格上;我们将其标记为1,然后返回到4,并临时标记为2:

3 1 2 5    - x - -    5 2 1 -
4 2 5 6    - x - -    4 - - -
5 3 4 7    - x x -    3 - 2 -
6 7 5 4    - - x -    2 1 1 -

然后我们尝试4上面的5,继续到7;我们将它标记为1,然后返回到我们临时标记为2的单元格;它在当前路径中的标记将是4,这是更高的值,因此我们将2替换为4,然后再返回,直到到达临时标记为2的路径的起点。新标记为7,因此我们将2替换为7,以得到:

3 1 2 5    - x - -    5 7 1 -
4 2 5 6    - x x x    4 6 3 2
5 3 4 7    - x x x    3 5 4 1
6 7 5 4    - - - -    2 1 1 -

我们继续到下一个未标记的单元格,即右上角的5。它有一个相邻的6,它已经标记为2,这意味着我们可以将此单元格标记为3(您将看到它实际上是从5到7的三步路径的开始):

3 1 2 5    - - - x    5 7 1 3
4 2 5 6    - - - x    4 6 3 2
5 3 4 7    - - - -    3 5 4 1
6 7 5 4    - - - -    2 1 1 -

我们继续到下一个未标记的单元格,即右下角的4。它有一个相邻的5,它已经标记为1,这意味着我们可以将这个单元格标记为2。

3 1 2 5    - - - -    5 7 1 3
4 2 5 6    - - - -    4 6 3 2
5 3 4 7    - - - -    3 5 4 1
6 7 5 4    - - x x    2 1 1 2

第二个网格现在已经完成了,我们添加到其中的最高数字是7,这意味着网格中最长的序列的长度为7。

复杂性

我们已经访问了作为路径一部分的每个单元格,并在第二个网格中输入值时沿着路径返回,因此复杂性与单元格的数量或O(n)成线性关系。当然,这种方法需要第二个网格,所以空间的复杂性也是O(n)。

代码示例

这里有一个用javascript编写的快速代码示例,我编写它来测试方法并检查我对时间复杂性的假设。结果可以在代码段下面找到。

function longestSequence(val) {
    var dx = [0, 1, 0, -1], dy = [-1, 0, 1, 0]; // up, right, down, left
    var height = val.length;
    var width = val[0].length;
    var max = 0;                                // max length found so far
    var stack = [];                             // cells in the current path
    var len = [];                               // length of upwards sequence from each cell
    for (var y = 0; y < height; y++) {
        len[y] = [];
        for (var x = 0; x < width; x++) {
            len[y][x] = 0;                      // initialize length grid
        }
    }
    for (var y = 0; y < height; y++) {          // iterate over every cell
        for (var x = 0; x < width; x++) {
            if (len[y][x] != 0) continue;       // skip cells already checked
            stack.push({x: x, y: y});           // start from this cell upwards ...
            while (stack.length) {              // and do a depth-first search
                var cur = stack.pop();          // take current cell from stack
                for (var i = 0; i < 4; i++) {   // check four neighbouring cells
                    var nbr = {x: cur.x + dx[i], y: cur.y + dy[i]};        // get neighbouring cell
                    if (nbr.x < 0 || nbr.x == width || nbr.y < 0 || nbr.y == height) {
                        continue;               // skip if off-grid
                    }
                    if (val[nbr.y][nbr.x] == val[cur.y][cur.x] + 1) {      // neighbour has next value
                        if (len[nbr.y][nbr.x] == 0) {                      // neighbour not yet checked
                            stack.push(cur);    // this cell is not last in path
                            stack.push(nbr);    // move to neighbouring cell
                            break;
                        }
                        else if (len[nbr.y][nbr.x] >= len[cur.y][cur.x]) { // neighbour has higher length
                            len[cur.y][cur.x] = len[nbr.y][nbr.x] + 1;     // take length from neighbour
                        }
                    }
                }
                if (len[cur.y][cur.x] == 0) {   // no suitable neighbours ...
                    len[cur.y][cur.x] = 1;      // cell is end-point of path
                }
            }
            if (len[cur.y][cur.x] > max) {      // new maximum length found
                max = len[cur.y][cur.x];
            }
        }
    }
    return max;
}

var grid = [[3, 1, 2, 5],
            [4, 2, 5, 6],
            [5, 3, 4, 7],
            [6, 7, 5, 4]];
document.write(longestSequence(grid));

检查线性复杂性

通过查看带有嵌套循环的代码来判断该算法的复杂性并不是那么简单。为了检查我的线性假设,我使用1到9之间的随机数网格运行代码,并添加一个计数器,以查看总共有多少个单元格被推到堆栈上:

  grid size        cells     push/pop

   8 x    8           64           75
  16 x   16          256          297
  32 x   32        1,024        1,235
  64 x   64        4,096        4,912
 128 x  128       16,384       19,557
 256 x  256       65,536       78,254
 512 x  512      262,144      313,371
1024 x 1024    1,048,576    1,253,540

结果证实,复杂性确实与细胞数量呈线性关系。推到堆栈上的单元数约为网格中单元数的120%,而不是精确的100%,这是因为根据它们在路径中的位置(终点、中点、十字路口),单元被访问一次、两次或多次。

为了显示真实世界的速度:上面的javascript版本在不到一秒钟的时间内解决了一个1024×1024的网格。

这里有一个有趣的小技巧:按值对单元格排序,并将每个元素1+上一个可连接单元格中标记的最长可实现序列的长度。例如:

4 2 2
5 6 3
7 5 4

2 2 3 4 4 5 5 6 7

2 -> 1
2 -> 1
3 -> 1 + 1 = 2
4 -> 1 + 2 = 3
5 -> 1 + 3 = 4
6 -> 1 + 4 = 5
7 -> 1

对于重复的元素,我们需要每个值创建一个位置的散列,这样我们就可以快速找到我们遍历的下一个元素的可连接单元格。 O(n*m * log(n*m))

我说k*(4^k),因为我检查了每个数字(因此是k)

它不会将复杂性乘以k。您可以安全地添加o(k),以确保复杂性至少为o(k),但您不需要将复杂性乘以k,除非在每个步骤(递归调用)中通过~k个值。

然后我可以看到它的四个邻居。

你看到4个邻居,但是除非你在每一个邻居中成功地分叉递归,否则它不算数。您可以简单地乘以4来反映4个选项,但常量将在o数学中删除。

实际上,根据问题定义,您不能每次都使用这四种方法,因为前一项在当前项的旁边。所以,最多可以用3叉,而且由于欧比乌平面构图的原因,它不能长时间工作-矩阵密度是不够的。不幸的是,我不知道简单的方法

实际上,您对每个有效点*4(下一步)的不同方式不超过n*个。

尽管我举了一个例子来说明达到o(2^k)复杂性的坏情况。完成对角线:左上格1个,下对角线2个,下对角线3个等。在矩阵最长对角线处完成,右下角用零填充。

0,1,2,3,4,5,6

1,2,3,4,5,6,0

2,3,4,5,6,0,0

3,4,5,6,0,0,0

4,5,6,0,0,0,0

5,6,0,0,0,0,0,0

6,0,0,0,0,0,0,0

因为从另一方面来说,我最多只考虑每个号码,我们访问所有的号码 在矩阵中,在这种情况下,复杂度为k^2。

错误的是,如果您不使用“已访问”标志以简单的复活方式执行此操作,则递归将对每个单元格进行一次以上的访问。对于上面的矩阵,你可以用6个元素的数组来模拟,其中right=0或down=1个元素,显然每个组合都有一种方法,而且它们显然是不同的,因此你有2^6个不同的有效方法来进行6次访问。

还有一件事。用结果长度或值计算复杂度是不实际的。你有像矩阵维数这样的输入值,这是我们通常在数学中使用的,因为人们无法预测他们会得到什么答案…