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 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;
}

根据 log(n) 绘制 T(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 时，就会出现“最坏”情况，在这种情况下，内部循环始终执行一次。

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