查找算法的指令数

Question

鉴于此算法 (a>0, b>0)：

while(a>=b){
   k=1;
   while(a>=k*b){
      a = a - k*b;
      k++;
   }
}

我的问题：我必须找到这个算法的时间复杂度，为此，我必须找到指令的数量，但我找不到。有没有办法找到这个数字，如果没有，我怎样才能找到它的时间复杂度？

我做了什么：首先我试图找到第一个循环的迭代次数，我找到了一个模式：a_i = a - ( i(i+1)/2)*b 其中 i 是迭代次数。我花了几个小时对它进行一些操作，但我找不到任何相关的东西（我发现了奇怪的结果，比如 q² <= a/b < q²+q 其中 q 是迭代次数）。

Answer 1

您已经正确计算出 a 在内循环的第 i 次迭代后的值为：

其中 a_j0 是 a 在第 j 外循环开始时的值。内循环的停止条件为：

可以解为二次不等式：

因此内循环大约是O(sqrt(a_j0 / b))。 a的next起始值满足：

大致按 sqrt(2b * a_j0) 缩放。准确计算时间复杂度会非常繁琐，所以让我们从这里开始应用上述近似值：

其中a_n代替了a_j0，而t_n是内层循环的运行-时间——当然总的时间复杂度只是t_n。注意第一项由n = 1给出，a的输入值定义为a_0.

在直接解决这个递归之前，请注意，由于第二项 t_2 已经与第一项 t_1 的平方根成正比，因此后者在总和中支配所有其他项。

The total time complexity is therefore just O(sqrt(a / b)).

更新：数值测试。

注意，由于a值的所有变化都与b成正比，所有循环条件也与b成正比，所以函数可以"normalized" 通过设置 b = 1 并且只改变 a.

Javascript测试函数，测量内循环执行的次数：

function T(n)
{
   let t = 0, k = 0;
   while (n >= 1) {
      k = 1;
      while (n >= k) {
          n -= k;
          k++; t++;
      }
   }
   return t;
}

sqrt(n) 对 T(n) 的情节：

一条令人信服的直线，证实时间复杂度确实是半幂。

查找算法的指令数

Find the number of instructions of an algorithm

algorithm

complexity-theory

time-complexity