教科书长除法是如何使用O(n ^ 2)算法的? [英] How is schoolbook long division an O(n^2) algorithm?

问题描述

前提:

此 Wikipedia页面建议 的计算复杂度 教科书"长除法是 O(n ^ 2).

This Wikipedia page suggests that the computational complexity of "Schoolbook" long division is O(n^2).

扣除:

而不是取两个n位数字 数字，如果我取一个n位数字 和一个m位数字，然后 复杂度为 O(n * m).

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).

矛盾:

假设您除以100000000(n 数乘以1000(m位数)，您将得到100000，这需要 6步 到达.

Suppose you divide 100000000 (n digits) by 1000 (m digits), you get 100000, which takes six steps to arrive at.

现在，如果除以100000000(n 位)乘以10000(m位)，就得到10000.现在只需五个步骤.

Now, if you divide 100000000 (n digits) by 10000 (m digits), you get 10000. Now this takes only five steps.

结论:

因此，似乎 计算应该像 O(n/m).

So, it seems that the order of computation should be something like O(n/m).

问题:

谁错了，我还是维基百科，以及 在哪里?

Who is wrong, me or Wikipedia, and where?

推荐答案

您错了，这是因为您没有对每个数字进行计数.相反，您要进行计数，好像可以对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).

这篇关于教科书长除法是如何使用O(n ^ 2)算法的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！