递归函数的证明时间复杂度

我试图确定这个函数的复杂性，其中D和元素是整数，列表是整数的有序列表。请注意，（otherElement-element）将严格为正值。递归函数的证明时间复杂度

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

鉴于列表不会总是完全迭代，我不知道如何确定此函数的时间复杂度。

来源

2014-03-26 FranckN

请参阅http://stackoverflow.com/a/22615862/847269，我回答的问题与此类似，但显然与此不同。 – Patrick87

我试图优化算法。你看，我必须在严格低于O（n^2）的时间复杂度下解决一个问题，但我并没有真正看到如何计算这个大o。我认为增加一个新的条件可能会帮助我降低复杂性。您是否告诉我这与之前发布的其他产品相同？ – FranckN

不;我现在正在写一个答案，但这里的复杂性确实更好。只是指出这是一个类似的问题;对不起，如果这是你的问题，我不认识你:) – Patrick87

doFunc检查list从左到右找到大于或等于提供的element的otherElement。最多只能进行一次递归调用。我们可以通过推导什么是最坏情况输入和分析行为来试图找出这个函数的最坏情况时间复杂性。

假设我们从大小为1的列表开始;称它为{1}。如果我们在这个列表中调用函数，那么我们可能从for循环中获得的最多迭代次数是多少？那么，如果我们设置element = 1，我们会得到一个迭代。但是，如果设置为element = 0，我们可以通过element = 1递归地调用doFunc;这意味着我们有两个迭代。说服你自己，我们无法获得这个列表的超过两个迭代doFunc。还要说服自己，{1}的选择基本上不重要;任何单元素列表都会以同样的方式工作。

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

说服自己最糟糕的情况是数字上升列表;实际上，由于D的限制因素，最坏的情况是n元素的形式列表{a, a+1, a+2, ..., a+n-1}。对于这样一个名单，我们有以下行为设置element < a时：

上 doFunc初始呼叫

一次迭代;我们然后有otherElement > element，所以我们递归地调用doFunc。
第一次递归调用doFunc的两次迭代;然后我们有otherElement > element，所以我们再次递归调用。
同样，在k递归调用doFunc，我们应该期待for循环的迭代k+1迭代。由于for循环在单次调用的上下文中不能迭代超过n次，这意味着我们最多可以递归调用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，在这种情况下性能是相同的。

编辑：还要注意，这里的时间复杂性的常量几乎保证明显好于其他尝试，所以即使具有相同的渐近复杂性，您也会看到明显更好的性能。

来源

2014-03-26 16:26:54 Patrick87

递归函数的证明时间复杂度

回答

相关问题