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

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个项目，将排序视为无关紧要的项目。从远古时代开始，我们知道期望有多少种组合：

    n!

-----------

(n - k)! k!

对于给定的n（例如10），当k等于n（5）的一半时，该表达式将最大化。当n或k接近极限时，组合的数量将大大减少。

通过一些重组和简化，我们可以重写您的代码，以便combos()在最坏的情况下对的调用次数大致等于组合的次数。有趣的是，调用次数和组合次数具有很好的对称逆关系。

最重要的是，在最坏的情况下，两者都受上面显示的公式约束。这实际上是O()您所要求的范围。但是也许不完全是因为重写的代码产生的子例程调用比您的代码少，即使它们确实产生了相同的结果。下例中的短路逻辑防止了额外的调用，因此使最坏情况下的参数都能正常运行。

如果该公式是最坏情况的界限，那么您的算法是否在多项式时间内运行？在这些问题上，我比专家更直观，但我认为答案是否定的。最糟糕的情况是when k = n / 2，它为您提供了以下简化。尽管分母真的很快变大，但与分子的Chuck-Norris增长率相比却相形见pale。

      n!

-------------

(n/2)! (n/2)!

# For example, when n = 40.

       product(1..40)             product(      21..40)   # Eat my dust, Homer!

-----------------------------  =  ---------------------

product(1..20) product(1..20)     product(1..20       )   # Doh!

# Q.E.D.

关于n和k的许多值的经验说明：

from itertools import combinations

from math import factorial

n_calls = 0

def combos(vals, size):

    # Track the number of calls.

    global n_calls

    n_calls += 1

    # Basically your algorithm, but simplified

    # and written as a generator.

    for i in range(0, len(vals) - size + 1):

        v = vals[i]

        if size == 1:

            yield [v]

        else:

            for c in combos(vals[i+1:], size - 1):

                yield [v] + c

def expected_n(n, k):

    # The mathematical formula for expected N of k-combinations.

    return factorial(n) / ( factorial(n - k) * factorial(k) )

def main():

    global n_calls

    # Run through a bunch of values for n and k.

    max_n = 15

    for n in range(1, max_n + 1):

        # Worst case is when k is half of n.

        worst_case = expected_n(n, n // 2)

        for k in range(1, n + 1):

            # Get the combos and count the calls.

            n_calls = 0

            vs = list(range(n))

            cs = list(combos(vs, k))

            # Our result agrees with:

            #   - itertools.combinations

            #   - the math

            #   - the worst-case analysis

            assert cs      == list(list(c) for c in combinations(vs, k))

            assert len(cs) == expected_n(n, k)

            assert n_calls <= worst_case

            assert len(cs) <= worst_case

            # Inspect the numbers for one value of n.

            if n == max_n:

                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 -1），

...对于size = 2，您正在看f（n）函数调用。

如果我们定义一个函数g（n）= f（1）+ f（2）+ f（3）+ ... + f（n -1），

...对于size = 3，您正在看g（n）函数调用。

因此，您似乎可以说函数的复杂度受O（n ^ s）限制，其中n是列表的长度，s是您的size参数。

Answer 3

看一下Run Snake Run配置文件查看器。它接受一个概要文件输出，并创建一个漂亮的函数调用可视化效果。

您使用cProfile模块运行程序，然后将输出日志发送到Run Snake Run：

python -m cProfile -o profile.log your_program.py

runsnake profile.log

这个例子是针对Linux的。Windows使用情况可能略有不同。