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

Question

我正在分析一个算法，它给出了一个方阵的 "峰值值 "的位置（这意味着该值的邻域小于或等于该值）.该算法的效率非常低，因为它从位置（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 五十一至五十三条
• 等。

此时，模式应该是清晰的，因此可以建立以下最坏情况下的递归关系。

    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 或为im2迭代。因此插回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)