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

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

让我们开始“标准化”函数，就像在您的previous question 中一样。 ，再次注意到 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的值:

这是 Modulus operator % 的确切定义在语言的“C 族”中:

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 时，“最坏”的情况就会发生，在这种情况下，内部循环 to 总是执行一次。

无论如何，对于 n 的 any 值，外层循环执行 ceil(log2(n)) 次。