如何计算这个算法的Big O？

Question

我想x++在下面的算法中计算Big O.

for (int i = 2;i < n;i*=2)
    for(int j = i;j < m;j*=j)
       x++;

我想了很多,但我无法解决它.我该如何解决？

Answer 1

O(lg(n) * lg(lg(m)))

最多lg(n)用于外环和lg(lg(m))另一个用于外环.

编辑:更多帮助证明:

让我们改变变量:

nn = lg(n);
mm = lg(m);

代码将变为:

for (int i = 1;i < nn;i++)
    for(int j = i;j < mm;j *= 2)
        x++;

现在运行时将是O(nn * lg(mm)).

编辑(2):绑定可以变得更紧(因为我们j = i在第二个循环中,没有j = 1)

如果nn >= mm那么(x++) = theta(mm * lg(mm)) = theta(lg(m) * lg(lg(m)))

和

如果nn < mm 那么(x++) = theta(nn * lg(mm)) = theta(lg(n) * lg(lg(m)))

Answer 2

显然,外部循环是O(log ₂(n)),因为i从2到n的每次迭代加倍.所以:

2 ^X < Ñ
⇔日志₂(2 ^X)<日志₂(Ñ)
⇔ X <日志₂(Ñ)

因此,它需要外循环的最多log ₂(n)次迭代,直到i < n不再满足为止,因此为O(log(n)).

内部有点棘手,因为外部循环的i的当前值用于初始化内部循环的j.另外,j在每次迭代时与其自身(即,j ²)相乘.所以:

Ĵ ^{2 X} < 米
⇔登录_Ĵ(Ĵ ^{2 X})<日志_Ĵ(米)
⇔2 ^X <日志_Ĵ(米)
⇔日志₂(2 ^X)<日志₂(日志_Ĵ(米))
⇔ X <日志₂(log _j(m))

因此,它最多需要内循环的log ₂(log _j(m))迭代,直到j < m不再满足条件,因此O(log(log(m))).如果我们忽略基数,我们可以估算O的总复杂度(log(n)·log(log(m))).