帮助找到该算法的复杂性

Question

我试图找到这个算法的复杂性：

m=0;
i=1;
while (i<=n)
{
   i=i*2;
   for (j=1;j<=(long int)(log10(i)/log10(2));j++)
     for (k=1;k<=j;k++)
          m++;
}

我认为它是 O(log(n)*log(log(n))*log(log(n)))：

• “i”循环运行直到 i=log(n )
• 'j' 循环运行直到 log(i) 意味着 log(log(n)) '
• k' 循环运行直到 k=j --> k=log(i) --> k=log(log(n))

因此 O(log(n)*log(log(n))*log(log(n)))。

Answer 1

时间复杂度为Theta(log(n)^3)。

令 T = 下限 (log_2(n))。您的代码可以重写为：

  int m = 0;
  for (int i = 0; i <= T; i++)
   for (int j = 1; j <= i+1; j++)
    for (int k = 1; k <= j; k++)
     m++;

这显然是 Theta(T^3)。

编辑：这是重写代码的中间步骤。令 a = log_2(i)。 a 始终是整数，因为 i 是 2 的幂。那么您的代码显然相当于：

m=0;
a=0;
while (a<=log_2(n))
{
   a+=1;
   for (j=1;j<=a;j++)
     for (k=1;k<=j;k++)
          m++;
}

我所做的其他更改是将 Floor(log_2(n)) 命名为 T，将 a 命名为 i，并使用 for 循环而不是 a尽管。

希望现在已经清楚了。

Answer 2

这是作业吗？

一些提示：

我不确定代码是否做了它应该做的事情。 log10 返回一个浮点值，转换为 (long int) 可能会减少 0.9999999999。我不认为这是有意的。该行可能看起来像这样：

for (j=1;j<=(long int)(log10(i)/log10(2)+0.5);j++)

在这种情况下，您可以将其重写为：

m=0;
for (i=1, a=1; i<=n; i=i*2, a++)
    for (j=1; j<=a; j++)
        for (k=1; k<=j; k++)
            m++;

因此，您对“j”和“k”循环的复杂性假设是错误的。
（外层循环运行 log n 次，但 i 一直增加到 n，而不是 log n）