什么是Stein算法的最坏情况输入？

Question

我正在尝试得出Stein算法（二进制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的相关部分，但我认为它有点超出了我当前的理解范围，因为我觉得它没有什么意义。

- Pilkoid

Answer 1

您想要一个递归关系，表示u和v的位数，而不是stein（u，v）的值，因此让我们进行一些推理。
给定任意的u和v，最好和最坏的情况是什么？
最好的情况（我们很快就能完成）：其中一个常数时间情况。
最坏的情况：对stein（u/2，v/2），stein（u，v/2）或stein（较大-较小/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）。

- Jean-Bernard Pellerin

Answer 2

您正在寻找一条规则，该规则依赖于使用尽可能大的子问题大小（相对于问题大小）递归地评估函数。有两个规则需要解决一个比特少的子问题：处理恰好一个u或v为奇数的情况的规则。奇数不变，偶数应尽可能保持偶数。这表明以下是最坏情况：（1）未作为基本情况处理的最小奇数整数（2）自由增长的2的幂次。也就是说，取u = 3和v=2^n，其中n是某个数字。在这种情况下，stein的运行时间与输入位数成线性关系。

- Patrick87

---

2^n 总是偶数。你想要像 v' = v*2 + 3 这样的东西。 - Jean-Bernard Pellerin

@Jean-BernardPellerin 我忽略了减法的时间复杂度是O(n)。有了这个观察结果，这种情况肯定是最糟糕的，你是正确的。 - Patrick87