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

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 +…= series ~= O(3/2 * n) = O(n)

，因为3/2是常数。这里第k个循环将运行n/3^k步。

---

请注意与链接问题的关键区别，其中外循环运行n次并且这是固定的。