确定递归算法的计算复杂度

Question

我正在尝试确定我编写的算法是否在多项式时间内运行，目前我不知道该如何使用该函数

def combo(list, size):

    if size == 0 or not list:                            # order doesn't matter

        return [list[:0]]                                # xyz == yzx

    else:

        result = []

        for i in range(0, (len(list) - size) + 1):       # iff enough left

            pick = list[i:i+1]

            rest = list[i+1:]                            # drop [:i] part

            for x in combo(rest, size - 1):

                result.append(pick + x)

        return result

Answer 1

您已经有了“ k个组合”的算法：给定n个项目，选择k个项目，将排序视为无关紧要的项目。从远古时代开始，我们知道期望有多少种组合：&nbsp; &nbsp; n!-----------(n - k)! k!对于给定的n（例如10），当k等于n（5）的一半时，该表达式将最大化。当n或k接近极限时，组合的数量将大大减少。通过一些重组和简化，我们可以重写您的代码，以便combos()在最坏的情况下对的调用次数大致等于组合的次数。有趣的是，调用次数和组合次数具有很好的对称逆关系。最重要的是，在最坏的情况下，两者都受上面显示的公式约束。这实际上是O()您所要求的范围。但是也许不完全是因为重写的代码产生的子例程调用比您的代码少，即使它们确实产生了相同的结果。下例中的短路逻辑防止了额外的调用，因此使最坏情况下的参数都能正常运行。如果该公式是最坏情况的界限，那么您的算法是否在多项式时间内运行？在这些问题上，我比专家更直观，但我认为答案是否定的。最糟糕的情况是when k = n / 2，它为您提供了以下简化。尽管分母真的很快变大，但与分子的Chuck-Norris增长率相比却相形见pale。&nbsp; &nbsp; &nbsp; n!-------------(n/2)! (n/2)!# For example, when n = 40.&nbsp; &nbsp; &nbsp; &nbsp;product(1..40)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;product(&nbsp; &nbsp; &nbsp; 21..40)&nbsp; &nbsp;# Eat my dust, Homer!-----------------------------&nbsp; =&nbsp; ---------------------product(1..20) product(1..20)&nbsp; &nbsp; &nbsp;product(1..20&nbsp; &nbsp; &nbsp; &nbsp;)&nbsp; &nbsp;# Doh!# Q.E.D.关于n和k的许多值的经验说明：from itertools import combinationsfrom math import factorialn_calls = 0def combos(vals, size):&nbsp; &nbsp; # Track the number of calls.&nbsp; &nbsp; global n_calls&nbsp; &nbsp; n_calls += 1&nbsp; &nbsp; # Basically your algorithm, but simplified&nbsp; &nbsp; # and written as a generator.&nbsp; &nbsp; for i in range(0, len(vals) - size + 1):&nbsp; &nbsp; &nbsp; &nbsp; v = vals[i]&nbsp; &nbsp; &nbsp; &nbsp; if size == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [v]&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for c in combos(vals[i+1:], size - 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [v] + cdef expected_n(n, k):&nbsp; &nbsp; # The mathematical formula for expected N of k-combinations.&nbsp; &nbsp; return factorial(n) / ( factorial(n - k) * factorial(k) )def main():&nbsp; &nbsp; global n_calls&nbsp; &nbsp; # Run through a bunch of values for n and k.&nbsp; &nbsp; max_n = 15&nbsp; &nbsp; for n in range(1, max_n + 1):&nbsp; &nbsp; &nbsp; &nbsp; # Worst case is when k is half of n.&nbsp; &nbsp; &nbsp; &nbsp; worst_case = expected_n(n, n // 2)&nbsp; &nbsp; &nbsp; &nbsp; for k in range(1, n + 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # Get the combos and count the calls.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n_calls = 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vs = list(range(n))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cs = list(combos(vs, k))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # Our result agrees with:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; &nbsp;- itertools.combinations&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; &nbsp;- the math&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; &nbsp;- the worst-case analysis&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; assert cs&nbsp; &nbsp; &nbsp; == list(list(c) for c in combinations(vs, k))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; assert len(cs) == expected_n(n, k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; assert n_calls <= worst_case&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; assert len(cs) <= worst_case&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # Inspect the numbers for one value of n.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n == max_n:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print [n, k, len(cs), n_calls]main()输出：[15, 1, 15, 1][15, 2, 105, 15][15, 3, 455, 105][15, 4, 1365, 455][15, 5, 3003, 1365][15, 6, 5005, 3003][15, 7, 6435, 5005][15, 8, 6435, 6435][15, 9, 5005, 6435][15, 10, 3003, 5005][15, 11, 1365, 3003][15, 12, 455, 1365][15, 13, 105, 455][15, 14, 15, 105][15, 15, 1, 15]

Answer 2

这取决于您的size变量。如果n是列表列表的长度（在此处阴影，请顺便说一句）。对于size = 1，您正在查看对的n次调用combo。如果我们定义一个函数f（n）= 1 + 2 + 3 + ... +（n&nbsp;-1），...对于size = 2，您正在看f（n）函数调用。如果我们定义一个函数g（n）= f（1）+ f（2）+ f（3）+ ... + f（n&nbsp;-1），...对于size = 3，您正在看g（n）函数调用。因此，您似乎可以说函数的复杂度受O（n&nbsp;^&nbsp;s）限制，其中n是列表的长度，s是您的size参数。

Answer 3

看一下Run Snake Run配置文件查看器。它接受一个概要文件输出，并创建一个漂亮的函数调用可视化效果。您使用cProfile模块运行程序，然后将输出日志发送到Run Snake Run：python -m cProfile -o profile.log your_program.pyrunsnake profile.log这个例子是针对Linux的。Windows使用情况可能略有不同。