我和我的朋友讨论了以下算法问题，
"Describe a recursive algorithm for finding the maximum element in an array A of n
elements. What is your running time and space usage?"
我们得出结论，它有 O(n) 的时间使用。根据此语句，F(n) =compare A[n] 与 F(n-1)，在递归的基本情况下，它比较 A[0] 和 A[1]，然后返回更大的一个，它将与A2]。随着递归的进行，最终，它将返回数组中的最大元素。
每 n 次递归，它只比较一次，所以最后我们猜测它有 O(n) 的时间使用。我的问题是我们不确定我们的解决方案，所以我们想要关于这个算法和我们的解决方案的任何其他评论。谢谢你。
是的。你是对的，这是事实O(n)。你可以做的很简单是，
该算法的基本操作是比较。并且在递归步骤中，比较只进行一次。
所以你可以说
m(n) = m(n-1) + 1
m(n-1) = m(n-2) + 1 + 1
m(n-2) = m(n-3) + 2 + 1
概括我们得到
m(n-i) = m(n-1-i) + i + 1
现在在您的基本情况下，您将不进行任何比较（基本情况没有剩余元素，因此您返回当前最大的）。你可以这样写
m(0) = 1
现在代入递推方程得到基本情况，让i = n-1
我们得到
m(n) = m(0) + n - 1 + 1
但m(0) = 0
所以我们得到
m(n) = n
因此你的算法是O(n)。还有其他方法可以证明这一点。即使没有数学证明，您也可以在逻辑上说您的算法是O(n)因为它在每个递归步骤中只执行一个基本操作，并且该算法将始终递归 n 步骤，而与输入无关。
如果数组包含integers. 在数字的情况下，比较两个数字可以被认为是一个单元操作。并且在遍历数组时，为了找到最大值，这个操作被执行了n几次。因此O(n)。
但是如果数组包含复杂的数据类型，比如string，那么比较两个字符串不能被视为一个单元操作。要比较字符串，您可能必须遍历字符串的每个字符。在这种情况下，算法的时间复杂度也可能取决于数组中字符串的长度。同样对于其他数据类型，比较两个对象可能不是单元操作。但在你的情况下，看起来数组包含数字，所以你很好。