如何比较计算复杂度：O(k * M(n)) 和 O(log^6(n))?

Question

假设我有两个计算复杂度：

1. O(k * M(n)) - 模幂运算的计算复杂度，其中k是指数位数，n是数字位数，M(n)是牛顿-拉夫逊除法算法的计算复杂度。

2. O(log^6(n)) - 一种算法的计算复杂度。

如何确定这两个复杂度中哪一个更“便宜”？实际上，符号M(n)是最让我困惑的。

- pedja

---

根据维基百科对模指数的定义，它的复杂度仅为O(n)--计算a^n(mod c)需要进行n次乘法和1次除法。此外，你的O(k * M(n))似乎关注的是位复杂度，而第二个复杂度并不是位复杂度。 - Victor Sorokin

@VictorSorokin，算术运算的复杂度 - Peđa

@VictorSorokin，我不知道... - Peđa

你对理论复杂度还是实际可用性感兴趣？大O符号只描述渐近行为，即当n趋近于无穷大时。但对于小的n，情况可能完全相反。 - mitchus

嗯，这真的取决于算法。例如，想象一个执行3 n^2次乘法的算法，即O(n^2)，另一个算法则会调用一百万次非常昂贵的函数，即O(n)。尽管在渐近意义下第二个更好，但如果你的问题中n大约为100，那么第一个更好。基本上，如果您追求的是可用性，我建议您查看性能比较研究，而不是理论复杂度，或者更好的是，如果有多个算法可用，请尝试它们并进行比较 :) - mitchus

Answer 1

首先，对于任何给定的固定 n，只需将其放入运行时间函数（注意不包含 Landau O）并进行比较。

渐近地，您可以将一个函数（或其 Landau 项）除以另一个函数，并考虑商在 n 趋近无穷大时的极限。如果它是零，则分子中的函数在渐近意义下增长得更为适度，比另一个函数弱。如果它是无穷大，则增长速度更快。在所有其他情况下，它们的渐近增长相同，最多相差一个常数因子（即大 Theta）。如果极限中商为 1，则它们在渐近意义下相等。

- Raphael

Answer 2

根据这篇维基百科条目关于牛顿法在除法中的应用，你需要进行O(lg(n))步骤来计算n位的除法。每一步都需要乘法和减法，因此如果我们采用简单的“学校”方法，则其位复杂度为O(n^2)。

因此，第一种方法的复杂度为O(lg(n) * n^2)。它的渐近速度比第二种方法慢。

- Victor Sorokin

---

如果我们选择其他方法而不是“schoolbook”方法呢？ - Peđa

那么你将得到结果复杂度为 O(lg(n) * X)，其中 X 是该方法的复杂度（来自您在维基百科上的链接）。但是据我所知，所有其他乘法方法在实践中都相当复杂。 - Victor Sorokin

据我所知，O(n^3) 被称为多项式复杂度，而 O(log(n)*n^2) 则渐进地更快... @VictorSorocin - Peđa

实际上，这取决于$n$是什么。如果$n$是输入的大小（以位为单位），那么你在这里拥有的是多项式算法。如果它是构成输入的数字，则你拥有的是伪多项式算法。 - Raphael

请注意，渐近复杂度并不能直接告诉你哪个算法更昂贵或更便宜。后者还取决于您考虑的输入大小；对于小输入大小，渐近复杂度较慢的算法可能更受欢迎；例如，考虑 1000*n 和 1.00001^n。在实践中，空间复杂度也是一个问题，还有许多其他问题。 - Raphael