theta 符号中的 (3 + 9 + 27 + ... + 3^n) 是什么？

Question

直觉上，我认为它可以简化为 theta(3^n)。

但我不确定，因为我无法说服自己从 3^0 到 3^(n-1) 的所有内容都无关紧要。

Answer 1

尽管它是寻找程序的时间复杂度。但是更数学化。您应该避免在 Whosebug 上询问。您可以在 math.stackexchange.

上提问

只是求几何级数的和，我们需要求n项的和

s(n) = a1(1-r^n)/(1-r)   where r=common ratio and a1 is first term.

s(n) = 3(1-3^n)(1-3)
     = (3-3^(n+1))/-2
     = (3^(n+1)-3)/2
     = (3^n+1)/2     (appox)
     = 3^n+1       (appox)
     = O(3^n)    (appox)

因此你可以说时间复杂度是θ(3^n)。

theta 符号中的 (3 + 9 + 27 + ... + 3^n) 是什么？

what is (3 + 9 + 27 + ... + 3^n) in theta notation?

math

runtime

analysis