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

问题描述：

这是伪代码。我试图计算这个函数的时间复杂度，如this answer所说。它应该是这样的：这个伪代码的时间复杂度是多少？

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 
}

只需总结几何系列。 –

@AbhishekBansal就像这个'n + n/3 + n/9 + ...'？但这不是O（n）。 –

答

该算法将运行：

N + N/3 + N/9 + ... = series〜= O（3/2 * N）= O（N）

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

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