時間這一系列的複雜

Question

如何找到以下系列

的時間複雜度，請告訴我，這是正確的綁定與否。

Answer 1

有關完整嚴謹，證據必須是一個小更復雜。

讓f成爲O*(2^k)的函數。如果O*(2^k)被理解爲與O(2^k)相同，則對於某些m,k≥m => f(k)≤C B(n,k)2^k。 k<m的限制needen't。

那麼對於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. 

Answer 2

由於從數學交換記憶西格瑪（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 3

我認爲這是正確的綁定。
根據二項式定理，我們有：

然後令x = 1和y = 2