該代碼的複雜性是多少減少值？

-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

該代碼的複雜性是多少減少值？

回答

相關問題