递归函数的证明时间复杂度 [英] Proof time complexity for recursive function

问题描述

我正在尝试确定此函数的复杂性，其中D和element是整数，而list是整数的有序列表.请注意，(otherElement-element)将严格为正.

I'm trying to determine the complexity of this function, where D and element are integers and list is an ordered list of integers. Note from this that (otherElement-element) will be strictly positive.

def doFunc(element, D, list):
  x = 0 
  if(D > 0):
    for otherElement in list:
      if otherElement == element:
        x += 1
      if otherElement > element:
        return x + (doFunc (otherElement,D-(otherElement-element) , list))
  return x

鉴于列表将不会始终被完全迭代，因此我不知道如何确定此函数的时间复杂度.

Given that the list will not be always fully iterated, I don't know how can I determine a time complexity for this function.

推荐答案

doFunc从左到右检查list，以找到一个大于或等于提供的element的otherElement.最多进行一次递归调用.通过推导出最坏情况下的输入并分析行为，我们可以尝试找出此函数的最坏情况下的时间复杂度.

doFunc checks the list from left to right to find an otherElement greater than or equal to the provided element. At most one recursive call is made. We can try to figure out the worst-case time complexity of this function by deducing what must be the worst-case input and analyzing the behavior.

假设我们从一个大小为1的列表开始；称为{1}.如果我们在此列表中调用该函数，那么从for循环中可以得到的最多迭代次数是多少?好吧，如果我们设置element = 1，我们将得到一个迭代.但是，如果设置为element = 0，则可以获取doFunc以使用element = 1进行递归调用.这意味着我们得到了两次迭代.说服自己，我们不可能从该列表的doFunc中获得两次以上的迭代.也要使自己相信，{1}的选择本质上并不重要.任何单元素列表都将以相同的方式工作.

Suppose we start with a list of size 1; call it {1}. If we call the function on this list, what's the most iterations we could possibly get out of the for loop? Well, if we set element = 1, we get a single iteration. However, if set element = 0, we can get doFunc to recursively call itself with element = 1; this means we get two iterations. Convince yourself that there's no way we can ever get more than two iterations out doFunc for this list. Also convince yourself that the choice of {1} is essentially unimportant; any single-element list would work the same way.

现在假设我们要查找长度为2的最坏情况的列表；下一个数字应该相同，更大还是更小?考虑{1, 1}，{1, 2}和{1, 0}.用element = -1调用doFunc将分别最多导致for循环进行3、5和3次迭代.添加更大的元素会导致长度2的列表出现最糟糕的行为.

Suppose now that we want to find a worst-case list of length 2; should the next number be the same, greater, or smaller? Consider {1, 1}, {1, 2} and {1, 0}. Calling doFunc with element = -1 will cause at most 3, 5, and 3 iterations, respectively, of the for loop. Adding a greater element results in the worst possible behavior for a list of length 2.

说服自己，最坏的情况是数字递增.实际上，由于D的限制因素，最坏的情况是n元素的{a, a+1, a+2, ..., a+n-1}形式的列表.对于这样的列表，设置element < a时，我们具有以下行为:

Convince yourself that the worst case is an ascending list of numbers; in fact, due to the limiting factor of D, the worst-case is a list of the form {a, a+1, a+2, ..., a+n-1} of n elements. For such a list, we have the following behavior when setting element < a:

1. 第一次调用doFunc的一次迭代；然后我们有otherElement > element，所以我们递归地调用doFunc.
2. 第一次递归调用doFunc的两次迭代；然后，我们有了otherElement > element，因此我们再次递归调用.
3. 类似地，在对doFunc的第k次递归调用中，我们应该期望for循环的k+1迭代.由于for循环在一次调用的上下文中不能迭代超过n次，因此这意味着我们最多可以对doFunc进行n - 1递归调用.

1. One iteration on the initial call to doFunc; we then have otherElement > element, so we recursively call doFunc.
2. Two iterations on the first recursive call to doFunc; we then have otherElement > element, so we recursively call again.
3. Similarly, on the kth recursive call to doFunc, we should expect k+1 iterations of the for loop. Since the for loop can't iterate more than n times in the context of a single invocation, this means that we have at most n - 1 recursive calls to doFunc.

我们有1 + 2 + ... + n = O(n^2).这是假设d > n.假设d < n，我们无法获得所有的递归调用.在这种情况下，最多只能有1 + 2 + ... + d个迭代或O(d^2).因此，此功能的最坏情况是O(min(n^2, d^2)).另一个问题中事物的复杂度是O(dn)，比这里的复杂度差，除非d = n，在这种情况下，性能是相同的.

We have 1 + 2 + ... + n = O(n^2). This is assuming that d > n. Assuming d < n, we can't get all of the recursive calls; we can have, at most, 1 + 2 + ... + d iterations in this case, or O(d^2). Therefore, the worst-case behavior of this function is O(min(n^2, d^2)). The complexity of the thing in your other question was O(dn), which is worse than the complexity here, unless d = n, in which case the performance is the same.

还请注意，这里保证时间复杂度的常数实际上要比其他尝试好得多，因此尽管具有相同的渐近复杂度，您也会看到明显更好的性能.

note also that the constants for the time complexity here are virtually guaranteed to be significantly better than for your other attempt, so you'd see noticeably better performance despite having the same asymptotic complexity.

这篇关于递归函数的证明时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！