time - 嵌套的 for 循环复杂度

Question

每个案例 (a-d) 的增长函数是什么？
我很难找到每个嵌套 for 循环的运行时间。我想我已经找到了其中一些，但我不确定。

一)

for(i = 1; i*i <= N; i = 2*i);

b)

for(i = 1; i <= N; i = 2*i);
    for(j = 1; j <= i; j = j+1);

c)

for(i = 1; i*i <= N; i=i+1);
    for(j=1; j <= i ; j=j+1);

d)

for(i = 1; i*i <= N; i=i+1)
    for(j = 1; j <= i ; j = 2*j);

Answer 1

这是我得到的:

增长:

1. O(log(sqrt(N)))
2. O(N)
3. O(N)
4. O(log(sqrt(N)!)) = O(sqrt(N)*log(sqrt(N))) 使用 Stirling's approximation

精确数字:([X] 是 X 的整数部分)

1. [log([sqrt(N)])]+1
2. 2^([log(N)]+1)
3. [sqrt(N)]*[sqrt(N)+1]/2
4. 不太确定。

这里有一个小检查:我用一个计数器实现了 for 循环，这是 N=10000000 的输出:

a(N)= 12           a(10*N)= 14
b(N)= 16777216     b(10*N)= 134217728
c(N)= 5000703      c(10*N)= 50005000
d(N)= 33861        d(10*N)= 123631

编辑:根据要求，解释
首先，一些考虑:

• 我们处理的是整数，因此对于您看到的任何实数函数(基本上是 sqrt 和 log)，您实际上应该取整数部分。
• 几乎在计算机科学中，log = log base 2

现在:

1. i 从 1 到 sqrt(N)，但它只“使用”2 的幂。有 log(M )(实际上是 +1)1 和 M 之间的 2 的幂，因此使用 M = sqrt(N) 可以得到公式。

2. i 从 1 到 N 2 的幂，和以前一样。对于每个 i 都有 i js。如果我们对每个 i 的 js 求和:
   1 + 2 + 4 + 8 + 16 + ... + 2^log(N) = 2N - 1 = O(N)

3. i 从 1 到 sqrt(N)。对于每一个i，都有i个js。和之前一样，我们对每个i的js数量求和:
   1 + 2 + 3 + 4 + 5 + ... + sqrt(N) = sqrt(N) * sqrt(N+1)/2 = O(N)

   <

4. i 从 1 到 sqrt(N)。对于每个 i，j 从 1 到 i 仅使用 2 的幂，因此对于每个 i 你有 log(i) js。如果你对每个 i 的所有 js 求和:

   log(1) + log(2) + log(3) + log(4) + log(5) + ... + log(sqrt(N))
   对于对数 log(a) + log(b) = log(a*b) 的性质。将其应用于我们的总结:
   log(1*2*3*4*5*..*sqrt(N)) = log(sqrt(N)!)
   这是结果。鉴于阶乘对于大数来说是个问题，您可以使用斯特林近似:ln(N!) -> N*log(N) - N 对于大数。

使用整数部分的差异示例

考虑 2。log(N) 的整数部分保持不变，直到 N 翻倍。这意味着，例如，对于 N=65536 和 N=，此 for 循环执行相同数量的操作 (131072) >131071。当 N 变为 131072(仅多一个)时，操作数翻倍(262144)。