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

Question

我使用除法算法。

根据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（或类似语言）用户来说，这些时间复杂度定义中的哪一个是正确的？

Answer 1

\n

1. 如前所述，如果您将 ALU 或 FPU 用于基本变量类型

   \n

   您可以假设除法复杂性是O(1)因为指令开销通常与所使用的除法的实际运行时间相当。如果使用的硬件平台不支持除法（例如某些较旧的 MCU），则必须通过程序（而不是单个指令）计算，这不再适用。

   \n

   另外，如果您有任意精度变量（bignums），那么实际的数字位或数字宽度开始变得重要，并且您不再处于O(1)这种情况下，请参阅#2。

   \n
\n

2. 大多数除法算法使用乘法作为核心函数

   \n

   然后，除法的复杂性由所使用的算法及其所使用的组件来定义。例如，如果您有基本变量但计算除法（没有硬件除法器支持），则使用的操作仍然是，O(1)但使用的除法不是。

   \n

   我们以连减除法为例。

   \n

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

   \n

   如果n是结果的位宽，那么这适用O(2^n)于基本变量。但是，如果变量是任意精度，那么所使用的操作就不再是O(1)减法、比较和增量O(n)，所以除法复杂度将O(n*(2^n))在算法或代码没有任何变化的情况下变得......所以你总是必须知道你的复杂度是多少正在谈论

   \n
   \n
   • 基本算法复杂度O(2^n)
   \n
   • 组合总复杂度O(n*(2^n))
   \n
   \n

   该算法未被使用，因为速度非常慢。相反，使用更先进的东西。大多数除法算法都使用乘法作为核心函数，因此 Sch\xc3\xb6nhage\xe2\x80\x93Strassen 和 Karatsuba 与除法算法相关。看：

   \n
   \n
   • 快速 bignum sqr 用于加速除法
   \n
   • 我最喜欢的近似除法器
   \n
   \n
\n

3. 现在如何确定自定义划分的复杂度呢？

   \n

   将算法的基本复杂度乘以其核心函数的最慢复杂度。如果每次迭代都不使用核心功能，这可能会变得非常棘手......在组合/比较复杂性时不要忘记使用相同的含义！n

   \n

   如果您无法访问所使用算法的源代码，那么您可以尝试测量具有足够大范围的大n数字集的除法，并尝试从测量时间的图表中估计复杂性......这是不可靠的，因为很多事情都会搞砸，比如多线程、调度粒度、未知n等等……

   \n
\n

\n