递归算法的时间使用

Question

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

"Describe a recursive algorithm for finding the maximum element in an array A of n   
elements. What is your running time and space usage?" 

我们conclusioned它有O（n）的时间使用。根据这个语句，F（n）=比较A [n]与F（n-1），在递归的基本情况下，比较A [0]和A [1]，然后返回更大的一个，这将与A [2]比较。随着递归的进行，最后，它会返回数组中的最大元素。

每n次递归，它只比较一次，所以最后我们猜测它有O（n）的时间使用率。 我的问题是我们不确定我们的解决方案，所以我们想要关于这个算法和我们的解决方案的任何其他意见。谢谢。

Answer 1

如果数组包含integers，则您可以使用这种方法来查找时间复杂度。在数字的情况下，比较两个数字可以被认为是一个单位操作。在迭代数组时，为了找到最大值，这个操作被执行n次。因此O(n)。

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

Answer 2

是的。你是对的，这实际上是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 

现在

在basecase，你会做任何比较（basecase留下任何元素，让你返回当前最大） 。你可以这样写为

m(0) = 1 

现在递推方程得到基本情况代，让i = n-1

我们得到

m(n) = m(0) + n - 1 + 1 

但m(0) = 0

所以我们得到

m(n) = n 

因此，您的算法是O(n)。还有其他方法可以证明这一点。即使没有数学证明，你也可以合理地说你的算法是O(n)，因为它在每个递归步骤中只执行一个基本操作，并且该算法将总是递归n个步骤，而不管输入如何。