这个算法的复杂度是多少？

Question

我正在学习如何找出算法的复杂度，但我无法弄清楚这个算法的复杂度是多少。有人可以向我解释如何获得答案吗？

void algorithm(int a, int b) {
    while (a >= b) {
        int x = a - b;
        for (int i = 0; i <= x; i++) {
            std::cout << "complexity of this algorithm?";
        }
        a = x;
    }
}

欢迎任何意见。这是我目前所拥有的：

Answer 1

由于修改了a，所以总和的参数中应该有：

(1) x = a - b  // first iteration
(2) x = a - 2b // second iteration
(3) x = a - 3b
...

如果a = k * b，外循环迭代k次。因此，最终的复杂度是：

(a - b) + (a - 2b) + ... + (a - (k-1) b) = 
(k-1) b + (k-2) b + ... + b = k * (k-1) * b/2

正如你所说 $k \leqslant \lceil\frac{a}{b} \rceil$ , 时间复杂度为 $O\left(\lceil\frac{a}{b} \rceil \times a\right)$ .

Answer 2

复杂度为(a^2/b)

正如我在图片中描述的那样，你需要将所有“x”相加，然后你就会得到复杂度。

in summation part for (-b -2b -3b - ... -nb) you can write :
[![enter image description here][1]][1]-b (1+2+...)
so this is -b*(n(n+1)/2)

summation_part_definition_link

所以最后，如果“a”和“b”是同一个订单，那么结果是：

O(c) = 0 (c is numeric)

这意味着复杂性是按数字顺序排列的。但是如果“a”是高阶那么结果是：

O((a^2)/b)

这个算法的复杂度是多少？

What's complexity of this algorithm?

algorithm

code-complexity