为何我的算法理论复杂度为O(m4^m)却呈现线性表现？

核心原因：理论复杂度是最坏场景上界，而随机矩阵的实际路径长度受限 #

1. 理论复杂度描述的是最坏情况
   参考网站给出的O(mn4^(m+n))是算法的最坏时间复杂度上界，仅当矩阵存在极端结构时才会触发：比如构造一个每个节点都能向多个方向延伸出长递增路径的矩阵（实际中几乎不可能自然出现）。这种场景下，每个DFS递归会产生多个分支，且递归深度与矩阵的m+n成正比，最终导致指数级时间消耗。

2. 随机矩阵的路径长度存在硬限制
   你使用random.randint(0,100)生成的矩阵，元素取值范围仅为0-100。这意味着最长递增路径的长度最多为101（从0到100依次递增的序列）。无论矩阵规模多大，每个DFS递归的深度都被限制在101以内，且由于元素重复率高，每个节点能找到的递增后续节点数量极少，递归分支数远小于4。

3. 实际总操作数接近线性
   固定n=10时，矩阵总元素数为10*m。由于每个节点的递归分支少、深度浅，算法遍历的总节点数与矩阵总元素数成正比，最终时间复杂度呈现为O(mn)=O(m)的线性特征。

验证最坏情况的方法 #

如果想观察到指数级时间消耗，可以构造一个严格递增的矩阵，比如：

# 构造每行、每列都严格递增的矩阵（每个点可向右/向下延伸递增路径）
def build_worst_case_matrix(m, n):
    matrix = []
    for i in range(m):
        row = [i * n + j + 1 for j in range(n)]
        matrix.append(row)
    return matrix

用这个矩阵替换随机矩阵进行测试，随着m增大，时间会呈现指数级增长。

内容的提问来源于stack exchange，提问作者John Martin