algorithm - 函数 T(n) = T(n//3)) + 1 的时间复杂度是多少

Question

这个函数的复杂度是多少？

T(n) = T(n/3) + 1

答案是O(n)。但是怎么走？

好的，这就是我的回答：

T(n) = T(n/3) + 1

我在这里使用主定理，

所以得到了T(n) = aT(n/b) + f(n)

将 n^logb(a) 与 f(n) 进行比较

a = 1, b = 3

n^logb(a) = n^log3(1)
          = n^0
          = 1

f(n) = Θ(n^logb(a))

所以我得到的解决方案是T(n) = Θ(logn)

这是我的答案，但是当我搜索它时，它说答案T(n) = Θ(n)？

标签： algorithmtime-complexitybig-ocomplexity-theory