分部的複雜性

Question

文章Computational complexity of mathematical operations提到O(M(n))的劃分的複雜性，以及下面的「M(n)」代表了所選乘法算法的複雜性。

但我不知道如何讀取M(n)嵌入O(M(n))：這是否意味着該分區具有與乘法相同的複雜性？

如果我使用Karatsuba乘法算法，請問該師還會採用O(n^1.585)？

Answer 1

這是否意味着該分區具有與乘法相同的複雜度？

從形式上來說，這意味着除法乘法的分裂不會比複雜性差。但實際上，這種表示法通常用來表示它們具有相同的複雜性。

如果我使用，比如Karatsuba乘法算法，請問該師還會採取O(n^1.585)？

根據聲明，是的。

但是，我不確定該陳述是否正確。事實上，當我看牛頓 - 拉夫森方法時，我發現它是一個迭代過程，必須按照log(n)（請參閱關於Shere的討論）的順序重複確切次數。 在這種情況下，複雜性將是O(log(n)M(n))。

但是，無論操作數的大小是多少，如果對於您只有一個固定的精度（即正確的數字的數量）沒有問題，您可以設置一個固定的迭代次數，從而產生一個O(M(n))複雜。