時間GCD代碼

Question

複雜我試圖理解下面的代碼的時間複雜度：

int gcd(int n, int m) { 
    if (n%m ==0) return m; 
    if (n < m) swap(n, m); 
    while (m > 0) { 
     n = n%m; 
     swap(n, m); 
    } 
    return n; 
} 

我看了上面的代碼的複雜度是Θ（LOGN）。有人可以向我解釋它背後的邏輯嗎？

Answer 1

考慮算法的任何兩個步驟。

在某些時候，你有數字（A，B）與A> B。在第一步驟之後，這些轉向（B，C）與C = A MOD b，和在第二步驟之後的兩個數字將是（C，d）與d = b的MODÇ。

現在回想一下。由於d = b mod c，我們知道b = kc + d對於某些k> 0。最小的可能性是k = 1，因此b≥1c + d = c + d。

從該結果和從a> b我們得到a> c + d。如果我們加上剛剛推導出來的最後兩個不等式，我們可以得到（a + b）> 2（c + d）。換言之，在每兩個連續的步驟之後，兩個數字的總和減少到小於其原始大小的一半。

現在看看算法的第一步。在開始時，我們有一些（a，b）與a> b。在第一步之後，我們有（b，c）與c = a mod b，並且清楚地b> c。因此，在第一步之後，兩個數字至多等於兩個輸入數字中較小的一個。

將這兩個結果放在一起，我們可以得出結論：迭代次數（其他實現中的遞歸調用）在較小的輸入數中最多爲對數。 換句話說，在較小的輸入數中，迭代次數最多與數字的數量成線性關係。