前提：
这个维基百科页面表明“竖式除法”的计算复杂度是O(n^2)。
推论：
如果我取一个n位数和一个m位数，那么计算复杂度将为O(n*m)。
矛盾：
假设你用1000（m位数）去除100000000（n位数），需要六步才能得到100000。
现在，如果你用10000（m位数）去除100000000（n位数），只需要五步就能得到10000。
结论：
所以，计算顺序似乎应该是类似于O(n/m)。问题：谁错了，我还是维基百科，在哪里？
学校教材中的长除法为什么是O(n^2)算法？
7
问题：谁错了，我还是维基百科，在哪里？
- Lazer
6个回答
12
你的观点是错误的，因为你没有考虑对每个数字进行操作。相反，你计算的方式好像可以在O(1)时间内对N位数进行减法运算一样，但实际上通常不行，需要O(N)时间。
- Rex Kerr
3
@Rex Kerr：我不理解“不计算每个数字的操作”的部分。您能否详细说明一下？ - Lazer
1假设您正在计算152 / 24。 首先，您必须计算6 * 24 =（6 * 4）+（6 * 20）=（20 + 4）+（100 + 20）= 100 +（20 + 20）+ 4 = 144。 然后，您必须计算152-144 =（100-100）+（50-40）+（2-4）= 10 +（-2）=（10-2）= 8。请注意，在数字中有一个操作（在减法步骤中，每个数字进行一次减法）。 - Rex Kerr
如果我将一个n位数除以一个m位数，则乘法的时间复杂度为O(m)，减法的时间复杂度也为O(m)，这个过程需要重复O(n)次。因此，总时间复杂度为O(n*(m+m)) = O(n*m)。当我们将一个n位数除以另一个n位数时（不仅仅是将m替换为n，而且还要按照整个过程再次执行），时间复杂度降至O(n^2)。现在我对如何得出O(n^2)有了一些想法。 - Lazer
6
请使用像12341234和43214321这样的数字再试一次。
Big O是所有情况下的限制复杂度，而不仅仅是对于特别简单的情况。
- dmckee --- ex-moderator kitten
2
我认为（没有证明，所以不确定）你的推断是正确的陈述，但它实际上并不是从你的前提中得出的。如果你只知道两个n位数相除是O(n^2)，那么你对一个n位数和一个m位数能够推断的只有它是O(max(n,m)^2)，而不能推断它是O(n*m)。这是因为一个n位数也可以被视为一个有前导0的n+1位数，用我们已知复杂度的操作替换它。
例如，使用长乘法计算A^2 + B^2，如果A和B是n位数，则是O(n^2)，但如果A是n位数而B是m位数，则不是O(n*m)。为了看清楚这一点，固定B=1，因此m=1，并注意到通过长乘法计算A^2 + 1肯定不是O(log(A))[*]。
你的“矛盾”既不否定你的前提也不否定你的推断。大O符号是关于某些东西趋于无穷大的渐进行为。函数f(3)=12的事实绝对不能告诉你关于f的大O极限的任何信息。即使对于所有奇数n，f(n)=12，这仍然不能告诉你关于大O估计的任何信息，因为你不知道函数在偶数上增长的速度。快速特殊情况的存在并不意味着函数很快。
[注]实际上，在那里我自己也滥用了符号。如果一个两个变量的函数f(n,m)是O(n*m)，那么它并不遵循（正如我所暗示的）f(n,1)是O(n)。但是，对于足够大的m，f(n,m)是O(n)，因此将1替换为“一些大常数或其他”。
例如，使用长乘法计算A^2 + B^2，如果A和B是n位数，则是O(n^2)，但如果A是n位数而B是m位数，则不是O(n*m)。为了看清楚这一点，固定B=1，因此m=1，并注意到通过长乘法计算A^2 + 1肯定不是O(log(A))[*]。
你的“矛盾”既不否定你的前提也不否定你的推断。大O符号是关于某些东西趋于无穷大的渐进行为。函数f(3)=12的事实绝对不能告诉你关于f的大O极限的任何信息。即使对于所有奇数n，f(n)=12，这仍然不能告诉你关于大O估计的任何信息，因为你不知道函数在偶数上增长的速度。快速特殊情况的存在并不意味着函数很快。
[注]实际上，在那里我自己也滥用了符号。如果一个两个变量的函数f(n,m)是O(n*m)，那么它并不遵循（正如我所暗示的）f(n,1)是O(n)。但是，对于足够大的m，f(n,m)是O(n)，因此将1替换为“一些大常数或其他”。
- Steve Jessop
2
@Steve Jessop：
O(log(A))是什么？不应该是O(n)吗（假设f(n,m)是O(n*m)=> f(n,1)是O(n)）？这是我不知道的某种备用符号吗？ - Lazer日志是对数。如果A的数字个数为n，则log(A)是O(n)，反之亦然。 - Steve Jessop
0
好的，Cormen书上说： 考虑普通的“纸和笔”算法进行长除法：将a除以b，得到商q和余数r。证明这种方法需要O((1 + lg q) lg b)位操作。
- daveangel
0
好的，考虑这个案例：
对数组
[1, 2, 3, 4, ..... , 10000000]进行排序只需一步。 与您从最优排序算法中期望的几乎~nlogn步相比，这几乎是不可思议的。
你的逻辑缺陷在于大O符号是对所有输入的渐近上界。你不能仅根据一个简单的输入来得出矛盾。
- Yuval Adam
1
2它仍然需要至少n-1次比较才能确定数组已经排序。此外，大O符号并不一定指最坏情况。它也可以用来描述算法的平均情况甚至是最佳情况的渐近性能。 - Daniel Stutzbach
0
是的，由于所有的乘法、减法和必须进行的除法，它是O(N^2)，随着数字的增长，所需的运行时间呈二次模式增加，例如4/2需要一单位时间，而2342677/39需要更多的时间。
- developer2001
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接