-2

我和我的朋友讨论了以下算法问题，

"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) 的时间使用。我的问题是我们不确定我们的解决方案，所以我们想要关于这个算法和我们的解决方案的任何其他评论。谢谢你。

4

2 回答 2

0

是的。你是对的，这是事实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 步骤，而与输入无关。

于 2013-03-11T13:14:43.333 回答
0

如果数组包含integers. 在数字的情况下，比较两个数字可以被认为是一个单元操作。并且在遍历数组时，为了找到最大值，这个操作被执行了n几次。因此O(n)。

但是如果数组包含复杂的数据类型，比如string，那么比较两个字符串不能被视为一个单元操作。要比较字符串，您可能必须遍历字符串的每个字符。在这种情况下，算法的时间复杂度也可能取决于数组中字符串的长度。同样对于其他数据类型，比较两个对象可能不是单元操作。但在你的情况下，看起来数组包含数字，所以你很好。

于 2013-03-11T13:16:54.040 回答