这个算法的时间复杂度是否为Θ(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)？

- Da Mike

---

第一印象我认为是O(n^2)的循环，外部的for循环是n，内部的while循环也是n。 - Seek Addo

@SeekAddo 我觉得如果你进行一些计算，你会发现存在一个比n^2更好的边界。 - Da Mike

еҶ…йғЁеҫӘзҺҜзҡ„иҝҗиЎҢж—¶й—ҙдёәO(log(n-i))пјҢеҰӮжһңдҪ жІЎжңүиҜҙи§ЈеҶіж–№жЎҲжҳҜO(n)пјҢжҲ‘зҡ„第дёҖдёӘжғіжі•е°ұжҳҜO(n*log(n))гҖӮ - Keiwan

@Keiwan：内部循环的运行时间为O(log(n/i))，而不是O(log(n-i))。 - user2357112

哎呀，是的，你当然是对的。 - Keiwan

不应忘记，复杂性来自于限制行为，因此，与外部线性增长循环相比，内部指数级增长的循环变得多余（仅因为内部循环从i开始）。 - philkark

Answer 1

问题在于你的公式与他们的等效。 您只需要知道一些数学：

前两个变换只是基本的对数属性，第三个变换是斯特林逼近。

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

- Salvador Dali

---

提到斯特林公式，点赞。 - Shravan40

非常感谢您，Dali先生！ - Da Mike

Answer 2

另一种证明方法可能是：

其中，

- kkonrad

---

但是内部循环执行的次数恰好为 ceiling{ log(n^n/n!) } - 1 次。没有关于此的大O符号说明。 - Da Mike

@kkonrad 嗯，他应该写成 ln n! = n ln n - n + O(ln n) = n ln n - Theta(n) 来表示斯特林公式，但也差不多啦。 - David Eisenstat

@kkonrad 这已经足够了，因为n ln n项是精确的。 - David Eisenstat

@DavidEisenstat，现在我明白你的意思了。是的，将其准确化会很好。PS从未知道Stirling公式可以以这种方式表达。好好知道。谢谢！ - kkonrad

@kkonrad 然后您可以更新您的答案，删除声明我的答案错误的部分。此外，如果您阅读我的答案，您会看到一个链接，其中明确说明了David所说的：“ln（n！）= n ln n-n + O（ln n）”。 - Salvador Dali

Answer 3

复杂度为Θ(n)。确切的运行时间是2n。

看一下这个：

import math

def get_complexity(n):
    counter = 0

    for i in range(1,n):
        j = i
        while j < n:
            j = 2 * j
            counter += 1

    print('n: %16d\niterations:  %6d\n2n:  %14d \n' % (n, counter, 2*n))


for ten in range(1,5):
    get_complexity(10 ** ten)

输出：

n:               10
counter:         16
2n:              20

n:              100
counter:        194
2n:             200

n:             1000
counter:       1990
2n:            2000

n:            10000
counter:      19990
2n:           20000

n:           100000
counter:     199988
2n:          200000

- Martin Gottweis

---

我不认为这会有太大的影响，但我认为你应该将 for i in range(1,n) 更改为 for i in range(1,n+1)。因为如果我没记错的话，range(1, n) 会给出 [1, 2, 3, .. n-1]。 - Da Mike