什么是这个天真code来计算组合的大O的复杂性？ [英] What is the big-O complexity of this naive code to compute combinations?

问题描述

下面的递归算法是（效率非常低）的方式来计算ñ选择K：

The following recursive algorithm is a (fairly inefficient) way to compute n choose k:

 int combinationsOf(int n, int k) {
     if (k == 0) return 1;
     if (n == 0) return 0;
     return combinationsOf(n - 1, k) + combinationsOf(n - 1, k - 1);
}

它是基于以下递归洞察：

It is based on the following recursive insight:

其实评价这一函数的函数调用了很多。例如，计算2选2这种方式使这些调用：

Actually evaluating this function takes a LOT of function calls. For example, computing 2 choose 2 this way makes these calls:

 combinationsOf(2, 2)
   |  |
   |  +- combinationsOf(1, 2)
   |       |  |
   |       |  +- combinationsOf(0, 2)
   |       |
   |       +-- combinationsOf(1, 1)
   |             |  |
   |             |  +- combinationsOf(0, 1)
   |             |
   |             +- combinationsOf(1, 0)
   +- combinationsOf(2, 1)
        |  |
        |  +- combinationsOf(2, 0)
        |
        +- combinationsOf(1, 1)
             |  |
             |  +- combinationsOf(0, 1)
             |
             +- combinationsOf(1, 0)

有许多的方法来改善该功能的运行时 - 我们可以使用动态编程，使用闭合形式的式NCK =正！ /（K（N - ！K））等。但是，我很好奇，刚才的如何的低效率这个特殊的算法

There are many ways to improve the runtime of this function - we could use dynamic programming, use the closed-form formula nCk = n! / (k! (n - k)!), etc. However, I am curious just how inefficient this particular algorithm is.

这是什么功能的大O的时间复杂性，n和k的函数？

What is the big-O time complexity of this function, as a function of n and k?

推荐答案

让 C（N，K）是计算成本 binom（ N，K）以这种方式，以

Let C(n,k) be the cost of computing binom(n,k) in that way, with

C(0,_) = 1
C(_,0) = 1

作为基础的情况下。

as base cases.

复发显然是

C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)

如果我们把除了拥有成本1。然后，我们可以很容易地检查

if we take addition to have cost 1. Then, we can easily check that

             k
C(n,k) = 2 * ∑ binom(n,j) - 1
            j=0

感应。

因此​​，对于 K＆GT; = N ，成本 2 ^（N + 1） - 1 ， C（N，N-1）= 2 ^（N + 1） - 3 ， C（N，1）= 2 * N + 1 ， C（N，2）= N *（N + 1）+1 ，（而除此之外，我没有看到整齐的公式）。

So for k >= n, the cost is 2^(n+1) - 1, C(n,n-1) = 2^(n+1)- 3, C(n,1) = 2*n+1, C(n,2) = n*(n+1)+1, (and beyond that, I don't see neat formulae).

我们有明显的上界

C(n,k) < 2^(n+1)

独立 K ，以及 K＆LT; N / 2 我们可以粗略估算

independent of k, and for k < n/2 we can coarsely estimate

C(n,k) <= 2*(k+1)*binom(n,k)

这给小得多界小 K ，所以总体

C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})

（需要夹紧 K 的最低，因为 binom（N，K）减小回1为 K＆GT; N / 2 ）

(need to clamp the k for the minimum, since binom(n,k) decreases back to 1 for k > n/2).

这篇关于什么是这个天真code来计算组合的大O的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！