循环运行日志时间时的复杂性

Question

如果我们找到没有。一个数字的因素，我们可以使用以下高效循环。 for(i=1;i<=sqrt(n);i++)，其中 n 是要找到其因子的 'no'。这个循环的复杂度为 O(n)。

以下代码片段的时间复杂度是多少？（假设 log(x) returns 以 2 为底数的对数值）。 O(n^2) 还是 O(n logn)？（我假设 log n 是循环除以二时的复杂度。即 i/=2）

void fun()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=log(i);j++)
            printf("hello world");
}

Answer 1

内部循环调用 printf 大约 log(i) 次，i 次 [1..n]。总调用次数约为

log(1)+log(2)+log(3)+...log(n) = log(n!)

现在，斯特林渐近公式将为您解答。

对于以 2 为底的对数，精确计数由

给出

0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + ... + floor(Lg(n))

或

1.0 + 2.1 + 4.2 + 8.3 + ... + k.floor(Lg(n))

为方便起见，假设 n 的形式为 n=2^m-1，因此最后的运行是完整的（和 k=2^(m-1)）。

现在从 0 到 m-1 取 x^k 的总和，等于 (x^m-1)/(x-1) 并推导 x 得到 x^k.k。计算 x=2，你得到

s = m.2^m-2^m+2 = (n+1).Lg(n+1)-n+1

对于其他n，您需要为最后一个部分运行添加一个修正项。随着 m=floor(Lg(n+1)):

t = m.(n+1-2.2^m)

Answer 2

您的代码中 "Hello world" 的实际打印数量是：

然后您可以使用 Srinivasa Ramanujan approximation 的 log(n!):

得到整个代码的实际复杂度，即O(n logn)

Answer 3

无需任何数学即可证明 O(n*Log(n)) 的上限。

void fun()
{
   int i,j;
   for(i=1;i<=n;i++)
       for(j=1;j<=log(n);j++)    // << notice I changed "i" to "n" 
           printf("hello world");
}

上面的函数会运行N次内循环，内循环会运行log(N)次。

因此，该函数将运行正好 nLog(n) 次。

因为这个函数

 (log(n) + log(n) + ... + log(n)) // n times

大于 OP 版本

(log(1) + log(2) + ... + log(n))

那就是原版的上界

<= O(n log(n)

Complexity when loop runs log times