这个算法的时间复杂度是Θ(n)吗？

Question

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

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)？

Answer 1

问题在于你的公式与他们的公式相同.你只需要知道一些数学:

前两个转换只是基本的对数属性,第三个是斯特林的近似.

显然每个人都知道这一点 n = ?(n)