重复减去值的代码有多复杂？

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})阶段,但每个阶段都不会花费一定的时间.使用任意阶段背后的几何直觉,可以构造数字对,其中每个阶段需要很长时间才能终止,因此我所知道的最佳界限就是说运行时为O(N + M).

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

希望这可以帮助!