time - 嵌套的 for 循环复杂度

Question

每个案例（广告）的增长函数是什么？
我很难找到每个嵌套 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)))使用斯特林近似

确切数字：（是[X]X 的整数部分）

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

这里有一个小检查：我用一个计数器实现了 for 循环，这是 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 和 M 之间有（+1 实际上）2 的幂，所以M = sqrt(N)你得到公式。

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

3. i从1到sqrt(N)。对于每一个i，都有ijs。和之前一样，我们将每个 js 的数量相加i：
   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翻倍。例如，这意味着该for循环对 N= 和 N=执行相同数量的操作 ( 131072) 。当变为（再多一个）时，操作数加倍（）。N=65536131071N131072262144

Answer 2

您可以使用 Sigma 表示法正式解决代码片段：

一个）

b)

C）

d)