java - 递归函数的时间复杂度

Question

我有一个 Java 函数，它接收一个矩阵（二维数组 [] []）并为此数组创建一个更改选项的动态数组，然后为动态数组的每个选项递归地创建一个动态数组。最终，对于 N 个选项之一中的每个选项，它会创建 N 个其他选项。 有人告诉我它的时间复杂度函数是T(n)=T(n)*n，这可能吗？大 O 表示法的渐近时间复杂度是多少？

Answer 1

如果递归关系是 T(n)=nT(n)，则递归永远不会停止。这种递归关系意味着每个子问题与原始问题的大小相同。在递归函数中，如果每个子问题的大小都与原始问题的大小相同，则意味着递归不会结束。从您的问题看来，您的函数在原始矩阵上运行一次，然后在第一个函数应用程序的结果上运行一次，然后停止。这不是一个真正的递归函数，也不真正适合计算时间复杂度的递归关系模型。不过，计算时间复杂度也非常简单，因为您实际上可以将所有计算加起来。