這段代碼的大O是什麼？

-1

return this.add(P2.multiply(-1));

添加O（n）並且乘以O（n²）。要計算大O我只是乘以O的權利？所以在最壞的情況下調用它會是O（n³）？ this和P2是多項式項的ArrayList。這段代碼的大O是什麼？

2012-10-05 crzrcn

而我們只是知道P2是什麼？它是一個int嗎？數組？你的狗的玩具盒？除非你在某個完全瘋狂的古怪平臺上，否則簡單數字的乘法操作就是O（1）操作。 –

P2，這是一個多項式項的ArrayList。我不認爲有必要添加這些信息，因爲我已經爲每個操作給出了O.很抱歉對於這個誤會。 – crzrcn

不要道歉。這個網站上的人們有時只喜歡成爲精英和黑客（像互聯網上的其他地方一樣）。 :) – asteri

要計算大O我只是乘以O的權利？

不一定。假設multiply取O（n ）時間，但總是最終返回3。然後add步是恆定時間，因爲它是O（3），它是O（1）;因爲它是O（n），它是O（3），它是O（1）。因此整體複雜度爲O（n ）。

在另一方面，假設multiply需要O（Ñ ）時間，並返回Ñ 。然後add步驟是立方體時，因爲它是O（Ñ）（Ñ是它的參數），這是O（Ñ ）（Ñ是的multiply參數）;所以整體複雜度爲O（n ）。

總的複雜性是multiply，加的的add複雜的任何值multiply返回的複雜性。

2012-10-05 14:29:34 ruakh

所以O（n）+ O（n²）只是O（n²）。

2012-10-05 14:28:45

當僅僅看一條線時，確定大O並不總是容易的。在這種情況下，兩個步驟（加法和倍數）是連續的，這意味着該概念將是O（n）+ O（或n）或O（n ）。

this.add（P2.multiply（-1））可被重寫爲
MUL = P2.multuple（-1）
this.add（MUL）

如果 '添加' 過程循環通過多個步驟（這將是一個新功能），然後你多個大O的條款

2012-10-05 14:57:14 BradRees

回答