该算法最坏情况下的时间复杂度是多少？

Question

我正在分析一种算法，该算法给出方阵的 "peak value" 的位置（这意味着该值的邻居小于或等于该值）。所讨论的算法效率非常低，因为它会一个一个地检查值，从位置 (0,0) 开始，然后移动到比该数字大的邻居。这是代码：

def algorithm(problem, location = (0, 0), trace = None):
    # if it's empty, it's done!
    if problem.numRow <= 0 or problem.numCol <= 0:                                  #O(1)
        return None

    nextLocation = problem.getBetterNeighbor(location, trace)                       #O(1)
    #This evaluates the neighbor values and returns the highest value. If it doesn't have a better neighbor, it return itself

    if nextLocation == location:
        # If it doesnt have a better neighbor, then its a peak.
        if not trace is None: trace.foundPeak(location)                             #O(1)
        return location
    else:
        #there is a better neighbor, go to the neighbor and do a recursive call with that location
        return algorithm(problem, nextLocation, trace)                             #O(????)

我知道最好的情况是峰值在 (0,0)，我确定最坏的情况如下（使用 10x10 矩阵）：

problem = [
 [0,   1,  2,  3,  4,  5,  6,  7,  8,  9],
 [0,   0,  0,  0,  0,  0,  0,  0,  0, 10],
 [34, 35, 36, 37, 38, 39, 40, 41,  0, 11],
 [33,  0,  0,  0,  0,  0,  0, 42,  0, 12],
 [32,  0, 54, 55, 56, 57,  0, 43,  0, 13],
 [31,  0, 53,  0,  0, 58,  0, 44,  0, 14],
 [30,  0, 52,  0,  0,  0,  0, 45,  0, 15],
 [29,  0, 51, 50, 49, 48, 47, 46,  0, 16],
 [28,  0,  0,  0,  0,  0,  0,  0,  0, 17],
 [27, 26, 25, 24, 23, 22, 21, 20, 19, 18]]

请注意，它基本上使算法呈螺旋状，并且必须评估 59 个位置。

所以，问题是：我如何获得这种情况下的时间复杂度，为什么会这样？我知道所有的操作都是O(1)，除了递归，我迷路了

Answer 1

对于大小为 [m,n], 的任意矩阵，如您在示例中所示，我们可以将此算法 (A) 生成的给定矩阵的遍历分解如下：

A将从左上角遍历n-1个元素到第8个元素，
然后m-1个9到17的元素，
然后 n-1 个元素从 18 到 27，
然后m-3个元素从27到33，
然后n-3个元素从34到40,
然后m-5个元素从41到45，
然后 n-5 个元素从 46 到 50，
然后 m-7 个元素从 51 到 53
等等

至此，模式应该清楚了，因此可以建立以下最坏情况递归关系：

    T(m,n) = T(m-2,n-2) + m-1 + n-1
    T(m,n) = T(m-4,n-4) + m-3 + n-3 + m-1 + n-1
    ...
    T(m,n) = T(m-2i,n-2i) + i*m + i*n -2*(i^2)

其中 i 是迭代次数，只有当 m-2i 和 n-2i 都大于 0 时，此循环才会继续。

WLOG 我们可以假设 m>=n，因此该算法在 m-2i>0 或 m>2i 或 im/2 迭代期间继续。因此，为 i 重新插入，我们得到：

    T(m,n) = T(m-m,n-m) + m/2*m + m/2*n -2*((m/2)^2)
    T(m,n) = 0 + m^2/2 + m*n/2 -2*((m^2/4))
    T(m,n) = 0 + m^2/2 + m*n/2 -2*((m^2/4))
    T(m,n) = m*n/2 = O(m*n)

该算法最坏情况下的时间复杂度是多少？

What is the time complexity for the worst case of this algorithm?

algorithm

complexity-theory

time-complexity

python-3.x