c++ - 这段重复减去值的代码的复杂性是什么？

Question

我有这段代码，想知道它的时间复杂度：

    int N,M; // let N and M be any two numbers 
    while(N != M && N > 0 && M > 0){
       if(N > M)N -= M;
       else M -= N;
    }

我不知道如何分析这一点，因为 M 和 N 的值以不寻常的方式下降。有没有标准的方法来解决这个问题？

Answer 1

此代码是欧几里得算法的简单实现。在每次迭代中，您都从较大的数字中减去较小的数字，因此您可以将算法划分为“阶段”。每个阶段都包括从较大的数字中减去尽可能多的较小数字的副本，直到较大的数字低于较小的数字。（这与古希腊人知道的称为anythpharesis的程序有关）现代版本可能只是用较小的数字来修改较大的数字，已知该数字在 O(log min{M, N}) 内终止步骤（这是现代欧几里得算法）并在每个步骤上花费 O(1) 时间，假设数字表示为整数。

在这种情况下，我们知道会有 O(log min{M, N}) 个阶段，但每个阶段不会花费恒定的时间。使用anythpharesis 背后的几何直觉，可以构造成对的数字，其中每个单独的阶段需要很长时间才能终止，所以我知道的最佳界限是说运行时间是 O(N + 米）。

简而言之：与以对数时间运行的现代实现相比，此代码效率低下。很难在运行时获得一个好的上限，但实际上这并不重要，因为您可能只是重写代码以提高效率。:-)

希望这可以帮助！