查找算法的指令数 [英] Find the number of instructions of an algorithm

问题描述

给出此算法（a> 0，b> 0）：

Given this algorithm (a>0, b>0) :

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

我的问题：我必须找到该算法的时间复杂度，并且这样做，我必须找到指令数量，但找不到。有没有办法找到这个数字，如果没有，我如何找到它的时间复杂度？

My question : I have to find the time complexity of this algorithm and to do so, I must find the number of instructions but I couldn't find it. Is there a way to find this number and if not, how can I find its time complexity ?

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

What I have done : First of all I tried to find the number of iterations of the first loop and I found a pattern : a_i = a - (i(i+1)/2)*b where i is the number of iterations. I've spent hours doing some manipulations on it but I couldn't find anything relevant (I've found weird results like q² <= a/b < q²+q where q is the number of iterations).

推荐答案

您已经正确计算出<$ c $之后的 a 值c> i 内循环的第一个迭代是：

You have correctly calculated that the value of a after the i-th iteration of the inner loop is:

其中 a_j0 是 a 在 j 次外循环。内循环的停止条件为：

Where a_j0 is the value of a at the start of the j-th outer loop. The stopping condition for the inner loop is:

可以将其解决为二次不等式：

Which can be solved as a quadratic inequality:

因此，内部循环大约为 O（sqrt（a_j0 / b））。 a 的 next 起始值满足：

Therefore the inner loop is approximately O(sqrt(a_j0 / b)). The next starting value of a satisfies:

大致缩放为 sqrt（2b * a_j0）。精确地计算时间复杂度将非常繁琐，因此让我们从此处开始应用上述近似值：

Scaling roughly as sqrt(2b * a_j0). It would be quite tedious to compute the time complexity exactly, so let's apply the above approximations from here on:

其中 a_n 替换 a_j0 和 t_n 是内部循环的运行时间–当然，总的时间复杂度只是 t_n 的总和。请注意，第一项由 n = 1 给出，并且 a 的输入值定义为 a_0 。

Where a_n replaces a_j0, and t_n is the run-time of the inner loop – and of course the total time complexity is just the sum of t_n. Note that the first term is given by n = 1, and that the input value of a is defined to be a_0.

在直接解决此重复项之前，请注意，由于第二项 t_2 已经与第一个 t_1 的平方根成比例，而后者在总和中占所有其他项。

Before directly solving this recurrence, note that since the second term t_2 is already proportional to the square root of the first t_1, the latter dominates all other terms in the sum.

因此，总时间复杂度仅为 O（sqrt（a / b）） 。

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

---

更新：数值测试。

---

Update: numerical tests.

请注意，由于 a 的所有值变化均与 b 成正比，因此所有循环条件均为也与 b 成正比，可以通过设置 b = 1 来规范化 并且只改变 a 。

Note that, since all changes in the value of a are proportional to b, and all loop conditions are also proportional to b, the function can be "normalized" by setting b = 1 and only varying a.

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

Javascript test function, which measures the number of times that the inner loop executes:

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）：

令人信服的直线，确认时间复杂度的确是一半。

A convincing straight line which confirms that the time complexity is indeed half-power.

这篇关于查找算法的指令数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！