数学运算的计算复杂性一文提到了O(M(n))中除法的复杂性，"下面的M(n)代表所选乘法算法的复杂性"。
但我不知道如何解读嵌入O(M(n))中的M(n)：这是否意味着除法与乘法具有相同的复杂性？
如果我用卡拉津巴乘法算法，除法也会取O(n^1.585)吗？
这是否意味着除法与乘法具有相同的复杂性？
从形式上讲，这意味着除法的复杂性不能比乘法差。但在实践中，符号经常被用来表示它们具有相同的复杂性。
如果我用卡拉津巴乘法算法，除法也会取
O(n^1.585)吗？
根据声明，是的。
然而，我不确定这种说法是否正确。事实上，当研究牛顿-拉斐森方法时，我发现它是一个迭代过程，必须精确地重复一定次数，顺序为log(n)（参见此处关于S的讨论）。在这种情况下，复杂性将是O(log(n)M(n))。
然而，如果无论操作数的大小如何，只有固定的精度（即正确位数）对您来说都不是问题，那么您可以设置恒定的迭代次数，从而产生O(M(n))的复杂性。