填充MxN矩阵某些部分的时间复杂度

Question

我不擅长计算算法的复杂度。填充MxN矩阵的时间复杂度为O(MN)。是的，我理解这一点，因为NxM是单元格填充的数量。我知道我们可以算出最好的、平均的和最坏的情况。

例如，这个4x4矩阵。我们只填写对角线(D)和一个对角线向上丹下降主对角线(x)。我知道复杂度是O(3M-2)，所以我们有3.4-2 = 10。

|D  x        |
|x  D   x    |
|   x   D   x|
|       x   D|

但我无法详细解释我是如何得到3M2的。我只是用我的想象力来尝试和错误。在最坏的情况下，我们必须填写第一主对角线( D1 )，第二主对角线( D2 )，D1和D2 (D)之间的单元格，以及一个单元格上和下主对角线(x)。我所知道的复杂性是O(2*M +(M-N-1)N +2(N1))

其中M=9(最大行，col)，N=6 (min行，col)。参见下面的示例

|D1 D   D   D2  x                 |
|x  D1  D   D   D2  x             |
|   x   D1  D   D   D2  x         |
|       x   D1  D   D   D2  x     |
|           x   D1  D   D   D2  x |
|               x   D1  D   D   D2|

填充面积为= 2*9 + (9-6-1)6 + 2(6-1) = 34。

2*M代表D1和D2。

(M-N-1)*N代表D.

2*(N-1)代表x

但我不知道怎么用数学来写这个。我的意思是如何从结构上来描述？我只想计算复杂度来填充矩阵的某些部分。谢谢。

Answer 1

在每个“完全”对角线中，你有N个元素。有M+1全对角线，因为从(1,1)开始的对角线以(N，N)结尾，但最后一行在最后一行中有M个元素。

您想要添加向上和向下的对角线，每个对角线都有(N1)元素。因此，您的复杂性是：

O(N(M-N+1) + 2(N-1)) = O(NM - NN + N + 2N - 2) = O(NM-NN+3N) = O(N(M-N+3))