1

我正在尝试确定我编写的算法是否在多项式时间内运行，目前我无法弄清楚它使用的这个函数的计数

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
4

3 回答 3

1

你有一个“k-combinations”算法：给定 n 个项目，选择其中的 k 个，将排序视为无关紧要。从古人那里，我们知道可以期待多少种组合：

    n!
-----------
(n - k)! k!

对于给定的 n（例如，10），当 k 等于 n (5) 的一半时，该表达式最大化。当 n 或 k 接近极端时，组合的数量会变得更少。

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

最重要的是，对于最坏的情况，两者都受上面所示的公式的限制。这实际上是O()您要求的界限。但也许不完全是，因为重写的代码比你的代码调用更少的子程序，即使它们产生相同的结果。下面示例中的短路逻辑可以防止额外的调用，从而允许最坏情况的参数正常运行。

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

      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]
于 2013-06-18T05:40:18.680 回答
0

查看 Run Snake Run 配置文件查看器。它采用配置文件输出并创建函数调用的良好可视化。

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

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

该示例适用于 Linux；Windows 使用情况可能略有不同。

于 2013-06-17T22:11:24.380 回答
0

这取决于你的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是您的大小参数。

于 2013-06-17T22:46:18.150 回答