这段代码的大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

回答