斯坦因算法的最壞情況輸入是什麼？

Question

我試圖想出斯坦因算法（二進制GCD算法）的遞推關係，但是我通過它追蹤的能力證明不是從頭開始的。

我完全被多重路徑和遞歸調用所困擾，以及我們正在處理的總位數代表我們的值而不是值本身。

這裏的算法：

stein(u, v): 
    if either of u or v are 0: return their sum. 
    if either of u or v are 1: return 1. 
    if both u and v are even: return 2 * stein(u/2, v/2) 
    if u is even and v is odd: return stein(u/2, v) 
    if u is odd and v is even: return stein(u, v/2) 
    if both u and v are odd: return stein(larger-smaller/2, smaller) 

我試圖找到遞推關係T（n），其中n是同時代表u和v我覺得這裏的第一步所需的位的總數。對於我來說，應該在最糟糕的情況下發揮作用。

我認爲每個除法操作都會將位數減1，但這是我迄今瞭解最多的。

我試過跟蹤算法，但無濟於事。我還閱讀了Knuth Vol。的相關部分。 2但我認爲這有點超出了我理解的範圍，因爲它對我來說沒有意義。

Answer 1

你想要一個遞推關係，它表示u和v中的位數，而不是stein（u，v）的值，所以讓我們通過一點來推斷它。
鑑於任意u和v，最好和最壞的情況是什麼？

最好的情況下（我們快速完成）：一個不變的情況。

最壞的情況：以斯坦遞歸調用（U/2，V/2），斯坦因（U，V/2），或斯坦（較大較小/ 2，更小）

• 在第一種情況是我們將值減半，這隻會刪除兩個二進制數字。這需要我們做一次手術。 T（n）= T（n-2）+ 1

• 在第二種情況下，我們只將其中一個值分開，因此只比我們開始時少了1個數字。這採取了一個操作。 T（n）= T（n-1）+ 1

• 第三種情況變得更糟。減法遍歷n中的所有數字。這意味着如果我們失去了m位數，但使用了n個步驟（減法），我們的遞歸是T（n）> = T（n-m）+ n。我們仍然需要找到m，如果我們可以證明這一步消除了許多數字（例如：m = n/2），那麼重現可能不會太慢​​。
  不幸的是，我們很容易想出一個非常糟糕的情況。
  將v設置爲3.這確保我們很奇怪，並且它總是兩者中較小的一個。現在，如果我們設定u使得（u-v）/ 2繼續爲奇數，那麼重現將繼續到第三種情況。而在v = 3時，（u-v）/ 2只比u短1個數字。這意味着在最壞的情況下，m爲1 ==> T（N）= T（N-1）+ n表示不良情形的

例如：（21,3） - >（9,3 ） - >（3,3）我們可以繼續用v'= v * 2 + 3來構造更大的數字。正如你所看到的，這些「壞」數字的增長是一次一個二進制數字，並且會導致我們總是走在第三條路上。這就是爲什麼m是1。

這最後復發的情況是不幸的是O（N * N）

Answer 2

您正在尋找依靠以儘可能大的子問題大小（相對於問題的規模）地評價遞歸函數的規則。有兩條規則需要用少一點來解決子問題：規則處理u或v中有一個是奇數的情況。奇數不會改變，偶數應該儘可能長。這表明以下是最壞的情況：（1）最小的奇數整數不作爲基本情況處理（2）自由增長的2的冪。也就是說，取u = 3和v=2^n對於一些n。在這種情況下，stein的運行時間在輸入位數上是線性的。