教科书长分为O(n ^ 2)算法怎么样？

Question

前提:

这个维基百科页面表明"教科书"长划分的计算复杂度 为 O(n ^ 2).

扣除:

如果我取一个n位数和一个m位数,而不是取两个n位数,那么复杂度将为O(n*m).

矛盾:

假设您将100000000(n位数)除以1000(m位数),则得到100000,这需要六个步骤才能到达.

现在,如果你将100000000(n位)除以10000(m位),你得到10000.现在这只需要五步.

结论:

因此,似乎计算的顺序应该是 O(n/m).

题:

谁错,我或维基百科,在哪里？

Answer 1

你错了,这是因为你不计算每一个数字的操作.相反,你计算好像你可以在O(1)中对N位数进行减法.一般来说,你不能; 需要O(N).

Answer 2

尝试再次使用12341234和43214321等数字.

Big O是所有案例的限制复杂性,而不是特别容易的案例.