algorithm - 该算法的时间复杂度是否为Θ(n)？

我想找到以下算法的时间复杂度

for i=1 to n do
    j=i
    while j<n do
        j=2*j

我做了计算，发现T(n) = log(n^n/n!)。

但是正确的答案应该是T(n) = Θ(n)。

我说错了吗还是log(n^n/n!) = Θ(n)？

最佳答案

问题是您的公式等于他们的公式。您只需要知道一些数学运算:



其中前两个转换只是基本的日志属性，第三个是Stirling's approximation。

显然每个人都知道n = Θ(n)

关于algorithm - 该算法的时间复杂度是否为Θ(n)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37666140/