该代码的复杂性是多少减少值？

-1

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减少不寻常的方式的值。有没有一个标准的方法来解决这个问题？

来源

2013-10-08 Ahmed_Mohsen

如果N == 1和M == 0，您将得到一个无限循环。 –

对不起，我纠正它 –

此代码是Euclidean algorithm的天真执行。在每次迭代中，您将从较大的数字中减去较小的数字，以便将算法分成“阶段”。每个阶段包括从较大的数字中减去尽可能多的较小数字的副本，直到较大的数字低于较小的数字。（这与古希腊人知道的有关呼叫anythpharesis的程序有关）现代版本可能只是将更大的数字修改为更小的数字，已知该数字在O（log min {M，N }）步骤（这是现代欧几里得算法），并在每一步上花费O（1）次，假设数字表示为整数。

在这种情况下，我们知道会有O（log min {M，N}）个相位，但是每个相位不会花费一定的时间。使用任意故障后面的几何直觉，可以构造成对的数字，每个单独相位需要很长时间才能终止，因此我所知道的最佳界限是运行时间为O（N + M）。

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

希望这有助于！

来源

2013-10-08 20:39:25 templatetypedef

该代码的复杂性是多少减少值？

回答

相关问题