计算递归函数的原始操作

Question

我正在阅读《算法设计与应用》，作者 Michael T. Goodrich 和 Roberto Tamassia，Wiley 出版。他们教授原始操作的概念以及如何在给定的算法中进行计数。一切对我来说都很清楚，直到他们展示了一个递归函数（一种计算数组最大值的简单递归方法）及其原始操作计数。 函数（伪代码）是这样的：

Algorithm recursiveMax(A, n):
    Input: An array A storing n ≥ 1 integers.
    Output: The maximum element in A.
    
    if n = 1 then
        return A[0]
    return max{recursiveMax(A, n − 1), A[n − 1]}

其中 

A

是一个数组，

n

是它的长度。作者阐述了以下关于我们如何计算该函数具有的原始操作数量的内容：

就像这个例子一样，递归算法通常非常优雅。分析 然而，递归算法的运行时间需要一些额外的工作。 特别是，为了分析这样的运行时间，我们使用递推方程，其中 定义了递归算法的运行时间必须的数学语句 满足。我们引入一个函数T(n)来表示算法的运行时间 在大小为 n 的输入上，我们写出 T (n) 必须满足的方程。例如， 我们可以将 recursiveMax 算法的运行时间 T (n) 描述为 T(n) = 3（如果 n = 1）或 T(n - 1) + 7（否则），假设我们对每个比较、数组引用、递归调用进行计数、最大值计算或作为单个原始操作返回。理想情况下，我们希望以封闭形式来描述像上面这样的递推方程，其中右侧没有出现对函数 T 的引用。对于 recursiveMax 算法，不难看出封闭形式为 T (n) = 7(n − 1) + 3 = 7n − 4。

我可以清楚地理解，在单项数组的情况下，我们的 T(n) 将仅为 3（只会发生 3 个基本操作，即比较 n = 1、数组索引 A[0] 和返回操作），但我不明白为什么在 n 不为 1 的情况下我们有 T(n-1) + 7。为什么 + 7？我们从哪里得到这个常数？

另外，我无法理解这个

封闭形式

：他是怎么得到T(n) = 7(n - 1) + 3？ 我感谢任何帮助。

Answer 1

T(n) = T(n-1)+7 成立，因为：

line 5: comparison n=1 => +1
line 7: return ==> +1
line 7: max ==> +1
line 7: computing n-1 for the argument of recursiveMax => +1
line 7: calling recursiveMax ==> +1
line 7: computing n-1 in A[n-1] ==> +1
line 7: array reference in A[n-1] ==> +1