時間複雜度低於gcd算法

我一直覺得很難計算二進制GCD算法的時間複雜度，也就是所謂的斯坦因算法，它被賦予O（n^2），其中n是位數在兩個數字中較大的一個。它不應該是O（n）嗎？算法是如下：時間複雜度低於gcd算法

1.gcd（0，V）= V，因爲一切劃分爲零，且v是劃分訴數量最多類似地，滿足gcd（U，0）= U。 GCD（0,0）不被通常定義，但是可以很方便地設置GCD（0，0）= 0。

2.如果u和v都是偶數，則滿足gcd（U，V）= 2· gcd（u/2，v/2），因爲2是一個公約數。

3.如果u是偶數並且v是奇數，那麼gcd（u，v）= gcd（u/2，v），因爲2不是公約數。同樣，如果u是奇數，v是偶數，那麼gcd（u，v）= gcd（u，v/2）。如果u和v都是奇數，且u≥v，則gcd（u，v）= gcd（（u-v）/ 2，v）。如果兩者都是奇數，則gcd（u，v）= gcd（（v-u）/ 2，u）。這些是簡單的歐幾里得算法的一個步驟的組合，其在每個步驟使用減法，以及上述步驟3的應用。除以2得到一個整數，因爲兩個奇數的差值是偶數。[3]

5.重複步驟2-4直到u = v，或者（再多一步），直到u = 0。無論哪種情況，GCD都是2kv，其中k是步驟2中找到的公因子數2 。

來源

2013-08-27 notsogeek

它是O（n ），因爲在最壞的情況下，你用小於n的所有除數除以每個數字。 – jambono

Knuth第2卷有一個非常複雜的分析，似乎證實了輸入位數的步數是最差線性的明顯猜測。然而，對於非常大的n，每個減法需要以它自己的權利（例如由於多精度算術）被充電爲O（n），在這種情況下總費用爲O（n^2）

來源

2013-08-27 18:42:53 mcdowella

但是在這種情況下它不應該像O（log n）的減法 – notsogeek

但是'n = log（max（u，v）） '，而不是'n = max（u，v）'。我們不應該期待'log n'出現在任何地方。 – Teepeemm

時間複雜度低於gcd算法

回答

相關問題