长除法的复杂度是多少？
What is the complexity of long-division?
在讲座中，我的教授正在解释各种算术运算的大 O 时间。他告诉我们，长除法大约是 O(n^2)。在网上查了一下，好像是这样，但是为什么呢？
谁能详细说说为什么长除法是 O(n^2) 时间？
它是你除的数字的位数的二次方，这意味着要将 n 除以 m 你需要 O((log max(m,n))^2) 时间。这是因为每次减法需要 O(log max(m, n)) 时间。
有解释可用here on Whosebug。
首先是一些定义：
- 除法运算：被除数/除数=商
- n = 股息的位数
- m = 除数的位数
- q = 商的位数
商的每一位的生成需要两次运算：
- 除数乘以一位数。这需要 O(m) 时间。
- 从股息中减去该结果。这需要 O(m) 时间。它不依赖于 n，因为你不需要从被除数的每个数字中减去它。
计算复杂度不依赖于股息的大小。例如，如果要计算 1/3 到 5 个位置 (.33333)，则需要 5 次迭代，但如果要计算 20 个位置 (.33333333333333333333)，则需要 20 次迭代。
除数的位数实际上也不是一个因素。假设您要计算 1/pi，并且希望结果精确到 4 位。您不需要 pi 的每个数字来计算它（这很方便，因为有很多！）。除数的前几位（其中几位大约为 q）外，您可以忽略所有数字。在这种情况下，使用 pi 的 4 位最高有效数字就足以将 1/pi 精确到 4 位：1/3.141 ~= 0.3183（对于上下文，20 位精度的 1/pi 是 0.31830988618379067153）。
所以需要q次迭代，每次迭代有O(q)个工作，所以长除法的计算复杂度为O(q^2)。
在讲座中，我的教授正在解释各种算术运算的大 O 时间。他告诉我们，长除法大约是 O(n^2)。在网上查了一下，好像是这样，但是为什么呢？
谁能详细说说为什么长除法是 O(n^2) 时间？
它是你除的数字的位数的二次方，这意味着要将 n 除以 m 你需要 O((log max(m,n))^2) 时间。这是因为每次减法需要 O(log max(m, n)) 时间。
有解释可用here on Whosebug。
首先是一些定义：
- 除法运算：被除数/除数=商
- n = 股息的位数
- m = 除数的位数
- q = 商的位数
商的每一位的生成需要两次运算：
- 除数乘以一位数。这需要 O(m) 时间。
- 从股息中减去该结果。这需要 O(m) 时间。它不依赖于 n，因为你不需要从被除数的每个数字中减去它。
计算复杂度不依赖于股息的大小。例如，如果要计算 1/3 到 5 个位置 (.33333)，则需要 5 次迭代，但如果要计算 20 个位置 (.33333333333333333333)，则需要 20 次迭代。
除数的位数实际上也不是一个因素。假设您要计算 1/pi，并且希望结果精确到 4 位。您不需要 pi 的每个数字来计算它（这很方便，因为有很多！）。除数的前几位（其中几位大约为 q）外，您可以忽略所有数字。在这种情况下，使用 pi 的 4 位最高有效数字就足以将 1/pi 精确到 4 位：1/3.141 ~= 0.3183（对于上下文，20 位精度的 1/pi 是 0.31830988618379067153）。
所以需要q次迭代，每次迭代有O(q)个工作，所以长除法的计算复杂度为O(q^2)。