GCD - 歐幾里德算法和分解算法分析

Question

正如我在準備我的算法導論類期中考試，我準備，雖然以前的一些測試教授發佈，我發現這樣一個問題：

計算GCD（312455）兩大方法：找出每個數的因式分解，並使用Euclid算法。每種方法的複雜性是什麼？

他的回答是：

gcd(455,312) = gcd(312,143) = gcd(143,26) = gcd(26,13) = gcd(13,0) = 13 

factors(312)= {2, 3, 13} factors(455)= {5, 7, 13} 

複雜性：

• GCD - log(n)
• 因素 - sqrt(n)

他是如何到達的複雜性？

Answer 1

給定的複雜性是粗糙的最壞情況界需要的算術運算次數：

• 歐幾里德算法：對於a >= b我們gcd(a,b) = gcd(b, a mod b)其中min(b, a mod b) < a/2，所以最多兩個削減步驟後，我們至少有一個第一個操作數減少了1/2。因此，對於某些常數c，還原步驟的數量受a的對數約束，基準爲sqrt(2)，其爲c * log(a)。

• 因式分解：爲了檢驗數字的素數或分解素數的平方，只需檢查數字的平方根即可。如果給定的數字具有較小的因子，那麼我們需要更少的可分性測試。所以需要的部門數量很容易被sqrt(a)+sqrt(b)限制。由於最多可以有ld(a)因子a和​​其餘的比較和乘法得到gcd也受sqrt(a)約束。

Answer 2

要分析歐幾里德GCD，你必須選擇最差情況下的值：我個人發現斐波那契對最適合這個問題。例如。

EGCD(121393, 75025) = 1; // With 24 iterations (or recursive calls). 

在這個 「序」 請看：

隨着斐波那契數對，我們注意到：

121393 % 75025 == 121393 - 75025 == 46368. 

因此，存在121393/46368 = **2.61** (more or less);

減少的因素

當然，最壞的情況下運行時間會使用Small Oh Notation，因爲最好的例子是Omega（1），換句話說就是Constant Time，例如，當股利是1000，除數是2時。

既然我們已經減少的因素，我們被允許把像遞推關係如下：

你必須要知道，這在運行時間適用完全相同的重複同樣的方式EGCD算法的版本。