这个系列的时间复杂度

Question

如何找到以下系列的时间复杂度

请告诉我这个绑定是否正确。

Answer 1

通过数学交流的小作弊来记住 sigma(0,n) nCk = 2^n。

(x+y)^n=nC0*x^n*y^0 + nC1*x^n-1*y^1......+nCn-1*x^1*y^n-1+nCn*y^n*x^0  --(1)

这是上述形式的任何方程的正常二项式展开。因此，在相同条件下，我们可以打开给定的方程

(1+2)^n = nC0*1^n*2^0 + nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(2)
(1+2)^n = 1 + nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(3)
(1+2)^n = 1+nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(4)
((3)^n)-1 = nC1*1^n-1*2^1 ......+ nCn-1*1^1*2^n-1 + nCn*2^n*1^0 --(4)

因此，如果问题是关于边界的，那么 -1 可以忽略，给定的边界是正确的

Answer 2

我认为这是正确的界限。
根据二项式定理，我们有：

然后让 x = 1 和 y = 2。

Answer 3

为了完全严谨，证明必须更复杂一些。

设f为O*(2^k)的函数。如果说 O*(2^k) 和 O(2^k) 是同一个意思，那么对于某些人来说 m，k≥m => f(k)≤C B(n,k)2^k。 k<m.

不需要边界

然后 n>m 总和必须分成两部分，

Σ(k=1->n) B(n,k)f(k)
    ≤ Σ(k=1->m-1) B(n,k)f(k) + Σ(k=m->n) C B(n,k)2^k 
    = Σ(k=1->m-1) B(n,k)f(k) - Σ(k=1->m-1) C B(n,k)2^k + Σ(k=1->n) C B(n,k)2^k
    = C' + C 3^n.
    ≤ (C' + C)3^n.

这个系列的时间复杂度

Time complexity of this series

algorithm

complexity-theory

time-complexity