logo标签列表

除法的时间复杂度是什么？

pythontime-complexity
10

我使用具有除法操作的算法。

根据https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations，除法的时间复杂度是以下的其中一种：

O(n log n log log n)
O(n log n 2O(log* n))
O(n**2)
O(M(n))

目前我在Python中使用这个算法，但是我需要在独立的平台上进行描述。对于Python（或类似语言）用户来说，在这些时间复杂度定义中哪一个是正确的？

1
在那个链接中，你看到哪里有除法的logn？ - OneCricketeer
我会称之为操作，而不是过于称之为算法... - OneCricketeer
4
像乘法和除法这样的算术运算的时间复杂度通常只涉及到任意精度计算。当您使用固定宽度为64或128位时，您可以安全地将其视为O(1)，因为运行时间在几个周期内被限制。 - Ctx
@cricket_007 Schönhage-Strassen算法，也许我复制错了，但问题仍然存在 - 有多个选项，哪一个是我要使用的？ - matousc
2
这取决于你认为的 n 是什么... - OneCricketeer
显示剩余8条评论
1个回答
4

  1. As mentioned if you use ALU or FPU for basic variable types

    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.

    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.

  2. most division algorithms use multiplication as a core function

    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.

    Let us take Division by repeated subtraction as example.

     variable a=...,b=...,d,r;
 for (d=0,r=a;r>=b;) { r-=b; d++; }
 // d=a/b
 // r=a%b

    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

    • base algorithm complexity O(2^n)
    • combined total complexity O(n*(2^n))

    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:

  3. Now how to determine the complexity of custom division?

    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 !!!

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接