如何比较计算复杂度: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)是让我最困惑的.

Answer 1

好的，根据这个维基百科条目有关牛顿法除法的应用，您必须执行O(lg(n))步骤来计算n除法的位数。O(n^2)每一步都采用乘法和减法，因此如果我们采用简单的“教科书”方法，就会有点复杂。

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