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

Question

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

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/3^k步骤运行。