斯坦因算法的最坏情况输入是什么？

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的运行时间在输入位数上是线性的。