分度的时间复杂度是多少？ [英] What is time complexity of divison?
问题描述
我使用除法算法。
根据 https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations 该部门的时间复杂度（以下一项）：
According to https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations the division has time complexity (one of following):
O(n log n log log n)
O(n log n 2O(log* n))
O(n**2)
O(M(n))
到目前为止，我在Python中使用此算法，但需要在平台上独立描述它。
So far I use this algorithm in Python but I need to describe it independently on platform. which one of those time complexity definitions is the correct one today for Python (or similar language) users?
推荐答案
-
如前所述，如果对基本变量类型使用ALU或FPU
您可以假定除法复杂度为 O（1），因为指令开销通常与所用除法的实际运行时间相当。如果使用的硬件平台不支持除法（例如，某些较旧的MCU），则必须通过程序（而不是单个指令）进行计算，并且不再适用。
you can assume division complexity is O(1) because the instruction overhead is usually comparable with the actual runtime of the division used. If used HW platform does not support division (some older MCU's for example) then it must be computed via program (not single instruction) and this no longer apply.
如果您具有任意的精度变量（大数），那么实际的数字位数或位数宽度就变得很重要，并且您不再位于 O（1）中，在这种情况下，请参见 ＃2 。
Also if you have arbitrary precision variables (bignums) then the actual number bit or digit width start to matter and you are no longer in O(1) In that case see the #2.
大多数除法算法都将乘法作为核心函数
除法的复杂度然后由使用的算法及其使用的组件定义。例如，如果您具有基本变量，但计算除法（不支持硬件除法器），则所使用的运算仍为 O（1），但所使用的除法不是。
The complexity of division is then defined by the used algorithm and components used by it. For example if you have basic variables but computing division (no HW divider support) then the used operations are still O(1) but the division used is not.
让我们以通过重复减法进行除法为例
variable a=...,b=...,d,r;
for (d=0,r=a;r>=b;) { r-=b; d++; }
// d=a/b
// r=a%b
如果 n 是结果的位宽，则基本变量为 O（2 ^ n）。但是，如果变量具有任意精度，则使用的运算不再是 O（1），所有这些使用的减法，比较和增量都是 O（n ），因此除法复杂度将变为 O（n *（2 ^ n）），而无需更改算法或代码...因此，您总是必须知道您在说什么复杂性
If n is the bit width of result then this is O(2^n) for basic variables. But if the variables are arbitrary precision then the used operations are no longer O(1) This use substraction,comparison and increment which are all O(n) so the division complexity will became O(n*(2^n)) without any change in the algorithm or code ... So you always have to know what complexity you are talking about
- 基本算法复杂度
O（2 ^ n） - 总复杂度
O（n *（2 ^ n））
- base algorithm complexity
O(2^n) - combined total complexity
O(n*(2^n))
不使用此算法，因为它速度很慢。而是使用更高级的东西。大多数除法算法都将乘法用作核心函数，因此Schönhage–Strassen和Karatsuba与除法算法有关。请参阅：
This algorithm is not used because is painfully slow. Instead more advanced thing are used. Most division algorithms use multiplication as a core function so Schönhage–Strassen and Karatsuba are relevant for division algorithms. See:
- 快速bignum sqr以获得除法速度
- 我最喜欢的近似分频器
- fast bignum sqr for division speed up
- my favorite Approximation divider
现在如何确定自定义划分的复杂性？
取算法的基本复杂度，然后乘以其核心功能最慢的复杂度。如果每次迭代都没有使用核心功能，这可能会变得非常棘手... 在组合/比较复杂性时，请不要忘记使用 n 的相同含义！ !!
Take the base complexity of your algorithm and multiply it by the slowest complexity of its core function. In case the core functions are not used each iteration this can became very tricky ... Do not forget to use the same meaning of n while combining/comparing complexities !!!
如果您无法访问所使用算法的源代码，则可以尝试测量 BIG 的除法一组具有足够大范围 n 的数字，并尝试从测量的时间图中估计复杂性...这是不可靠的，因为许多事情会像多线程一样搞砸，计划粒度，未知的 n 等...
If you do not have access to source code of the algorithm used then you can try to measure division for BIG set of numbers with big enough range of n and try to estimate the complexity from the graph of measured times ... This is not reliable because many things can screw this up like multithreading , scheduling granularity, unknown n ,etc ...
这篇关于分度的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
