我使用除法算法。
根据https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations 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（或类似语言）用户来说，这些时间复杂度定义中哪一项是正确的？
-
如前所述，如果您将 ALU 或 FPU 用于基本变量类型
你可以假设除法复杂度是O(1)因为指令开销通常与所使用的除法的实际运行时间相当。如果使用的硬件平台不支持除法（例如一些较旧的 MCU），则必须通过程序（而不是单个指令）计算，这不再适用。
此外，如果您有任意精度变量（bignums），那么实际的数字位或数字宽度开始变得重要，并且您不再处于O(1)在这种情况下，请参阅#2.
-
大多数除法算法使用乘法作为核心函数
然后，除法的复杂性由所使用的算法和所使用的组件来定义。例如，如果您有基本变量但计算除法（没有硬件除法器支持），那么使用的操作仍然是O(1)但所使用的除法不是。
让我们采取除法重复减法 https://en.wikipedia.org/wiki/Division_algorithm例如。
variable a=...,b=...,d,r;
for (d=0,r=a;r>=b;) { r-=b; d++; }
// d=a/b
// r=a%b
If n是结果的位宽，那么这是O(2^n)对于基本变量。但如果变量是任意精度，那么所使用的操作就不再是O(1)这使用减法、比较和增量，它们都是O(n)所以除法复杂度将变为O(n*(2^n))无需对算法或代码进行任何更改...因此您始终必须知道您正在谈论的复杂性
- 基本算法复杂度
O(2^n)
- 组合总复杂度
O(n*(2^n))
该算法未被使用，因为速度非常慢。相反，使用更先进的东西。大多数除法算法都使用乘法作为核心函数，因此 Schönhage–Strassen 和 Karatsuba 与除法算法相关。看：
- 快速 bignum sqr 用于加速除法 https://stackoverflow.com/q/18465326/2521214
- 我最喜欢的近似分频器 https://stackoverflow.com/a/18398246/2521214
-
现在如何确定自定义划分的复杂度呢？
将算法的基本复杂度乘以其核心函数的最慢复杂度。如果每次迭代都不使用核心功能，这可能会变得非常棘手......不要忘记使用相同的含义n同时结合/比较复杂性！！！
如果您无法访问所使用算法的源代码，那么您可以尝试测量除法BIG范围足够大的一组数字n并尝试从测量时间图表估计复杂性 https://stackoverflow.com/a/64784308/2521214...这是不可靠的，因为很多事情都会搞砸，比如多线程、调度粒度、未知n，ETC ...
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
