这个伪代码的时间复杂度是多少？

Question

这是伪代码.我试图计算这个函数的时间复杂度,正如这个答案所说的那样.应该是这样的:

n + n/3 + n/9 + ... 

也许时间的复杂性就像O(nlog(n))我猜的那样？或者log(n)应该是log(n) 基数3？有人说时间复杂度是O(n),这对我来说是完全不可接受的.

j = n
while j >= 1 {
    for i = 1 to j {
        x += 1
    }
    j /= 3
}

Answer 1

该算法将运行于:

n + n/3 + n/9 + ... = 系列〜= O(3/2*n)= O(n)

因为3/2是常数.这里第k个循环将以n/^3k步进行.

请注意与链接问题的关键区别,外部循环运行n时间是固定的.