T(n) = T(n - 1) + (n - 1)^2 的时间复杂度为什么

根据给出的递归关系式T(n) = T(n - 1) + (n - 1)^2，我们可以通过不断展开递归式来求解时间复杂度。

首先，我们可以展开T(n - 1)： T(n) = T(n - 1) + (n - 1)^2 = T(n - 2) + (n - 2)^2 + (n - 1)^2 = T(n - 3) + (n - 3)^2 + (n - 2)^2 + (n - 1)^2 ... = T(1) + (1)^2 + (2)^2 + ... + (n - 1)^2

我们可以看到，每次展开递归式都增加了一个平方项，所以展开到最后一步，会有n - 1个平方项。

因此，时间复杂度为O(n^2)。

下面是一个示例代码，用于计算T(n)的值：

def T(n):
    if n == 1:
        return 0
    else:
        return T(n - 1) + (n - 1) ** 2

n = 5
result = T(n)
print(result)

在上述代码中，我们定义了一个递归函数T(n)，其中当n等于1时，返回0；否则，返回T(n-1) + (n-1)^2。最后，我们通过传入n=5来计算T(n)的值，并将结果打印出来。