教科书上的长除法如何是 O(n^2) 算法？
前提：
扣除：
而不是取两个n位数字 数字，如果我取一个n位数字 和一个 m 位数字，则 复杂度将为O(n*m)。
矛盾：
假设您除以 100000000 (n 位）乘以 1000（m 位），您将得到 100000，这需要六个步骤 到达。
现在，如果你除以 100000000 (n 位）乘以 10000（m 位），您将得到 10000。现在只需五个步骤。
结论：
所以，看起来顺序是 计算应该是这样的 O(n/m)。
问题：
谁错了，我还是维基百科，以及 哪里？
Premise:
This Wikipedia page suggests that
the computational complexity of
"Schoolbook" long division is
O(n^2).
Deduction:
Instead of taking two n-digit
numbers, if I take one n-digit number
and one m-digit number, then the
complexity would be O(n*m).
Contradiction:
Suppose you divide 100000000 (n
digits) by 1000 (m digits), you get 100000, which takes six steps to
arrive at.Now, if you divide 100000000 (n
digits) by 10000 (m digits), you get 10000. Now this takes only five steps.
Conclusion:
So, it seems that the order of
computation should be something like
O(n/m).
Question:
Who is wrong, me or Wikipedia, and
where?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
你错了，这是因为你没有计算每个数字的运算次数。相反，您的计数就好像您可以在 O(1) 中对 N 位数字进行减法一样。一般来说，你不能；需要 O(N)。
You are wrong, and it is because you are not counting operations on every digit. Instead, you're counting as if you can do a subtraction on a N-digit number in O(1). In general, you can't; it takes O(N).
再次尝试使用 12341234 和 43214321 等数字。
大 O 是所有情况的限制复杂性，而不是特别简单的情况。
Try is again with numbers like 12341234 and 43214321.
Big O is the limiting complexity for all cases, not for a particularly easy one.
我认为（尚未证明，所以不确定）你的推论是一个真实的陈述，但它实际上并不能从你的前提得出。如果您只知道除两个 n 位数字是 O(n^2)，那么您只能推断出 n 位数字和 m 位数字是 O(max(n,m)^2)，并不是说它是 O(n*m)。这是因为 n 位数字也可以被视为带有前导 0 的 n+1 位数字，用我们知道其复杂性的操作替换该操作。
例如，这不是 O(nm)：使用长乘法，如果 A 和 B 是 n 位数字，则计算 A^2 + B^2 是 O(n^2)。然而，如果A是n位，B是m位，则不是O(nm)。要看到这一点，请固定 B=1，因此 m=1，并注意通过长乘法计算 A^2 + 1 当然不是 O(log(A))[*]。
你的“矛盾”并不与你的前提或你的推论相矛盾。 Big-O 表示法是关于渐近行为，即某物趋于无穷大。事实上，对于某些函数 f，f(3) = 12 绝对不能告诉您有关 f 的大 O 极限的信息。即使对于所有奇数 n，f(n) = 12，仍然无法告诉您有关大 O 估计的任何信息，因为您不知道函数在偶数上增长的速度有多快。快速特殊情况的存在并不意味着该函数很快。
[] 事实上，我自己就滥用了符号。如果一个二变量函数 f(n,m) 的复杂度是 O(nm)，那么它并不遵循（正如我所建议的）f(n,1) 是 O(n)。但它确实表明，对于足够大的 m，f(n,m) 是 O(n)，因此用“某个大常数或其他”替换 1。
I think (haven't proved, so not sure) that your deduction is a true statement, but it doesn't actually follow from your premise. If all you know is that dividing two n-digit numbers is O(n^2), all you can deduce about an n- and an m-digit number is that it is O(max(n,m)^2), not that it is O(n*m). That's because an n digit number can also be considered an n+1 digit number with a leading 0, replacing the operation with one that we know the complexity of.
For example which is not O(nm): using long multiplication, calculating A^2 + B^2 is O(n^2) if A and B are n-digit numbers. However, it is not O(nm) if A is n digits and B is m digits. To see this, fix B=1, hence m=1 and note that calculating A^2 + 1 by long multiplication certainly is not O(log(A))[*].
Your "contradiction" does not contradict either your premise or your deduction. Big-O notation is about asymptotic behaviour as something tends to infinity. The fact that f(3) = 12 for some function f tells you absolutely nothing about big-O limits for f. Even if f(n) = 12 for all odd n, that still tells you nothing about big-O estimates, because you don't know how fast the function grows on even numbers. The existence of fast special cases doesn't mean the function is fast.
[] Actually, I've made an abuse of notation myself, there. If a two-variable function f(n,m) is O(nm), it doesn't follow (as I've suggested), that f(n,1) is O(n). But it does follow that for sufficiently large m, f(n,m) is O(n), so replace 1 with "some large constant or other".
好吧，考虑一下这个例子：
您逻辑中的缺陷是 Big-O 是所有输入的渐近界限。你不能接受一个简单的输入并从中推断出矛盾。
Well, consider this case:
The flaw in your logic is that Big-O is an asymptotic bound on all inputs. You can't take one easy input and deduce a contradiction from it.
科门书里是这样说的：
考虑长除法的普通“纸笔”算法：a 除以 b，
产生商 q 和余数 r。表明该方法需要 O((1 + lg q)
lg b) 位运算。
Well the Cormen book says this:
Consider the ordinary "paper and pencil" algorithm for long division: dividing a by b,
which yields a quotient q and remainder r. Show that this method requires O((1 + lg q)
lg b) bit operations.
是的，它是 O(N^2)，因为必须完成所有乘法和减法加上除法，并且随着数字的增长，运行时间需要以二次模式增加，例如 4/2 需要一个单位的时间，而 2342677/39 需要更多的时间。
Yes, it is O(N^2) due to all the multiplication and the subtraction plus the division that has to be done and as the numbers grows the running time needed increase in quadratic pattern due to that, e.g. 4/2 take one unit of time while 2342677/39 takes much much more time.