具有两个嵌套循环的算法的时间复杂度

Question

鉴于此算法：

m = 1
while(a>m*b){
   m = m*2
}

while(a>=b){
   while(a>=m*b){
      a = a-m*b
   }
   m=m/2
}

我的问题：这个算法的时间复杂度是多少？

我做了什么：我必须找到指令的数量。所以我发现，第一次大约有 m=log_2(a/b) 次迭代。现在，对于该算法第二部分的内部 while，我发现了这种模式： a_i = a - i*m 其中 i 是迭代次数。所以内部 while 有 a/bm 次迭代。
但是我现在不知道如何计算外部，因为条件取决于内部 while 对 a 做了什么。

Answer 1

让我们从 "normalizing" 函数开始，方法与您的相同，请注意 a 中的所有更改并且停止条件与 b:

成正比

n = a/b

// 1)
m = 1
while(n>m){
   m = m*2
}

// 2)
while(n>=1){
   while(n>=m){
      n = n-m
   }
   m=m/2
}

不幸的是，相似之处到此为止...

片段 1)

请注意 m 可以写成 2 的整数次方，因为它会在每个循环中加倍：

i = 0
while (n > pow(2, i)) {
   i++
}
// m = pow(2, i)

从停止条件：

片段 2)

此处 m 以与 1) 完全相反的方式减少，因此它可以再次写成 2 的幂：

// using i from the end of 1)
while (n>=1) {
   k = pow(2, i)
   while (n >= k) {
      n = n - k
   }
   i--
}

内循环比你上一个问题的内循环更简单，因为m内部没有变化。很容易推导出它执行的次数c，最后n的值：

这是 "C-family" 语言中 Modulus operator % 的确切定义：

while (n>=1) {
   k = pow(2, i)
   n = n % k      // time complexity O(n / k) here instead of O(1)
   i--
}

请注意，由于 k 的连续值仅相差 2，因此 n 的值绝不会大于或等于 2k；这意味着内部循环每个外部循环最多执行一次一次。因此外循环最多执行i次.

Both the first and second loops are O(log n), which means the total time complexity is O(log n) = O(log [a/b]).

更新：Javascript中的数值测试和以前一样。

function T(n)
{
   let t = 0;

   let m = 1;
   while (n > m) {
      m *= 2; t++;
   }

   while (n >= 1) {
      while (n >= m) {
         n -= m; t++;
      }
      m/=2;
   }

   return t;
}

绘制 T(n) 对 log(n) 显示一条漂亮的直线：

编辑：对片段的更详尽解释 2).

在代码段 1) 的末尾，i = ceil(log2(n)) 的值表示二进制文件中的 有效位数 整数的表示 ceil(n).

计算具有 2 的正幂 2^i 的整数的模等于丢弃除第一个 i 位以外的所有位。例如：

n     = ...00011111111   (binary)
m     = ...00000100000   (= 2^5)
n % m = ...00000011111
                 -----   (5 least significant bits)

片段 2) 的操作因此等同于删除 n 的最高有效位，一次一个，直到只剩下零。例如：

 outer loop no |           n
 ----------------------------
 1             | ...110101101
               |    ^
 2             | ...010101101
               |     ^
 3             | ...000101101
               |      ^
 4             | ...000001101
               |       ^ 
 :             | :
 :             | :
 i (=9)        | ...000000001
               |            ^
 ----------------------------
 final         |    000000000

当当前最高位（^指向）为：

0：内部循环不执行，因为n的值已经小于k = 2^i（等于^的位位置值）。
1：内循环执行一次，因为n大于k，但小于2k（对应当前位置^上方的位）。

因此，当 n 的所有有效位都为 1 时，就会出现 "worst" 情况，在这种情况下，内部循环 to 总是执行一次。

无论如何，对于 n.

的 any 值，外循环执行 ceil(log2(n)) 次

具有两个嵌套循环的算法的时间复杂度

Time complexity of an algorithm with two nested loops

algorithm

complexity-theory

time-complexity