Stein 算法的最坏情况输入是什么？
What is the Worst-Case Input for Stein's Algorithm?
我正在尝试提出 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 但我认为它有点超出我目前的理解范围，因为它对我来说意义不大。
你想要一个表示 u 和 v 中位数的递归关系，而不是 stein(u,v) 的值，所以让我们稍微推理一下。
给定任意的 u 和 v，最好和最坏的情况是什么？
最佳情况（我们很快完成）：恒定时间情况之一。
最坏情况：递归调用 stein(u/2, v/2), stein(u,v/2), or stein(larger-smaller/2, smaller)
在第一种情况下，我们将值减半，这将简单地删除两个二进制数字。这样做花了我们一次手术。 T(n) = T(n-2) + 1
在第二种情况下，我们只对其中一个值进行除法，因此只比开始时少 1 位。这需要一次手术。 T(n) = T(n-1) + 1
第三种情况更加丑陋。减法迭代 n 中的所有数字。这意味着如果我们丢失了 m 个数字，但使用了 n 个步骤（减法），我们的递归是 T(n) >= T(n-m) + n。我们还是要找到m，如果我们能证明这一步消除了很多数字（ex: m = n/2），那么递归可能不会太慢。
不幸的是，我们很容易想出一个非常糟糕的场景。
将 v 设置为 3。这向我们保证它是奇数，并且它始终是两者中较小的一个。现在，如果我们将 u 设置为 (u-v)/2 继续为奇数，则递归将继续进行到第三种情况。当 v=3 时，(u-v)/2 只会比 u 少一位。这意味着在最坏的情况下 m 为 1。 ==> T(n) = T(n-1) + n
这种糟糕情况的例子：(21,3) -> (9,3) -> (3,3) 我们可以通过取 v' = v*2 + 3 继续构建更大的数字。正如你看，这些 "bad" 数字的增长一次是一个二进制数字，这将导致我们总是走第三条路。这就是为什么 m 是 1.
不幸的是，最后一个重复场景是 O(n*n)
您正在寻找一个规则，该规则依赖于使用尽可能大的子问题大小（相对于问题大小）递归地评估函数。有两个规则需要用少一位来解决子问题：处理 u 或 v 中恰好有一个为奇数的情况的规则。奇数不变，偶数应尽可能长时间保持偶数。这表明以下是最坏的情况：（1）未作为基本情况处理的最小奇数整数（2）自由增长 2 的幂。也就是说，对某些 u = 3 和 v=2^n n。在这种情况下，stein 的 运行 时间与输入的位数成线性关系。
我正在尝试提出 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 但我认为它有点超出我目前的理解范围，因为它对我来说意义不大。
你想要一个表示 u 和 v 中位数的递归关系，而不是 stein(u,v) 的值，所以让我们稍微推理一下。
给定任意的 u 和 v，最好和最坏的情况是什么？
最佳情况（我们很快完成）：恒定时间情况之一。
最坏情况：递归调用 stein(u/2, v/2), stein(u,v/2), or stein(larger-smaller/2, smaller)
在第一种情况下，我们将值减半，这将简单地删除两个二进制数字。这样做花了我们一次手术。 T(n) = T(n-2) + 1
在第二种情况下，我们只对其中一个值进行除法，因此只比开始时少 1 位。这需要一次手术。 T(n) = T(n-1) + 1
第三种情况更加丑陋。减法迭代 n 中的所有数字。这意味着如果我们丢失了 m 个数字，但使用了 n 个步骤（减法），我们的递归是 T(n) >= T(n-m) + n。我们还是要找到m，如果我们能证明这一步消除了很多数字（ex: m = n/2），那么递归可能不会太慢。
不幸的是，我们很容易想出一个非常糟糕的场景。
将 v 设置为 3。这向我们保证它是奇数，并且它始终是两者中较小的一个。现在，如果我们将 u 设置为 (u-v)/2 继续为奇数，则递归将继续进行到第三种情况。当 v=3 时，(u-v)/2 只会比 u 少一位。这意味着在最坏的情况下 m 为 1。 ==> T(n) = T(n-1) + n
这种糟糕情况的例子：(21,3) -> (9,3) -> (3,3) 我们可以通过取 v' = v*2 + 3 继续构建更大的数字。正如你看，这些 "bad" 数字的增长一次是一个二进制数字，这将导致我们总是走第三条路。这就是为什么 m 是 1.
不幸的是，最后一个重复场景是 O(n*n)
您正在寻找一个规则，该规则依赖于使用尽可能大的子问题大小（相对于问题大小）递归地评估函数。有两个规则需要用少一位来解决子问题：处理 u 或 v 中恰好有一个为奇数的情况的规则。奇数不变，偶数应尽可能长时间保持偶数。这表明以下是最坏的情况：（1）未作为基本情况处理的最小奇数整数（2）自由增长 2 的幂。也就是说，对某些 u = 3 和 v=2^n n。在这种情况下，stein 的 运行 时间与输入的位数成线性关系。