前提:
这个维基百科页面表明“竖式除法”的计算复杂度是O(n^2)。
推论:
如果我取一个n位数和一个m位数,那么计算复杂度将为O(n*m)。
矛盾:
假设你用1000(m位数)去除100000000(n位数),需要六步才能得到100000。
现在,如果你用10000(m位数)去除100000000(n位数),只需要五步就能得到10000。
结论:
所以,计算顺序似乎应该是类似于O(n/m)。问题:谁错了,我还是维基百科,在哪里?
前提:
这个维基百科页面表明“竖式除法”的计算复杂度是O(n^2)。
推论:
如果我取一个n位数和一个m位数,那么计算复杂度将为O(n*m)。
矛盾:
假设你用1000(m位数)去除100000000(n位数),需要六步才能得到100000。
现在,如果你用10000(m位数)去除100000000(n位数),只需要五步就能得到10000。
结论:
所以,计算顺序似乎应该是类似于O(n/m)。你的观点是错误的,因为你没有考虑对每个数字进行操作。相反,你计算的方式好像可以在O(1)时间内对N位数进行减法运算一样,但实际上通常不行,需要O(N)时间。
请使用像12341234和43214321这样的数字再试一次。
Big O是所有情况下的限制复杂度,而不仅仅是对于特别简单的情况。
O(log(A))
是什么?不应该是O(n)吗(假设f(n,m)是O(n*m)=> f(n,1)是O(n))?这是我不知道的某种备用符号吗? - Lazer好的,Cormen书上说: 考虑普通的“纸和笔”算法进行长除法:将a除以b,得到商q和余数r。证明这种方法需要O((1 + lg q) lg b)位操作。
好的,考虑这个案例:
对数组
[1, 2, 3, 4, ..... , 10000000]
进行排序只需一步。 与您从最优排序算法中期望的几乎~nlogn
步相比,这几乎是不可思议的。
你的逻辑缺陷在于大O符号是对所有输入的渐近上界。你不能仅根据一个简单的输入来得出矛盾。
是的,由于所有的乘法、减法和必须进行的除法,它是O(N^2),随着数字的增长,所需的运行时间呈二次模式增加,例如4/2需要一单位时间,而2342677/39需要更多的时间。